Substitution secant/finite difference method to large sparse minimax problems

Junxiang Li; Yan Gao; Tao Dai; Chunming Ye; Qiang Su; Jiazhen Huo

doi:10.3934/jimo.2014.10.637

Article Contents

2014, Volume 10, Issue 2: 637-663. Doi: 10.3934/jimo.2014.10.637

This issue Previous Article LS-SVM approximate solution for affine nonlinear systems with partially unknown functions Next Article

Substitution secant/finite difference method to large sparse minimax problems

1.
Business School, University of Shanghai for Science and Technology, Shanghai, 200093
2.
Glorious Sun School of Business and Management, Donghua University, Shanghai, 200051
3.
School of Economics and Management, Tongji University, Shanghai, 200092

Received: May 2012

Revised: May 2013

Published: April 2014

Abstract Related Papers Cited by

Abstract

We present a substitution secant/finite difference (SSFD) method to solve the finite minimax optimization problems with a number of functions whose Hessians are often sparse, i.e., these matrices are populated primarily with zeros. By combining of a substitution method, a secant method and a finite difference method, the gradient evaluations can be employed as efficiently as possible in forming quadratic approximations to the functions, which is more effective than that for large sparse unconstrained differentiable optimization. Without strict complementarity and linear independence, local and global convergence is proven and $q$-superlinear convergence result and $r$-convergence rate estimate show that the method has a good convergence property. A handling method of a nonpositive definitive Hessian is given to solve nonconvex problems. Our numerical tests show that the algorithm is robust and quite effective, and that its performance is comparable to or better than that of other algorithms available.

Keywords:

Mathematics Subject Classification: Primary: 90C06, 90C30, 90C47, 49K35; Secondary: 65K10.

Citation:

Related Papers

Cited by

References

[1]	S. Bhulai, G. Koole and A. Pot, Simple methods for shift scheduling in multiskill call centers, Manufacturing & Service Operations Management, 10 (2008), 411-420.doi: 10.1287/msom.1070.0172.
[2]	X. Cai, K. Teo, X. Yang and X. Zhou, Portfolio optimization under a minimax rule, Manag. Sci., 46 (2000), 957-972.doi: 10.1287/mnsc.46.7.957.12039.
[3]	F. H. Clarke, Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983.
[4]	T. F. Coleman and J. J. Moré, Estimation of sparse Hessian matrices and graph coloring problems, Mathematical Programming, 28 (1984), 243-270.doi: 10.1007/BF02612334.
[5]	T. F. Coleman and J. J. Moré, Software for estimation of sparse Hessian matrices, ACM Transaction on Mathematical software, 11 (1985), 363-377.doi: 10.1145/6187.6190.
[6]	V. F. Demyanov and V. N. Malozemov, Introduction to Minimax, Translated from the Russian by D. Louvish. Halsted Press [John Wiley & Sons], New York-Toronto, Ont.; Israel Program for Scientific Translations, Jerusalem-London, 1974.
[7]	P. Gill, W. Murray and M. H. Wright, Practical Optimization, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1981.
[8]	A. Griewank and G. F. Corliss, Automatic Differentiation of Algorithms: Theory, Implementation, and Application, Proceedings of the First SIAM Workshop held in Breckenridge, Colorado, January 6–8, 1991. Edited by Andreas Griewank and George F. Corliss. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991.
[9]	S. P. Han, Variable-Metric methods for minimizing a class of nondifferentiable functions, Mathematical Programming, 20 (1981), 1-13.doi: 10.1007/BF01589328.
[10]	D. L. Han, J. B. Jian and J. Li, On the accurate identification of active set for constrained minimax problems, Nonlinear Analysis, 74 (2011), 3022-3032.doi: 10.1016/j.na.2011.01.024.
[11]	W. Hare and M. Macklem, Derivative-free optimization methods for finite minimax problems, Optimization Methods and Software, 28 (2013), 300-312.doi: 10.1080/10556788.2011.638923.
[12]	S. X. He and S. M. Zhou, A nonlinear augmented Lagrangian for constrained minimax problems, Applied Mathematics and Computation, 218 (2011), 4567-4579.doi: 10.1016/j.amc.2011.10.039.
[13]	J. B. Jian, R. Quan and X. L. Zhang, Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints, Journal of Computational and Applied Mathematics, 205 (2007), 406-429.doi: 10.1016/j.cam.2006.05.034.
[14]	J. B. Jian and M. T. Chao, A sequential quadratically constrained quadratic programming method for unconstrained minimax problems, J. Math. Anal. Appl., 362 (2010), 34-45.doi: 10.1016/j.jmaa.2009.08.046.
[15]	J. X. Li, L. M. Yan, S. D. Li and J. Z. Huo, Inexact trust region PGC method for large sparse unconstrained optimization, Computational Optimization and Applications, 51 (2012), 981-999.doi: 10.1007/s10589-010-9381-z.
[16]	J. X. Li and J. Z. Huo, Inexact smoothing method for large sparse minimax optimization, Applied Mathematics and Computation, 218 (2011), 2750-2760.doi: 10.1016/j.amc.2011.08.017.
[17]	S. S. Liu and L. G. Papageorgiou, Multiobjective optimisation of production, distribution and capacity planning of global supply chains in the process industry, Omega, 41 (2013), 369-382.doi: 10.1016/j.omega.2012.03.007.
[18]	G. Liuzzi, S. Lucidi and M. Sciandrone, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM J. Optim., 16 (2006), 1054-1075.doi: 10.1137/040615821.
[19]	X. S. Li, An entropy-based aggregate method for minimax optimization, Engineering Optimization, 18 (1992), 277-285.
[20]	L. Lukšan and J. Vlček, Sparse and Partially Separable Test Problems for Unconstrained and Equality Constrained Optimization, Report V-767, Prague, ICS AS CR, 1999.
[21]	L. Lukšan and J. Vlček, Test Problems for Nonsmooth Unconstrained and Linearly Constrained Optimization, Report V-798, Prague, ICS AS CR, 2000.
[22]	L. Luksan, C. Matonoha and J. Vlcek, Primal Interior-Point Method for Large Sparse Minimax Optimization, Technical Report 941, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, Czech Republic (2005).
[23]	B. Mor and G. Mosheiov, Minmax scheduling problems with common flow-allowance, Journal of the Operational Research Society, 63 (2012), 1284-1293.doi: 10.1057/jors.2011.135.
[24]	W. Murray and M. L. Overton, A projected Lagrangian algorithm for nonlinear minimax optimization, SIAM Journal on Scientific and Statistical Computing, 1 (1980), 345-370.doi: 10.1137/0901025.
[25]	J. Nocedal and S. J. Wright, Numerical Optimization, Springer, NewYork, 1999.doi: 10.1007/b98874.
[26]	E. Obasanjo, G. Tzallas-Regas and B. Rustem, An interior-point algorithm for nonlinear minimax problems, J. Optim. Theory Appl., 144 (2010), 291-318.doi: 10.1007/s10957-009-9599-z.
[27]	J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[28]	E. Y. Pee and J. O. Royset, On solving large-scale finite minimax problems using exponential smoothing, J. Optim. Theory Appl., 148 (2011), 390-421.doi: 10.1007/s10957-010-9759-1.
[29]	E. Polak, On the mathematical foundations of nondifferentiable optimization in engineering design, SIAM Rev., 29 (1987), 21-89.doi: 10.1137/1029002.
[30]	E. Polak, S. Salcudean and D. Q. Mayne, Adaptive control of ARMA plants using worst case design by semi-infinite optimization, IEEE Trans. Autom. Control, 32 (1987), 388-396.doi: 10.1109/TAC.1987.1104614.
[31]	E. R. Panier and A. L. Tits, A globally convergent algorithm with adaptively refined discretization for semi-infinite optimization problems arising in engineering design, IEEE Trans. Autom. Control, 34 (1989), 903-908.doi: 10.1109/9.29441.
[32]	E. Polak, D. Q. Mayne and J. E. Higgins, Superlinearly convergent algorithm for min-max problems, Journal of Optimization Theory and Applications, 69 (1991), 407-439.doi: 10.1007/BF00940683.
[33]	E. Polak, D. Q. Mayne and J. E. Higgins, On the extension of Newton's method to semi-infinite minimax problems, SIAM Journal on Control and Optimization, 30 (1992), 367-389.doi: 10.1137/0330023.
[34]	E. Polak, Optimization Algorithm and Consistent Approximations, Applied Mathematical Sciences, 124, Springer-Verlag, New York, 1997.doi: 10.1007/978-1-4612-0663-7.
[35]	E. Polak, R. Trahan and D. Q. Mayne, Combined phase I-phase II methods of feasible directions, Mathematical Programming, 17 (1979), 61-73.doi: 10.1007/BF01588225.
[36]	E. Polak, J. O. Royset and R. S. Womersley, Algorithms with adaptive smoothing for finite minimax problems, Journal of Optimization Theory and Applications, 119 (2003), 459-484.doi: 10.1023/B:JOTA.0000006685.60019.3e.
[37]	E. Polak, R. S. Womersley and X. H. Yin, An algorithm based on active sets and smoothing for discretized semi-infinite minimax problems, J. Optim. Theory Appl., 138 (2008), 311-328.doi: 10.1007/s10957-008-9355-9.
[38]	A. Pot, S. Bhulai and G. Koole, A simple staffing method for multiskill call centers, Manuf. Ser. Oper. Manage., 10 (2008), 421-428.doi: 10.1287/msom.1070.0173.
[39]	M. J. D. Powell and Ph. L. Toint, On the estimation of sparse Hessian matrices, SIAM Journal on Numerical Analysis, 16 (1979), 1060-1074.doi: 10.1137/0716078.
[40]	S. M. Robinson, Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear-programming algorithms, Mathematical Programming, 7 (1974), 1-16.doi: 10.1007/BF01585500.
[41]	J. O. Royset and E. Y. Pee, Rate of convergence analysis of discretization and smoothing algorithms for semiinfinite minimax problems, J. Optim. Theory Appl., 155 (2012), 855-882.doi: 10.1007/s10957-012-0109-3.
[42]	J. F. Sturm and S. Zhang, A dual and interior-point approach to solve convex min-max problems, in Minimax and Applications, Nonconvex Optim. Appl., 4, Kluwer Acad. Publ., Dordrecht, 1995, 69-78.doi: 10.1007/978-1-4613-3557-3_4.
[43]	R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
[44]	S. Ruzika and M. Thiemann, Min-Max quickest path problems, Networks, 60 (2012), 253-258.doi: 10.1002/net.21473.
[45]	F. S. Wang and Y. P. Wang, Nonmonotone aglorithm for minimax optimization problems, Applied Mathematics and Computation, 217 (2011), 6296-6308.doi: 10.1016/j.amc.2011.01.002.
[46]	S. Wolfram, The Mathematica Book, Third edition, Wolfram Media, Inc., Champaign, IL; Cambridge University Press, Cambridge, 1996.
[47]	S. Xu, Smoothing methods for minimax problems, Computational Optimization and Applications, 20 (2001), 267-279.doi: 10.1023/A:1011211101714.
[48]	F. Ye, H. liu, S. Zhou and S. Liu, A smoothing trust-region Newton-CG method for minimax problem, Appl. Math. Comput., 199 (2008), 581-589.doi: 10.1016/j.amc.2007.10.070.
[49]	B. Yu, G. X. Liu and G. C. Feng, The aggregate homotopy methods for constrained sequential max-min problems, Northeastern Mathematical Journal, 19 (2003), 287-290.
[50]	Y. X. Yuan and W. Y. Sun, Optimization Theorem and Methods, Science Press, Beijing, China, 2001.
[51]	S. T. Zhang and B. Yu, A globally convergent method for nonconvex generalized semi-infinite minimax problems, Numerical Mathematics A Journal of Chinese Universities, 27 (2005), 316-319.
[52]	H. W. Zhang and J. X. Li, The substitution secant/finite difference method for large scale sparse unconstrained optimization, Acta Mathematicae Applicatae Sinica, English series, 21 (2005), 581-596.doi: 10.1007/s10255-005-0267-2.