Lagrange duality compared with Lagrange multiplier method

109 Views Asked by At

As we all know, Lagrange multiplier method says: in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$, one instead finds the extremum of $f(x)+\lambda g(x)$ over $x$ and $\lambda$. Note here only finding extrema is talked about, not min or max.

Lagrange duality says $$ \min_x(\max_\lambda(f(x)+\lambda g(x)))=\max_\lambda(\min_x(f(x)+\lambda g(x))) $$ I understand here one has to talk about min and max unlike extremum as in normal Lagrange multiplier method in order for the duality to exist. It is particularly useful for inequality constraints, and perhaps only used for inequality constraints. I know the way I understand might not have grasped the entire meanings, so any comments or corrections about what I said?

1

There are 1 best solutions below

2
On

Some geometrical ideas about.

The Lagrangian $L(x,\lambda)$ stationary points are saddle points. Saddle points have that characteristic

$$ \min_x(\max_\lambda(f(x)+\lambda g(x)))=\max_\lambda(\min_x(f(x)+\lambda g(x))) $$

See for instance the plot of

$$ L(x,\lambda) = x + \lambda(x-1) $$

The stationary point is located at $(x^*,\lambda^*) = (1,-1)$ in red, as solution for

$$ L_x = 1+\lambda = 0\\ L_{\lambda} = x-1 = 0 $$

Observe the level curves for $L(x,\lambda)$ characterizing a saddle point around the stationary point.

enter image description here