Skip to main content
SpringerLink
Log in

Relaxed cutting plane method with convexification for solving nonlinear semi-infinite programming problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we present an algorithm to solve nonlinear semi-infinite programming (NSIP) problems. To deal with the nonlinear constraint, Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007) suggest an adaptive convexification relaxation to approximate the nonlinear constraint function. The αBB method, used widely in global optimization, is applied to construct the convexification relaxation. We then combine the idea of the cutting plane method with the convexification relaxation to propose a new algorithm to solve NSIP problems. With some given tolerances, our algorithm terminates in a finite number of iterations and obtains an approximate stationary point of the NSIP problems. In addition, some NSIP application examples are implemented by the method proposed in this paper, such as the proportional-integral-derivative controller design problem and the nonlinear finite impulse response filter design problem. Based on our numerical experience, we demonstrate that our algorithm enhances the computational speed for solving NSIP problems.

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

Fig. 1
Fig. 2

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. Bianco, C.G.L., Piazzi, A.: A hybrid algorithm for infinitely constrained optimization. Int. J. Syst. Sci. 32, 91–102 (2001)

    Article  MATH  Google Scholar 

  4. Betrò, B.: An accelerated central cutting plane algorithm for linear semi-infinite programming. Math. Program. 101, 479–495 (2004)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  8. Floudas, C.A., 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 

  9. Gonzaga, G., Polak, E., Trahan, R.: An improved algorithm for optimization problems with functional inequality constraints. IEEE Trans. Autom. Control AC25, 49–54 (1980)

    Article  MathSciNet  Google Scholar 

  10. Görner, S., Potchinkov, A., Reemtsen, R.: The direct solution of nonconvex nonlinear FIR filter design problems by a SIP method. Optim. Eng. 1, 123–154 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gramlich, G., Hettich, R., Sachs, E.W.: Local convergence of SQP methods in semi-infinite programming. SIAM J. Optim. 5, 641–658 (1995)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Jennings, L.S., Teo, K.L.: A computational algorithm for functional inequality constrained optimization problems. Automatica 26, 371–375 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kortanek, K., No, H.: A central cutting plane algorithm for convex semi-infinite programming problems. SIAM J. Optim. 3, 901–918 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ni, Q., Ling, C., Qi, L., Teo, K.L.: A truncated projected Newton-type algorithm for large-scale semi-infinite programming. SIAM J. Optim. 16, 1137–1154 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Potchinkov, A., Reemtsen, R.: FIR filter design in the complex domain by a semi-infinite programming technique. I. The method. Arch. Elektron. Übertrag.tech. 48, 35–144 (1994). II. Examples: 200–209

    Google Scholar 

  17. Potchinkov, A., Reemtsen, R.: The simultaneous approximation of magnitude and phase by FIR digital filters. Part 1. A new approach. Int. J. Circuit Theory Appl. 25, 167–177 (1997). Part 2. Methods and examples: 179–197

    Article  MATH  Google Scholar 

  18. Price, C.J., Coope, C.J.: Numerical experiments in semi-infinite programming. Comput. Optim. Appl. 6, 169–189 (1996)

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  20. Qi, L., Ling, C., Tong, X.J., Zhou, G.: A smoothing projected Newton-type algorithm for semi-infinite programming. Comput. Optim. Appl. 42, 1–30 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Reemsten, R., Görner, S.: Numerical methods for semi-infinite programming: a survey. In: Reemsten, R., Rückmann, J. (eds.) Semi-infinite Programming, pp. 195–275. Kluwer Academic, Boston (1998)

    Google Scholar 

  22. Shapiro, A.: Semi-infinite programming, duality, discretization and optimality condition. Optimization 58, 133–161 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  23. Still, G.: Discretization in semi-infinite programming: the rate of convergence. Math. Program. 91, 53–69 (2001)

    MathSciNet  MATH  Google Scholar 

  24. Tanaka, Y., Fukushima, M., Ibaraki, T.: A global convergent SQP method for semi-infinite nonlinear optimization. J. Comput. Appl. Math. 23, 141–153 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  25. Teo, K.L., Yang, X.Q., Jennings, L.S.: Computational discretization algorithms for functional inequality constrained optimization. Ann. Oper. Res. 28, 215–234 (2000)

    Article  MathSciNet  Google Scholar 

  26. Wu, S.Y., Li, D.H., Qi, L., Zhou, G.: An iterative method for solving KKT system of the semi-infinite programming. Optim. Methods Softw. 20, 629–643 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Zhang, L.P., Hayashi, S., Wu, S.Y.: On the finite termination of an exchange method for convex and nonlinear semi-infinite programming problems. Technique report (2010)

  28. Zhang, L.P., Wu, S.Y., López, M.A.: A new exchange method for convex semi-infinite programming. SIAM J. Optim. 20, 2959–2977 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the associate editor and the two anonymous referees for their helpful comments and suggestions that have enabled us to improve the preliminary version of this paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

    Ting-Jang Shiu & Soon-Yi Wu

  2. Taiwan and National Center for Theoretical Sciences, Tainan, Taiwan

    Soon-Yi Wu

Authors
  1. Ting-Jang Shiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Soon-Yi Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Soon-Yi Wu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shiu, TJ., Wu, SY. Relaxed cutting plane method with convexification for solving nonlinear semi-infinite programming problems. Comput Optim Appl 53, 91–113 (2012). https://doi.org/10.1007/s10589-011-9452-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-011-9452-9

Keywords

Search

Navigation