I want to figure out the dual problem for the following primal \begin{alignat*}{2} &\underset{x,t}{\text{mininimize}} &\qquad& t \\ &\text{subject to} & & x_1 \geq 1 \\ & & & x_2 \geq 1 \\ & & & \vert|x\vert|_2 \leq t \\ & & & x_1+x_2 = 5 \end{alignat*}

I found the Lagrangian $$L(x,t,\lambda_1,\lambda_2,\lambda_3,v) = t(1-\lambda_3)+x_1(v-\lambda_1)+x_2(v-\lambda_2)+\lambda_3 \vert|x\vert|_2 + \lambda_1+\lambda_2-5v.$$ The terms in $t$ are unbounded below unless $\lambda_3 = 1$. To get the dual we need to solve $$\min_{x} \left\{x_1(v-\lambda_1)+x_2(v-\lambda_2)+\vert|x\vert|_2\right\}.$$

How does one determine the solution? It seems like a lot of conditions would be required to guarantee this is unbounded in $x$.

  • $\begingroup$ This optimization problem is infeasible. Is that intended? $\endgroup$ – David M. Dec 8 '18 at 14:18
  • $\begingroup$ No, that was my mistake. The equality constraint has been edited. $\endgroup$ – user20354139 Dec 8 '18 at 14:29

For simplicity, I will introduce the vector $\vec{z} = (v-\lambda_1,v-\lambda_2)$ so that we may write the optimization problem in question as $$ f(\vec{z})=\min_{\vec{x}} \{\langle \vec{z},\vec{x}\rangle + \lVert\vec{x}\rVert_2 \} $$ where $\langle\cdot,\cdot\rangle$ denotes the inner product of the vectors. If it holds that $\lVert \vec{z}\rVert_2>1$, one may choose $\vec{x}=-\alpha\vec{z}$ for any value $\alpha>0$ such that \begin{align*} \langle \vec{z},\vec{x}\rangle + \lVert\vec{x}\rVert_2 &= -\alpha\lVert\vec{z}\rVert_2^2 + \alpha \lVert\vec{z}\rVert_2 \\ &= \alpha\lVert\vec{z}\rVert_2 \left(1 - \lVert\vec{z}\rVert_2\right), \end{align*} and thus the minimization problem is unbounded from below. On the other hand, if it holds that $\lVert \vec{z}\rVert_2\leq 1$ then $$ \langle \vec{z},\vec{x}\rangle \geq - \lVert \vec{x}\lVert_2 $$ holds for any $\vec{x}$.

We may therefore conclude that $$ f(\vec{z}) = \left\{ \begin{array}{ll} 0 & \text{if }\lVert \vec{z}\rVert_2\leq 1\\-\infty & \text{if } \lVert \vec{z}\rVert_2>1.\end{array}\right. $$ The dual problem can thus be stated as follows: \begin{alignat*}{2} &\underset{v,\lambda_1,\lambda_2}{\text{maximize}} &\qquad& \lambda_1 + \lambda_2 -5v \\ &\text{subject to} & & \left\lVert \begin{pmatrix}v-\lambda_1\\v-\lambda_2\end{pmatrix}\right\rVert_2\leq1\\ & & & \lambda_1,\lambda_2\geq0 \end{alignat*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.