Example for Lagrange dual objective does not have an explicit expression

Question

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?

Answer 1

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.