Skip to main content
SpringerLink
Log in

A homotopy interior point method for semi-infinite programming problems

  • Original Article
  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path \(\Gamma_{w^{(0)}}\subset (X^{0}\times\mathcal{Y}^{0})\times\Re_{++}\times\Re^{l}_{++}\times(0,1]\) from a given interior point \(w^{(0)} \in (X^{0}\times\mathcal{Y}^{0})\times\Re_{++}\times\Re^{l}_{++}\) to a point w *, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods. SIAM Society for Industried and Applied Mathematics, Philadelphia (2003)

  2. Chow S.N., Mallet-Paret J., Yorke J.A. (1978) Finding zeros of maps: Homotopy methods that are constructive with probability one. Math. Comput. 32, 887–899

    Article  Google Scholar 

  3. Coope I.D., Watson G.A. (1985) A projected Lagrangian algorithm for semi-infinite programming. Math. Program. 32, 337–356

    Article  Google Scholar 

  4. Conn A.R., Gould N.I.M. (1987) An exact penalty function for semi-infinite programming. Math. Program. 37, 19–40

    Google Scholar 

  5. Feng G.C., Yu B. (1995) Combined homotopy interior point method for nonlinear programming problems. Lecture Notes in Numerical and Applied Analysis 14, 9–16

    Google Scholar 

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

    Article  Google Scholar 

  7. Jongen H.TH., Stein O. (1997) On generic one-parametric semi-infinite optimization. SIAM J. Optim. 7, 1103–1137

    Article  Google Scholar 

  8. Jongen H.TH., Wetterling W., Zwier G. (1987) On sufficient conditions for local optimality in semi-infinite programming. Math. Program. 18, 165–178

    Google Scholar 

  9. Leon T., Sanmatias S., Vercher E. (2000) On the numerical treatment of linearly constrained semi-infinite optimization problems. Eur. J. Oper. Res. 121, 78–91

    Article  Google Scholar 

  10. Li D.H., Qi L., Tam J., Wu S.Y.(2004) A smoothing Newton method for semi-infinite programming. J. Global Optim. 30, 169–194

    Article  Google Scholar 

  11. Reemtsen R., Ruckmann J.J. (eds)(1998) Semi-Infinite Programming. Kluwer Academic Publishers, Boston

    Google Scholar 

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

    Article  Google Scholar 

  13. Stein O., Still G. (2003) Solving semi-infinite optimization problems with interior point techniques. SIAM J. Control Optim. 42, 769–788

    Article  Google Scholar 

  14. Stein O. (2003) Bi-level Strategies in Semi-infinite Programming. Kluwer Academic Publishers, UK

    Google Scholar 

  15. Qi L., Wu S.Y., Zhou G.L. (2003) Semismooth Newton methods for solving semi-infinite programming problems. J. Global Optim. 27, 215–232

    Article  Google Scholar 

  16. Watson G.A. (1981) Globally convergent methods for semi-infinite programming. BIT 21, 362–373

    Article  Google Scholar 

  17. Watson L.T. (2000) Theory of globally convergent probability-one homotopies for nonlinear programming. SIAM J. Optim. 11, 761–780

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computational Mathematics and Scientific/ Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, P.O. Box 2719, Beijing, 100080, P. R. China

    Guo-xin Liu

  2. School of Mathematics, Jilin University, Changchun, 130012, P. R. China

    Guo-xin Liu

Authors
  1. Guo-xin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guo-xin Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, Gx. A homotopy interior point method for semi-infinite programming problems. J Glob Optim 37, 631–646 (2007). https://doi.org/10.1007/s10898-006-9077-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-006-9077-1

Keywords

Search

Navigation