1
$\begingroup$

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$.

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

1 Answer 1

2
$\begingroup$

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*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .