How to find the infimum of a function (Lagrangian Dual)

Question

In optimisation, we form what is known as a primal problem, e.g. (5.5 from Boyd and Vandenberghe) $$ \min_x \;\;x^\top x $$ $$ s.t. \;\;\;Ax=b$$

In the example, the Lagrangian is: $$ x^\top x + \nu^\top(Ax-b) $$

Now, I understand we can find the dual problem by first identifying the dual function, which is defined: $$ g(x) = \inf_x \mathcal{L(x,\lambda,\nu)} $$

where $\mathcal{L} $ represents the Lagrangian, and $\lambda$ and $\nu$ are the respective Lagrangian multipliers for the inequality and equality constraints.

In the example, the Lagrangian is found by setting $\nabla_x \mathcal{L}$ to zero and solving for $x*$, which appears to work because the function is convex? So, my question(s):

• Is this the method to find the dual for convex functions in general? (i.e. one solves for $x*$ and substitutes into $\mathcal{L}$)
• What if $\nabla_x \mathcal{L}$ does not give a single solution? (e.g. quadratic with nonzero determinant)
• Is there a general way to find the infimum of the Lagrangian function? It is okay if this is general within e.g. linear or quadratic programming

Answer 1

In general, the dual function $g$ is

$g(\lambda, \nu)=\inf_{x} L(x,\lambda,\nu)$

This is a function of $\lambda$ and $\nu$, not a function of $x$ (correcting a misstatement in the question.) The dual problem is then

$\max_{\lambda>0,\nu} g(\lambda,\nu)$

There's no completely general approach to finding the inf of $L(x,\lambda,\nu)$, but in those cases where $L$ is differentiable and convex with respect to $x$, any $x$ with $\nabla_{x} L(x,\lambda,\nu)=0$ will attain the inf. In cases where $L$ isn't differentiable with respect to $x$, you'll have to find some other way to determine the inf.

In practice, it is often the case that the inf is $-\infty$ for values of $\lambda$ and $\nu$ that don't satisfy some constraint. This gives an implicit constraint on the values of $\lambda$ and $\nu$ that provide a useful lower bound on the optimal primal objective value. Such a constraint is typically made explicit in the dual problem.

To answer your specific questions:

Is this the method to find the dual for convex functions in general? (i.e. one solves for x∗ and substitutes into L)

Yes. For problems with linear equality constraints it's also possible to use the Fenchel conjugate to find the Lagrangian dual problem, but that's a bit more advanced.

What if ∇xL does not give a single solution? (e.g. quadratic with nonzero determinant)

It's irrelevant whether there are multiple $x$ values at which the inf is attained, since only the value of the inf matters in $g(\lambda,\nu)$.

Is there a general way to find the infimum of the Lagrangian function? It is okay if this is general within e.g. linear or quadratic programming

Not really. We've already discussed the case where $L$ is differentiable with respect to $x$.