×

Constrained optimization: Projected gradient flows. (English) Zbl 1226.90107

Summary: We consider a dynamical system 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 transform a general optimization problem into an associated problem 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 [H. T. Jongen and O. Stein, in: Frontiers in global optimization. Boston, MA: Kluwer Academic Publishers. Nonconvex Optim. Appl. 74, 223–236 (2004; Zbl 1176.90571)]).
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.

MSC:

90C30 Nonlinear programming
90C52 Methods of reduced gradient type

Citations:

Zbl 1176.90571
Full Text: DOI

References:

[1] Jongen, H.Th., Stein, O.: Constrained global optimization: adaptive gradient flows. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 223–236. Kluwer Academic, Dordrecht (2003) · Zbl 1176.90571
[2] Rosen, J.B.: The gradient projection method for nonlinear programming: part II, nonlinear constraints. SIAM J. Appl. Math. 9, 514–532 (1961) · Zbl 0231.90048 · doi:10.1137/0109044
[3] Botsaris, C.A.: Differential gradient methods. J. Math. Anal. Appl. 63, 177–198 (1978) · Zbl 0405.65040 · doi:10.1016/0022-247X(78)90114-2
[4] Tanabe, K.: An algorithm for constrained maximization in nonlinear programming. J. Oper. Res. Soc. Jpn. 17, 184–201 (1974) · Zbl 0306.90064
[5] Tanabe, K.: A geometric method in nonlinear programming. J. Optim. Theory Appl. 30, 181–210 (1980) · Zbl 0396.90078 · doi:10.1007/BF00934495
[6] Yamashita, H.: Differential equation approach to nonlinear programming. Comput. Anal. 7, 11–38 (1976)
[7] Yamashita, H.: A differential equation approach to nonlinear programming. Math. Program. 18, 155–168 (1980) · Zbl 0436.90094 · doi:10.1007/BF01588311
[8] Bartholomew-Biggs, M.C., Brown, A.A.: ODE versus SQP methods for constrained optimization. Technical Report 179, The Hatfield Polytechnic Optimization Centre (1987) · Zbl 0655.65092
[9] Bartholomew-Biggs, M.C., Brown, A.A.: ODE versus SQP methods for constrained optimization. J. Optim. Theory Appl. 62, 371–386 (1989) · doi:10.1007/BF00939812
[10] Evtushenko, Y.G., Zhadan, V.G.: Stable Barrier-projection and Barrier-Newton methods in nonlinear programming. Optim. Methods Softw. 3, 237–256 (1994) · Zbl 0828.90122 · doi:10.1080/10556789408805567
[11] Schropp, J.: One- and multistep procedures for constrained minimization problems. IMA J. Numer. Anal. 20(1), 135–152 (2000) · Zbl 0945.65065 · doi:10.1093/imanum/20.1.135
[12] Schropp, J.: A dynamical systems approach to constrained minimization. Numer. Funct. Anal. Optim. 21(3,4), 537–551 (2000) · Zbl 1017.90106 · doi:10.1080/01630560008816971
[13] Jongen, H.Th., Stein, O.: On the complexity of equalizing inequalities. J. Glob. Optim. 27, 367–374 (2003) · Zbl 1061.90118 · doi:10.1023/A:1026051901133
[14] Jongen, H.Th., Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions: Morse Theory, Chebyshev Approximation, Transversality, Flows, Parametric Aspects. Kluwer Academic, Dordrecht (2000) · Zbl 0985.90083
[15] Rapcsák, T.: Smooth Nonlinear Optimization of \(\mathbb{R}\) n . Kluwer Academic, Dordrecht (1997) · Zbl 1009.90109
[16] Jongen, H.Th., Meer, K., Triesch, E.: Optimization Theory. Kluwer Academic, Dordrecht (2004) · Zbl 1059.90101
[17] Shikhman, V.: Ein projezierter Gradientenfluss für restringierte Optimierungsprobleme: Singularitäten, Asymptotik und Diskretisierungseigenschaften. Diploma Thesis, Department of Mathematics–C, RWTH Aachen University (2006)
[18] Perko, L.: Differential Equation and Dynamical Systems. Springer, New York (2000)
[19] LaSalle, J.P.: The Stability of Dynamical Systems. SIAM, Philadelphia (1976) · Zbl 0364.93002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.