[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A generalized Newton method for absolute value equations

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

A direct generalized Newton method is proposed for solving the NP-hard absolute value equation (AVE) Ax − |x| = b when the singular values of A exceed 1. A simple MATLAB implementation of the method solved 100 randomly generated 1,000-dimensional AVEs to an accuracy of 10−6 in less than 10 s each. Similarly, AVEs corresponding to 100 randomly generated linear complementarity problems with 1,000 × 1,000 nonsymmetric positive definite matrices were also solved to the same accuracy in less than 29 s each.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bertsekas D.P.: Nonlinear Programming. Athena Scientific, Belmont (1995)

    MATH  Google Scholar 

  2. Chung S.J.: NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60, 393–399 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  3. Cottle R.W., Dantzig G.: Complementary pivot theory of mathematical programming. Linear Algebra Appl. 1, 103–125 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  4. Cottle R.W., Pang J.S., Stone R.E.: The Linear Complementarity Problem. Academic Press, New York (1992)

    MATH  Google Scholar 

  5. Mangasarian, O.L.: Absolute value equation solution via concaveminimization. Optim. Lett. 1(1), 3–8 (2007). ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/06-02.pdf

  6. Mangasarian, O.L.: Absolute value programming. Comput. Optim. Appl. 36(1), 43–53 (2007). ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/05-04.ps

    Google Scholar 

  7. Mangasarian, O.L., Meyer, R.R.: Absolute value equations. Linear Algebra Appl. 419, 359–367 (2006). ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/05-06.pdf

    Google Scholar 

  8. Ortega J.M., Rheinboldt W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)

    MATH  Google Scholar 

  9. Polyak B.T.: Introduction to Optimization. Optimization Software Inc, Publications Division, New York (1987)

    Google Scholar 

  10. Rockafellar R.T.: New applications of duality in convex programming. In Proceedings Fourth Conference on Probability, Brasov (1971)

    Google Scholar 

  11. Rohn, J.: A theorem of the alternatives for the equation A x + B|x| = b. Linear Multilinear Algebra, 52(6), 421–426 (2004). http://www.cs.cas.cz/~rohn/publist/alternatives.pdf

Download references

Author information

Authors and Affiliations

  1. Computer Sciences Department, University of Wisconsin, Madison, WI, 53706, USA

    O. L. Mangasarian

  2. Department of Mathematics, University of California at San Diego, La Jolla, CA, 92093, USA

    O. L. Mangasarian

Authors
  1. O. L. Mangasarian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to O. L. Mangasarian.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mangasarian, O.L. A generalized Newton method for absolute value equations. Optim Lett 3, 101–108 (2009). https://doi.org/10.1007/s11590-008-0094-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-008-0094-5

Keywords

Search

Navigation