Abstract
We study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level problems where, using NCP functions, the upper and lower level Karush-Kuhn-Tucker conditions of the optimization problem are reformulated as a semismooth system of equations. Nonsmoothness is caused by a possible violation of strict complementarity slackness. We show that the standard regularity condition for convergence of the semismooth Newton method is satisfied under natural assumptions for semi-infinite programs. In fact, under the Reduction Ansatz in the lower level and strong stability in the reduced upper level problem this regularity condition is satisfied. In particular, we do not have to assume strict complementary slackness in the upper level. Numerical examples from, among others, design centering and robust optimization illustrate the performance of the method.
Similar content being viewed by others
References
Ben-Tal A. and Nemirovski A. (1999). Robust solutions of uncertain linear programs. Opera. Res. Lett. 25: 1–13
Clarke F.H. (1983). Optimization and Nonsmooth Analysis. Wiley, New York
Floudas, C. A., Stein, O.: The adaptive convexification algorithm: a feasible point method for semi-infinite programming. SIAM J Optim (to appear)
Goberna M.A. and López M.A. (1998). Linear Semi-infinite Optimization. Wiley, Chichester
Günzel, H., Jongen, H. Th., Stein, O.: Generalized semi-infinite programming: on generic local minimizers, AOR-Preprint 2/2007, Chair for Applications of OR, University of Karlsruhe (2007)
Guerra Vazquez, F., Rückmann, J.-J., Stein, O., Still, G.: Generalized semi-infinite programming: a tutorial. J. Comput. Appl. Math. (to appear)
Hettich R. and Kortanek K. (1993). Semi-infinite programming: theory, methods and applications. SIAM Rev. 35: 380–429
Hettich R. and Still G. (1995). Second order optimality conditions for generalized semi-infinite programming problems. Optimization. 34: 195–211
John, F.: Extremum problems with inequalities as subsidiary conditions, In: studies and essays, R. Courant Anniversary Volume, Interscience, New York 187–204 (1948)
Jongen H.Th., Jonker P. and Twilt F. (1986). Critical sets in parametric optimization. Math. Programming 34: 333–353
Jongen H.Th., Möbert T., Rückmann J.-J. and Tammer T. (1987). On inertia and Schur complement in optimization. Lin. Alg. Appl. 95: 97–109
Jongen H.Th., Wetterling W. and Zwier G. (1987). On sufficient conditions for local optimality in semi-infinite programming. Optimization 18: 165–178
Klatte D. and Kummer B. (2002). Nonsmooth Equations in Optimization. Kluwer, Dordrecht
Mifflin R. (1997). Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15: 959–972
Ouellette D.V. (1981). Schur complements and statistics. Lin. Alg. Appl. 36: 187–295
Qi L. and Jiang H. (1997). Semismooth KKT equations and convergence analysis of Newton and quasi-Newton methods for solving these equations. Math. Op. Res. 22: 301–325
Qi L. and Sun J. (1993). A nonsmooth version of Newton’s Method. Math. Programming 58: 353–367
Qi L., Wu S.-Y. and Zhou G. (2003). Semismooth Newton Methods for Solving Semi-infinite Problems. J. Global Optim. 27: 215–232
Reemtsen R. and Görner S. (1998). Numerical methods for semi-infinite programming: a survey. In: Reemtsen, R. and Rückmann, J.-J. (eds) Semi-Infinite Programming, pp 195–275. Kluwer, Boston
Robinson S.M. (1982). Generalized Equations and their solutions, Part II, Applications to nonlinear programming. Math. Programming Stud. 19: 200–221
Stein, O.: On parametric semi-infinite optimization. PhD Thesis, University of Trier, Department of Mathematics (1997)
Stein, O.: Bi-level strategies in semi-infinite programming. Kluwer (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Stein, O., Tezel, A. The semismooth approach for semi-infinite programming under the Reduction Ansatz. J Glob Optim 41, 245–266 (2008). https://doi.org/10.1007/s10898-007-9228-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-007-9228-z
Keywords
- Generalized semi-infinite optimization
- Semismooth Newton method
- NCP function
- CD-regularity
- Reduction Ansatz