0
votes
0answers
40 views

Online convex programming: Projection followed by normalization

I have the following projected gradient descent online linear programming problem which has been well studied in www.cs.cmu.edu/~maz/publications/techconvex.pdf‎ $\mathbf{y}_{t+1}=\mathbf{w}_t - ...
0
votes
0answers
26 views

Prove that a point is optimal in LP-problem

I have the following LP-problem: Minimize $B_1^t Y_1 + B_2^t Y_2 + B_3^t Y_3$ subject to $$ (C_1,C_2,I) \begin{pmatrix} Y_1 \\ Y_2 \\ Y_3 \end{pmatrix}\geq 2 \text{ and } Y\geq 0 $$ where $B_1$ is ...
0
votes
0answers
11 views

NNLS for under determined system

I have system of equations to solve Ax=B under x>=0. I read that Non Negative least Square(NNlS) algorithm proposed by Lawson and Hanson could solve this system for over determined case( number of ...
1
vote
0answers
50 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
1
vote
1answer
33 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
1
vote
0answers
47 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
2
votes
1answer
31 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
0
votes
1answer
99 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
0
votes
1answer
30 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
1
vote
0answers
46 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
0
votes
2answers
64 views

How can I find the center of a region in a linear programming problem?

I have an optimization problem that in most respects can be very elegantly expressed via linear programming. The twist is that I don't actually want to minimize or maximize any of my variables; I ...
1
vote
1answer
53 views

Containment of one convex hull in another

This question is related my previous question (Comparing two probability distributions) which are both related to my current research. Suppose we have two bounded convex hulls in $\mathbb{R}^n$ ...
1
vote
0answers
34 views

Least square with constraints

I want to solve the least squares problem $(Ax-b)^2$ with no intercept term for linear regression with the constraint that the sum of the params/weights is equal to 1. I am trying to get the closed ...
2
votes
2answers
141 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
1
vote
0answers
49 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
1
vote
0answers
103 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
3
votes
1answer
54 views

Rewrite constrained optimization objective

I wanted to ask, under which conditions can one rewrite the optimization objective $\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$ as $\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$ I have particular interest ...
1
vote
1answer
94 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
0
votes
0answers
51 views

Semi definite programming for MAX-2-SAT

I didn't understand something in formulating this program, to a vector program. Assume that each clause is of the form $C_{j}=\left(u_{j}\lor v_{j}\right)$ where $u_{j},v_{j}$ are literals (meaning, ...
1
vote
1answer
116 views

formulate this scheduling problem as linear programming problem

Sorry if this very silly, but i am something new to optimization theory: We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
2
votes
1answer
152 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
1
vote
1answer
48 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
2
votes
2answers
58 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
1
vote
1answer
55 views

linear equivalent min{} constraint

Activities are assigned to venues. Each activity $a_i$ has maximum size $b_i$ and demand $c_i$. Each venue $v_j$ has maximum size $d_j$. An activity can be assigned to multiple venues, and we need to ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
0
votes
0answers
37 views

Uncertaint linear program

I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It ...
5
votes
1answer
2k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...
1
vote
2answers
649 views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
1
vote
0answers
220 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
1
vote
0answers
45 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
1answer
122 views

How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
2
votes
1answer
45 views

Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $ and $ H : \mathbf{c}^{T}\mathbf{x} = \beta $ with $ \min_S ( ...
-1
votes
1answer
98 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
35 views

using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
3
votes
0answers
101 views

Branch-and-Price algorithms for IP/MIP

I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
0
votes
1answer
123 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
2
votes
0answers
79 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
1
vote
1answer
383 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0answers
68 views

Solving PSD matrix in Newton's method

I have functions defined as follows: $f_1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f_2(A) = \sum\|x_k-x_l\|^2_A$ where $A$ is a positive semi-definite (PSD) matrix, $x$ are ...
1
vote
1answer
46 views

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s?

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s? When $a_i$'s are independent, it should easy. What ...
1
vote
1answer
135 views

Continuity of a Parametric Linear Program

Consider the convex optimization problem $$ \min_{x \in X, \ y \in Y } x $$ $$ \text{sub. to } \ x A + B y + C = 0 $$ where $X = [0,1] \subset \mathbb{R}$, $Y \subset \mathbb{R}^M $ are compact ...
3
votes
1answer
4k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
2
votes
1answer
248 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...