# Finding the optimal value for a dual problem in optimization

Consider the following optimization problem: \begin{align*} &\min_{x_1,x_2 \in \mathbb{R}}x_1x_2\\ &\text{Subject to } x_1^2 + x_2^2\le 1, x_1\ge 0, x_2 \ge 0\\ \end{align*} I have been tasked with find the optimal value of the dual problem here. The definition for the optimal value of the dual problem that I have been given is $$d^* = \max_{\vec{\lambda} \in \mathbb{R}^m, \vec{\lambda} \ge 0} g(\vec{\lambda})$$ where $$g(\vec{\lambda}) = \inf_{\vec{x}\in D}\bigg(x_1x_2 + \lambda_1 (x_1^2+x_2^2-1)-\lambda_2x_1-\lambda_3x_2\bigg)$$ and $$D$$ is the domain under consideration. Here, $$D$$ is $$\mathbb{R}^2$$.

NOTE: Normally $$g$$ is a function of $$\lambda$$ and $$\mu$$, but since there are no equality constraints, this is just a function of $$\lambda$$.

My issue here is I have no idea how to find $$g(\vec{\lambda})$$, much less how to find the maximum over all $$\vec{\lambda} \in \mathbb{R}^3$$. Are there any steps that I should consider here? Any help would be greatly appreciated.

• You've misunderstood the relationship between the constraints that have been handled in the Lagrangian and the domain $D$. Since the constraints that force $x$ to be in the upper right section of the unit disk have been incorporated into the Lagrangian they don't have to be incorporated into the domain. – Brian Borchers Oct 1 '18 at 3:03
• I'm not entirely sure I follow. Do you mean that my interpretation of $D$ is incorrect? If so, what should it be? – BSplitter Oct 1 '18 at 3:06
• Try $D=R^{2}$. Random text added for length... – Brian Borchers Oct 1 '18 at 3:08
• Note Brian's comment: The $\inf$ should be over all $x$. – copper.hat Oct 1 '18 at 3:14
• Find conditions under when the $\inf$ is finite. This will give the dual constraints. – copper.hat Oct 1 '18 at 3:16

## 1 Answer

Look for additional conditions on $$\lambda$$ such that $$g$$ is finite.

It is a little easier to do if we write $$g$$ as a quadratic.

Let $$S= {1 \over 2} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ (note the eigenvalues are $$\pm {1 \over 2}$$), then $$g(\lambda) = \inf_x x^T (\lambda_1 I + S) x -(\lambda_2, \lambda_3)^T x -\lambda_1$$.

Note that we need $$\lambda_1 \ge {1 \over 2}$$, as otherwise the $$\inf$$ is $$-\infty$$.

If $$\lambda_1 = {1 \over 2}$$, we can choose $$x_2 = -x_1$$, and then we can see that if $$\lambda_2 \neq \lambda_3$$, then the $$\inf$$ is $$-\infty$$. Hence if $$\lambda_1 = {1 \over 2}$$ we must have $$\lambda_2 = \lambda_3$$ in order to have a finite $$g$$.

If $$\lambda_1 > {1 \over 2}$$ then we see that the minimising $$x$$ satisfies $$x = {1 \over 2} (\lambda_1 I + S)^{-1} \begin{bmatrix} \lambda_2 \\ \lambda_3 \end{bmatrix}$$, and so $$g(\lambda) = -{1 \over 4} \begin{bmatrix} \lambda_2 & \lambda_3 \end{bmatrix}(\lambda_1 I + S)^{-1} \begin{bmatrix} \lambda_2 \\ \lambda_3 \end{bmatrix} -\lambda_1 < -{1 \over 2}$$.

If $$\lambda_1 = {1 \over 2}$$ and $$\lambda_2 = \lambda_3$$, then we can write $$x^T (\lambda_1 I + S) x -(\lambda_2, \lambda_3)^T x = {1 \over 2} (e^T x)^2 - \lambda_2 (e^T x)$$, where $$e$$ is the vector of ones. In particular, the $$\min$$ occurs when $$e^T x = \lambda_2$$ and hence $$g(\lambda) = -{1 \over 2}\lambda_2^2 -{1 \over 2} \le - {1\over 2}$$.

Hence $$d^*=\sup_{\lambda \ge 0} g(\lambda) = - { 1\over 2}$$.

• I apologize for not responding sooner; I haven't had a chance to look at this problem until today. Correct me if I'm wrong, but in the $\lambda_1>\frac{1}{2}$ case, wouldn't $g(\lambda) = -\lambda_1$, since the first and second terms of $g(\lambda)$ would cancel out? I still agree with the conclusion. – BSplitter Oct 4 '18 at 2:25
• @BSplitter: I think you might be missing a factor of ${1 \over 2}$ so it doesn't exactly cancel. (Of course, I am prone to making mistakes!) – copper.hat Oct 4 '18 at 2:27
• I wrote it out slightly differently. I just called the matrix in question $M$, and its inverse $M^{-1}$. Then the minimizing $x$ would be $M^{-1} \begin{bmatrix}\lambda_2 \\ \lambda_3\end{bmatrix}$. Plugging that in allows some cancellation, I think. – BSplitter Oct 4 '18 at 2:29