Skip to main content
SpringerLink
Log in

Smoothing algorithms for complementarity problems over symmetric cones

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

Abstract

There recently has been much interest in studying optimization problems over symmetric cones. In this paper, we first investigate a smoothing function in the context of symmetric cones and show that it is coercive under suitable assumptions. We then extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones, and prove the proposed algorithms are globally convergent under suitable assumptions. We also give a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for second-order cone complementarity problems are reported.

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., Schmieta, S.H.: Symmetric cones, potential reduction methods and word-by-word extensions. In: Sail, R., Vandenberghe, L., Wolkowicz, H. (eds.) Handbook of Semidefinite Programming, Theory, Algorithms and Applications, pp. 195–233. Kluwer Academic, Dordrecht (2000)

    Google Scholar 

  2. Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Math. Program. 87, 113–130 (2000)

    MATH  MathSciNet  Google Scholar 

  3. Chen, X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen, B., Harker, P.T.: A non-interior-point continuation method for linear complementarity problem. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chen, J.-S.: The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem. J. Glob. Optim. 36, 565–580 (2006)

    Article  MATH  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., Ye, Y.: On homotopy-smoothing methods for variational inequalities. SIAM J. Control Optim. 37, 589–616 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chen, X., Tseng, P.: Non-interior continuous methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chen, X., Sun, D., Sun, J.: Complementarity function and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Engelke, S., Kanzow, C.: Improved non-interior continuation methods for the solution of linear programming. Numer. Math. 90, 487–507 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Facchinei, F., Kanzow, C.: Beyond monotonicity in regularization methods for nonlinear complementarity problems. SIAM J. Control Optim. 37, 1150–1161 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  12. Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  13. Faraut, U., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. Oxford University Press, Oxford (1994)

    Google Scholar 

  14. Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149–175 (1987)

    Article  MathSciNet  Google Scholar 

  15. Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1, 331–357 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  16. Faybusovich, L., Lu, Y.: Jordan-algebraic aspects of nonconvex optimization over symmetric cones. Appl. Math. Optim. 53, 67–77 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Faybusovich, L., Tsuchiya, T.: Primal-dual algorithms and inifite-dimensional Jordan algebras of finite rank. Math. Program. 97, 471–493 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  18. Gowda, M.S., Sznajder, R.: Some global uniqueness and solvability results for linear complementarity problems over symmetric cones. SIAM J. Optim. 18, 461–481 (2006)

    Article  MathSciNet  Google Scholar 

  19. Gowda, M.S., Sznajder, R.: Automorphism invariance of P and GUS properties of linear transformations in Euclidean Jordan algebras. Math. Oper. Res. 31, 109–123 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  20. Gowda, M.S., Sznajder, R., Tao, J.: Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 393, 203–232 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. 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 

  22. Huang, Z.H., Han, J., Chen, Z.: A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P 0 function. J. Optim. Theory Appl. 117, 39–68 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  23. Huang, Z.H., Liu, X.H.: Extension of smoothing Newton algorithms to solve linear programming over symmetric cones. Technique Report, Department of Mathematics, School of Science, Tianjin University, China (2007)

  24. Huang, Z.H., Sun, D., Zhao, G.Y.: A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput. Optim. Appl. 35, 199–237 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  25. Huang, Z.H., Sun, J.: A non-interior continuation algorithm for the P 0 or P * LCP with strong global local convergence properties. Appl. Math. Optim. 26, 237–262 (2005)

    Article  MathSciNet  Google Scholar 

  26. Huang, Z.H., Xu, S.W.: Convergence properties of a non-interior-point smoothing algorithm for the P * NCP. J. Ind. Manage. Optim. 3, 569–584 (2007)

    MATH  MathSciNet  Google Scholar 

  27. Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17, 851–868 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  28. Kanzow, C., Nagel, C.: Semidefinite programs: new search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13, 1–23 (2003)

    Article  MathSciNet  Google Scholar 

  29. Kong, L.C., Xiu, N.H.: New smooth C-functions for symmetric cone complementarity problems. Opt. Lett. 1, 391–400 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  30. Korányi, A.: Monotone functions on formally real Jordan algebras. Math. Ann. 269, 73–76 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  31. Lin, Y., Yoshise, A.: A homogeneous model for mixed complementarity problems over symmetric cones. Technique Report, Graduate School of Systems and Information Engineering, University of Tsukuba, Japan (2005)

  32. Palais, R.S., Terng, C.-L.: Critical Point Theory and Submanifold Geometry. Lecture Notes in Mathematics, vol. 1353. Springer, Berlin (1988)

    MATH  Google Scholar 

  33. Qi, H.D.: A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions. SIAM J. Optim. 10, 315–330 (2000)

    Article  MathSciNet  Google Scholar 

  34. Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  36. Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 96, 409–438 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  37. Smale, S.: Algorithms for solving equations. In: Gleason, A.M. (ed.) Proceeding of International Congress of Mathematicians, pp. 172–195. American Mathematics Society, Providence (1987)

    Google Scholar 

  38. Sun, D., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  39. Sun, D., Sun, J.: Löwner’s operator and spectral functions in Euclidean Jordan algebras. Math. Oper. Res. 33 (2008, in press)

  40. Sun, J., Sun, D., Qi, L.: A square smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems. SIAM J. Optim. 14, 783–806 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  41. Tseng, P.: Merit functions for semidefinite complementarity problems. Math. Program. 83, 159–185 (1998)

    MathSciNet  Google Scholar 

  42. Yoshise, A.: Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J. Optim. 17, 1129–1153 (2006)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, People’s Republic of China

    Zheng-Hai Huang & Tie Ni

Authors
  1. Zheng-Hai Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tie Ni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zheng-Hai Huang.

Additional information

This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huang, ZH., Ni, T. Smoothing algorithms for complementarity problems over symmetric cones. Comput Optim Appl 45, 557–579 (2010). https://doi.org/10.1007/s10589-008-9180-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9180-y

Keywords

Search

Navigation