A new Newton method for convex optimization problems with singular Hessian matrices

Tianji Wang; Qingdao Huang; Tianji Wang; Qingdao Huang

doi:10.3934/math.20231078

AIMS Mathematics

2023, Volume 8, Issue 9: 21161-21175. doi: 10.3934/math.20231078

Previous Article Next Article

Research article

A new Newton method for convex optimization problems with singular Hessian matrices

Tianji Wang ,
Qingdao Huang ^,

School of Mathematics, Jilin University, Changchun 130012, China

Received: 30 March 2023 Revised: 30 May 2023 Accepted: 04 June 2023 Published: 03 July 2023
MSC : 49M15, 90C25

In this paper, we propose a new Newton method for minimizing convex optimization problems with singular Hessian matrices including the special case that the Hessian matrix of the objective function is singular at any iteration point. The new method we proposed has some updates in the regularized parameter and the search direction. The step size of our method can be obtained by using Armijo backtracking line search. We also prove that the new method has global convergence. Some numerical experimental results show that the new method performs well for solving convex optimization problems whose Hessian matrices of the objective functions are singular everywhere.
- convex optimization,
- regularized Newton method,
- singular Hessian matrices,
- global convergence
Citation: Tianji Wang, Qingdao Huang. A new Newton method for convex optimization problems with singular Hessian matrices[J]. AIMS Mathematics, 2023, 8(9): 21161-21175. doi: 10.3934/math.20231078

Related Papers:

Abstract

In this paper, we propose a new Newton method for minimizing convex optimization problems with singular Hessian matrices including the special case that the Hessian matrix of the objective function is singular at any iteration point. The new method we proposed has some updates in the regularized parameter and the search direction. The step size of our method can be obtained by using Armijo backtracking line search. We also prove that the new method has global convergence. Some numerical experimental results show that the new method performs well for solving convex optimization problems whose Hessian matrices of the objective functions are singular everywhere.

References

[1]	Z. S. Yu, P. X. Li, An active set quasi-Newton method with projection step for monotone nonlinear equations, AIMS Mathematics, 6 (2021), 3606–3623. https://doi.org/10.3934/math.2021215 doi: 10.3934/math.2021215
[2]	H. C. Zhang, W. H. William, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004), 1043–1056. https://doi.org/10.1137/S1052623403428208 doi: 10.1137/S1052623403428208
[3]	M. Sun, Y. J. Wang, The conjugate gradient methods for solving the generalized periodic Sylvester matrix equations, J. Appl. Math. Comput., 60 (2019), 413–434. https://doi.org/10.1007/s12190-018-01220-3 doi: 10.1007/s12190-018-01220-3
[4]	J. Y. Fan, J. Y. Pan, On the convergence rate of the inexact Levenberg-Marquardt method, J. Ind. Manag. Optim., 7 (2011), 199–210. https://doi.org/10.3934/jimo.2011.7.199 doi: 10.3934/jimo.2011.7.199
[5]	W. J. Zhou, D. H. Li, A globally convergence BFGS method for nonlinear monotone equations without any merit functions, Math. Comput., 77 (2008), 2231–2240. https://doi.org/10.1090/S0025-5718-08-02121-2 doi: 10.1090/S0025-5718-08-02121-2
[6]	J. Y. Fan, Y. X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingular assumption, Computing, 74 (2005), 23–39. https://doi.org/10.1007/s00607-004-0083-1 doi: 10.1007/s00607-004-0083-1
[7]	M. K. Riaha, A new approach to improve ill-conditioned parabolic optimal control problem via time domain decomposition, Numer. Algor., 72 (2016), 635–666. http://doi.org/10.1007/s11075-015-0060-0 doi: 10.1007/s11075-015-0060-0
[8]	T. D. Niri, S. A. S. Fazeli, M. Heydari, A two-step improved Newton method to solve convex unconstrained optimization problems, J. Appl. Math. Comput., 62 (2020), 37–53. http://doi.org/10.1007/s12190-019-01272-z doi: 10.1007/s12190-019-01272-z
[9]	C. Cartis, N. I. M. Gould, P. L. Tpint, Adaptive cubic regularisation methods for unconstrained optimization. Part Ⅰ: motivation, convergence and numerical results, Math. Program., 127 (2011), 245–295. http://doi.org/10.1007/s10107-009-0286-5 doi: 10.1007/s10107-009-0286-5
[10]	D. K. R. Babajee, M. Z. Dauhoo, M. T. Darvishi, A. Karami, A. Barati, Analysis of two Chebyshev-like third order methods free from second derivatives for solving systems of nonlinear equations, J. Comput. Appl. Math., 233 (2010), 2002–2012. http://doi.org/10.1016/j.cam.2009.09.035 doi: 10.1016/j.cam.2009.09.035
[11]	X. H. Wang, J. S. Kou, R-order of convergence for the improved multi-point Chebyshev-like methods under generalized continuity condition, Int. J. Comput. Math., 97 (2020), 906–919. http://doi.org/10.1080/00207160.2019.1599867 doi: 10.1080/00207160.2019.1599867
[12]	H. Darvishi, M. T. Darvishi, An analytical study on two high-order hybrid methods to solve systems of nonlinear equations, J. Math.-UK, 2023 (2023), 9917774. https://doi.org/10.1155/2023/9917774 doi: 10.1155/2023/9917774
[13]	C. Cartis, N. I. M. Gould, P. L. Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems, SIAM J. Optim., 20 (2010), 2833–2852. https://doi.org/10.1137/090774100 doi: 10.1137/090774100
[14]	H. Zhang, Q. Ni, A new regularized quasi-Newton algorithm for unconstrained optimization, Appl. Math. Comput., 259 (2005), 460–469. https://doi.org/10.1016/j.amc.2015.02.032 doi: 10.1016/j.amc.2015.02.032
[15]	Y. Nesterov, B. T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program., 108 (2006), 177–205. https://doi.org/10.1007/s10107-006-0706-8 doi: 10.1007/s10107-006-0706-8
[16]	C. G. Shen, X. D. Chen, Y. M. Liang, A regularized Newton method for degenerate unconstrained optimization problems, Optim. Lett., 6 (2012), 1913–1933. https://doi.org/10.1007/s11590-011-0386-z doi: 10.1007/s11590-011-0386-z
[17]	S. M. Goldfeld, R. E. Quandt, H. F. Trotter, Maximization by quadratic hill-climbing, Econometrica, 34 (1966), 541–551.
[18]	P. E. Gill, W. Murray, Newton-type methods for unconstrained and linearly constrained optimization, Math. Program., 7 (1974), 311–350. https://doi.org/10.1007/BF01585529 doi: 10.1007/BF01585529
[19]	Y. J. Li, D. H. Li, Truncated regularized Newton method for convex minimization, Comput. Optim. Appl., 43 (2009), 119–131. https://doi.org/10.1007/s10589-007-9128-7 doi: 10.1007/s10589-007-9128-7
[20]	G. L. Zhou, L. Q. Qi, On the convergence of an inexact Newton-type method, Oper. Res. Lett., 34 (2006), 647–652. https://doi.org/10.1016/j.orl.2005.11.001 doi: 10.1016/j.orl.2005.11.001
[21]	H. Zhang, Q. Ni, A new regularized quasi-Newton method for unconstrained optimization, Optim. Lett., 12 (2018), 1639–1658. https://doi.org/10.1007/s11590-018-1236-z doi: 10.1007/s11590-018-1236-z
[22]	M. C. Yue, Z. R. Zhou, A. M. C. So, On the quadratic convergence of the cubic regularization method under a local error bound condition, SIAM J. Optim., 29 (2019), 904–932. http://doi.org/10.1137/18M1167498 doi: 10.1137/18M1167498
[23]	R. A. Polyak, Regularized Newton method for unconstrained convex optimization, Math. Program., 120 (2009), 125–145. https://doi.org/10.1007/s10107-007-0143-3 doi: 10.1007/s10107-007-0143-3
[24]	K. Ueda, N. Yamashita, Convergence properties of the regularized Newton method for the unconstrained nonconvex optimization, Appl. Math. Optim., 62 (2010), 27–46. https://doi.org/10.1007/s00245-009-9094-9 doi: 10.1007/s00245-009-9094-9
[25]	K. Ueda, N. Yamashita, A regularized Newton method without line search for unconstrained optimization, Comput. Optim. Appl., 59 (2014), 321–351. https://doi.org/10.1007/s10589-014-9656-x doi: 10.1007/s10589-014-9656-x
[26]	J. Y. Fan, Y. X. Yuan, A regularized Newton method for monotone nonlinear equations and its application, Optim. Method. Softw., 29 (2014), 102–119. https://doi.org/10.1080/10556788.2012.746344 doi: 10.1080/10556788.2012.746344
[27]	W. J. Zhou, X. J. Chen, On the convergence of a modified regularized Newton method for convex optimization with singular solutions, J. Comput. Appl. Math., 239 (2013), 179–188. https://doi.org/10.1016/j.cam.2012.09.030 doi: 10.1016/j.cam.2012.09.030
[28]	D. H. Li, M. Fukushima, L. Q. Qi, N. Yamashita, Regularized newton methods for convex minimization problems with singular solutions, Comput. Optim. Appl., 28 (2004), 131–147. https://doi.org/10.1023/B:COAP.0000026881.96694.32 doi: 10.1023/B:COAP.0000026881.96694.32
[29]	E. D. Dolan, J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201–213. https://doi.org/10.1007/s101070100263 doi: 10.1007/s101070100263

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)