# Augmented Lagrangian Minimizer

Posted 9 years ago
5632 Views
|
5 Replies
|
0 Total Likes
|
 Packing problems have O(n^2) inequality constraints for packing n objects, which can make them computationally challenging. The attached notebook contains an experimental augmented Lagrangian nonlinear minimizer which uses FindMinimum for minimizing the unconstrained augmented Lagrangian. Results are shown for packing 10, 20, 30, and 40 integer radii circles in a circle from random starting locations. The code is approximately 10 times faster than FindMinimum's Interior Point solver for packing 10 circles and approximately 30 times faster for packing 20 circles. The function call is the same as FindMinimum.A simple example is augLag[{x + y, x^2 + y^2 <= 1, x/3 + 2 y/3 == 1/2}, {{x, -1}, {y, 1}}] {0.568338, {x -> -0.363325, y -> 0.931662}, {\[Lambda][[1]] -> 0.301511, \[Lambda][[2]] -> -2.34272}, "Max Cons Viol" -> 1.63459*10^-8} For interpreting the Lagrange multiplier values, note that >= constraints are converted to <= constraints. Also, only nonzero multiplier values are returned.Comments and suggestions are welcome. Attachments:
5 Replies
Sort By:
Posted 9 years ago
 just what you would expect.
Posted 9 years ago
 This is the global minimum for packing 10 integer circles, as calculated using MathOptimizer Professional
Posted 9 years ago
 Just for fun, what is the outcome of MathOptimizer Professional if one circle has radius 1 and the other nine circles have radius 0.52? Thanks in advance!
Posted 9 years ago
 I did not expect the results to be global optima, since I was starting each calculation from only one randomly chosen set of initial values. What I wanted to do was to compare the interior point method used by FindMinimum with the augmented Lagrangian method I had coded, for a problem with many more constraints than variables.
Posted 9 years ago
 How do you verify the outcome? The goal is to get a circumventing circle with minimal radius around all packed non-overlapping sample circles?I mean the 10 circle solution (above) looks like the minimal radius found could yet decrease if only the yellow marked circles moved towards the center and the two small circles near the center moved outward to the boundary somewhere between bigger ones?Have you tried the algorithm with a set of sample circles known to fit into a circumventing circle, likethe delta is only a visual guess, I did not compute that to reach a match.