Skip to main content
SpringerLink
Log in

On Solving Large-Scale Finite Minimax Problems Using Exponential Smoothing

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper focuses on finite minimax problems with many functions, and their solution by means of exponential smoothing. We conduct run-time complexity and rate of convergence analysis of smoothing algorithms and compare them with those of SQP algorithms. We find that smoothing algorithms may have only sublinear rate of convergence, but as shown by our complexity results, their slow rate of convergence may be compensated by small computational work per iteration. We present two smoothing algorithms with active-set strategies and novel precision-parameter adjustment schemes. Numerical results indicate that the algorithms are competitive with other algorithms from the literature, and especially so when a large number of functions are nearly active at stationary points.

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. Polak, E.: On the mathematical foundations of nondifferentiable optimization in engineering design. SIAM Rev. 29, 21–89 (1987)

    Article  MathSciNet  Google Scholar 

  2. Polak, E., Salcudean, S., Mayne, D.Q.: Adaptive control of ARMA plants using worst case design by semi-infinite optimization. IEEE Trans. Autom. Control 32, 388–397 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cai, X., Teo, K., Yang, X., Zhou, X.: Portfolio optimization under a minimax rule. Manag. Sci. 46(7), 957–972 (2000)

    Article  Google Scholar 

  4. Demyanov, V.F., Malozemov, V.N.: Introduction to Minimax. Wiley, New York (1974)

    Google Scholar 

  5. Panier, E.R., Tits, A.L.: A globally convergent algorithm with adaptively refined discretization for semi-infinite optimization problems arising in engineering design. IEEE Trans. Autom. Control 34(8), 903–908 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  6. Zhou, J.L., Tits, A.L.: An SQP algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions. SIAM J. Optim. 6(2), 461–487 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Polak, E., Royset, J.O., Womersley, R.S.: Algorithms with adaptive smoothing for finite minimax problems. J. Optim. Theory Appl. 119(3), 459–484 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Obasanjo, E., Tzallas-Regas, G., Rustem, B.: An interior-point algorithm for nonlinear minimax problems. J. Optim. Theory Appl. 144, 291–318 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Zhu, Z., Cai, X., Jian, J.: An improved SQP algorithm for solving minimax problems. Appl. Math. Lett. 22(4), 464–469 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Sturm, J.F., Zhang, S.: A dual and interior-point approach to solve convex min-max problems. In: Du, D.Z., Pardalos, P.M. (eds.) Minimax and Applications, pp. 69–78. Kluwer Academic, Dordrecht (1995)

    Google Scholar 

  11. Luksan, L., Matonoha, C., Vlcek, J.: Primal interior-point method for large sparse minimax optimization. Technical Report 941, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, Czech Republic (2005)

  12. Ye, F., Liu, H., Zhou, S., Liu, S.: A smoothing trust-region Newton-CG method for minimax problem. Appl. Math. Comput. 199(2), 581–589 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  13. Polak, E., Womersley, R.S., Yin, H.X.: An algorithm based on active sets and smoothing for discretized semi-infinite minimax problems. J. Optim. Theory Appl. 138, 311–328 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Li, X.: An entropy-based aggregate method for minimax optimization. Eng. Optim. 18, 277–285 (1992)

    Article  Google Scholar 

  15. Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20, 267–279 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kort, B.W., Bertsekas, D.P.: A new penalty function algorithm for constrained minimization. In: Proceedings 1972 IEEE Conf. Decision and Control, vol. 82, pp. 343–362 (1972)

    Google Scholar 

  17. Nemirovski, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)

    Google Scholar 

  18. Drezner, Z.: On the complexity of the exchange algorithm for minimax optimization problems. Math. Program. 38(2), 219–222 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  19. Wiest, E.J., Polak, E.: On the rate of convergence of two minimax algorithms. J. Optim. Theory Appl. 71(1), 1–30 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  20. Nesterov, Yu.: Complexity estimates of some cutting plane methods based on the analytic barrier. Math. Program. 69(1), 149–176 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ariyawansa, K.A., Jiang, P.L.: On complexity of the translational-cut algorithm for convex minimax problems. J. Optim. Theory Appl. 107(2), 223–243 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  22. Nesterov, Yu., Vial, J.Ph.: Augmented self-concordant barriers and nonlinear optimization problems with finite complexity. Math. Program. 99(1), 149–174 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  23. Nesterov, Yu.: Introductory Lectures on Convex Optimization: A Basic Course (Applied Optimization). Kluwer Academic, Dordrecht (2004)

    MATH  Google Scholar 

  24. Polak, E.: Optimization. Algorithms and Consistent Approximations. Springer, New York (1997)

    MATH  Google Scholar 

  25. Urruty, H., Baptiste, J.: Convex Analysis and Minimization Algorithms 1. Fundamentals. Springer, Berlin (1996)

    Google Scholar 

  26. Gill, P.E., Murray, W., Wright, M.H.: Numerical Linear Algebra and Optimization. Addison-Wesley, Redwood (1991)

    MATH  Google Scholar 

  27. Monteiro, R.D.C., Adler, I.: Interior path following primal-dual algorithms. Part II: Convex quadratic programming. Math. Program. 44(1), 43–66 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  28. Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Heidelberg (1998)

    Book  MATH  Google Scholar 

  29. Polak, E.: Smoothing techniques for the solution of finite and semi-infinite min-max-min problems. In: Pillo, G.D., Murli, A. (eds.) High Performance Algorithms and Software for Nonlinear Optimization. Kluwer Academic, Dordrecht (2003)

    Google Scholar 

  30. Polak, E.: On the convergence of the Pshenichnyi-Pironneau-Polak minimax algorithm with an active set strategy. J. Optim. Theory Appl. 138(2), 305–309 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  31. Mathworks Inc.: MATLAB 7 Getting Started Guide. Natick, MA (2009)

  32. Tomlab Optimization Inc.: User’s Guide for TOMLAB/CPLEX v12.1. Pullman, WA (2009)

  33. Gill, P.E., Hammarling, S.J., Murray, W., Saunders, M.A., Wright, M.H.: User’s Guide for LSSOL (Version 1.0): A Fortran Package for Constrained Linear Least-Squares and Convex Quadratic Programming. Stanford, CA (1986)

  34. Lawrence, C., Zhou, J.L., Tits, A.L.: User’s Guide for CFSQP Version 2.5: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints. Technical Report (1997)

  35. Brualdi, R.A.: Introductory Combinatorics. Prentice-Hall, Upper Saddle River (2004)

    Google Scholar 

  36. Zhu, Z., Zhang, K.: A superlinearly convergent sequential quadratic programming algorithm for minimax problems. Chin. J. Numer. Math. Appl. 27(4), 15–32 (2005)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Operations Research Department, Naval Postgraduate School, Monterey, CA, USA

    E. Y. Pee & J. O. Royset

Authors
  1. E. Y. Pee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. O. Royset
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. O. Royset.

Additional information

The second author acknowledges support from AFOSR Young Investigator grant F1ATA08337G003.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pee, E.Y., Royset, J.O. On Solving Large-Scale Finite Minimax Problems Using Exponential Smoothing. J Optim Theory Appl 148, 390–421 (2011). https://doi.org/10.1007/s10957-010-9759-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-010-9759-1

Keywords

Search

Navigation