21
$\begingroup$

So I was just starting on convex optimization and was having a slightly hard time visualizing the lagrangian being always concave because it is the pointwise infimum of a family of affine functions.

Can anyone help explain this? I've googled extensively but most places just state this without elaboration or examples.

Thanks.

$\endgroup$
3
  • 9
    $\begingroup$ Affine functions are themselves concave (and convex). The pointwise infimum of concave functions is concave. You will probably find more for the equivalent: The pointwise supremum of convex functions is convex. A function is convex if and only if its epigraph is convex, and the epigraph of a pointwise supremum is the intersection of the epigraphs. $\endgroup$ Oct 5, 2013 at 18:59
  • $\begingroup$ Hi, thank you, there was more lucid literature from that point of view. $\endgroup$
    – Achint
    Oct 8, 2013 at 1:08
  • $\begingroup$ Just a quick comment that the Lagrangian per se is not always concave as stated by OP (I have edited your post) - I think OP is referring to the dual function of the Lagrangian that takes the pointwise infimum. That is concave, regardless of whether the original objective function is convex, concave, or neither. $\endgroup$
    – Samuel Low
    Feb 3 at 22:10

3 Answers 3

14
$\begingroup$

Daniel Fischer gave a transparent explanation in terms of epigraphs $\{(x,y): y\ge f(x)\}$:

A function is convex if and only if its epigraph is convex, and the epigraph of a pointwise supremum is the intersection of the epigraphs. [Hence,] the pointwise supremum of convex functions is convex.

One can similarly argue from concavity, using the sets $\{(x,y): y\le f(x)\}$: this set is convex if and only if $f$ is concave. Taking infimum of functions results in taking the intersection of such sets.

$\endgroup$
9
$\begingroup$

See picture below for some intuition on why that may be (bold line is the pointwise infimum of the four affine functions). Similarly, you can conclude that the

Pointwise supremum of the set of affine functions is convex

enter image description here

$\endgroup$
1
  • 3
    $\begingroup$ This visualization is brilliant. $\endgroup$ Oct 31, 2021 at 1:21
1
$\begingroup$

The point-wise maximum of a set of convex functions is convex. $$g(x) = \max_i f_i(x) $$ The corresponding epigraph $$\{(x,t) | t > \max_i f_i(x)\}$$ is convex which could also be visualized as the insertion of a family of convex spaces, $$\cap_i \{(x ,t)| t > f_i(x)\}$$

The lagrangian could be rewritten as the negative of the supremum, $$lagrangian(x) = \min_i f_i(x) = - \max_i -f_i(x)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .