# Tag Info

0

$g(x, \lambda, v)$ as a function of $x$ is convex only if $v\leq 0$ (the hessian is diagonal positive semidefinite), otherwise it has at least one negative eigenvalue. Hence for $v\nleqslant0$, $\inf_{x}g(x,\lambda,v)=-\infty$, and thus the max of $g(\lambda, v)$ must be at a point where $v\leq0$. Therefore the Lagrange relaxation and the dual of the LP ...

1

Suppose that $(y,t)$ is such that $\|y\|_\infty \leq t$. Select any $(x,t') \in K$. We apply Hölder's inequality to find $$\langle(x,t'),(y,t)\rangle =\\ \langle x,y \rangle + t't \geq\\ - \|x\|_1 \|y\|_{\infty} + t't \geq\\ -\|x\|_1 \|y\|_{\infty} + \|x\|_1 \|y\|_{\infty} = 0$$ Now, suppose that $(y,t)$ is such that $\langle(x,t'),(y,t)\rangle \geq 0$ ...

0

The question is asking how to convert the dual back into the primal. After the substitution of $y^+ - y^-$ for $y$, you have \begin{align*} \min W &= b^Ty^+ - b^T y^- & \\ {\rm s.t.} \hspace{1in} \\ A^Ty^+ - A^Ty^- & \geq c \\ y^+ & \geq 0 \\ y^- &\geq 0 \end{align*} Moving back to the primal, you have one variable for each ...

Top 50 recent answers are included