The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets | Mathematical Programming Skip to main content
Springer Nature Link
Log in

The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of Floudas and Stein (SIAM J Optim 18:1187–1208, 2007), convex relaxations of the lower level problem are adaptively constructed and then reformulated as mathematical programs with complementarity constraints and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex relaxations and needed parameters are constructed with ideas of the αBB method of global optimization and interval methods. It is shown that after finitely many steps an \({\epsilon}\)-stationary point of the original semi-infinite problem is reached. A numerical example illustrates the performance of the proposed method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    Article  Google Scholar 

  2. 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)

    Article  Google Scholar 

  3. Akrotirianakis I.G., Floudas C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30, 367–390 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bhattacharjee B., Green W.H., Barton P.I.: Interval methods for semi-infinite programs. Comput. Optim. Appl. 30, 63–93 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bhattacharjee B., Lemonidis P., Green W.H., Barton P.I.: Global solution of semi-infinite programs. Math. Program 103, 283–307 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Demiguel V., Friedlander M.P., Nogales F.J., Scholtes S.: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16, 587–609 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Floudas C.A.: Deterministic Global Optimization, Theory, Methods and Applications. Kluwer, Dordrecht (2000)

    Google Scholar 

  8. Floudas C.A., Gounaris C.E.: Tight convex underestimators for C 2-continuous functions: I. Univariate functions. J. Glob. Optim. 42, 51–67 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  9. Floudas C.A., Gounaris C.E.: Tight convex underestimators for C 2-continuous problems: II. Multivariate functions. J. Glob. Optim. 42, 69–89 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Floudas C., Stein O.: The adaptive convexification algorithm: a feasible point method for semi-infinite programming. SIAM J. Optim. 18, 1187–1208 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Graettinger T.J., Krogh B.H.: The acceleration radius: a global performance measure for robotic manipulators. IEEE J. Robot. Autom. 4, 60–69 (1988)

    Article  Google Scholar 

  12. Gritzmann P., Klee V.: On the complexity of some basic problems in computational convexity. I. Containment problems. Discr. Math. 136, 129–174 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hansen E.: Global Optimization using Interval Analysis. Marcel Dekker, New York (1992)

    MATH  Google Scholar 

  14. Hettich R., Kortanek K.: Semi-infinite programming: theory, methods and applications. SIAM Rev. 35, 380–429 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hettich R., Still G.: Semi-infinite programming models in robotics. In: Guddat, J., Jongen, H.Th., Kummer, B., Nožička, F. (eds.) Parametric Optimization and Related Topics II., pp. 112–118. Akademie Verlag, Berlin (1991)

    Google Scholar 

  16. Hettich R., Zencke P.: Numerische methoden der approximation und semi-infiniten optimierung. Teubner, Stuttgart (1982)

    MATH  Google Scholar 

  17. John F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays, R. Courant Anniversary Volume, pp. 187–204. Interscience, New York (1948)

    Google Scholar 

  18. Lemonidis, P.: Global optimization algorithms for semi-infinite and generalized semi-infinite programs. PhD Thesis, Massachusetts Institute of Technology (2007)

  19. Mitsos A., Lemonidis P., Barton P.I.: Global solution of bilevel programs with a nonconvex inner program. J. Glob. Optim. 42, 475–513 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Mitsos A., Lemonidis P., Lee C.K., Barton P.I.: Relaxation-based bounds for semi-infinite programs. SIAM J. Optim. 19, 77–113 (2007)

    Article  MathSciNet  Google Scholar 

  21. Neumaier A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  22. Nguyen V.H., Strodiot J.J.: Computing a global optimal solution to a design centering problem. Math. Program 53, 111–123 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Pang J.-S.: Error bounds in mathematical programming. Math. Progam 79, 299–332 (1997)

    MATH  Google Scholar 

  24. Polak E.: On the mathematical foundation of nondifferentiable optimization in engineering design. SIAM Rev. 29, 21–89 (1987)

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  26. Reemtsen, R., Görner, S.: In: Reemtsen, R., Rückmann, J. (eds.) Numerical Methods for Semi-Infinite Programming: A survey in Semi-Infinite Programming pp. 195–275. Kluwer, Boston (1998)

  27. Rump, S.M.: INTLAB—INTerval LABoratory, Institute for Reliable Computing, Hamburg University of Technology, Hamburg (2008). http://www.ti3.tu-harburg.de/rump/intlab

  28. Scholtes S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  29. Stein O.: Bi-level strategies in semi-infinite programming. Kluwer, Boston (2003)

    MATH  Google Scholar 

  30. Stein O.: Lifting mathematical programs with complementarity constraints. Math. Program. 131, 71–94 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  31. Stein O., Still G.: On generalized semi-infinite optimization and bilevel optimization. Eur. J. Oper. Res. 142, 444–462 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  32. Wächter A., Biegler L.T.: Line Search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16, 1–31 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  33. Wächter A., Biegler L.T.: Line search filter methods for nonlinear programming: local convergence. SIAM J. Optim. 16, 32–48 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  34. Winterfeld, A.: Maximizing volumes of lapidaries by use of hierarchical GSIP-models. Diploma thesis, Technische Universität Kaiserslautern and Fraunhofer Institut für Techno- und Wirtschaftsmathematik (2004)

Download references

Author information

Authors and Affiliations

  1. Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany

    Oliver Stein & Paul Steuermann

Authors
  1. Oliver Stein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul Steuermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Oliver Stein.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stein, O., Steuermann, P. The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets. Math. Program. 136, 183–207 (2012). https://doi.org/10.1007/s10107-012-0556-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0556-5

Keywords

Mathematics Subject Classification

Search

Navigation