1
$\begingroup$

I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \lambda) = f(x) - \sum_{i=1}^m\lambda_i g_i(x)$ and look for a stationary point.

In my particular case, this amounts to looking for a saddle point, which is not convenient for me because I have to perform several extremizations before I find a satisfactory point (for example by using Uzawa's algorithm). I'd rather have to look for a minimum or a maximum, that I can reach with a single gradient descent/BFGS run/whatever.

So, I was wondering: is there any way I can "rephrase" my optimization problem so that the stationary point of the Lagrangian is an extremum, or are there some cases where a saddle point is the best I can hope for?

$\endgroup$
  • 2
    $\begingroup$ Welcome to SciComp.SE! What do you consider a "stationary point" of a Lagrangian? (Also, are you assuming any convexity?) $\endgroup$ – Christian Clason Nov 2 '18 at 15:47
3
$\begingroup$

By the very definition of the Lagrangian, the extrema of the original, constrained problem are stationary points of the Lagrangian. That's just how the Lagrangian is defined.

What you are looking for are "penalty methods" or "augmented Lagrangian methods". In essence, it adds something to either the objective function or to the Lagrangian to make sure that the solutions of the problem are really the minima of the augmented function.

As with all things optimization, I've found the book by Nocedal and Wright ("Numerical Optimization") to be an excellent source of insight. It has long sections on both penalty methods and augmented Lagrangian methods, and how to choose the term(s) you will want to add.

$\endgroup$

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.