Geodesic
Primal interior-point method for large sparse minimax optimization
Kybernetika, Tome 45 (2009) no. 5, pp. 841-864 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we propose a primal interior-point method for large sparse minimax optimization. After a short introduction, the complete algorithm is introduced and important implementation details are given. We prove that this algorithm is globally convergent under standard mild assumptions. Thus the large sparse nonconvex minimax optimization problems can be solved successfully. The results of extensive computational experiments given in this paper confirm efficiency and robustness of the proposed method.
In this paper, we propose a primal interior-point method for large sparse minimax optimization. After a short introduction, the complete algorithm is introduced and important implementation details are given. We prove that this algorithm is globally convergent under standard mild assumptions. Thus the large sparse nonconvex minimax optimization problems can be solved successfully. The results of extensive computational experiments given in this paper confirm efficiency and robustness of the proposed method.
Classification : 49K35, 65K10, 90C06, 90C47, 90C51
Keywords: unconstrained optimization; large-scale optimization; minimax optimization; nonsmooth optimization; interior-point methods; modified Newton methods; variable metric methods; computational experiments 
@article{KYB_2009_45_5_a10,
     author = {Luk\v{s}an, Ladislav and Matonoha, Ctirad and Vl\v{c}ek, Jan},
     title = {Primal interior-point method for large sparse minimax optimization},
     journal = {Kybernetika},
     pages = {841--864},
     year = {2009},
     volume = {45},
     number = {5},
     mrnumber = {2599116},
     zbl = {1198.90394},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2009_45_5_a10/}
}
TY  - JOUR
AU  - Lukšan, Ladislav
AU  - Matonoha, Ctirad
AU  - Vlček, Jan
TI  - Primal interior-point method for large sparse minimax optimization
JO  - Kybernetika
PY  - 2009
SP  - 841
EP  - 864
VL  - 45
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2009_45_5_a10/
LA  - en
ID  - KYB_2009_45_5_a10
ER  - 
%0 Journal Article
%A Lukšan, Ladislav
%A Matonoha, Ctirad
%A Vlček, Jan
%T Primal interior-point method for large sparse minimax optimization
%J Kybernetika
%D 2009
%P 841-864
%V 45
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2009_45_5_a10/
%G en
%F KYB_2009_45_5_a10
Lukšan, Ladislav; Matonoha, Ctirad; Vlček, Jan. Primal interior-point method for large sparse minimax optimization. Kybernetika, Tome 45 (2009) no. 5, pp. 841-864. http://geodesic.mathdoc.fr/item/KYB_2009_45_5_a10/

[1] J. R. Bunch and B. N. Parlett: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8 (1971), 639–655. | MR

[2] R. H. Byrd, J. Nocedal, and R. A. Waltz: KNITRO: An integrated package for nonlinear optimization. In: Large-Scale Nonlinear Optimization (G. di Pillo and M. Roma, eds.), Springer, Berlin 2006, pp. 35–59. | MR

[3] R. Fletcher: Practical Methods of Optimization. Second edition. Wiley, New York 1987. | MR | Zbl

[4] R. Fletcher and E. Sainz de la Maza: Nonlinear programming and nonsmooth optimization by successive linear programming. Math. Programming 43 (1989), 235–256. | MR

[5] Y. Gao and X. Li: Nonsmooth equations approach to a constrained minimax problem. Appl. Math. 50 (2005), 115–130. | MR

[6] P. E. Gill and W. Murray: Newton type methods for unconstrained and linearly constrained optimization. Math. Programming 7 (1974), 311–350. | MR

[7] P. E. Gill, W. Murray, and M. A. Saunders: SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47 (2005), 99–131. | MR

[8] A. A. Goldstein: On steepest descent. SIAM J. Control 3 (1965), 147–151. | MR | Zbl

[9] A. Griewank: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia 2000. | MR | Zbl

[10] A. Griewank and P. L. Toint: Partitioned variable metric updates for large-scale structured optimization problems. Numer. Math. 39 (1982), 119–137. | MR

[11] S. P. Han: Variable metric methods for minimizing a class of nondifferentiable functions. Math. Programming 20 (1981), 1–13. | MR | Zbl

[12] K. Jónasson and K. Madsen: Corrected sequential linear programming for sparse minimax optimization. BIT 34 (1994), 372–387. | MR

[13] D. Le: Three new rapidly convergent algorithms for finding a zero of a function. SIAM J. Sci. Statist. Comput. 6 (1985), 193–208. | MR | Zbl

[14] D. Le: An efficient derivative-free method for solving nonlinear equations. ACM Trans. Math. Software 11 (1985), 250–262. | MR | Zbl

[15] L. Lukšan, C. Matonoha, and J. Vlček: Interior point method for nonlinear nonconvex optimization. Numer. Linear Algebra Appl. 11 (2004), 431–453. | MR

[16] L. Lukšan, C. Matonoha, and J. Vlček: Nonsmooth equation method for nonlinear nonconvex optimization. In: Conjugate Gradient Algorithms and Finite Element Methods (M. Křížek, P. Neittaanmäki, R. Glovinski, and S. Korotov, eds.), Springer Verlag, Berlin 2004. | MR

[17] L. Lukšan, M. Tůma, J. Hartman, J. Vlček, N. Ramešová, M. Šiška, and C. Matonoha: Interactive System for Universal Functional Optimization (UFO), Version 2006. ICS AS CR Report No. V-977, Prague, 2006.

[18] L. Lukšan and E. Spedicato: Variable metric methods for unconstrained optimization and nonlinear least squares. J. Comput. Appl. Math. 124 (2000), 61–93. | MR

[19] L. Lukšan and J. Vlček: Sparse and Partially Separable Test Problems for Unconstrained and Equality Constrained Optimization, ICS AS CR Report No. V-767, Prague 1998.

[20] E. Polak, J. O. Royset, and R. S. Womersley: Algorithm with adaptive smoothing for finite minimax problems. J. Optim. Theory Appl. 119 (2003), 459–484. | MR

[21] J. Vanderbei and D. F. Shanno: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13 (1999), 231–252. | MR

[22] S. Xu: Smoothing methods for minimax problems. Comput. Optim. Appl. 20 (2001), 267–279.