March  2022, 12(1): 47-61. doi: 10.3934/naco.2021050

Levenberg-Marquardt method for absolute value equation associated with second-order cone

1. 

School of Mathematics, Tianjin University, Tianjin 300072, P.R. China

2. 

Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan

* Corresponding author: Jein-Shan Chen

Received  February 2020 Revised  January 2021 Published  March 2022 Early access  November 2021

Fund Project: The first author is supported by by National Natural Science Foundation of China (No. 11471241) and Natural Science Foundation of Inner Mongolia (No. 2019LH01001). The last author is supported by Ministry of Science and Technology, Taiwan

In this paper, we suggest the Levenberg-Marquardt method with Armijo line search for solving absolute value equations associated with the second-order cone (SOCAVE for short), which is a generalization of the standard absolute value equation frequently discussed in the literature during the past decade. We analyze the convergence of the proposed algorithm. For numerical reports, we not only show the efficiency of the proposed method, but also present numerical comparison with smoothing Newton method. It indicates that the proposed algorithm could also be a good choice for solving the SOCAVE.

Citation: Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050
References:
[1]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Massachusetts, 1995.  Google Scholar

[2]

L. CaccettaB. Qu and G.-L. Zhou, A globally and quadratically convergent method for absolute value equations, Computational Optimization and Applications, 48 (2011), 45-58.  doi: 10.1007/s10589-009-9242-9.  Google Scholar

[3]

J. S. Chen, The convex and monotone functions associated with second-order cone, Optimization, 55 (2006), 363-385.  doi: 10.1080/02331930600819514.  Google Scholar

[4]

J. S. Chen, SOC Functions and Their Applications, Springer Optimization and Its Applications 143, Springer, Singapore, 2019. doi: 10.1007/978-981-13-4077-2.  Google Scholar

[5]

J. S. ChenX. Chen and P. Tseng, Analysis of nonsmooth vector-valued functions associated with second-order cones, Mathematical Programming, 101 (2004), 95-117.  doi: 10.1007/s10107-004-0538-3.  Google Scholar

[6]

J. S. Chen and S. H. Pan, A survey on SOC complementarity functions and solution methods for SOCPs and SOCCPs, Pacific Journal of Optimization, 8 (2012), 33-74.   Google Scholar

[7]

J. S. Chen and P. Tseng, An unconstrained smooth minimization reformulation of second-order cone complementarity problem, Mathematical Programming, 104 (2005), 293-327.  doi: 10.1007/s10107-005-0617-0.  Google Scholar

[8]

E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213.  doi: 10.1007/s101070100263.  Google Scholar

[9] U. Faraut and A. Koranyi, Anlysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994.   Google Scholar
[10]

J.-Y. Fan and Y.-X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23-39.  doi: 10.1007/s00607-004-0083-1.  Google Scholar

[11]

S.-L. Hu and Z.-H. Huang, A note on absolute value equations, Optimization Letters, 4 (2010), 417-424.  doi: 10.1007/s11590-009-0169-y.  Google Scholar

[12]

S.-L. HuZ.-H. Huang and Q. Zhang, A generalized Newton method for absolute value equations associated with second order cones, Journal of Computational and Applied Mathematics, 235 (2011), 1490-1501.  doi: 10.1016/j.cam.2010.08.036.  Google Scholar

[13]

J. IqbalA. Iqbal and M. Arif, Levenberg-Marquardt method for solving systems of absolute value equations, Journal of Computational and Applied Mathematics, 282 (2015), 134-138.  doi: 10.1016/j.cam.2014.11.062.  Google Scholar

[14]

X.-Q. Jiang, A smoothing newton method for solving absolute value equations, Advanced Materials Research, 765-767 (2013), 703-708.   Google Scholar

[15]

X.-Q. Jiang and Y. Zhang, A smoothing-type algorithm for absolute value equations, Journal of Industrial and Management Optimization, 9 (2013), 789-798.  doi: 10.3934/jimo.2013.9.789.  Google Scholar

[16]

S. Ketabchi and H. Moosaei, Minimum norm solution to the absolute value equation in the convex case, Journal of Optimization Theory and Applications, 154 (2012), 1080-1087.  doi: 10.1007/s10957-012-0044-3.  Google Scholar

[17]

K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quarterly of Applied Mathematics, 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[18]

O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, 36 (2007), 43-53.  doi: 10.1007/s10589-006-0395-5.  Google Scholar

[19]

O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, 1 (2007), 3-5.  doi: 10.1007/s11590-006-0005-6.  Google Scholar

[20]

O. L. Mangasarian, A generalized Newton method for absolute value equations, Optimization Letters, 3 (2009), 101-108.  doi: 10.1007/s11590-008-0094-5.  Google Scholar

[21]

O. L. Mangasarian, Absolute value equation solution via dual complementarity, Optimization Letters, 7 (2013), 625-630.  doi: 10.1007/s11590-012-0469-5.  Google Scholar

[22]

O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, 8 (2014), 1529-1534.  doi: 10.1007/s11590-013-0656-z.  Google Scholar

[23]

O. L. Mangasarian, Absolute value equation solution via linear programming, Journal of Optimization Theory and Applications, 161 (2014), 870-876.  doi: 10.1007/s10957-013-0461-y.  Google Scholar

[24]

O. L. Mangasarian and R. R. Meyer, Absolute value equation, Linear Algebra and Its Applications, 419 (2006), 359-367.  doi: 10.1016/j.laa.2006.05.004.  Google Scholar

[25]

D. W. Marquardt, An algorithm for least squares estimation of nonlinear inequalities, Journal of the Society for Industrial and Applied Mathematics, 11 (1963), 431-441.   Google Scholar

[26]

X.-H. MiaoW.-M. HsuC. T. Nguyen and J.-S. Chen, The solvabilities of three optimization problems associated with second-order cone, Journal of Nonlinear and Convex Analysis, 22 (2021), 937-967.   Google Scholar

[27]

X.-H. MiaoJ.-T. YangB. Saheya and J.-S. Chen, A smoothing Newton method for absolute value equation associated with second-order cone, Applied Numerical Mathematics, 120 (2017), 82-96.  doi: 10.1016/j.apnum.2017.04.012.  Google Scholar

[28]

C. T. NguyenB. SaheyaY.-L. Chang and J.-S. Chen, Unified smoothing functions for absolute value equation associated with second-order cone, Applied Numerical Mathematics, 135 (2019), 206-227.  doi: 10.1016/j.apnum.2018.08.019.  Google Scholar

[29]

O. A. Prokopyev, On equivalent reformulations for absolute value equations, Computational Optimization and Applications, 44 (2009), 363-372.  doi: 10.1007/s10589-007-9158-1.  Google Scholar

[30]

J. Rohn, A theorem of the alternative for the equation $Ax+B|x| = b$, Linear and Multilinear Algebra, 52 (2004), 421-426.  doi: 10.1080/0308108042000220686.  Google Scholar

[31]

J. Rohn, An algorithm for solving the absolute value equation, Eletronic Journal of Linear Algebra, 18 (2009), 589-599.  doi: 10.13001/1081-3810.1332.  Google Scholar

[32]

S. Yamanaka and M. Fukushima, A brancd and bound method for the absolute value programs, Optimization, 63 (2014), 305-319.  doi: 10.1080/02331934.2011.644289.  Google Scholar

[33]

N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, in Topics in Nonlinear Analysis (eds. by G. Alefeld and X. Chen), Springer-Verlag, (2001), 239–249. doi: 10.1007/978-3-7091-6217-0_18.  Google Scholar

[34]

X. Zhu and G.-H. Lin, Improved convergence results for a modified Levenberg-Marquardt method for nonlinear equations and applications in MPCC, Optimization Methods and Software, 31 (2016), 791-804.  doi: 10.1080/10556788.2016.1171863.  Google Scholar

[35]

C. Zhang and Q.-J. Wei, Global and finite convergence of a generalized Newton method for absolute value equations, Journal of Optimization Theory and Applications, 143 (2009), 391-403.  doi: 10.1007/s10957-009-9557-9.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Massachusetts, 1995.  Google Scholar

[2]

L. CaccettaB. Qu and G.-L. Zhou, A globally and quadratically convergent method for absolute value equations, Computational Optimization and Applications, 48 (2011), 45-58.  doi: 10.1007/s10589-009-9242-9.  Google Scholar

[3]

J. S. Chen, The convex and monotone functions associated with second-order cone, Optimization, 55 (2006), 363-385.  doi: 10.1080/02331930600819514.  Google Scholar

[4]

J. S. Chen, SOC Functions and Their Applications, Springer Optimization and Its Applications 143, Springer, Singapore, 2019. doi: 10.1007/978-981-13-4077-2.  Google Scholar

[5]

J. S. ChenX. Chen and P. Tseng, Analysis of nonsmooth vector-valued functions associated with second-order cones, Mathematical Programming, 101 (2004), 95-117.  doi: 10.1007/s10107-004-0538-3.  Google Scholar

[6]

J. S. Chen and S. H. Pan, A survey on SOC complementarity functions and solution methods for SOCPs and SOCCPs, Pacific Journal of Optimization, 8 (2012), 33-74.   Google Scholar

[7]

J. S. Chen and P. Tseng, An unconstrained smooth minimization reformulation of second-order cone complementarity problem, Mathematical Programming, 104 (2005), 293-327.  doi: 10.1007/s10107-005-0617-0.  Google Scholar

[8]

E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213.  doi: 10.1007/s101070100263.  Google Scholar

[9] U. Faraut and A. Koranyi, Anlysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994.   Google Scholar
[10]

J.-Y. Fan and Y.-X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23-39.  doi: 10.1007/s00607-004-0083-1.  Google Scholar

[11]

S.-L. Hu and Z.-H. Huang, A note on absolute value equations, Optimization Letters, 4 (2010), 417-424.  doi: 10.1007/s11590-009-0169-y.  Google Scholar

[12]

S.-L. HuZ.-H. Huang and Q. Zhang, A generalized Newton method for absolute value equations associated with second order cones, Journal of Computational and Applied Mathematics, 235 (2011), 1490-1501.  doi: 10.1016/j.cam.2010.08.036.  Google Scholar

[13]

J. IqbalA. Iqbal and M. Arif, Levenberg-Marquardt method for solving systems of absolute value equations, Journal of Computational and Applied Mathematics, 282 (2015), 134-138.  doi: 10.1016/j.cam.2014.11.062.  Google Scholar

[14]

X.-Q. Jiang, A smoothing newton method for solving absolute value equations, Advanced Materials Research, 765-767 (2013), 703-708.   Google Scholar

[15]

X.-Q. Jiang and Y. Zhang, A smoothing-type algorithm for absolute value equations, Journal of Industrial and Management Optimization, 9 (2013), 789-798.  doi: 10.3934/jimo.2013.9.789.  Google Scholar

[16]

S. Ketabchi and H. Moosaei, Minimum norm solution to the absolute value equation in the convex case, Journal of Optimization Theory and Applications, 154 (2012), 1080-1087.  doi: 10.1007/s10957-012-0044-3.  Google Scholar

[17]

K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quarterly of Applied Mathematics, 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[18]

O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, 36 (2007), 43-53.  doi: 10.1007/s10589-006-0395-5.  Google Scholar

[19]

O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, 1 (2007), 3-5.  doi: 10.1007/s11590-006-0005-6.  Google Scholar

[20]

O. L. Mangasarian, A generalized Newton method for absolute value equations, Optimization Letters, 3 (2009), 101-108.  doi: 10.1007/s11590-008-0094-5.  Google Scholar

[21]

O. L. Mangasarian, Absolute value equation solution via dual complementarity, Optimization Letters, 7 (2013), 625-630.  doi: 10.1007/s11590-012-0469-5.  Google Scholar

[22]

O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, 8 (2014), 1529-1534.  doi: 10.1007/s11590-013-0656-z.  Google Scholar

[23]

O. L. Mangasarian, Absolute value equation solution via linear programming, Journal of Optimization Theory and Applications, 161 (2014), 870-876.  doi: 10.1007/s10957-013-0461-y.  Google Scholar

[24]

O. L. Mangasarian and R. R. Meyer, Absolute value equation, Linear Algebra and Its Applications, 419 (2006), 359-367.  doi: 10.1016/j.laa.2006.05.004.  Google Scholar

[25]

D. W. Marquardt, An algorithm for least squares estimation of nonlinear inequalities, Journal of the Society for Industrial and Applied Mathematics, 11 (1963), 431-441.   Google Scholar

[26]

X.-H. MiaoW.-M. HsuC. T. Nguyen and J.-S. Chen, The solvabilities of three optimization problems associated with second-order cone, Journal of Nonlinear and Convex Analysis, 22 (2021), 937-967.   Google Scholar

[27]

X.-H. MiaoJ.-T. YangB. Saheya and J.-S. Chen, A smoothing Newton method for absolute value equation associated with second-order cone, Applied Numerical Mathematics, 120 (2017), 82-96.  doi: 10.1016/j.apnum.2017.04.012.  Google Scholar

[28]

C. T. NguyenB. SaheyaY.-L. Chang and J.-S. Chen, Unified smoothing functions for absolute value equation associated with second-order cone, Applied Numerical Mathematics, 135 (2019), 206-227.  doi: 10.1016/j.apnum.2018.08.019.  Google Scholar

[29]

O. A. Prokopyev, On equivalent reformulations for absolute value equations, Computational Optimization and Applications, 44 (2009), 363-372.  doi: 10.1007/s10589-007-9158-1.  Google Scholar

[30]

J. Rohn, A theorem of the alternative for the equation $Ax+B|x| = b$, Linear and Multilinear Algebra, 52 (2004), 421-426.  doi: 10.1080/0308108042000220686.  Google Scholar

[31]

J. Rohn, An algorithm for solving the absolute value equation, Eletronic Journal of Linear Algebra, 18 (2009), 589-599.  doi: 10.13001/1081-3810.1332.  Google Scholar

[32]

S. Yamanaka and M. Fukushima, A brancd and bound method for the absolute value programs, Optimization, 63 (2014), 305-319.  doi: 10.1080/02331934.2011.644289.  Google Scholar

[33]

N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, in Topics in Nonlinear Analysis (eds. by G. Alefeld and X. Chen), Springer-Verlag, (2001), 239–249. doi: 10.1007/978-3-7091-6217-0_18.  Google Scholar

[34]

X. Zhu and G.-H. Lin, Improved convergence results for a modified Levenberg-Marquardt method for nonlinear equations and applications in MPCC, Optimization Methods and Software, 31 (2016), 791-804.  doi: 10.1080/10556788.2016.1171863.  Google Scholar

[35]

C. Zhang and Q.-J. Wei, Global and finite convergence of a generalized Newton method for absolute value equations, Journal of Optimization Theory and Applications, 143 (2009), 391-403.  doi: 10.1007/s10957-009-9557-9.  Google Scholar

Figure 1.  Performance profile of computing time of Problem 4.1 with different $ p $
Figure 2.  Performance profile of computing time of Problem 4.1 with LM and SN methods
Figure 3.  Performance profile of computing time of Problem 4.2 with different $ p $
Figure 4.  Performance profile of computing time of Problem 4.2 with LM and SN methods
Figure 5.  Performance profile of computing time of Problem 4.3 with different $ p $
Figure 6.  Performance profile of computing time of Problem 4.3 with LM and SN methods
Figure 7.  Performance profile of computing time of Problem 4.4 with different $ p $
Figure 8.  Performance profile of computing time of Problem 4.4 with LM and SN methods
[1]

Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223

[2]

Jinyan Fan. On the Levenberg-Marquardt methods for convex constrained nonlinear equations. Journal of Industrial & Management Optimization, 2013, 9 (1) : 227-241. doi: 10.3934/jimo.2013.9.227

[3]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199

[4]

Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25

[5]

Xiaoqin Jiang, Ying Zhang. A smoothing-type algorithm for absolute value equations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 789-798. doi: 10.3934/jimo.2013.9.789

[6]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[7]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068

[8]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[9]

José F. Cariñena, Javier de Lucas Araujo. Superposition rules and second-order Riccati equations. Journal of Geometric Mechanics, 2011, 3 (1) : 1-22. doi: 10.3934/jgm.2011.3.1

[10]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[11]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[12]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021030

[13]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089

[14]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[15]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[16]

W. Sarlet, G. E. Prince, M. Crampin. Generalized submersiveness of second-order ordinary differential equations. Journal of Geometric Mechanics, 2009, 1 (2) : 209-221. doi: 10.3934/jgm.2009.1.209

[17]

José F. Cariñena, Irina Gheorghiu, Eduardo Martínez. Jacobi fields for second-order differential equations on Lie algebroids. Conference Publications, 2015, 2015 (special) : 213-222. doi: 10.3934/proc.2015.0213

[18]

Raegan Higgins. Asymptotic behavior of second-order nonlinear dynamic equations on time scales. Discrete & Continuous Dynamical Systems - B, 2010, 13 (3) : 609-622. doi: 10.3934/dcdsb.2010.13.609

[19]

Jaume Llibre, Amar Makhlouf. Periodic solutions of some classes of continuous second-order differential equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (2) : 477-482. doi: 10.3934/dcdsb.2017022

[20]

M. Euler, N. Euler, M. C. Nucci. On nonlocal symmetries generated by recursion operators: Second-order evolution equations. Discrete & Continuous Dynamical Systems, 2017, 37 (8) : 4239-4247. doi: 10.3934/dcds.2017181

 Impact Factor: 

Metrics

  • PDF downloads (19)
  • HTML views (23)
  • Cited by (0)

Other articles
by authors

[Back to Top]