Abstract
In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the numerical method are feasible points of the original optimization problem. The new method has the same computational cost as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Stein, O., Still, G.: Solving semi-infinite optimization problems with interior point techniques. SIAM J. Control Optim. 42, 769–788 (2003)
Floudas, C.A., Stein, O.: The adaptive convexification algorithm: a feasible point method for semi-infinite programming. SIAM J. Optim. 18, 1187–1208 (2007)
Stein, O.: Bi-level Strategies in Semi-infinite Programming. Kluwer Academic, Boston (2003)
Guerra Vazquez, F., Rückmann, J.-J., Stein, O., Still, G.: Generalized semi-infinite programming: a tutorial. J. Comput. Appl. Math. (2007). doi:10.1016/j.cam.2007.02.012
Stein, O.: A semi-infinite approach to design centering. In: Dempe, S., Kalashnikov, V. (eds.) Optimization with Multivalued Mappings, pp. 209–228. Springer, Berlin (2006)
Winterfeld, A.: Large-scale semi-infinite optimization applied to industrial gemstone cutting. PhD thesis, TU Kaiserslautern (2007)
Graettinger, T.J., Krogh, B.H.: The acceleration radius: a global performance measure for robotic manipulators. IEEE J. Robot. Autom. 4, 60–69 (1988)
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Heidelberg (1996)
Hogan, W.W.: Directional derivatives for extremal value functions with applications to the completely convex case. Oper. Res. 21, 188–209 (1973)
Bhattacharjee, B., Lemonidis, P., Green, W.H., Barton, P.I.: Global solution of semi-infinite programs. Math. Program. 103(2), 283–307 (2005)
Stein, O., Still, G.: On generalized semi-infinite optimization and bilevel optimization. Eur. J. Oper. Res. 142, 444–462 (2002)
Shimizu, K., Ishizuka, Y., Bard, J.F.: Nondifferentiable and Two-Level Mathematical Programming. Kluwer Academic, Boston (1997)
Ferris, M.C., Pang, J.S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669–713 (1997)
Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52(3), 333–359 (2003)
Pieper, H.: Algorithms for mathematical programs with equilibrium constraints with applications to deregulated electricity markets. PhD thesis, Stanford University (2001)
Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000)
Jongen, H.Th., Weber, G.-W.: Nonlinear optimization: Characterization of structural stability. J. Global Optim. 1, 47–64 (1991)
Fletcher, R., Leyffer, S.: Numerical experience with solving mpecs as nlps. Technical Report NA/210, University of Dundee (2002)
Chen, C., Mangasarian, O.L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Program. 71(1), 51–69 (1995)
Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85(1), 107–134 (1999)
Jiang, H., Ralph, D.: Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. SIAM J. Optim. 10(3), 779–808 (2000)
Lin, G.-H., Fukushima, M.: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133(22), 63–84 (2005)
Yang, X.Q., Huang, X.X.: Lower-order penalty methods for mathematical programs with complementarity constraints. Optim. Methods Softw. 19(6), 693–720 (2004)
Jiang, H., Ralph, D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25(1–3), 123–150 (2003)
Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Program. (2010, to appear)
Ferris, M.C., Kanzow, C.: Complementarity and related problems: A survey. In: Handbook of Applied Optimization, pp. 514–530 (2002)
Sun, D., Qi, L.: On NCP-functions. Comput. Optim. Appl. 13, 201–220 (1999)
Stein, O.: On Karush-Kuhn-Tucker points for a smoothing method in semi-infinite optimization. J. Comput. Math. 24, 719–732 (2006)
Levitin, E., Tichatschke, R.: A branch-and-bound approach for solving a class of generalized semi-infinite programming problems. J. Global Optim. 13, 299–315 (1998)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 2nd edn. Wiley, New York (1993)
Den Hertog, D., Roos, C., Terlaky, T.: On the classical logarithmic barrier function method for a class of smooth convex programming problems. J. Optim. Theory Appl. 73(1), 1–25 (1992)
Izmailov, A.F., Solodov, M.V.: Smoothing methods for convex inequalities and linear complementarity problems. Lect. Not. Econ. Math. Syst. 563, 133–145 (2006)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs—I: Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs—II: Implementation and computational results. Comput. Chem. Eng. 22, 1159–1179 (1998)
Floudas, C.A.: Deterministic Global Optimization, Theory, Methods and Applications. Kluwer Academic, Dordrecht (2000)
Stein, O.: Adaptive convexification in semi-infinite optimization. In: Pardalos, P.M., Floudas, C.A. (eds.) Encyclopedia of Optimization, Part 1, 2nd edn., pp. 13–19. Springer, Berlin (2009)
Goberna, M.A., Lopez, M.A.: Linear Semi-Infinite Optimization. Wiley, Chichester (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Stein, O., Winterfeld, A. Feasible Method for Generalized Semi-Infinite Programming. J Optim Theory Appl 146, 419–443 (2010). https://doi.org/10.1007/s10957-010-9674-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-010-9674-5