Augmented Lagrangian Duality and Nondifferentiable Optimization Methods in Nonconvex Programming

Journal of Global Optimization - 2002
Rafail N. Gasimov1
1Department of Industrial Engineering, Osmangazi University, Bademlik, Eskişehir, Turkey

Tóm tắt

In this paper we present augmented Lagrangians for nonconvex minimization problems with equality constraints. We construct a dual problem with respect to the presented here Lagrangian, give the saddle point optimality conditions and obtain strong duality results. We use these results and modify the subgradient and cutting plane methods for solving the dual problem constructed. Algorithms proposed in this paper have some advantages. We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies. The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the ‘penalty like parameter’ to infinity in the new methods. In both methods the value of the dual function strongly increases at each iteration. In the contrast, by using the primal-dual gap, the proposed algorithms possess a natural stopping criteria. The convergence theorem for the subgradient method is also presented.

Từ khóa


Tài liệu tham khảo

Andramanov, M.Yu., Rubinov, A.M. and Glover, B.M. (1997), Cutting Angle Method for Minimizing increasing Convex-Along-Rays Functions, Research Report 97/7, SITMS, University of Ballarat, Australia.

Andramanov, M.Yu., Rubinov, A.M. and Glover, B.M. (1999), Cutting Angle Methods in Global Optimization, Applied Mathematics Letters 12, 95–100.

Bazaraa, M.S., Sherali, H.D. and Shetty, C.M. (1993), Nonlinear Programming. Theory and Algorithms, John Wiley & Sons, Inc., New York.

Bertsekas, D.P. (1995), Nonlinear Programming, Athena Scientific, Belmont, MA.

Buys, J.D. (1972), Dual Algorithms for Constrained Optimization Problems, Doctoral Dissertation, University of Leiden, Leiden, the Netherlands.

Cheney, E.W. and Goldstein, A.A. (1959), Newton's Method for Convex Programming and Tchebycheff Approximation, Numer. Math. 1, 253–268.

Courant, R. (1943), Variational Methods for the Solution of Problems of Equilibrium and Vibrations, Bull. Amer. Math. Soc. 49, 1–23.

Demyanov, V.F. (1968), Algorithm for some Minimax Problems, J. Computer and System Sciences 2, 342–380.

Ekeland, I. and Temam, R. (1976) Convex Analysis and Variational Problems, Elsevier-North Holland, Amsterdam.

Fletcher, R. (1970), A Class of Methods for Nonlinear Programming with Termination and Convergence Properties, in Abadie, J. (ed.), Integer and Nonlinear Programming, North Holland, Amsterdam, pp. 157–173.

Floudas, C.A., et al. (1999), Handbook of Test Problems in Local and Global Optimization, Kluwer Academic Publishers, Dordrecht.

Goffin, J.L. (1977), On Convergent Rates of Subgradient Optimization Methods, Math. Programming 13, 329–347.

Haarhoff, P.C. and Buys, J.D. (1970), A New Method for the Optimization of a Nonlinear Function Subject to Nonlinear Constraints, Comput. J. 13, 178–184.

Hestenes, M.R. (1969), Multiplier and Gradient Methods, J. Optim. Theory Appl. 4, 303–320.

Himmelblau, D.M. (1972) Applied Nonlinear Optimization, McGraw-Hill Book Company, New York.

Kelley, J.E. (1960), The Cutting-Plane Method for Solving Convex programs, J. Soc. Indust. Appl. Math. 8, 703–712.

Khenkin, E.I. (1976), A Search Algorithm for General Problem of Mathematical Programming, USSR Journal of Computational Mathematics and Mathematical Physics 16, 61–71, (in Russian).

Kort, B.W. and Bertsekas, D.P. (1972), A New Penalty Function Method for Constrained Minimization, Proc. IEEE Decision and Control Conference, New Orleans, LA, pp. 162–166.

Krein, M.G. and Rutman, M.A. (1962), Linear Operators Leaving Invariant a Cone in a Banach Space, Trans. Amer. Math. Soc., Providence, RI, 10, 199–325

Pallaschke, D. and Rolewicz, S. (1997), Foundations of Mathematical Optimization (Convex Analysis without Linearity), Kluwer Academic Publishers, Dordrecht.

Pietrzykowski, T. (1969), An Exact Potential Method for Constrained Maxima, SIAM J. Numer. Anal. 6, 299–304.

Polak, E. (1997), Optimization. Algorithms and Consistent Approximations, Springer, Berlin.

Poljak, B.T. (1969a), Minimization of Unsmooth Functionals, Z. Vychislitelnoy Matematiki i Matematicheskoy Fiziki 9, 14–29.

Poljak, B.T. (1969b), The Conjugate Gradient Method in Extremal Problems, Z. Vychislitelnoy Matematiki i Matematicheskoy Fiziki 9, 94–112.

Poljak, B.T. (1970), Iterative Methods Using Lagrange Multipliers for Solving Extremal Problems with Constraints of the Equation Type, Z. Vyc¸islitelnoy Mat. i Mat. Fiziki 10, 1098–1106.

Powell, M.J.D. (1969), A Method for Nonlinear Constraints in Minimization Problems, in Fletcher, R. (ed.), Optimization, Academic Press, New York, pp. 283–298.

Rockafellar, R.T. (1970), Convex Analysis, Princeton University Press, Princeton, NJ.

Rockafellar, R.T. (1993), Lagrange Multipliers and Optimality, SIAM Review 35, 183–238.

Rockafellar, R.T. and Wets, R.J.-B. (1998), Variational Analysis, Springer, Berlin.

Rubinov, A.M. (2000), Abstract Convexity and Global Optimization, Kluwer Academic Publishers, Dordrecht.

Shor, N.Z. (1985), Minimization Methods for Nondifferentiable Functions, Springer, Berlin.

Shor, N.Z. (1995), Dual Estimates in Multiextremal Problems, Journal of Global Optimzation 7, 75–91.

Singer, I. (1997), Abstract Convex Analysis, John Wiley and Sons, Inc., New York.

Wierzbicki, A.P. (1971), A Penalty Function Shifting Method in Constrained Static Optimization and its Convergence Properties, Arch. Automat. i Telemechaniki 16, 395–415.

Zangwill, W.I. (1967), Nonlinear Programming via Penalty Functions, Management Sci. 13, 344–358.

Thông tin
Thông tin xuất bản

Journal of Global Optimization

Thông tin tác giả