Constrained optimization: projected gradient flows
Abstract. We consider a dynamical systems approach to solve finite dimensional smooth optimization problems with a compact and connected feasible set. In fact, by the well-known technique of equalizing inequality constraints using quadratic slack variables, we lift a general optimization problem to an associated one without inequality constraints in a higher-dimensional space. We compute the projected gradient for the latter problem and consider its projection on the feasible set in the original, lower-dimensional space. In this way, we obtain an ordinary differential equation in the original variables, which is specially adapted to treat inequality constraints (for the idea see [1]).
The article shows that the derived ordinary differential equation possesses the basic properties which make it appropriate to solve the underlying optimization problem: the longtime behavior of its trajectories becomes stationary, all singularities are critical points, and the stable singularities are exactly the local minima. Finally, we sketch two numerical methods based on our approach.
[1] H.Th. Jongen, O. Stein, Constrained global optimization: adaptive gradient flows, in: C.A. Floudas, P.M. Pardalos (eds): Frontiers in Global Optimization, Kluwer Academic Publishers, Boston, 2004, 223-236.