Exact penalty functions and stability in locally Lipschitz programming. (English) Zbl 0587.90083

We extend the theory of exact penalty functions for nonlinear programs whose objective functions and equality and inequality constraints are locally Lipschitz; arbitrary simple constraints are also allowed. Assuming a weak stability condition, we show that for all sufficiently large penalty parameter values an isolated minimum of the nonlinear program is also an isolated local minimum of the exact penalty function. A tight lower bound on the parameter value is provided when certain first order sufficiency conditions are satisfied. We apply these results to unify and extend some results for convex programming. Since several effective algorithms for solving nonlinear programs with differentiable functions rely on exact penalty functions, our results provide a framework for extending these algorithms to problems with locally Lipschitz functions.


90C30 Nonlinear programming
90C31 Sensitivity, stability, parametric optimization
49M37 Numerical methods based on nonlinear programming
90C25 Convex programming
Full Text: DOI


[1] M.S. Bazaraa and J.J. Goode, ”Sufficient conditions for a globally exact penalty function without convexity”,Mathematical Programming Study 19 (1982) 1–15. · Zbl 0497.90058
[2] D.P. Bertsekas, ”Necessary and sufficient conditions for a penalty function to be exact”,Mathematical Programming 9 (1975) 87–99. · Zbl 0325.90055
[3] D.P. Bertsekas, ”Variable metric methods for constrained optimization using differentiable exact penalty functions”, Proceedings of the 18th Annual Allerton Conference on Communication, Control, and Computing (1980) 584–593.
[4] R.W. Chaney, ”A general sufficiency theorem for nonsmooth nonlinear programming”,Transactions of the American Mathematical Society 276 (1983) 235–245. · Zbl 0504.49013
[5] C. Charalambous, ”A lower bound for the controlling parameters of the exact penalty functions”,Mathematical Programming 15 (1978) 278–290. · Zbl 0395.90071
[6] F.H. Clarke, ”A new approach to lagrange multipliers”,Mathematics of Operations Research 1 (1976) 165–174. · Zbl 0404.90100
[7] F.H. Clarke,Optimization and nonsmooth analysis (Wiley, New York, 1983). · Zbl 0582.49001
[8] A.R. Conn and T. Pietrzykowski, ”A penalty function method converging directly to a constrained optimum”,SIAM Journal on Numerical Analysis 14 (1977) 348–375. · Zbl 0361.90076
[9] J.P. Evans, F.J. Gould and J.W. Tolle, ”Exact penalty functions in nonlinear programming,”Mathematical Programming 4 (1973) 72–97. · Zbl 0267.90079
[10] R. Fletcher, ”Numerical experiments with an exactL 1 penalty function method”, in: O.L. Mangasarian, S.M. Robinson, eds.,Nonlinear Programming 4 (Academic Press, New York, 1981) pp. 99–129.
[11] J. Gauvin and F. Dubeau, ”Differential properties of the marginal function in mathematical programming”,Mathematical Programming Study 19 (1982) 101–119. · Zbl 0502.90072
[12] A.M. Geoffrion, ”Duality in nonlinear programming: A simplified applications-oriented development”,SIAM Review 13 (1971) 1–37. · Zbl 0232.90049
[13] S.-P. Han, ”A globally convergent method for nonlinear programming,”Journal of Optimization Theory and Applications 22 (1977) 297–309. · Zbl 0336.90046
[14] S.-P. Han and O.L. Mangasarian ”Exact penalty functions in nonlinear programming”,Mathematical Programming 17 (1979) 251–269. · Zbl 0424.90057
[15] S.-P. Han and O.L. Mangasarian, ”A dual differentiable exact penalty function”,Mathematical Programming 25 (1983) 293–306. · Zbl 0495.90070
[16] J.B. Hiriart-Urruty, ”On optimality conditions in nondifferentiable programming,”Mathematical Programming 14 (1978) 73–86. · Zbl 0373.90071
[17] T. Pietrzykowski, ”An exact potential method for constrained maxima”,SIAM Journal on Numerical Analysis 6 (1969) 299–304. · Zbl 0181.46501
[18] E. Polak, D.Q. Mayne and Y. Wardi, ”On the extension of constrained optimization algorithms from differentiable to nondifferentiable problems”,SIAM Journal on Control and Optimization 21 (1983) 179–203. · Zbl 0503.49021
[19] M.J.D. Powell, ”A fast algorithm for nonlinearly constrained optimization calculations”, in: G.A. Watson, ed.,Numerical Analysis: Dundee 1977, Lecture Notes in Mathematics No. 630 (Springer-Verlag, New York 1978) pp. 144–157.
[20] B.N. Pshenichnyi, ”Convex programming in a normalized space”,Kibernetika 1 (1965) 46–54.
[21] R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[22] R.T. Rockafellar, ”Lagrange multipliers and subderivatives of optimal value functions in nonlinear programming”,Mathematical Programming Study 17 (1982) 28–66. · Zbl 0478.90060
[23] E. Rosenberg, ”Globally convergent algorithms for convex programming”,Mathematics of Operations Research 6 (1981) 437–444. · Zbl 0507.90072
[24] W.I. Zangwill, ”Nonlinear programming via penalty functions”,Management Science 13 (1967) 344–358. · Zbl 0171.18202
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.