|
|
|
|
|
|
 |
 |
|
Animating Optimization with the Gradient Projection Method
|
|
|
|
|
|
| Organization: | Physicist at Large Consulting |
|
|
|
|
|
|
2013-07-02
|
|
|
|
|
|
The gradient projection mimization technique, can be understood in terms of the tangent space of the active constraints at a point. Since any vector in the tangent space is orthogonal to the gradients of the constraints, a displacement in the direction of a vector in the tangent space does not change the value of the constraints, to first order. The gradient projection method starts at a feasible point and moves in the direction which is the projection of the negative of the objective function gradient onto the tangent space. The resulting point has a lower value for the objective function but is no longer feasible. A second step is then taken, moving perpendicular to the tangent space of the orginal point, to get back to feasibility. This process is repeated until a local minimum is found.
In the approach taken here, the gradient projection method is implemented using a differential equation approach, in which the time derivative of a point is equal to the projected negative objective function gradient plus the correction term for moving to feasibility, starting from a non-feasible point. This is slower than the usual step-wise approach, but results in a smooth path from a non-feasible, non-optimal point to a feasible local minimum, since NDSolve controls the step size. This path is suitable for animation. The method is illustrated with an animation of the packing of different size circles inside a circumscribing circle.
|
|
|
|
|
|
|
|
|
|
|
|
Optimization, Animation, Gradient Projection, Luenberger, circle packing
|
|
|
 |
|
|
| AnimatingOptimization.nb (125.9 KB) - Mathematica Notebook | | circle_packing10.gif (2.4 MB) - animated gif |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
