Message Boards Message Boards


Augmented Lagrangian Minimizer

Posted 9 years ago
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.

POSTED BY: Frank Kampas
5 Replies

just what you would expect.

enter image description here

POSTED BY: Frank Kampas

This is the global minimum for packing 10 integer circles, as calculated using MathOptimizer Professional

enter image description here

POSTED BY: Frank Kampas

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 BY: Udo Krause

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 BY: Frank Kampas

How do you verify the outcome? The goal is to get a circumventing circle with minimal radius around all packed non-overlapping sample circles?

augmented Lagrangian 10 circles solution

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, like

fitting circles

the delta is only a visual guess, I did not compute that to reach a match.

POSTED BY: Udo Krause
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract