×
Lukšan, Ladislav; Matonoha, Ctirad; Vlček, Jan

Primal interior point method for minimization of generalized minimax functions. (English) Zbl 1204.49022

Kybernetika 46, No. 4, 697-721 (2010).
Summary: 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. 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.

Cited in 2 Documents

MSC:

49K35 Optimality conditions for minimax problems
90C06 Large-scale problems in mathematical programming
90C47 Minimax problems in mathematical programming
90C51 Interior-point methods

Keywords:

unconstrained optimization; large-scale optimization; nonsmooth optimization; generalized minimax optimization; interior-point methods; modified Newton methods; variable metric methods; global convergence; computational experiments

Software:

ve08
PDF BibTeX XML Cite
\textit{L. Lukšan} et al., Kybernetika 46, No. 4, 697--721 (2010; Zbl 1204.49022)
Full Text: EuDML Link

References:

[1] Bertsekas, D. P.: Nondifferentiable optimization via approximation. Nondifferentiable Optimization (M. L. Balinski and P.Wolfe, Math. Programming Stud. 3 (1975), 1-25. · Zbl 0383.49025
[2] Coleman, T. F., Garbow, B. S., Moré, J. J.: Software for estimating sparse Hessian matrices. ACM Trans. Math. Software 11 (1985), 363-377. · Zbl 0584.65010
[3] Coleman, T. F., Moré, J. J.: Estimation of sparse Hessian matrices and graph coloring problems. Math. Programming 28 (1984), 243-270. · Zbl 0572.65029
[4] Demyanov, V. F., Malozemov, V. N.: Introduction to Minimax. Dover Publications, 1990. · Zbl 0781.90079
[5] Fletcher, R.: Practical Methods of Optimization. Second edition. Wiley, New York 1987. · Zbl 0905.65002
[6] Gill, P. E., Murray, W.: Newton type methods for unconstrained and linearly constrained optimization. Math. Programming 7 (1974), 311-350. · Zbl 0297.90082
[7] Griewank, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia 2000. · Zbl 0958.65028
[8] Griewank, A., Toint, P. L.: Partitioned variable metric updates for large-scale structured optimization problems. Numer. Math. 39 (1982), 119-137. · Zbl 0482.65035
[9] Le, D.: Three new rapidly convergent algorithms for finding a zero of a function. SIAM J. Sci. Stat. Computat. 6 (1985), 193-208. · Zbl 0561.65033
[10] Le, D.: An efficient derivative-free method for solving nonlinear equations. ACM Trans. Math. Software 11 (1985), 250-262. · Zbl 0581.65033
[11] Lukšan, L., Matonoha, C., Vlček, J.: Interior point method for nonlinear nonconvex optimization. Numer. Linear Algebra Appl. 11 (2004), 431-453. · Zbl 1164.90422
[12] Lukšan, L., Matonoha, C., Vlček, J.: On Lagrange multipliers of trust-region subproblems. BIT Numer. Math. 48 (2008), 763-768. · Zbl 1203.65092
[13] Lukšan, L., Matonoha, C., Vlček, J.: Primal interior-point method for large sparse minimax optimization. Kybernetika 45 (2009), 841-864. · Zbl 1198.90394
[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. · Zbl 1193.90197
[15] Lukšan, L., Spedicato, E.: Variable metric methods for unconstrained optimization and nonlinear least squares. J. Comput. Appl. Math. 124 (2000), 61-93. · Zbl 0985.65066
[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. · Zbl 1147.65316
[18] Pillo, G. Di, Grippo, L., Lucidi, S.: Smooth transformation of the generalized minimax problem. J. Optim. Theory Appl. 95 (1997), 1-24. · Zbl 0890.90165
[19] Vanderbei, J., Shanno, D. F.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13 (1999), 231-252. · Zbl 1040.90564
[20] Xu, S.: Smoothing methods for minimax problems. Computational Optim. Appl. 20 (2001), 267-279. · Zbl 1054.90087
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.