# Determining the dual problem

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

• This optimization problem is infeasible. Is that intended? – David M. Dec 8 '18 at 14:18
• No, that was my mistake. The equality constraint has been edited. – 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*}