# American Institute of Mathematical Sciences

April  2014, 10(2): 637-663. doi: 10.3934/jimo.2014.10.637

## Substitution secant/finite difference method to large sparse minimax problems

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

Received  May 2012 Revised  May 2013 Published  October 2013

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.
Citation: Junxiang Li, Yan Gao, Tao Dai, Chunming Ye, Qiang Su, Jiazhen Huo. Substitution secant/finite difference method to large sparse minimax problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 637-663. doi: 10.3934/jimo.2014.10.637
##### References:

show all references

##### References:
 [1] Claire david@lmm.jussieu.fr David, Pierre Sagaut. Theoretical optimization of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 286-293. doi: 10.3934/proc.2007.2007.286 [2] Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020196 [3] Qiang Du, Jingyan Zhang. Asymptotic analysis of a diffuse interface relaxation to a nonlocal optimal partition problem. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1443-1461. doi: 10.3934/dcds.2011.29.1443 [4] Zhongyi Huang. Tailored finite point method for the interface problem. Networks & Heterogeneous Media, 2009, 4 (1) : 91-106. doi: 10.3934/nhm.2009.4.91 [5] Jian Lu, Lixin Shen, Chen Xu, Yuesheng Xu. Multiplicative noise removal with a sparsity-aware optimization model. Inverse Problems & Imaging, 2017, 11 (6) : 949-974. doi: 10.3934/ipi.2017044 [6] Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007 [7] Weizhu Bao, Chunmei Su. Uniform error estimates of a finite difference method for the Klein-Gordon-Schrödinger system in the nonrelativistic and massless limit regimes. Kinetic & Related Models, 2018, 11 (4) : 1037-1062. doi: 10.3934/krm.2018040 [8] Wen Chen, Song Wang. A finite difference method for pricing European and American options under a geometric Lévy process. Journal of Industrial & Management Optimization, 2015, 11 (1) : 241-264. doi: 10.3934/jimo.2015.11.241 [9] Ömer Oruç, Alaattin Esen, Fatih Bulut. A unified finite difference Chebyshev wavelet method for numerically solving time fractional Burgers' equation. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 533-542. doi: 10.3934/dcdss.2019035 [10] Yones Esmaeelzade Aghdam, Hamid Safdari, Yaqub Azari, Hossein Jafari, Dumitru Baleanu. Numerical investigation of space fractional order diffusion equation by the Chebyshev collocation method of the fourth kind and compact finite difference scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020402 [11] Jeong-Yup Lee, Boris Solomyak. On substitution tilings and Delone sets without finite local complexity. Discrete & Continuous Dynamical Systems - A, 2019, 39 (6) : 3149-3177. doi: 10.3934/dcds.2019130 [12] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [13] Brahim El Asri. The value of a minimax problem involving impulse control. Journal of Dynamics & Games, 2019, 6 (1) : 1-17. doi: 10.3934/jdg.2019001 [14] Hawraa Alsayed, Hussein Fakih, Alain Miranville, Ali Wehbe. Finite difference scheme for 2D parabolic problem modelling electrostatic Micro-Electromechanical Systems. Electronic Research Announcements, 2019, 26: 54-71. doi: 10.3934/era.2019.26.005 [15] Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020184 [16] Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327 [17] Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645 [18] Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 [19] Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136 [20] Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019135

2019 Impact Factor: 1.366