Separating plane algorithms for convex optimization
Tóm tắt
The equivalent formulation of a convex optimization problem is the computation of a value of a conjugate function at the origin. The latter can be achieved by approximation of the epigraph of the conjugate function around the origin and gradual refinement of the approximation. This yields a generic algorithm of convex optimization which transforms into some well-known techniques when certain strategies of approximation are employed. It also suggests new algorithmic approaches with promising computational experience and provides a uniform treatment of constrained and unconstrained optimization.
Tài liệu tham khảo
V.F. Demyanov and V.N. Malozemov,Introduction to Minimax (Wiley, New York, 1974).
S.-P. Han and O. Mangasarian, Exact penalty functions in nonlinear programming,Mathematical Programming 17 (1979) 251–269.
J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms, Parts I and II (Springer, Berlin, 1993).
J.B. Kelley, The cutting plane method for solving convex programs,SIAM 8(4) (1960) 703–712.
K. Kiwiel, A survey of bundle methods for nondifferentiable optimization, in:Proceedings, XIII International Symposium on Mathematical Programming (Tokyo, 1988).
K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization,Mathematical Programming 46 (1990) 105–122.
A.V. Kuntzevich and S.V. Rzhevski, Application ofε-subgradient method for solving dual and primal mathematical programming problems.Kibernetika 5 (1985) 51–54.
C. Lemaréchal, Nondifferentiable optimization, in: E. Spedicato, L.C.W. Dixon and G.P. Szegö, eds.,Nonlinear Optimization (Birkhäuser, Boston, 1980) 84–93.
C. Lemaréchal, Numerical experiments in nonsmooth optimization, in: E. Nurminski, ed.,Progress in Nondifferentiable Optimization, Collaborative Proceedings (IIASA, Laxenburg, 1982) 61–84.
C. Lemaréchal, Nondifferentiable optimization, in: G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Handbooks in Operations Research and Management Science, Vol. I. Optimization (North-Holland, Amsterdam, 1989) 529–572.
C. Lemaréchal and R. Mifflin, Global and superlinear convergence of an algorithm for one-dimensional minimization of convex functions,Mathematical Programming 24 (1982) 241–256.
L. Luksan, Dual method for solving a special problem of quadratic programming as a subproblem at nonlinear minimax approximation,Applikace Matematiky 31(5) (1986) 379–395.
R. Mifflin, A stable method for solving certain least squares problems,Mathematical Programming 16 (1979) 141–158.
R. Mifflin, A rapidly convergent five-point algorithm for univariate minimization,Mathematical Programming 62 (1993) 299–319.
R. Mifflin and J.-J. Strodiot, A bracketing technique to ensure desirable convergence in univariate minimization,Mathematical Programming 43 (1989) 117–130.
A.S. Nemirovski and D.B. Judin, Estimation of the information complexity of mathematical programming problems,Matecon 13 (1979) 2–25, 25–45.
E.A. Nurminski, Convex optimization with constraints,Kibernetika 4 (1987) 29–31.
E.A. Nurminski,Numerical Methods of Convex Optimization (Nauka, Moscow, 1991).
E.A. Nurminski, Superlinear convergence in convex nondifferentiable optimization, in: W. Oettli and D. Pallaschke, eds.,Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 382 (Springer, Berlin, 1991) 267–280.
E.A. Nurminski, Separating plane algorithms for convex optimization with linear constraints, Technical report 443, Bayreuth University (Bayreuth, 1993).
E.A. Nurminski, Acceleration of iterative methods of projection on polyhedron,Far-Eastern Mathematical Reports 1 (1995) 51–62.
E.A. Nurminski, A quadratically convergent line-search algorithm for piece-wise smooth convex optimization,Optimization Methods and Software 6 (1995) 59–80.
M.B. Schepakin, On the method of orthogonal descent,Kibernetika 1 (1987) 58–62.
H. Schramm,Eine Kombination von Bundle- und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme, Haft 30, Bayreuther Mathematische Schriften (Bayreuth, 1989).
H. Schramm, J. Outrata and J. Zowe, Bundle trust methods: Fortran codes for nondifferentiable optimization. User’s guide, Report 269, Mathematische Institute, Universität Bayreuth (Bayreuth, 1991).
H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,SIAM Journal on Optimization 2 (1992) 121–152.
N.Z. Shor,Minimization Methods for Nondifferentiable Optimization (Springer, Berlin, 1985).
P. Wolfe, Finding the nearest point in a polytope,Mathematical Programming 11(2) (1976) 128–149.
N.G. Zhurbenko and N.Z. Shor, A minimization method using the operation of extension of space in the direction of the difference between two successive gradients,Kibernetika 7 (1971) 51–59.
J. Zowe, Nondifferentiable optimization, in: K. Schiukowski, ed.,Computational Mathematical Programming, NATO ASI Series, Vol. F15 (Springer, Heidelberg, 1985) 323–356.