4
$\begingroup$

Suppose we have a primal problem

$ \min_x f(x), s.t. h_i(x)=0, $

where $h_i$ are all affine, and $f$ is convex.

Then its Lagrangian is

$\min_x \max_{z_i} f(x) + \sum_i z_i h_i(x)$

and the dual problem is

$\max_{z_i} \min_x f(x) + \sum_i z_i h_i(x)$

The KKT condition (sufficient and necessary here) only says for any optimal solution x*, there exists $z^*_i$ such that

$\nabla f(x^*) + \sum_i z^*_i \nabla h_i(x^*) = 0$

But is the following claim correct?

For any optimal $z^*_i$ of the dual problem, there must be an optimal $x^*$ of the primal problem, such that

$\nabla f(x^*) + \sum_i z^*_i \nabla h_i(x^*) = 0$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

At the level of generality you asked about, the answer is no, the claim is not correct. Of course, your case of interest may rule out counterexamples like the one below.

It can happen that the primal is bounded below but does not achieve its optimum, whereas the dual does. For example take $f(x_1,x_2) = \exp(x_1)$ and $h_1(x_1,x_2)=x_2$. Then the primal is $\min_{x_1\in\mathbb{R}} \exp(x_1)$ and the dual is $\max_{z_1 = 0} 0$. Both have optimal value zero, but in the case of the primal the infimum is not achieved. The KKT equation \[ \begin{bmatrix} \exp(x_1) & 0\end{bmatrix} + z_1\begin{bmatrix} 0 & 1\end{bmatrix} = 0 \] has no solutions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In this counter-example, there is no finite primal optimal solution, so of course there is no primal-dual pair which satisfies the KKT condition. I was just pointed to Rockefellar's "Convex Analysis" book, which devoted the whole Section 28 to the duality properties. It turns out that under quite mild conditions, any dual optimal solution and any primal optimal solution can be paired to satisfy the KKT condition. The result is surely nontrivial :) $\endgroup$
    – Jonathan
    Commented Dec 30, 2011 at 9:17
0
$\begingroup$

Unless I am confused, this is proved in Boyd-Vanderberghe "Convex Optimization", page 244.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Unfortunately no. The book only says $x^*$ is optimal if and only if there are $z_i$ that, together with $x^*$, satisfy the KKT conditions. However my question is given any $z^*_i$ which optimizes the dual problem, whether there exists a primal optimal solution $x^*$ which attains zero gradient together with $z^*_i$. $\endgroup$
    – Jonathan
    Commented Dec 29, 2011 at 19:55
  • $\begingroup$ I am probably still confused, but the book seems to say that if $x, z$ (in your notation) satisfy the KKT conditions, then $x, z$ are primal and dual optimal, with zero duality gap, which appears to be exactly what you are asking... $\endgroup$
    – Igor Rivin
    Commented Dec 29, 2011 at 20:03
  • $\begingroup$ Sorry for the confusion; it's tricky. The optimal solutions to the primal and dual problems are not unique. For any primal optimal $x^*$, there must exist a dual optimal solution $z^*_i$ such that they together satisfy the KKT condition. But it is possible that although a $z^*_i$ is a dual optimal solution, there does not exist any primal optimal $x^*$ which satisfies KKT condition together with $z^*_i$. $\endgroup$
    – Jonathan
    Commented Dec 29, 2011 at 20:13
  • $\begingroup$ In other words, can one treat the dual problem as the "primal problem" in the theorem, and then apply the theorem in a reverse way? I think not, because in Lagrange dual, there is no "the dual of the dual is the primal", loosely speaking. $\endgroup$
    – Jonathan
    Commented Dec 29, 2011 at 20:20
  • $\begingroup$ I will ponder, but do you have an example for your $n-1$st comment? $\endgroup$
    – Igor Rivin
    Commented Dec 29, 2011 at 20:53

You must log in to answer this question.

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