2
$\begingroup$

Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*}

In this expository paper, Boyd claims (top of page $8$) that if:

  1. $\lambda^*$ is a dual optimal solution
  2. There is no duality gap
  3. $L(x, \lambda^*)$ has a unique minimizer $x^*$ (which can happen, for example, if $f$ is strongly convex)

then $x^*$ is primal optimial.

I've played around with the Lagrangian for some time, but I have not been able to show that $x^*$ is primal feasible, nor that $f(x^*)$ is the primal optimal value.

I am also wondering: if $L(x, \lambda^*)$ does not have a unique minimizer, must a primal optimal solution $x^*$ be among them?

Thank you in advance for any help.

$\endgroup$
10
  • $\begingroup$ Hint: "no duality gap", i.e., the optimal values of the primal and dual problems are the same. is a crucial condition for the correctness of the statements you question. $\endgroup$ – Mark L. Stone May 18 at 19:34
  • $\begingroup$ Related question: link(or.stackexchange.com/questions/1065/…) $\endgroup$ – batwing May 19 at 13:59
  • $\begingroup$ @MarkL.Stone Thanks for encouraging me to solve this on my own. Does strong duality usually mean $\tag*{}$ A) There is no duality gap $\tag*{}$ B) There is no duality gap and the primal, dual values are attained $\tag*{}$ In the second case, it's not too difficult. Let $\overline{x}$ be a primal optimal solution and $p^*, d^*$ the primal/dual optimal values. Then $$L(\overline{x}, \lambda^*) = f(\overline{x}) = p^* = d^* = \inf_x L(x, \lambda^*),$$ so $\overline{x}$ is a minimizer of $L(x, \lambda^*)$, and by uniqueness we must have $\overline{x} = x^*.$ $\endgroup$ – user56202 May 19 at 14:07
  • $\begingroup$ @batwing Thank you I will check it out. $\endgroup$ – user56202 May 19 at 14:08
  • $\begingroup$ Re: strong duality. I have heard the term "strong duality" used in the larger setting of (A). That is, some people would say that strong duality holds as long as the primal optimum equals the dual optimum, even if neither is attained. For more background on when the latter occurs, I can recommend the Mosek modelling cookbook: docs.mosek.com/modeling-cookbook/… $\endgroup$ – mtanneau May 21 at 20:18
2
$\begingroup$

A proof that $x^*$ is optimal can be achieved by a Taylor expansion around $x^*$ at optimality. Observe that $$f(x^*+p) = f(x^*) + p^\top f'(x^*) + \frac12p^\top f''(x^*)p$$

Note that at a local optimum $\nabla f=0$ and given that $f$ is strictly convex it is a PD matrix with positive eigenvalues. Thus the third argument involving the Hessian $>0$ thereby implies that $f(x^*+p) > f(x^*)$ and thus proves that $x^*$ is a global minimum on $f$.

As to your question on how to prove $x^*$ is feasible I think you can prove that by contradiction assuming $A(x^*) \ne b$ and then the KKT conditions under that assumption will not be satisfied.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I have not read it in detail yet, but $f$ being differentiable is not part of the assumptions. $\endgroup$ – user56202 May 21 at 16:15
  • $\begingroup$ If $f()$ is an MIP then the proof still holds by the LP relaxation on $f()$. If the polyhedron of the LP relaxation containing the convex hull of the IP is not feasible then the MIP convex hull is the empty set and is itself not feasible. In general you are guaranteed to achieve optimality on an MIP through branch and bound which is guaranteed to find the global optimum solution to an MIP. $\endgroup$ – mathcomp guy May 21 at 16:20
  • $\begingroup$ @user56202 Differentiability is indeed one of the assumptions, otherwise these formulas are not defined, e.g. if the problem is a MIP or even if its functions are non-smooth (such as abs). $\endgroup$ – Nikos Kazazakis May 24 at 9:36

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.