0
$\begingroup$

In Section 5.5.5 of Boyd's book "Convex Optimization", the book states that the primal problem can be solved by the dual problem. More precisely, suppose we have strong duality and an optimal $\{\lambda^{\ast}, \nu^{\ast} \}$ is known. Suppose that the minimizer of $\mathcal{L} (x,\lambda^{\ast}, \nu^{\ast})$, i.e., the solution of

$$\underset{x}{minimize} \; f_0 (x) + \sum_{i=1}^m \lambda_{i}^{\ast} f_i(x) + \sum_{i=1}^p \nu_{i}^{\ast} h_i (x)$$

is unique. (For a convex problem this occurs, for example, $\mathcal{L} (x,\lambda^{\ast}, \nu^{\ast})$ is a strictly convex function of $x$).

My question is that: Because linear/affine functions are not strictly convex, could we get the globally optimal solution to the primal problem by solving the dual problem?

$\endgroup$
  • $\begingroup$ Your question is unclear. Are you asking whether the dual LP has an optimal solution (the answer is no), or whether you can obtain an optimal solution to the primal problem from an optimal solution to the dual? $\endgroup$ – Brian Borchers Aug 14 '17 at 12:17
  • $\begingroup$ @BrianBorchers: Hi! I edited the question, hoping that it is clear now. $\endgroup$ – Hoping_Blessing Aug 14 '17 at 12:43
  • 1
    $\begingroup$ Yes, it is definitely possible to recover the primal solution from the solution to the dual, and vice versa. The simplex method depends on this. I would recommend deriving the Lagrangian for a standard primal/dual LP pair. Then substitute in the dual optimal point $(\lambda^*, \nu^*)$ and simplify. You'll be surprised at what you get, I'll bet. That won't get you all the way to the answer, but at least it will show you why you're too focused on the Lagrangian. $\endgroup$ – Michael Grant Aug 14 '17 at 14:43
1
$\begingroup$

In convex programming under a constraint qualification (slater for example)

The Primal problem has solution if and only if the dual problem has solution.

In this case the optimal value of both problem is same (strong duality holds) and moreover focusing complementary slackness conditions , it makes a bridge between optimal solutions of primal problem to dual problem.

Therefor the answer of your question is "YES" under presence of a constraint qualification.

EDIT

For the particular case, Linear programing , there is no need of constraint qualifications, (in precise words the linear CQ is automatically holds). Also in the later case things become much easier, through an optimal solution which is vertex one can easily get an optimal solution of primal problem which is again vertex.

$\endgroup$
  • $\begingroup$ However, for a linear program, the solution to the dual problem may be not unique as stated in the question. How can we ensure that the dual gap equals zero?To be honest, I don't still understand why the authors include the strictly convex definition here. $\endgroup$ – Hoping_Blessing Aug 14 '17 at 20:27
  • $\begingroup$ I edited my answer! BTW why are you worried about uniqueness of dual solution? ! Plus in convex programing with strictly convex objective, one may have many dual solutions. $\endgroup$ – Red shoes Aug 14 '17 at 21:05
  • $\begingroup$ @Hoping_Blessing it's important to read their text carefully. What they are saying is that strict convexity is an example of a condition under which the solution to $\inf_x \mathcal{L}(x,\lambda^*,\nu^*)$ exists. It is certainly not necessary for that to be the case. As I hinted above, it exists for any linear program with a finite optimal solution. $\endgroup$ – Michael Grant Aug 14 '17 at 22:51
  • $\begingroup$ @MichaelGrant: Thank you very much for your hint. I will investigate more carefully. $\endgroup$ – Hoping_Blessing Aug 15 '17 at 7:15

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.