2
$\begingroup$

In some applications of convex optimization (e.g. SVM) the way to go is via the Lagrangian Dual Problem.

I'm clear about the following statements (please correct me if I'm wrong):

  • The dual problem provides a lower bound for the primal problem.
  • The dual problem is always concave. If the primal problem is hard to optimise (not convex, high-dimensional) it's easier to find a lower bound via the dual and use it as an approximation for the primal problem.
  • Under KKT-Conditions the optimal solutions of the primal and the dual problem are the same. Therefore the solution can be obtained by both, the primal and the dual problem.

Assuming KKT-conditions, WHEN and WHY is the dual problem the better (or the only) way to go?

$\endgroup$
  • 2
    $\begingroup$ Another advantage: the dual problem has as many variables as constraints are there in the primal. So you can reduce the dimensionality, sometimes by much. $\endgroup$ – Anna SdTC Mar 21 '17 at 17:39
  • 2
    $\begingroup$ @Anna SdTC is right: this is one of the main reasons. Sometimes also, the variables in the dual problem can be interpreted in such a way that it improves the unerstanding of the problem. $\endgroup$ – Jean Marie Mar 21 '17 at 22:21
  • 1
    $\begingroup$ Strong duality (equal primal and dual optimal values) doesn't generally hold for non-convex problems or even for convex problems unless there is a suitable constraint qualification. Thus your third statement is incorrect. $\endgroup$ – Brian Borchers Mar 22 '17 at 1:22
  • 2
    $\begingroup$ Many optimization methods (so-called primal-dual methods) simultaneously solve the primal and dual problems. $\endgroup$ – Brian Borchers Mar 22 '17 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.