June  2017, 7(2): 113-119. doi: 10.3934/naco.2017008

Computing minimum norm solution of linear systems of equations by the generalized Newton method

1. 

Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

2. 

Department of Mathematics, Faculty of Science, University of Bojnord, Bojnord, Iran

3. 

Shahed University, Tehran, Iran

* Corresponding author: Saeed Ketabchi

Received  July 2015 Published  June 2017

The aim of this paper is to find the minimum norm solution of a linear system of equations. The proposed method is based on presenting a view of solution on the dual exterior penalty problem of primal quadratic programming. To solve the unconstrained minimization problem, the generalized Newton method was employed and to guarantee its finite global convergence, the Armijo step size regulation was adopted. This method was tested on all systems selected in NETLIB 1. Numerical results were compared with the MOSEK Optimization Software 2 on linear systems in NETLIB (Table 1) and on linear systems generated by the Linear systems generator (Table 2).

1www.netlib.org

2 www.mosek.com

Citation: Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
References:
[1]

L. Armijo, Minimazation of functions havinig Lipschitz continuous first partial derivetives, Pacific Journal of Mathematics, 16 (1966), 1-3.   Google Scholar

[2]

T. V. Anh, An extragradient method for finding minimum-norm solution of the split equilibrium problem, Acta Mathematica Vietnamica, 44 (2016), 1-18.   Google Scholar

[3]

M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming Theory and Algorithms, John Wiely and Sons, 1999.  Google Scholar

[4]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 2014.  Google Scholar

[5]

Yu. G. EvtushenkoA. I. Golikov and N. Mollaverdi, Augmented Lagrangian method for large-scale linear programming problems, Optimization Methods and Software, 20 (2005), 515-524.  doi: 10.1080/10556780500139690.  Google Scholar

[6]

Yu. G. EvtushenkoA. I. GolikovS. Ketabchi and N. Mollaverdi, The augmented Lagrangian function for the linear programming problems, Dynamics of non-homogeneous systems (Ed. YuSPopkov), Russian Academy of Sciences Institute for System Analysis, 2 (2004), 101-106.   Google Scholar

[7]

A. I. Golikov and Yu. G. Evtushenko, Theorems of the alternative and their applications in numerical methods, Comput. Maths. and Math. Phys, 43 (2003), 338-358.   Google Scholar

[8]

J. B. Hiriart-UrrutyJ. J. Strodiot and V. H. Nguyen, Generalized Hessian matrics and second-order optimality condisions for problems $C^{1,1}$ data, Applied Mathmatics and Optimazation, 11 (1984), 43-56.  doi: 10.1007/BF01442169.  Google Scholar

[9]

S. Ketabchi and E. Ansari-Piri, On the solution set of convex problems and its numerical application, Journal of Computational and Applied Mathematics, 206 (2007), 288-292.  doi: 10.1016/j.cam.2006.07.004.  Google Scholar

[10]

C. Kanzow, H. Qi and L. Qi, On the minimum norm soloution of linear programs, Journal of Optimazition Theory and Applications, 116 (2003), 333-345. doi: 10.1023/A:1022457904979.  Google Scholar

[11]

O. L. Mangasarian, A Newton method for linear programming, Journal of Optimization Theory and Applications, 121 (2004), 1-18.  doi: 10.1023/B:JOTA.0000026128.34294.77.  Google Scholar

[12]

O. L. Mangasarian, A finite Newton method for classification, Optimization Methods and Software, 17 (2002), 913-930.  doi: 10.1080/1055678021000028375.  Google Scholar

[13]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Science, 1999. doi: 10.1007/b98874.  Google Scholar

[14]

W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.  Google Scholar

show all references

References:
[1]

L. Armijo, Minimazation of functions havinig Lipschitz continuous first partial derivetives, Pacific Journal of Mathematics, 16 (1966), 1-3.   Google Scholar

[2]

T. V. Anh, An extragradient method for finding minimum-norm solution of the split equilibrium problem, Acta Mathematica Vietnamica, 44 (2016), 1-18.   Google Scholar

[3]

M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming Theory and Algorithms, John Wiely and Sons, 1999.  Google Scholar

[4]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 2014.  Google Scholar

[5]

Yu. G. EvtushenkoA. I. Golikov and N. Mollaverdi, Augmented Lagrangian method for large-scale linear programming problems, Optimization Methods and Software, 20 (2005), 515-524.  doi: 10.1080/10556780500139690.  Google Scholar

[6]

Yu. G. EvtushenkoA. I. GolikovS. Ketabchi and N. Mollaverdi, The augmented Lagrangian function for the linear programming problems, Dynamics of non-homogeneous systems (Ed. YuSPopkov), Russian Academy of Sciences Institute for System Analysis, 2 (2004), 101-106.   Google Scholar

[7]

A. I. Golikov and Yu. G. Evtushenko, Theorems of the alternative and their applications in numerical methods, Comput. Maths. and Math. Phys, 43 (2003), 338-358.   Google Scholar

[8]

J. B. Hiriart-UrrutyJ. J. Strodiot and V. H. Nguyen, Generalized Hessian matrics and second-order optimality condisions for problems $C^{1,1}$ data, Applied Mathmatics and Optimazation, 11 (1984), 43-56.  doi: 10.1007/BF01442169.  Google Scholar

[9]

S. Ketabchi and E. Ansari-Piri, On the solution set of convex problems and its numerical application, Journal of Computational and Applied Mathematics, 206 (2007), 288-292.  doi: 10.1016/j.cam.2006.07.004.  Google Scholar

[10]

C. Kanzow, H. Qi and L. Qi, On the minimum norm soloution of linear programs, Journal of Optimazition Theory and Applications, 116 (2003), 333-345. doi: 10.1023/A:1022457904979.  Google Scholar

[11]

O. L. Mangasarian, A Newton method for linear programming, Journal of Optimization Theory and Applications, 121 (2004), 1-18.  doi: 10.1023/B:JOTA.0000026128.34294.77.  Google Scholar

[12]

O. L. Mangasarian, A finite Newton method for classification, Optimization Methods and Software, 17 (2002), 913-930.  doi: 10.1080/1055678021000028375.  Google Scholar

[13]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Science, 1999. doi: 10.1007/b98874.  Google Scholar

[14]

W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.  Google Scholar

Table 1.  Comparison of ssGNewton and cqpMosek on systems in NETLIB. In all solved examples $\|(-x^*)_+\|=0 $
$Systems$Method$ time(sec)$$\|{x^*}\|$ $\|Ax^*-b\|_{\infty}$
$25fv47$ ssGNewton $1.51$$3.31\times 10^3 $$3.43\times 10^{-9}$
cqpMosek $1.36$ $3.31\times 10^3$ $1.91\times 10^{-11}$
$80bau3b$ ssGNewton $0.95$$4.13\times 10^3 $$1.18\times 10^{-12}$
cqpMosek $0.80$ $4.13\times 10^3$ $2.90\times 10^{-7}$
$addlittle$ ssGNewton $0.05$$4.3\times 10^2$$2.27\times 10^{-13}$
cqpMosek0.35 $4.3\times 10^2$ $7.18\times 10^{-11}$
$ afiro $ssGNewton $0.06$$6.34\times 10^2$$6.39\times 10^{-14}$
cqpMosek $0.31$ $6.34\times 10^2$ $1.13\times 10^{-13}$
$creb$ ssGNewton $13.20$$6.24\times 10^{2}$ $1.62\times 10^{-9}$
cqpMosek $ 2.31$ $6.24\times 10^{2}$ $1.61\times 10^{-6}$
$maroser7$ssGNewton $2.86$$1.41\times 10^5 $$2.54\times 10^{-11}$
cqpMosek $55.20$ $1.41\times 10^5$ $3.27\times 10^{-11}$
$pds02$ ssGNewton $2.30$$1.61\times 10^5$$1.40\times 10^{-7}$
cqpMosek $0.51$ $1.61\times 10^5$ $8.2\times 10^{-6}$
$ken13$ ssGNewton $9.09$$2.53\times 10^4 $$4.39\times 10^{-9}$
cqpMosek $2.09$ $2.53\times 10^4 $ $1.71\times 10^{-9}$
$osa14$ ssGNewton $60.10$ $1.19\times 10^5$ $4.10\times10^{-8}$
cqpMosek $4.40$ $1.19\times 10^5$ $7.82\times 10^{-5}$
$agg3$ ssGNewton $0.27$ $7.65\times 10^5$ $3.59\times10^{-8}$
cqpMosek$ 0.40$ $7.65\times 10^5$ $2.32\times10^{-10}$
$crea $ ssGNewton $1.25$ $1.62\times10^{3}$ $4.13\times10^{-6}$
cqpMosek0.61 $1.62\times10^{3}$ $2.15\times10^{-10}$
$Systems$Method$ time(sec)$$\|{x^*}\|$ $\|Ax^*-b\|_{\infty}$
$25fv47$ ssGNewton $1.51$$3.31\times 10^3 $$3.43\times 10^{-9}$
cqpMosek $1.36$ $3.31\times 10^3$ $1.91\times 10^{-11}$
$80bau3b$ ssGNewton $0.95$$4.13\times 10^3 $$1.18\times 10^{-12}$
cqpMosek $0.80$ $4.13\times 10^3$ $2.90\times 10^{-7}$
$addlittle$ ssGNewton $0.05$$4.3\times 10^2$$2.27\times 10^{-13}$
cqpMosek0.35 $4.3\times 10^2$ $7.18\times 10^{-11}$
$ afiro $ssGNewton $0.06$$6.34\times 10^2$$6.39\times 10^{-14}$
cqpMosek $0.31$ $6.34\times 10^2$ $1.13\times 10^{-13}$
$creb$ ssGNewton $13.20$$6.24\times 10^{2}$ $1.62\times 10^{-9}$
cqpMosek $ 2.31$ $6.24\times 10^{2}$ $1.61\times 10^{-6}$
$maroser7$ssGNewton $2.86$$1.41\times 10^5 $$2.54\times 10^{-11}$
cqpMosek $55.20$ $1.41\times 10^5$ $3.27\times 10^{-11}$
$pds02$ ssGNewton $2.30$$1.61\times 10^5$$1.40\times 10^{-7}$
cqpMosek $0.51$ $1.61\times 10^5$ $8.2\times 10^{-6}$
$ken13$ ssGNewton $9.09$$2.53\times 10^4 $$4.39\times 10^{-9}$
cqpMosek $2.09$ $2.53\times 10^4 $ $1.71\times 10^{-9}$
$osa14$ ssGNewton $60.10$ $1.19\times 10^5$ $4.10\times10^{-8}$
cqpMosek $4.40$ $1.19\times 10^5$ $7.82\times 10^{-5}$
$agg3$ ssGNewton $0.27$ $7.65\times 10^5$ $3.59\times10^{-8}$
cqpMosek$ 0.40$ $7.65\times 10^5$ $2.32\times10^{-10}$
$crea $ ssGNewton $1.25$ $1.62\times10^{3}$ $4.13\times10^{-6}$
cqpMosek0.61 $1.62\times10^{3}$ $2.15\times10^{-10}$
Table 2.  Comparison of ssGNewton and cqpMosek on randomly generated systems. 'OOM' denotes out of memory. In all solved examples $\|(-x^*)_+\|=0 $
$m, n, d$Method$ time(sec)$$\|{x^*}\|$ $\|Ax^*-b\|_{\infty}$
$1000\times 1200\times 0.1$ ssGNewton $6.92$$1.87\times 10^0 $$7.73\times 10^{-12}$
cqpMosek $14.70$ $1.87\times 10^0 $ $5.45\times 10^{-12}$
$1000\times 1500\times 0.01$ ssGNewton $3.94$$1.90\times 10^2 $$1.13\times 10^{-12}$
cqpMosek $3.10$ $1.90\times 10^2$ $6.80\times 10^{-13}$
$2000\times 10000\times 0.1$ ssGNewton $29.10$$2.94\times 10^2$$4.54\times 10^{-11}$
cqpMosek122.00 $2.94\times 10^2$ $6.18\times 10^{-11}$
$ 4500\times 5000\times 0.1 $ ssGNewtonOOM$-$$-$
cqpMosek $339.00$ $3.95\times 10^2$ $3.89\times 10^{-8}$
$1000\times (5\times 10^6)\times 10^{-6} $ ssGNewton $19.20$$2.02\times 10^{2}$ $2.27\times 10^{-13}$
cqpMosekOOM $-$ $-$
$1000\times 100000\times 0.01$ ssGNewton $4.54$$2.45\times 10^2 $$3.27\times 10^{-11}$
cqpMosek $9.10$ $2.45\times 10^2$ $3.63\times 10^{-11}$
$100\times (2\times 10^6)\times 0.001$ ssGNewton $4.35$$8.13\times 10$$5.09\times 10^{-11}$
cqpMosek $30.40$ $8.13\times 10$ $4.69\times 10^{-10}$
$(2.5\times10^5) \times(3\times 10^5)\times 10^{-6}$ ssGNewton $70.12$$1.41\times 10^3 $$4.10\times 10^{-3}$
cqpMosek $5.32$ $1.41\times 10^3 $ $4.90\times 10^{-13}$
$10^5\times (2\times10^5)\times 10^{-6}$ ssGNewton $9.85$ $7.65\times 10^2$ $2.87\times10^{-8}$
cqpMosek $3.26$ $7.65\times 10^2$ $2.27\times 10^{-13}$
$m, n, d$Method$ time(sec)$$\|{x^*}\|$ $\|Ax^*-b\|_{\infty}$
$1000\times 1200\times 0.1$ ssGNewton $6.92$$1.87\times 10^0 $$7.73\times 10^{-12}$
cqpMosek $14.70$ $1.87\times 10^0 $ $5.45\times 10^{-12}$
$1000\times 1500\times 0.01$ ssGNewton $3.94$$1.90\times 10^2 $$1.13\times 10^{-12}$
cqpMosek $3.10$ $1.90\times 10^2$ $6.80\times 10^{-13}$
$2000\times 10000\times 0.1$ ssGNewton $29.10$$2.94\times 10^2$$4.54\times 10^{-11}$
cqpMosek122.00 $2.94\times 10^2$ $6.18\times 10^{-11}$
$ 4500\times 5000\times 0.1 $ ssGNewtonOOM$-$$-$
cqpMosek $339.00$ $3.95\times 10^2$ $3.89\times 10^{-8}$
$1000\times (5\times 10^6)\times 10^{-6} $ ssGNewton $19.20$$2.02\times 10^{2}$ $2.27\times 10^{-13}$
cqpMosekOOM $-$ $-$
$1000\times 100000\times 0.01$ ssGNewton $4.54$$2.45\times 10^2 $$3.27\times 10^{-11}$
cqpMosek $9.10$ $2.45\times 10^2$ $3.63\times 10^{-11}$
$100\times (2\times 10^6)\times 0.001$ ssGNewton $4.35$$8.13\times 10$$5.09\times 10^{-11}$
cqpMosek $30.40$ $8.13\times 10$ $4.69\times 10^{-10}$
$(2.5\times10^5) \times(3\times 10^5)\times 10^{-6}$ ssGNewton $70.12$$1.41\times 10^3 $$4.10\times 10^{-3}$
cqpMosek $5.32$ $1.41\times 10^3 $ $4.90\times 10^{-13}$
$10^5\times (2\times10^5)\times 10^{-6}$ ssGNewton $9.85$ $7.65\times 10^2$ $2.87\times10^{-8}$
cqpMosek $3.26$ $7.65\times 10^2$ $2.27\times 10^{-13}$
[1]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381

[2]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[3]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51

[4]

Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034

[5]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018

[6]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044

[7]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153

[8]

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

[9]

Hengrui Luo, Alice Patania, Jisu Kim, Mikael Vejdemo-Johansson. Generalized penalty for circular coordinate representation. Foundations of Data Science, 2021, 3 (4) : 729-764. doi: 10.3934/fods.2021024

[10]

Donghui Yang, Jie Zhong. Optimal actuator location of the minimum norm controls for stochastic heat equations. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1081-1095. doi: 10.3934/mcrf.2018046

[11]

Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197

[12]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[13]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391

[14]

T. Tachim Medjo. On the Newton method in robust control of fluid flow. Discrete & Continuous Dynamical Systems, 2003, 9 (5) : 1201-1222. doi: 10.3934/dcds.2003.9.1201

[15]

Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial & Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553

[16]

Zhi-Feng Pang, Yu-Fei Yang. Semismooth Newton method for minimization of the LLT model. Inverse Problems & Imaging, 2009, 3 (4) : 677-691. doi: 10.3934/ipi.2009.3.677

[17]

Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028

[18]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[19]

Daniel Schnellmann. Typical points for one-parameter families of piecewise expanding maps of the interval. Discrete & Continuous Dynamical Systems, 2011, 31 (3) : 877-911. doi: 10.3934/dcds.2011.31.877

[20]

GUANGBING LI. Positive solution for quasilinear Schrödinger equations with a parameter. Communications on Pure & Applied Analysis, 2015, 14 (5) : 1803-1816. doi: 10.3934/cpaa.2015.14.1803

 Impact Factor: 

Metrics

  • PDF downloads (247)
  • HTML views (212)
  • Cited by (2)

[Back to Top]