×

Primal interior-point method for large sparse minimax optimization. (English) Zbl 1198.90394

The paper introduces a feasible primal interior point method for solving the problem: minimize \(F(x):=\max_{1\leq i\leq m}f_{i}(x)\), where \(f_{i}:\mathbb{R}^{m}\rightarrow \mathbb{R}\) are functions which are bounded below, and have bounded continuous first and second-order derivatives on the convex hull of a level set of \(F\). It is shown that the algorithm converges globally. In the last section of the paper, the method is compared to three other known methods by testing each one on a set of 22 problems.

MSC:

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

Software:

ve08; SNOPT; UFO; KNITRO
PDFBibTeX XMLCite
Full Text: EuDML Link

References:

[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. · Zbl 0199.49802
[2] R. H. Byrd, J. Nocedal, and R. A. Waltz: KNITRO: An integrated package for nonlinear optimization. Large-Scale Nonlinear Optimization (G. di Pillo and M. Roma, Springer, Berlin 2006, pp. 35-59. · Zbl 1108.90004
[3] R. Fletcher: Practical Methods of Optimization. Second edition. Wiley, New York 1987. · Zbl 0988.65043
[4] R. Fletcher and E. Sainz de la Maza: Nonlinear programming and nonsmooth optimization by successive linear programming. Math. Programming 43 (1989), 235-256. · Zbl 0724.90062 · doi:10.1007/BF01582292
[5] Y. Gao and X. Li: Nonsmooth equations approach to a constrained minimax problem. Appl. Math. 50 (2005), 115-130. · Zbl 1099.90075 · doi:10.1007/s10492-005-0008-0
[6] P. E. Gill and W. Murray: Newton type methods for unconstrained and linearly constrained optimization. Math. Programming 7 (1974), 311-350. · Zbl 0297.90082 · doi:10.1007/BF01585529
[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. · Zbl 1210.90176 · doi:10.1137/S0036144504446096
[8] A. A. Goldstein: On steepest descent. SIAM J. Control 3 (1965), 147-151. · Zbl 0221.65094 · doi:10.1137/0303013
[9] A. Griewank: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia 2000. · Zbl 1159.65026 · doi:10.1137/1.9780898717761
[10] A. Griewank and P. L. Toint: Partitioned variable metric updates for large-scale structured optimization problems. Numer. Math. 39 (1982), 119-137. · Zbl 0482.65035 · doi:10.1007/BF01399316
[11] S. P. Han: Variable metric methods for minimizing a class of nondifferentiable functions. Math. Programming 20 (1981), 1-13. · Zbl 0441.90095 · doi:10.1007/BF01589328
[12] K. Jónasson and K. Madsen: Corrected sequential linear programming for sparse minimax optimization. BIT 34 (1994), 372-387. · Zbl 0813.65090 · doi:10.1007/BF01935647
[13] D. Le: Three new rapidly convergent algorithms for finding a zero of a function. SIAM J. Sci. Statist. Comput. 6 (1985), 193-208. · Zbl 0561.65033 · doi:10.1137/0906016
[14] D. Le: An efficient derivative-free method for solving nonlinear equations. ACM Trans. Math. Software 11 (1985), 250-262. · Zbl 0581.65033 · doi:10.1145/214408.214416
[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.
[16] L. Lukšan, C. Matonoha, and J. Vlček: Nonsmooth equation method for nonlinear nonconvex optimization. Conjugate Gradient Algorithms and Finite Element Methods (M. Křížek, P. Neittaanmäki, R. Glovinski, and S. Korotov, Springer Verlag, Berlin 2004.
[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. · Zbl 0985.65066 · doi:10.1016/S0377-0427(00)00420-9
[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. · Zbl 1061.90117 · doi:10.1023/B:JOTA.0000006685.60019.3e
[21] J. Vanderbei and D. F. Shanno: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13 (1999), 231-252. · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[22] S. Xu: Smoothing methods for minimax problems. Comput. Optim. Appl. 20 (2001), 267-279. · Zbl 1054.90087 · doi:10.1023/A:1011211101714
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.