0
votes
1answer
23 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
0
votes
0answers
12 views

Equivalence of Two Statements (Duality Theory, Optimization)

Let $a$ and $a_{1}, ... , a_{m}$ be given vectors in $\mathbb{R^{n}}$. Prove that the following two statements are equivalent. $a)$ For all $x \geq 0$ we have $a'x \leq max_{i} a_{i}'x$. $b)$ There ...
0
votes
0answers
31 views

Fenchel dual vs Lagrange dual

Consider the Fenchel dual and the Lagrangian dual. Are these duals equivalent? In other words, is using one of the these duals (say for solving an optimization), would give the same answer as using ...
1
vote
1answer
32 views

Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
0
votes
0answers
38 views

How to derive dual of this L1 norm approximation problem?

I am working through a question in Convex Optimization by Boyd and Vandenberghe. I've made an image with the original question, and the part of the solution I don't understand: how the dual is ...
0
votes
0answers
16 views

Dual problem of SDP

Suppose we have the following optimization problem: \begin{array}{l} \mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\mathrm{Tr}\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\ ...
0
votes
0answers
71 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 ...
0
votes
0answers
33 views

dual form of an optimization

Consider the following optimization in primal form $\displaystyle\max_{x_1, \ldots, x_n}\sum_{i=1}^n d_ix_i -\sum_{i=1}^n x_i\log(x_i)$ subject to $a_i\leq x_i\leq b_i$ and $\sum_{i=1}^n ...
0
votes
0answers
31 views

Dual of a polyhedra vs. dual of an optimalization problem

There are lot of fields where the term duality appear. Is there any relationship between dual of an optimalization problem and dual of a polyhedra?
0
votes
1answer
54 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are ...
0
votes
1answer
72 views

Lagrangian dual for the sum of norms

I would like some help in deriving the Lagrangian dual function of a sum-of-norms minimization problem : $\sum{||A_{i}x-b_{i}||}$ when $A_{i}$ are matrices, and $b_{i},x$ vectors. I understand I can ...
0
votes
0answers
29 views

how to check slater condition for a constrained optimization problem?

Given any optimization problem that you suppose to solve with Lagrange by thrusting strong duality, you need to be sure the Slater Conditions. And I guess there is no algorithmic way to solve for all ...
1
vote
0answers
53 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 ...
6
votes
1answer
164 views

Is duality theory in optimization as useful as it seems?

I have been reading a lot about nonlinear optimization and duality, and it seems that duality theory is extremely useful. I feel that I am missing some of the negative aspects/difficulties associated ...
1
vote
3answers
177 views

What is the dual of this optimization problem?

Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am looking for the dual of the following optimization ...
1
vote
1answer
179 views

Are these convex optimization problems equivalent?

Consider the optimization problem $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
0
votes
1answer
325 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
2
votes
3answers
122 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 \\ ...
0
votes
1answer
704 views

Maximizing and Minimizing a function

Let $f(x,y)$ be a function such that $f:\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$. Now we have to maximize $f$ over $x$ and minimize it over $y$ $i.e.\ $ $$\underset{x}{\text{max}}\: ...
0
votes
1answer
257 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
174 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
186 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}$, ...
5
votes
1answer
501 views

Conditions for no duality gap in quadratic programming?

Assume $Q \in \mathbb{R}^{n\times n}$, and $b,c,d \in \mathbb{R}^n$. A quadratic programming problem is: $$ \min_{x \in \mathbb{R}^{n}} \tfrac{1}{2} x^T Q x + c^T x,$$ subject to $A x \leq b, E x ...
3
votes
0answers
73 views

Questions about no duality gap and optimal solutions

My questions are regarding a constrained problem, $$\min_{x \in X \subseteq \mathbb{R}^n} f(x),$$ subject to $g(x) \leq 0 \in \mathbb{R}^m, h(x) =0 \in \mathbb{R}^k$. Its dual problem is $$\sup_{u ...
1
vote
1answer
227 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 ...