Tagged Questions

Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.

133 views

Uniform sampling from general simplex with a twist

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
40 views

convert absolute form into linear programming problem [closed]

I would like to convert this problem into a Linear Programming Problem : $\min |x|+|y|+|z|$ subject to $x+y \leq 1$ $2x+z=3$. The solution to this problem is given chapter and here. But I still ...
134 views

Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints

Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints: ...
488 views

optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint. $D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter. $x$ and $v$ are two known p-dimensional vectors. The ...
47 views

Combination of certain linear-programming topics new?

Consider the combination of the following topics, aimed at a future book on Linear Programming: Generalization of certain parts of the polyhedron theory and of the Simplex Algorithm to arbitrary ...
26 views

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ... 0answers 42 views Existence of probability distribution satisfying upper/lower bounds on events Suppose we have a finite sample space$S$and some events$A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on$S$so that no element has probability greater than a ... 2answers 421 views Multiplicative gradient descent? The normal gradient descent is additive:$w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like$w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ... 1answer 65 views Minimum cover for sets in which each element appears in exactly 2 sets? Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ... 0answers 646 views Infinite Linear Programming I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ... 0answers 68 views Optimization with vectors I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ... 1answer 193 views Covering max flow arcs by arc disjoint paths Let$(N,A,s,t,u)$be a network with node set$N$, arc set$A$, source$s\in N$, sink$t\in N$and capacity vector$u\in\{1,2,\ldots,T\}^A$, and let$x=(x_a)_{a\in A}$be a maximum$(s,t)$-flow. Is it ... 0answers 51 views About identifying a few diagrams Please have a look at these beautiful seminar slides, https://math.berkeley.edu/~bernd/coimbra1.pdf Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ... 0answers 137 views Closed-form solution of a linear programming question Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \... 1answer 113 views Is it possible to represent non-linear ranking type constraints as equivalent linear constraints? I have formulated a linear program with binary indicator variables$z_i(a)$which is equal to$1$if the$i^{th}$document is of rank$a$and$0$otherwise. The other variables in the linear program,... 1answer 112 views Convert general optimization problem to LP problem I am trying to convert the following problem into a linear programming problem: There are$M\times N$matrix$T$of real numbers between 0 and 1 and$N\times 1$vector$w$of real numbers between 0 ... 1answer 101 views Is the linear production game a convex game? In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem. Does anyone know if the LPG is a convex ... 0answers 29 views Maximisation of a discrete linear function I am trying to maximise the function $$Q=\sum_i{\alpha _{i}x_{i}}$$ subject to the constraint $$W<=\sum_i{\alpha _{i}w_{i}x_{i}}$$ By changing$\alpha _{i}$subject to$ 0<=\alpha _{i}<=1$... 0answers 27 views Equivalence between multiclass SVMs, power diagrams, and constrained$k$-means Apologies in advance for the long post: Suppose we have a collection of points$\mathbf{p}_1,\dots,\mathbf{p}_n$in$\mathbb{R}^d$, and we consider the following three ways of partitioning these ... 6answers 1k views Circumference of Convex Shapes Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ... 1answer 66 views Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces Suppose you have two polytopes$P_1, P_2 \in \Bbb{R}^n$given by $$P_1 = \lbrace x: A_1 x \le b_1\rbrace$$ $$P_2 = \lbrace x: A_2 x \le b_2\rbrace$$ I wish to find their convex hull, that is a ... 0answers 33 views Linear Program for Single Source Shortest Paths Tree This question originates in quick, however wrong, idea to calculate a shortest paths tree in the presence of negative cycles. The essential motivation was that a linear program would determine binary ... 0answers 111 views Formulating shortest path as submodular minimization I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ... 3answers 2k views How to solve Linear Programming problem with tighter Integer Programming constraints I want to learn a bit about Linear Programming. After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ... 0answers 20 views Is there a standard technique for overdetermined homogeneous integer programming? Given$M\in\Bbb Z^{n\times n}$of$\mathsf{rank}(M)=r\leq n$consider$MX=\mathsf0_n$where$X\in\Bbb Z^{n\times 1}$holds. We also have a$\mathsf{rank}(N)=m\leq n$matrix$N\in\Bbb R^{m\times n}$... 1answer 123 views Algorithm that solves every Mixed Integer Linear Program (to optimality)? Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically? I know that you usually ... 0answers 33 views Pcross-like, nonogram-like in near-linear time [closed] I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col.... 1answer 169 views Constrained optimization (QCLP) over$x$with the constraint$x = Az$I have a problem that looks very much like a (norm-constrained) linear program, but with an extra constraint that is unusual for me. The problem is, given a matrix$A$and a vector$w$, $$\min_{x \... 1answer 87 views Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables I am working out an interesting problem and would like some help with this particular sub problem: Suppose we have a matrix M =\left\lbrace a_{ij}\right\rbrace of size n\times m where a_{ij}\... 1answer 56 views When to use non-negative-least square and least-square [closed] What are the typical case we need to use Non-negative least squares NNLS$$ ||Ax - B||^2 $$instead of least-square$$ Ax-B$$(or vice versa)? And is there any drawback in applying them on large A... 1answer 90 views Better alternative to solve quadratic programming for large matrices I have the following problem. Let's say we have x_{jk} it is an expression value of gene j in a sample k. It is the average of expression levels across the cell types s_{ij}, weighted by ... 0answers 67 views Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :) Let R = (R_x, R_y, R_z) be the resultant vector of the n vectors and M = (M_x, ... 2answers 299 views ILP for minimum edge coloring problem We know that for a graph G=(V,E), minimum edge coloring is a coloring of E, i.e., a partition of E into disjoint sets E_1, E_2, \dots, E_k such that, for 1 \leq i \leq k, no two edges in ... 0answers 70 views Is there a space in which the \vec a in \sin(a_1\cdot x)+\sin(a_2\cdot x) is linear? Suppose one has equations of the form \sin(a_1\cdot x_i)+\sin(a_2\cdot x_i)=y_i for i = 1, \dots, n (there are also amplitudes and phase shifts, but let's ignore these for now). I want to solve ... 0answers 134 views Testing if a point is inside a convex polytope formed by halfspaces in n-dimension Assume we have a convex polytope that is formed by the intersection of k-halfspaces in \mathbb{R}^{n}.$$ a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0  a_{1,0}x^{n-1} + {a}_{1,... 1answer 60 views Introducton books for ‎$\frak{E}_p(I)$Are there any good books different from abstract harmonic analysis by hewitt to study ‎$\frak{E}_p(I)$. where ‎$\frak{E}_p(I)$is: ‎Let$I$be an arbitrary index set‎. ‎For each$i\in I$let$H_i$... 0answers 48 views How does one go from convexity to submodularity? If I have a function which is convex in the hypercube,$[-1,1]^n$then when would it imply that its restriction to$\{-1,1\}^n$is submodular? It would be helpful is someone can share some specific ... 1answer 72 views approximate diameter of polytopes in high dimensions I just came across the following problem: Let us consider the unit corner of the n-cube$$\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \... 0answers 85 views Listing all Lattice Points in a Box Let$B := [-1,1]^n$be an$n$-dimensional box. Moreover, let$v_1,\ldots,v_n \in \mathbb{R}^n$form a basis of$\mathbb{R}^n$, where the entries of the$v_i$are explicitly irrational. We can assume ... 2answers 134 views Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed] I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ... 0answers 69 views Finding all feasible solutions Let$u$be a$n_{max} \times m$matrix. Let$z$be a$n_{max} \times s_{max} \times n_{max}$cube. Let$w$be a$n_{max} \times 1$vector. All the three matrices can have values from the set$\{ 0, 1\}...
I previously posted this on MathSE and am now trying here. I have the following situation, as shown in the following diagram: $W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue)...