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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Oct 1 '18 at 3:03
  • $\begingroup$ I'm not entirely sure I follow. Do you mean that my interpretation of $D$ is incorrect? If so, what should it be? $\endgroup$ – BSplitter Oct 1 '18 at 3:06
  • 2
    $\begingroup$ Try $D=R^{2}$. Random text added for length... $\endgroup$ – Brian Borchers Oct 1 '18 at 3:08
  • $\begingroup$ Note Brian's comment: The $\inf$ should be over all $x$. $\endgroup$ – copper.hat Oct 1 '18 at 3:14
  • 1
    $\begingroup$ Find conditions under when the $\inf$ is finite. This will give the dual constraints. $\endgroup$ – copper.hat Oct 1 '18 at 3:16

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

  • $\begingroup$ 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. $\endgroup$ – BSplitter Oct 4 '18 at 2:25
  • $\begingroup$ @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!) $\endgroup$ – copper.hat Oct 4 '18 at 2:27
  • 1
    $\begingroup$ 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. $\endgroup$ – BSplitter Oct 4 '18 at 2:29

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.