An interior-point algorithm for nonlinear minimax problems. (English) Zbl 1196.90129

The algorithm is based on the primal-dual interior-point method described in the paper of I. Akrotirianakis and B. Rustem [J. Optimization Theory Appl. 125, No. 3, 497–521 (2005; Zbl 1079.90154)] and based on the minimax approach of B. Rustem [Math. Program., Ser. A 53, No. 3, 279–295 (1992; Zbl 0751.90057)] with the different choice of the merit function, stepsize rule and computation of search direction. For a constrained nonlinear, discrete minimax problem where the objective functions and constraints are not necessarily convex, the algorithm uses two merit functions to ensure progress toward the points satisfying the first-order optimality conditions of the original problem. Convergence properties are described and numerical results provided.


90C51 Interior-point methods
90C47 Minimax problems in mathematical programming


Full Text: DOI


[1] Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984) · Zbl 0557.90065
[2] El-Bakry, A.S., Tapia, R.A., Tsuchiya, T., Zhang, Y.: On the formulation and theory of the Newton interior-point method for nonlinear programming. J. Optim. Theory Appl. 89(3), 507–541 (1996) · Zbl 0851.90115
[3] Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point method for linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming, pp. 29–47. Springer, New York (1989) · Zbl 0708.90049
[4] Benson, H.Y., Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: jamming and numerical testing. Math. Program. Ser. A 99(1), 35–48 (2004) · Zbl 1055.90068
[5] Du, D.-Z., Pardalos, P.M.: Minimax and Applications. Nonconvex Optimization and Its Applications. Springer, Dordrecht (1995)
[6] Rustem, B., Howe, M.: Algorithms for Worst-Case Design and Applications to Risk Management. Princeton University Press, Princeton (2002) · Zbl 1140.90013
[7] Akrotirianakis, I., Rustem, B.: A globally convergent interior point algorithm for non-linear problems. J. Optim. Theory Appl. 125(3), 497–521 (2005) · Zbl 1079.90154
[8] Rustem, B.: A constrained min-max algorithm for rival models of the same economic system. Math. Program. Ser. A 53(3), 279–295 (1992) · Zbl 0751.90057
[9] Medanić, J., Andjelić, M.: On a class of differential games without saddle-point solutions. J. Optim. Theory Appl. 8, 413–430 (1971) · Zbl 0217.57502
[10] Medanić, J., Andjelić, M.: Minimax solution of the multiple-target problem. IEEE Trans. Automat. Control 17(5), 597–604 (1972) · Zbl 0262.90088
[11] Vanderbei, R.J., Shanno, D.F.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13, 231–252 (1999) · Zbl 1040.90564
[12] Chamberlain, R.M., Powell, M.J.D., Lemarechal, C., Pedersen, H.C.: The watchdog technique for forcing convergence in algorithms for constrained optimization. Math. Program. Stud. 16, 1–17 (1982) · Zbl 0477.90072
[13] Gay, D.M., Overton, M.L., Wright, M.H.: A primal-dual interior method for nonconvex nonlinear programming. In: Yuan, Y. (ed.) Advances in Nonlinear Programming, Beijing, 1996. Appl. Optim., vol. 14, pp. 31–56. Kluwer Academic, Dordrecht (1998) · Zbl 0908.90236
[14] Rustem, B.: Convergent stepsizes for constrained optimization algorithms. J. Optim. Theory Appl. 49, 135–160 (1986) · Zbl 0568.90078
[15] Rustem, B.: Equality and inequality constrained optimization algorithms with convergent stepsizes. J. Optim. Theory Appl. 76(3), 429–453 (1993) · Zbl 0797.90097
[16] Rustem, B., Nguyen, Q.: An algorithm for the inequality-constrained discrete min-max problem. SIAM J. Optim. 8(1), 265–283 (1998) (electronic) · Zbl 0911.90310
[17] Yamashita, H.: A globally convergent primal–dual interior point method for constrained optimization. Optim. Methods Softw. 10, 443–469 (1998) · Zbl 0946.90110
[18] Yamashita, H., Yabe, H.: Superlinear and quadratic convergence of some primal–dual interior point methods for constrained optimization. Math. Program. 75, 377–397 (1996) · Zbl 0874.90175
[19] Tzallas-Regas, G.: Switching stepsize strategies for nonlinear programming. Ph.D. Thesis. University of London, Imperial College London, London (2007) · Zbl 1219.90190
[20] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL–A Modeling Language for Mathematical Programming. The Scientific Press, London (1993) · Zbl 0701.90062
[21] Benson, H.: The Cute AMPL models, http://www.orfe.princeton.edu/\(\sim\)rvdb/ampl/nlmodels/cute (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.