0
$\begingroup$

In the study of Lagrange dual of an optimization problem, Page 277 of the third edition book of Nonlinear Programming by Bazaraa, Sherali and Shetty says that "the main difficulty in solving the dual problem is that the dual objective function is not explicitly available". I am convinced with the explanation given n the book thereafter. However, I am not getting a concrete classroom primal problem for which dual objective does not have an explicit expression. Can you please give one?

$\endgroup$
2
$\begingroup$

Although many examples of Lagrangian duality in textbooks involve functions and constraints for which it is easy to minimize the Lagrangian for a fixed Lagrange multiplier, there are situations where there is no explicit formula for the dual function. For example, consider the problem:

$\min \| Ax - b \|_{1}$

subject to

$Cx=d$.

The Lagrangian is

$L(x,\lambda)=\| Ax-b \|_{1} + \lambda^{T}(Cx-d)$

The dual function is

$g(\lambda)=\inf_{x} \| Ax-b \|_{1} + \lambda^{T}(Cx-d)$.

There's no explicit formula for $g(\lambda)$, although it's possible to evaluate $g(\lambda)$ by solving an LP.

$\endgroup$
4
  • $\begingroup$ Thanks a lot, Professor Borchers $\endgroup$ – user144660 Oct 6 '20 at 4:18
  • $\begingroup$ @Profssor Brochers: I am not getting a perfect explanation for 'why there is no explicit formula for g(\lambda)?' Or, 'why there cannot exist an explicit formula for g(\lambda)? Can you please give me an answer to this? $\endgroup$ – user144660 Oct 6 '20 at 4:38
  • 1
    $\begingroup$ @user144660 no explicit solution means that we cannot directly calculate an optimal point. "Optimal" can have different definitions, but taking the most fundamental one, Fermat's optimality condition, we cannot find values $\lambda$ for which $\mathbf{0}\in\partial g(\lambda)$. In these cases we can use an iterative scheme (algorithm) that will gradually progress towards such points (in the example above we do so using Linear Programming). $\endgroup$ – iarbel84 Oct 6 '20 at 8:31
  • $\begingroup$ I got the point. Thank you, @iarbel84 $\endgroup$ – user144660 Oct 6 '20 at 11:25

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.