# Tagged Questions

21 views

### LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron

I've encountered the following question which I am unable to solve: $$P = \{\vec x | A\vec x \geq \vec a\} \\ Q = \{\vec x | B\vec x \geq \vec b\}\\ P, Q \subseteq R^n$$ Find an algorithm to ...
16 views

25 views

### Dual of Linear Program

I was wondering what a $symmetric$ dual is. For example, the following is supposed to be a symmetric primal and dual form of LP. Primal : $$\max c^Tx$$ subject to $$Ax \le b$$ $$x \ge 0$$ Dual: ...
35 views

### Finding the dual of a linear program

I have an exam next week and I would like to make sure I am doing this problem correctly and I would also appreciate if somebody could explain to me the purpose of duality? What is the ultimate goal ...
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 ...
158 views

### Duality and the Minimax Theorem

I review LP duality by reading Lecture 7: The LP Duality Theorem. I get the idea how to find the dual LP from primal LP, but my basic knowledge is not enough for finding dual LP for the LP in chapter ...
150 views

### Why do we need duality in linear programming or convex optimization?

I'm learning convex optimization, just get started with linear programming, and there is such a thing as duality in linear programming. Here is my problems, why there is a dual problem for a linear ...
61 views

### Finding the dual of this primal LP.

I am going over sample questions from a sample exam, and I got stuck on the following question. I need to determine the dual of this LP: $min: c^Tx + d^Tu \\ s.t: Ax + Du = b\\ x \ge 0$ $A$ is an ...
51 views

### Clarification needed for this linear programming problem

I am stuck on the following problem: I have got only confusion over option (1). The options (2) ,(3) are correct and option (4) is wrong. But how can I check whether the problem has more ...
109 views

### weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if x and p are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
888 views

### From a primal problem optimal solution to a dual problem optimal solution

Having this linear programming problem: $minimize$ $2x_1 + 9 x_2 + 3x_3$ subject to $-2x_1 + 2 x_2 + x_3 ≥ 1$ $x_1 + 4 x_2 - x_3 ≥ 1$ $x_1, x_2, x_3 ≥ 0$ and its dual ...
50 views

### How to construct an LP problem that makes a (partial) theorem fail?

I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem. The theorem is Theorem ...
205 views

### Directly from primal to dual when primal not in standard form

This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, ...
117 views

### Dual of a Linear Program

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ ...
153 views

### intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
245 views

### Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
166 views

### Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful. Given the following primal program: (Decision variables are $\xi_{v}$, ...