Mathematica 9 is now available

Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Animating Optimization with the Gradient Projection Method
Author

Frank Kampas
Organization: Physicist at Large Consulting
Revision date

2013-07-02
Description

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.
Subjects

*Applied Mathematics > Optimization
*Mathematica Technology > Application Packages > Applications from Independent Developers > MathOptimizer
*Mathematica Technology > Application Packages > Applications from Independent Developers > MathOptimizer Professional
*Mathematica Technology > Programming > Animations
Keywords

Optimization, Animation, Gradient Projection, Luenberger, circle packing
Downloads Download Wolfram CDF Player

Download
AnimatingOptimization.nb (125.9 KB) - Mathematica Notebook
Download
circle_packing10.gif (2.4 MB) - animated gif