0
votes
2answers
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 ...
0
votes
0answers
16 views

Conic programming duality - relative interior

Consider the primal/dual conic programming problems $$ \newcommand{\ip}[1]{\left< #1 \right>} \newcommand{\myvec}[1]{\mathbf{#1}} \newcommand{\bvec}[0]{\mathbf{b}} ...
0
votes
0answers
51 views

The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
2
votes
1answer
32 views

Does the Duality Theorem of Linear Programming hold only in closed convex cones

I've just read the the Duality Theorem of Linear Programming. Here is the proof from my book (and my questions after it): Duality Theorem of Linear Programming: If the primal or dual linear ...
1
vote
1answer
35 views

Why $(1,\textbf{0}) \not\in \{(r,\textbf{w}): r=tz_0-\textbf{c}^T\textbf{x}, \textbf{w}=t\textbf{b}-\textbf{Ax}, \;\textbf{x}\geq\textbf{0}, t\geq0\}$

I'm learning about linear and nonlinear programming and on the chapter about duality I have the following statement and proof I can't understand: minimize $\textbf{c}^T\textbf{x}$ subject to ...
3
votes
1answer
35 views

Trouble seeing why this is the dual of an LP

$A$ is an $m \times n$ matrix. Using the notation $x=(x_1, \ldots, x_n)$, $z=(z_1, \ldots, z_m)$, and $y=(y_1, \ldots, y_m)$, I'm reading that if the primal LP is $$ \min 0x_1 + 0x_2 + \cdots + 0x_n ...
0
votes
0answers
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: ...
0
votes
0answers
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 ...
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
2
votes
3answers
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 \\ ...
2
votes
0answers
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 ...
0
votes
1answer
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. ...
1
vote
1answer
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?
6
votes
1answer
177 views

Difficulties in Writing the Dual of a Primal Program

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}$, ...
1
vote
1answer
223 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq ...
1
vote
1answer
488 views

Weak duality theorem and false corollary

Let $A\in\mathbb{R}^{m\times n}, \ c\in \mathbb{R}^n, \ b\in\mathbb{R}^m$ and consider the linear program $$\max \{ c^Tx : Ax\le b\} \ (1)$$ Its dual is $$\min \{ b^Ty : A^Ty=c, \ y\ge 0\} \ (2)$$ The ...