# Tagged Questions

30 views

### Using l1 magic toolbox for compressive sensing : Positive definite matricies.

I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is ...
33 views

55 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 ...
82 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 ...
56 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$ ...
35 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 ...
193 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 ...
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 ...
104 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 ...
57 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 ...
145 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 <= ...
139 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. ...
165 views

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 ... 0answers 86 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 ... 2answers 446 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 ... 0answers 70 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 ... 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 ... 1answer 143 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 ...
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 ...