Abstract
The purpose of this paper is twofold. First we consider a class of nondifferentiable penalty functions for constrained Lipschitz programs and then we show how these penalty functions can be employed to solve a constrained Lipschitz program. The penalty functions considered incorporate a barrier term which makes their value go to infinity on the boundary of a perturbation of the feasible set. Exploiting this fact it is possible to prove, under mild compactness and regularity assumptions, a complete correspondence between the unconstrained minimization of the penalty functions and the solution of the constrained program, thus showing that the penalty functions are exact according to the definition introduced in [17]. Motivated by these results, we propose some algorithm models and study their convergence properties. We show that, even when the assumptions used to establish the exactness of the penalty functions are not satisfied, every limit point of the sequence produced by a basic algorithm model is an extended stationary point according to the definition given in [8]. Then, based on this analysis and on the one previously carried out on the penalty functions, we study the consequence on the convergence properties of increasingly demanding assumptions. In particular we show that under the same assumptions used to establish the exactness properties of the penalty functions, it is possible to guarantee that a limit point at least exists, and that any such limit point is a KKT point for the constrained problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. S. Bazaraa and J. J. Goode. Sufficient conditions for a globally exact penalty function without convexity. Mathematical Programming Study, 19:1–15, 1982.
D. P. Bertsekas. Necessary and sufficient conditions for a penalty method to be exact. Mathematical Programming, 9:87–99, 1975.
D. P. Bertsekas. Constrained Optimization and Lagrange Multipliers Methods. Academic Press, New York, 1982.
J. M. Borwein. Stability and regular points of inequality systems. Journal of Optimization Theory and Applications, 48:9–52, 1986.
J. V. Burke. A sequential quadratic programming method for potentially infeasible mathematical programs. Journal of Mathematical Analysis and Applications, 139:319–351, 1989.
J. V. Burke, Calmness and exact penalization. SIAM Journal on Control and Optimization, 29:493–497, 1991.
J. V. Burke. An exact penalization viewpoint of constrained optimization. SIAM Journal on Control and Optimization, 29:968–998, 1991.
J. V. Burke. A robust trust region method for constrained nonlinear programming problems. SIAM Journal on Optimization, 2:325–347, 1992.
J. V. Burke and S.-P. Han. A robust sequential quadratic programming method. Mathematical Programming, 43:277–303, 1989.
C. Charalambous. A lower bound for the controlling parameters of the exact penalty functions. Mathematical Programming, 15:278–290, 1978.
C. Charalambous. On conditions for optimality of a class of nondifferentiable functions. Journal of Optimization Theory and Applications, 43:135–142, 1982.
F. H. Clarke. Optimization and Nonsmooth Analysis. Wiley, New York, 1983.
G. Di Pillo and F. Facchinei. Exact penalty functions for nondifferential programming problems. In F. H. Clarke, V. F. Demyanov, and F. Giannessi, editors, Nonsmooth Optimization and Related Topics, pp. 89–107, Plenum, New York, 1989.
G. Di Pillo and F. Facchinei. Regularity conditions and exact penalty functions in Lipschitz programming problems. In F. Giannessi, editor, Nonsmooth Optimization Methods and Applications, pp. 107–120. Gordon and Breach, New York, 1992.
G. Di Pillo and L. Grippo. An exact penalty method with global convergence properties for nonlinear programming problems. Mathematical Programming, 36:1–18, 1986.
G. Di Pillo and L. Grippo. On the exactness of a class of nondifferentiable penalty functions. Journal of Optimization Theory and Applications, 57:399–410, 1988.
G. Di Pillo and L. Grippo. Exact penalty functions in constrained optimization. SIAM Journal on Control and Optimization, 27:1333–1360, 1989.
G. Di Pillo, L. Grippo, and S. Lucidi. A smooth method for the minimax problem. Mathematical Programming, 60:187–214, 1993.
J. P. Evans, F. J. Gould, and J. W. Tolle. Exact penalty functions in nonlinear programming. Mathematical Programming, 4:72–97, 1973.
F. Facchinei. Exact penalty functions and Lagrange multipliers. Optimization, 22:579–606, 1991.
F. Facchinei. Refinements of necessary conditions for optimality in nonlinear programming. Journal of Optimization Theory and Applications, 73:65–74, 1992.
A. V. Fiacco and G. P. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York, 1968.
R. Fletcher. Practical Methods of Optimization. Wiley, New York, 1987.
S. P. Han. A globally convergent method for nonlinear programming. Journal of Optimization Theory and Applications, 22:297–309, 1977.
S. P. Han and O. L. Mangasarian. Exact penalty functions in nonlinear programming. Mathematical Programming, 17:251–269, 1979.
J.-B. Hiriart-Urruty. Refinements of necessary optimality conditions in nondifferentiable programming, I. Applied Mathematics and Optimization, 5:63–82, 1979.
J.-B. Hiriart-Urruty. Refinements of necessary optimality conditions in nondifferentiable programming, II. Mathematical Programming Study, 19:120–139, 1982.
S. Howe. New conditions for the exactness of a simple penalty function. SIAM Journal on Control, 11:378–381, 1973.
A. D. Ioffe. Necessary and sufficient conditions for a local minimum. 1: A reduction theorem and first-order conditions. SIAM Journal on Control and Optimization, 17:245–250, 1979.
A. D. Ioffe. Necessary and sufficient conditions for a local minimum. 2: Conditions of Levitin-Miljutin-Osmolovskii type. SIAM Journal on Control and Optimization, 17:251–265, 1979.
A. D. Ioffe. Necessary and sufficient conditions for a local minimum. 3: Second-order conditions and augmented duality. SIAM Journal on Control and Optimization, 17:266–288, 1979.
V. H. Nguyen, J.-J. Strodiot, and R. Mifflin. On conditions to have bounded multipliers in locally Lipschitz programming. Mathematical Programming, 18:100–106, 1980.
T. Pietrzykowski. An exact potential method for constrained maxima. SIAM Journal on Numerical Analysis, 6:299–304, 1969.
T. Pietrzykowski. The potential method for conditional maxima in the locally compact metric spaces. Numerische Mathematik, 14:325–329, 1970.
E. Polak, D. Q. Mayne, and Y. Ward. On the extension of constrained optimization algorithms from differentiable to nondifferentiable problems. SIAM Journal on Control and Optimization, 21:179–203, 1983.
R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
E. Rosenberg. Exact penalty functions and stability in locally lipschitz programming. Mathematical Programming, 30:340–356, 1984.
J. Stoer. Principles of sequential quadratic programming methods for solving nonlinear programs. In K. Schittkowski, editor, Computational Mathematical Programming, NATO ASI Series, Vol. F15. Springer-Verlag, Berlin, 1985.
D. E. Ward. Exact penalties and sufficient conditions for optimality in nonsmooth optimization. Journal of Optimization Theory and Applications, 57:485–499, 1988.
D. E. Ward and J. M. Borwein. Nonsmooth calculus in finite dimensions. SIAM Journal on Control and Optimization, 25:1312–1340, 1987.
W. I. Zangwill. Non-linear programming via penalty functions. Management Science, 13:344–358, 1967.
Author information
Authors and Affiliations
Additional information
Communicated by F. H. Clarke
This research has been partially supported by the National Research Program on “Metodi di Ottimizzazione per le Decisioni”, Ministero dell' Università e della Ricerca Scientifica e Tecnologica.
Rights and permissions
About this article
Cite this article
Di Pillo, G., Facchinei, F. Exact barrier function methods for Lipschitz programs. Appl Math Optim 32, 1–31 (1995). https://doi.org/10.1007/BF01189901
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01189901
Key words
- Constrained optimization
- Nonsmooth optimization
- Penalty methods
- Barrier functions
- Extended stationary points