# American Institute of Mathematical Sciences

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 and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050
##### References:
 [1] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Massachusetts, 1995. [2] L. Caccetta, B. 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. [3] J. S. Chen, The convex and monotone functions associated with second-order cone, Optimization, 55 (2006), 363-385.  doi: 10.1080/02331930600819514. [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. [5] J. S. Chen, X. 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. [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. [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. [8] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213.  doi: 10.1007/s101070100263. [9] U. Faraut and A. Koranyi, Anlysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994. [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. [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. [12] S.-L. Hu, Z.-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. [13] J. Iqbal, A. 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. [14] X.-Q. Jiang, A smoothing newton method for solving absolute value equations, Advanced Materials Research, 765-767 (2013), 703-708. [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. [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. [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. [18] O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, 36 (2007), 43-53.  doi: 10.1007/s10589-006-0395-5. [19] O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, 1 (2007), 3-5.  doi: 10.1007/s11590-006-0005-6. [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. [21] O. L. Mangasarian, Absolute value equation solution via dual complementarity, Optimization Letters, 7 (2013), 625-630.  doi: 10.1007/s11590-012-0469-5. [22] O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, 8 (2014), 1529-1534.  doi: 10.1007/s11590-013-0656-z. [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. [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. [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. [26] X.-H. Miao, W.-M. Hsu, C. 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. [27] X.-H. Miao, J.-T. Yang, B. 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. [28] C. T. Nguyen, B. Saheya, Y.-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. [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. [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. [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. [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. [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. [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. [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.

show all references

##### References:
 [1] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Massachusetts, 1995. [2] L. Caccetta, B. 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. [3] J. S. Chen, The convex and monotone functions associated with second-order cone, Optimization, 55 (2006), 363-385.  doi: 10.1080/02331930600819514. [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. [5] J. S. Chen, X. 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. [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. [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. [8] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213.  doi: 10.1007/s101070100263. [9] U. Faraut and A. Koranyi, Anlysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994. [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. [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. [12] S.-L. Hu, Z.-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. [13] J. Iqbal, A. 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. [14] X.-Q. Jiang, A smoothing newton method for solving absolute value equations, Advanced Materials Research, 765-767 (2013), 703-708. [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. [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. [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. [18] O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, 36 (2007), 43-53.  doi: 10.1007/s10589-006-0395-5. [19] O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, 1 (2007), 3-5.  doi: 10.1007/s11590-006-0005-6. [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. [21] O. L. Mangasarian, Absolute value equation solution via dual complementarity, Optimization Letters, 7 (2013), 625-630.  doi: 10.1007/s11590-012-0469-5. [22] O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, 8 (2014), 1529-1534.  doi: 10.1007/s11590-013-0656-z. [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. [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. [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. [26] X.-H. Miao, W.-M. Hsu, C. 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. [27] X.-H. Miao, J.-T. Yang, B. 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. [28] C. T. Nguyen, B. Saheya, Y.-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. [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. [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. [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. [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. [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. [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. [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.
Performance profile of computing time of Problem 4.1 with different $p$
Performance profile of computing time of Problem 4.1 with LM and SN methods
Performance profile of computing time of Problem 4.2 with different $p$
Performance profile of computing time of Problem 4.2 with LM and SN methods
Performance profile of computing time of Problem 4.3 with different $p$
Performance profile of computing time of Problem 4.3 with LM and SN methods
Performance profile of computing time of Problem 4.4 with different $p$
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 and 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 and 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 and 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 and 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 and Management Optimization, 2013, 9 (4) : 789-798. doi: 10.3934/jimo.2013.9.789 [6] Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068 [7] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [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 and 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 and 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 and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [12] Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 [13] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [14] 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 and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [15] Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 [16] Johann Baumeister, Barbara Kaltenbacher, Antonio Leitão. On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations. Inverse Problems and Imaging, 2010, 4 (3) : 335-350. doi: 10.3934/ipi.2010.4.335 [17] 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 [18] 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 [19] Raegan Higgins. Asymptotic behavior of second-order nonlinear dynamic equations on time scales. Discrete and Continuous Dynamical Systems - B, 2010, 13 (3) : 609-622. doi: 10.3934/dcdsb.2010.13.609 [20] Jaume Llibre, Amar Makhlouf. Periodic solutions of some classes of continuous second-order differential equations. Discrete and Continuous Dynamical Systems - B, 2017, 22 (2) : 477-482. doi: 10.3934/dcdsb.2017022

Impact Factor:

## Metrics

• PDF downloads (161)
• HTML views (160)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]