Article
Full entry |
PDF
(0.9 MB)
Feedback
PDF
(0.9 MB)
Feedback
Keywords:
unconstrained optimization; large-scale optimization; minimax optimization; nonsmooth optimization; interior-point methods; modified Newton methods; variable metric methods; computational experiments
unconstrained optimization; large-scale optimization; minimax optimization; nonsmooth optimization; interior-point methods; modified Newton methods; variable metric methods; computational experiments
Summary:
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.
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. MR 0305564
[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 2194566
[3] R. Fletcher: Practical Methods of Optimization. Second edition. Wiley, New York 1987. MR 0955799 | 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. MR 0993464
[5] Y. Gao and X. Li: Nonsmooth equations approach to a constrained minimax problem. Appl. Math. 50 (2005), 115–130. MR 2125154
[6] P. E. Gill and W. Murray: Newton type methods for unconstrained and linearly constrained optimization. Math. Programming 7 (1974), 311–350. MR 0356503
[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 2149103
[8] A. A. Goldstein: On steepest descent. SIAM J. Control 3 (1965), 147–151. MR 0184777 | Zbl 0221.65094
[9] A. Griewank: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia 2000. MR 1753583 | Zbl 1159.65026
[10] A. Griewank and P. L. Toint: Partitioned variable metric updates for large-scale structured optimization problems. Numer. Math. 39 (1982), 119–137. MR 0664541
[11] S. P. Han: Variable metric methods for minimizing a class of nondifferentiable functions. Math. Programming 20 (1981), 1–13. MR 0594019 | Zbl 0441.90095
[12] K. Jónasson and K. Madsen: Corrected sequential linear programming for sparse minimax optimization. BIT 34 (1994), 372–387. MR 1429938
[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 0773291 | Zbl 0561.65033
[14] D. Le: An efficient derivative-free method for solving nonlinear equations. ACM Trans. Math. Software 11 (1985), 250–262. MR 0814340 | Zbl 0581.65033
[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 2067814
[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 2082558
[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 1803294
[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 2026459
[21] J. Vanderbei and D. F. Shanno: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13 (1999), 231–252. MR 1704122
[22] S. Xu: Smoothing methods for minimax problems. Comput. Optim. Appl. 20 (2001), 267–279.
Search
Partner of
