Geodesic
Primal interior point method for minimization of generalized minimax functions
Kybernetika, Tome 46 (2010) no. 4, pp. 697-721 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 generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. (i. e. interior point method that uses explicitly computed approximations of Lagrange multipliers instead of their updates). Next we describe the basic algorithm and give more details concerning its implementation covering numerical differentiation, variable metric updates, and a barrier parameter decrease. Using standard weak assumptions, we prove that this algorithm is globally convergent if a bounded barrier is used. Then, using stronger assumptions, we prove that it is globally convergent also for the logarithmic barrier. Finally, we present results of computational experiments confirming the efficiency of the primal interior point method for special cases of generalized minimax problems.
In this paper, we propose a primal interior-point method for large sparse generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. (i. e. interior point method that uses explicitly computed approximations of Lagrange multipliers instead of their updates). Next we describe the basic algorithm and give more details concerning its implementation covering numerical differentiation, variable metric updates, and a barrier parameter decrease. Using standard weak assumptions, we prove that this algorithm is globally convergent if a bounded barrier is used. Then, using stronger assumptions, we prove that it is globally convergent also for the logarithmic barrier. Finally, we present results of computational experiments confirming the efficiency of the primal interior point method for special cases of generalized minimax problems.
Classification : 49K35, 90C06, 90C47, 90C51
Keywords: unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments 
@article{KYB_2010_46_4_a7,
     author = {Luk\v{s}an, Ladislav and Matonoha, Ctirad and Vl\v{c}ek, Jan},
     title = {Primal interior point method for minimization of generalized minimax functions},
     journal = {Kybernetika},
     pages = {697--721},
     year = {2010},
     volume = {46},
     number = {4},
     mrnumber = {2722096},
     zbl = {1204.49022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2010_46_4_a7/}
}
TY  - JOUR
AU  - Lukšan, Ladislav
AU  - Matonoha, Ctirad
AU  - Vlček, Jan
TI  - Primal interior point method for minimization of generalized minimax functions
JO  - Kybernetika
PY  - 2010
SP  - 697
EP  - 721
VL  - 46
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/KYB_2010_46_4_a7/
LA  - en
ID  - KYB_2010_46_4_a7
ER  - 
%0 Journal Article
%A Lukšan, Ladislav
%A Matonoha, Ctirad
%A Vlček, Jan
%T Primal interior point method for minimization of generalized minimax functions
%J Kybernetika
%D 2010
%P 697-721
%V 46
%N 4
%U http://geodesic.mathdoc.fr/item/KYB_2010_46_4_a7/
%G en
%F KYB_2010_46_4_a7
Lukšan, Ladislav; Matonoha, Ctirad; Vlček, Jan. Primal interior point method for minimization of generalized minimax functions. Kybernetika, Tome 46 (2010) no. 4, pp. 697-721. http://geodesic.mathdoc.fr/item/KYB_2010_46_4_a7/

[1] Bertsekas, D. P.: Nondifferentiable optimization via approximation. In: Nondifferentiable Optimization (M. L. Balinski and P.Wolfe, eds.), Math. Programming Stud. 3 (1975), 1–25. | MR | Zbl

[2] Coleman, T. F., Garbow, B. S., Moré, J. J.: Software for estimating sparse Hessian matrices. ACM Trans. Math. Software 11 (1985), 363–377. | DOI | MR

[3] Coleman, T. F., Moré, J. J.: Estimation of sparse Hessian matrices and graph coloring problems. Math. Programming 28 (1984), 243–270. | DOI | MR

[4] Demyanov, V. F., Malozemov, V. N.: Introduction to Minimax. Dover Publications, 1990. | MR

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

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

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

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

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

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

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

[12] Lukšan, L., Matonoha, C., Vlček, J.: On Lagrange multipliers of trust-region subproblems. BIT Numer. Math. 48 (2008), 763–768. | DOI | MR | Zbl

[13] Lukšan, L., Matonoha, C., Vlček, J.: Primal interior-point method for large sparse minimax optimization. Kybernetika 45 (2009), 841–864. | MR | Zbl

[14] Lukšan, L., Matonoha, C., Vlček, J.: Trust-region interior-point method for large sparse $l_1$ optimization. Optimization Methods and Software 22 (2007), 737–753. | DOI | MR | Zbl

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

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

[17] Lukšan, L., Vlček, J.: Variable metric method for minimization of partially separable nonsmooth functions. Pacific J. Optim. 2 (2006), 59–70. | MR

[18] Pillo, G. Di, Grippo, L., Lucidi, S.: Smooth transformation of the generalized minimax problem. J. Optim. Theory Appl. 95 (1997), 1–24. | DOI | MR | Zbl

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

[20] Xu, S.: Smoothing methods for minimax problems. Computational Optim. Appl. 20 (2001), 267–279. | DOI | MR