Skip to main content
SpringerLink
Log in

A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we present a detailed investigation for the properties of a one-parametric class of SOC complementarity functions, which include the globally Lipschitz continuity, strong semismoothness, and the characterization of their B-subdifferential. Moreover, for the merit functions induced by them for the second-order cone complementarity problem (SOCCP), we provide a condition for each stationary point to be a solution of the SOCCP and establish the boundedness of their level sets, by exploiting Cartesian P-properties. We also propose a semismooth Newton type method based on the reformulation of the nonsmooth system of equations involving the class of SOC complementarity functions. The global and superlinear convergence results are obtained, and among others, the superlinear convergence is established under strict complementarity. Preliminary numerical results are reported for DIMACS second-order cone programs, which confirm the favorable theoretical properties of the method.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  2. Alizadeh, F., Schmieta, S.: Symmetric cones, potential reduction methods, and word-by-word extensions. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, pp. 195–233. Kluwer Academic, Boston (2000)

    Google Scholar 

  3. Andersen, E.D., Roos, C., Terlaky, T.: On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Program. Ser. B 95, 249–277 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen, J.-S., Pan, S.-H.: A one-parametric class of merit functions for the second-order cone complementarity problem. Comput. Optim. Appl. (2008, accepted)

  5. Chen, X., Qi, H.: Cartesian P-property and its applications to the semidefinite linear complementarity problem. Math. Program. 106, 177–201 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Chen, J.-S., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293–327 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chen, X.-D., Sun, D., Sun, J.: Complementarity functions and numerical experiments for second-order cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reprinted by SIAM, Philadelphia (1990)

    MATH  Google Scholar 

  9. De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75, 407–439 (1996)

    Article  Google Scholar 

  10. Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. Oxford University Press, New York (1994)

    MATH  Google Scholar 

  11. Fischer, A.: A special Newton-type optimization methods. Optimization 24, 269–284 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  12. Fischer, A.: Solution of the monotone complementarity problem with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997)

    Google Scholar 

  13. Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12, 436–460 (2002)

    Article  MathSciNet  Google Scholar 

  14. Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  15. Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kanzow, C., Fukushima, M.: Semismooth methods for linear and nonlinear second-order cone programs. Technical Report, Department of Applied Mathematics and Physics, Kyoto University (2006)

  17. Kanzow, C., Kleinmichel, H.: A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput. Optim. Appl. 11, 227–251 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  18. Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Application of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  19. Monteiro, R.D.C., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions. Math. Program. 88, 61–83 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. Pan, S.-H., Chen, J.-S.: A damped Gauss-Newton method for the second-order cone complementarity problem. Appl. Math. Optim. (2008, accepted)

  21. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  22. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  Google Scholar 

  23. Schmieta, S., Alizadeh, F.: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26, 543–564 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  24. Sun, D., Qi, L.-Q.: On NCP-functions. Comput. Optim. Appl. 13, 201–220 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  25. Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program. 103, 575–581 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  26. Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11, 141–182 (1999)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, South China University of Technology, Guangzhou, 510640, People’s Republic of China

    Shaohua Pan

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

    Jein-Shan Chen

Authors
  1. Shaohua Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jein-Shan Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jein-Shan Chen.

Additional information

S. Pan work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province.

J.-S. Chen member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work is partially supported by National Science Council of Taiwan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pan, S., Chen, JS. A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions. Comput Optim Appl 45, 59–88 (2010). https://doi.org/10.1007/s10589-008-9166-9

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9166-9

Keywords

Search

Navigation