\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Saeed Ketabchi

    * Corresponding author: Saeed Ketabchi 
Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • 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

    Mathematics Subject Classification: Primary: 90C06; Secondary: 90C20.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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}$
     | Show Table
    DownLoad: CSV

    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}$
     | Show Table
    DownLoad: CSV
  • [1] L. Armijo, Minimazation of functions havinig Lipschitz continuous first partial derivetives, Pacific Journal of Mathematics, 16 (1966), 1-3. 
    [2] T. V. Anh, An extragradient method for finding minimum-norm solution of the split equilibrium problem, Acta Mathematica Vietnamica, 44 (2016), 1-18. 
    [3] M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming Theory and Algorithms, John Wiely and Sons, 1999.
    [4] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 2014.
    [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.
    [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. 
    [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. 
    [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.
    [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.
    [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.
    [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.
    [12] O. L. Mangasarian, A finite Newton method for classification, Optimization Methods and Software, 17 (2002), 913-930.  doi: 10.1080/1055678021000028375.
    [13] J. Nocedal and S. J. Wright, Numerical Optimization, Springer Science, 1999. doi: 10.1007/b98874.
    [14] W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(1873) PDF downloads(388) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return