5
$\begingroup$

I am trying to implement (constrained) minimization of a certain function with the augmented Lagrangian method. Where can I find a reference that discusses in detail the good practices for the various algorithmic parameters? For instance: the increase rate for $\mu_k$, the initial value for the Lagrange multipliers, the stopping criterion to use for the gradient and how to change it across iterations...

$\endgroup$
2
  • 2
    $\begingroup$ Why not use one of the big packages using this method -- say LANCELOT? :-) $\endgroup$ Commented Oct 18, 2023 at 15:06
  • 3
    $\begingroup$ @WolfgangBangerth Because I want to have some more control: an implementation on manifolds, a specific solver for part of the subproblems. I am not sure I can fit all these variants into it. $\endgroup$ Commented Oct 18, 2023 at 16:41

1 Answer 1

7
$\begingroup$

My favorite reference on this is Constrained Optimization and Lagrange Multiplier Methods by Bertsekas. It's a little old (1982) but I haven't seen any other reference that describes many of the important details that other texts like Nocedal and Wright just assume. For example, why does it work to use not just a simple gradient ascent routine to update the Lagrange multipliers, but to also use a constant stepsize? That always struck me as totally bonkers and only Bertsekas bothers to explain why it can work.

As for stopping criteria, Nocedal and Wright has more information about merit functions to use for constrained optimization problems. This isn't as totally obvious as it is for the unconstrained and strictly convex case where the ratio of the Newton decrement to the objective itself essentially tells you everything you need.

Finally, for a more modern perspective including non-smooth problems and the connection to proximal algorithms, Proximal Algorithms by Parikh and Boyd and Distributed Optimization and Statistical Learning via ADMM by Boyd and friends are both great reads.

A lot of what you mentioned specifically (increase rate for the penalty parameter, initial guess for the multipliers) are decided in a heuristic and ad hoc manner. For example, I've seen people recommend increasing the penalty by a factor of 10% each time that you don't get a satisfactory guess. When I've used ADMM before I've managed to figure out a good starting guess for the penalty parameter by dimensional analysis. As for the initial value of the multipliers, starting with 0 is usually fine. You can maybe do better if you can reason directly on the dual functional for your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.