Skip to main content
SpringerLink
Log in

Merit functions for semi-definite complemetarity problems

  • Published:
Mathematical Programming Submit manuscript

Abstract

Merit functions such as the gap function, the regularized gap function, the implicit Lagrangian, and the norm squared of the Fischer-Burmeister function have played an important role in the solution of complementarity problems defined over the cone of nonnegative real vectors. We study the extension of these merit functions to complementarity problems defined over the cone of block-diagonal symmetric positive semi-definite real matrices. The extension suggests new solution methods for the latter problems.

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. F. Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization. SIAM Journal on Optimization 5 (1995) 13–51.

    Article  MATH  MathSciNet  Google Scholar 

  2. F. Alizadeh, J.-P.A. Haeberly, M.L. Overton, Primal-dual interior point methods for semidefinite programming, Working paper, RUTCOR, Rutgers University, New Brunswick, 1994.

    Google Scholar 

  3. G. Auchmuty, Variational principles for variational inequalities. Numerical Functional Analysis and Optimization 10 (1989) 863–874.

    Article  MathSciNet  MATH  Google Scholar 

  4. A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976.

    MATH  Google Scholar 

  5. S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, 1994.

    MATH  Google Scholar 

  6. C. Chen, O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications 5 (1996) 97–138.

    Article  MATH  MathSciNet  Google Scholar 

  7. R.W. Cottle, J.-S. Pang, R.E. Stone, The Linear Complementarity Problems, Academic Press, New York, 1992.

    Google Scholar 

  8. T. De Luca, F. Facchinei, C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming 75 (1996) 407–439.

    MathSciNet  Google Scholar 

  9. Y.G. Evtushenko, V.A. Purtov, Sufficient conditions for a minimum for nonlinear programming problems, Soviet Mathematics Doklady 30 (1984) 313–316.

    MATH  Google Scholar 

  10. F. Facchinei, C. Kanzow, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Mathematical Programming 76 (1997) 493–512.

    MathSciNet  Google Scholar 

  11. F. Facchinei, C. Kanzow, On unconstrained and constrained stationary points of the implicit Lagrangian, Journal of Optimization Theory and Applications 94 (1997) 99–115.

    Article  MathSciNet  Google Scholar 

  12. F. Facchinei, A. Fischer, C. Kanzow, Inexact Newton methods for semismooth equations with applications to variational inequality problems, in: G. Di Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Applications., Plenum Press, New York, 1996, pp. 125–139.

    Google Scholar 

  13. F. Facchinei, J. Soares, Testing a new class of algorithms for nonlinear complementarity problems, in: F. Giannessi, A. Maugeri (Eds.), Variational Inequalities and Network Equilibrium Problems, Plenum Press, New York, 1995, pp. 69–83.

    Google Scholar 

  14. F. Facchinei, J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal on Optimization 7 (1997) 225–247.

    Article  MATH  MathSciNet  Google Scholar 

  15. A. Fischer, A special Newton-type optimization method, Optimization 24 (1992) 269–284.

    Article  MATH  MathSciNet  Google Scholar 

  16. A. Fischer, An NCP-function and its use for the solution of complementarity problems, in: D.-Z. Du, L. Qi, R. Womersley, (Eds.), Recent Advances in Nonsmooth Optimization, World Scientific, Singapore, 1995, pp. 88–105.

    Google Scholar 

  17. A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems, Journal of Optimization Theory and Applications 86 (1995) 585–608.

    Article  MATH  MathSciNet  Google Scholar 

  18. A. Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions, Optimization Methods and Software 6 (1995) 83–107.

    Article  Google Scholar 

  19. A. Fischer, Solution of the monotone complementarity problem with locally Lipschitzian functions, Mathematical Programming 76 (1997) 513–532.

    MathSciNet  Google Scholar 

  20. M. Fukushima, Equivalent, differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming 53 (1992) 99–110.

    Article  MATH  MathSciNet  Google Scholar 

  21. M. Fukushima, Merit functions for variational inequality and complementarity problems, in: G. Di Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Applications, Plenum Press, New York, 1996, pp. 155–170.

    Google Scholar 

  22. C. Geiger, C. Kanzow, On the resolution of monotone complementarity problems., Computational Optimization and Applications 5 (1996) 155–173.

    Article  MATH  MathSciNet  Google Scholar 

  23. M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association of Computing Machinery (to appear); A preliminary version appeared in Proceedings of the 26th Annual ACM Symposium on Theory of Computing 1994.

  24. D.W. Hearn, The gap function of a convex program, Operations Research Letters 1 (1982) 67–71.

    Article  MATH  MathSciNet  Google Scholar 

  25. C. Helmberg, F. Rendl, R.J. Vanderbei, H. Wolkowicz, An interior-point method for semidefinite programming, SIAM Journal on Optimization 6 (1996) 342–361.

    Article  MATH  MathSciNet  Google Scholar 

  26. R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.

    MATH  Google Scholar 

  27. F. Jarre, An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, SIAM Journal on Control and Optimization 31 (1993) 1360–1377.

    Article  MATH  MathSciNet  Google Scholar 

  28. H. Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, Journal of Global Optimization 9 (1996) 169–181.

    Article  MATH  Google Scholar 

  29. H. Jiang, L. Qi, A new nonsmooth equations approach to nonlinear complementarities, SIAM Journal on Control and Optimization 35 (1997) 178–193.

    Article  MATH  MathSciNet  Google Scholar 

  30. C. Kanzow, Some equation-based methods for the nonlinear complementarity problem, Optimization Methods and Software 3 (1994) 327–340.

    Article  Google Scholar 

  31. C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems, SIAM Journal on Optimization 6 (1996) 326–341.

    Article  MATH  MathSciNet  Google Scholar 

  32. C. Kanzow, Nonlinear complementarity as unconstrained optimization, Journal of Optimization Theory and Applications 88 (1996) 139–155.

    Article  MATH  MathSciNet  Google Scholar 

  33. C. Kanzow, M. Fukushima, Equivalence of the generalized complementarity problem to differentiable unconstrained minimization, Journal of Optimization Theory and Applications 90 (1996) 581–603.

    Article  MATH  MathSciNet  Google Scholar 

  34. C. Kanzow, H. Kleinmichel, A class of Newton-type methods for equality and inequality constrained optimization, Optimization Methods and Software 5 (1995) 173–198.

    Article  Google Scholar 

  35. M. Kojima, S. Shindoh, S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problems, SIAM Journal of Optimization 7 (1997) 86–125.

    Article  MATH  MathSciNet  Google Scholar 

  36. T. Larsson, M. Patriksson, A class of gap functions for variational inequalities. Mathermatical Programming 64 (1994) 53–79.

    Article  MathSciNet  Google Scholar 

  37. X.-D. Luo, P. Tseng, On a global projection-type error bound for the linear complernentarity problem, Linear Algebra and Its Applications 253 (1997) 251–278.

    Article  MATH  MathSciNet  Google Scholar 

  38. Z.-Q. Luo, O.L. Mangasarian, J. Ren, M.V. Solodov, New error bounds for the linear complementarity problem, Mathematics of Operations Research 19 (1994) 880–892.

    MATH  MathSciNet  Google Scholar 

  39. Z.-Q. Luo, J.-S. Pang. Error bounds for analytic systems and their applications, Mathematical Programming 67 (1995) 1–28.

    Article  MathSciNet  Google Scholar 

  40. Z.-Q. Luo, P. Tseng, On a global error bound for a class of monotone affine variational inequality problems, Operations Research Letters 11 (1992) 159–165.

    Article  MATH  MathSciNet  Google Scholar 

  41. Z.-Q., Luo, P. Tseng, Error bounds and convergence analysis of feasible descent methods: A general approach, Annals of Operations Research 46 (1993) 157–178.

    Article  MathSciNet  Google Scholar 

  42. Z.-Q. Luo, P. Tseng, A new class of merit functions for the nonlinear complementarity problem, in: M.C. Ferris, J.S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, 1997, pp. 204–225.

    Google Scholar 

  43. O.L. Mangasarian, Equivalence of the complementarity problem, to a system of nonlinear equations, SIAM Journal of Applied Mathematics 31 (1976) 89–92.

    Article  MathSciNet  MATH  Google Scholar 

  44. O.L. Mangasarian, M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization, Mathematical Programming 62 (1993) 277–297.

    Article  MathSciNet  Google Scholar 

  45. R. Mathias, J.-S. Pang, Error bounds for the linear complementarity problem with aP-matrix, Linear Algebra and Its Applications 132 (1990) 123–136.

    Article  MATH  MathSciNet  Google Scholar 

  46. Y.E. Nesterov, A.S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, 1993.

    Google Scholar 

  47. Y.E. Nesterov, M.J. Todd, Primal-dual interior-point methods for self-scaled cones, Technical report 1125, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, 1995; revised February 1996.

    Google Scholar 

  48. J.-S. Pang. A Posteriori Error bounds for the linearly-constrained variational inequality problem, Mathematics of Operations Research 12 (1987) 474–484.

    Article  MathSciNet  Google Scholar 

  49. J.-S. Pang, Complementarity problems, in: R. Horst, P. Pardalos (Eds.), Handbook on Global Optimization, Kluwer Academic Publishers, Norwell, 1995, pp. 271–338.

    Google Scholar 

  50. J.-S. Pang, S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Mathematical Programming 60 (1993) 295–337.

    Article  MathSciNet  Google Scholar 

  51. G. Pataki, Cone-LP's and semidefinite programs: Geometry and a simplex-type method, in: W.H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization: Proceedings of 5th International IPCO Conference, Springer, Heidelberg, 1996, pp. 162–174.

    Google Scholar 

  52. J.-M. Peng, Equivalence of variational inequality problems to unconstrained minimization, Mathematical Programming 78 (1997) 347–355.

    MathSciNet  Google Scholar 

  53. J.-M. Peng, The convexity of the implicit Lagrangian, Journal of Optimization Theory and Applications 92 (1997) 331–341.

    Article  MATH  MathSciNet  Google Scholar 

  54. F. Potra, R. Sheng, A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming, Reports on Computational Mathematics 78, Department of Mathematics, University of Iowa, Iowa City, 1995.

    Google Scholar 

  55. H.-D. Qi, X. Chen, On stationary points of merit functions for semi-definite complermentarity problems, Report, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, Beijing, 1997.

    Google Scholar 

  56. R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.

    MATH  Google Scholar 

  57. M. Shida, S. Shindoh, Monotone semidefinite complementarity problems, Research Report 312, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, March 1996, revised April 1996.

    Google Scholar 

  58. M.V. Solodov, P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization 34 (1996) 1814–1830.

    Article  MATH  MathSciNet  Google Scholar 

  59. P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problem, Journal of Optimization Theory and Applications 89 (1996) 17–37.

    Article  MATH  MathSciNet  Google Scholar 

  60. P. Tseng, Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP, Report, Department of Mathematics, University of Washington, Seattle, June 1996 (to appear in Optimization, Methods and Software).

    Google Scholar 

  61. P. Tseng, N. Yamashita, M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach, SIAM Journal of Optimization 6 (1996) 446–460.

    Article  MATH  MathSciNet  Google Scholar 

  62. L. Vandenberghe, S. Boyd, A primal-dual potential, reduction method for problems involving matrix inequalities, Mathematical Programming 69 (1995) 205–236.

    MathSciNet  Google Scholar 

  63. N. Yamashita, M. Fukushima, Equivalent unconstrained minimization and global error bounds for variational inequality problems, SIAM Journal on Control and Optimization 35 (1997) 73–284.

    Article  MathSciNet  Google Scholar 

  64. N. Yamashita, M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications 84 (1995) 653–663.

    Article  MATH  MathSciNet  Google Scholar 

  65. N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, Journal of Optimization Theory and Applications 92 (1997) 439–456.

    Article  MATH  MathSciNet  Google Scholar 

  66. E.H. Zarantonello, Projections on convex sets in Hilbert space and spectral theory, in: E.H. Zarantonello (Ed.), Contributions to Nonlinear Functional Analysis, Academic Press, New York, 1971, pp. 237–424.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Washington, 98195, Seattle, WA, USA

    Paul Tseng

Authors
  1. Paul Tseng
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research is supported by National Science Foundation Grant CCR-9311621.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tseng, P. Merit functions for semi-definite complemetarity problems. Mathematical Programming 83, 159–185 (1998). https://doi.org/10.1007/BF02680556

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02680556

Keywords

Search

Navigation