0
$\begingroup$

I am very new to optimization. so, sorry If I ask a simple question. I have a problem with a dozen of variables. I want to use Augmented Lagrangian for solving the problem. I write a code based on the method(in matlab). Unfortunately, the code doesn't work And I don't know how to understand what's going wrong?

How to debug an augmented lagrangian program? Is there a method for checking variable changes to understand the source of the bug? or could you provide some hints or insight on how to debug an augmented lagrangian code?

$\endgroup$
  • $\begingroup$ I'd be interested to here what the problem actually was if you figure it out. $\endgroup$ – Brian Borchers Feb 29 '16 at 5:55
5
$\begingroup$

It's very difficult to provide a useful answer to this question because you haven't provided enough details about your problem and what you have already tried.

There are various conditions under which the augmented Lagrangian method is certain to converge asymptotically to an optimal solution. You should make sure that the problem you're trying to solve satisfies these conditions so that there's a sound theoretical basis for what you're doing.

In the augmented Lagrangian method, you solve an unconstrained minimization problem within each major iteration. If the procedure that you're using to solve that unconstrained problem isn't working properly than the overall method can easily fail to converge to a solution.

The augmented Lagrangian method makes use of a penalty parameter that can be adjusted after each major iteration of the algorithm. In theory, the method is guaranteed to converge if a large enough penalty parameter is used. In practice, using too large a penalty parameter can make it hard to solve the unconstrained minimization problem and slow down convergence.
Starting with a bad value of the parameter (too big or too small) or adjusting the parameter incorrectly (not increasing the penalty enough) can lead to slow convergence or complete failure. In my experience, it's almost always necessary to run some experiments to adjust the penalty parameter for good convergence on a new class of problems.

You haven't said whether the method is failing entirely or simply converging slowly on your problem. For users who are used to the fast quadratic convergence of Newton based methods, it can be frustrating to see the slower convergence of augmented Lagrangian methods. You're often limited in practice to getting solutions that are only accurate to a few digits. If you need solutions that are accurate to 8-10 digits, than augmented Lagrangian methods are probably not the best way to go.

My recommendations for debugging this would be:

  1. Make sure you've got a theoretical convergence result for the class of problems you're considering.

  2. Make sure that your code is correctly minimizing the augmented Lagrangian in each iteration. You may be able to get away with an imprecise solution later, but for debugging I'd just try for the best accuracy you can get.

  3. Adjust the penalty parameter so that you're getting reasonably fast convergence to feasibility.

You should obviously be monitoring the feasibility of the solution after each major iteration. Assuming the constraints are reasonably scaled, simply computing the norm of the constraint violations is usually a good measure. You can also track the evolution of the Lagrange multipliers to see whether they're converging to some fixed values.

If you've got access to some other reliable solver, you can solve your problem using that solver first so that you know what an optimal solution looks like.

$\endgroup$
  • $\begingroup$ Thank you very much for your excellent answer, Brian. My problem is semidefinite with 2 semidefinite matrices, where they are related. it looks like the problem in this question on MatSE$[ ](math.stackexchange.com/questions/1252544/…. I want to use some some structure in $R$ matrix. $\endgroup$ – user85361 Feb 29 '16 at 6:00
  • $\begingroup$ I have some constraints on diagonal elements of semidefinite matrix, I just didn't consider this constraints when updating other variables related to them, and instead I update them and use diagonal elements of sdp matrix in accordance with constraints. and after that I project the matrix on sdp cone. Is this can be cause of a problem? $\endgroup$ – user85361 Feb 29 '16 at 6:04
  • $\begingroup$ I'd suggest that you either modify your original question or ask a new question in which you explain what problem you're trying to solve and how you're solving it. I can't really respond to your brief comments. $\endgroup$ – Brian Borchers Feb 29 '16 at 15:07
  • $\begingroup$ I used your excellent hints and understood that what variable is not converging. But till know I didn't completely resolve the problem. I ask a new question which is my original problem, which I wanted to solve. Please have a look: scicomp.stackexchange.com/questions/23295/… $\endgroup$ – user85361 Mar 6 '16 at 15:08

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.