Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T03:01:17.439Z Has data issue: false hasContentIssue false
  • English
  • Français

PREDICTOR–CORRECTOR SMOOTHING NEWTON METHOD FOR SOLVING SEMIDEFINITE PROGRAMMING

Published online by Cambridge University Press:  17 April 2009

CAIYING WU  and
GUOQING CHEN
CAIYING WU*
Affiliation:
College of Mathematics Science, Inner Mongolia University, Hohhot 010021, People’s Republic of China (email: [email protected])
GUOQING CHEN
Affiliation:
College of Mathematics Science, Inner Mongolia University, Hohhot 010021, People’s Republic of China (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

There has been much interest recently in smoothing methods for solving semidefinite programming (SDP). In this paper, based on the equivalent transformation for the optimality conditions of SDP, we present a predictor–corrector smoothing Newton algorithm for SDP. Issues such as the existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence of our algorithm are studied under suitable assumptions.

Keywords

semidefinite complementaritysemidefinite programmingFischer–Burmeister functionsuperlinear convergence

MSC classification

Secondary: 90C22: Semidefinite programming
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 79 , Issue 3 , June 2009 , pp. 367 - 376
Copyright
Copyright © Australian Mathematical Society 2009

Footnotes

Project supported by the Teaching and Research Award Program for the Outstanding Young Teachers in Higher Education Institutes of Ministry of Education, People’s Republic of China.

References

[1] Alizadeh, F., Haeberly, J. P. A. and Overton, M. L., ‘Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results’, SIAM J. Optim. 8(3) (1998), 746–768.CrossRefGoogle Scholar
[2] Burer, S., ‘Semidefinite programming in the space of partial positive semidefinite matrices’, SIAM J. Optim. 14(1) (2003), 139–172.CrossRefGoogle Scholar
[3] Chen, X. and Tseng, P., ‘Noninterior continuation methods for solving semidefinite complementarity problems’, Math. Program., Ser. A 95 (2003), 431–474.CrossRefGoogle Scholar
[4] Helmberg, C., Rendl, F., Vanderbei, R. J. and Wolkowicz, H., ‘An interior-point method for semidefinite programming’, SIAM J. Optim. 6(2) (1996), 342–361.CrossRefGoogle Scholar
[5] Horn, R. A. and Johnson, C. R., Matrix Analysis (Cambridge University Press, New York, 1985).CrossRefGoogle Scholar
[6] Kanzow, C. and Nagel, C., ‘Semidefinite programs: new search directions, smoothing-type methods, and numerical results’, SIAM J. Optim. 13(1) (2002), 1–23.CrossRefGoogle Scholar
[7] Kojima, M., Shindoh, S. and Hara, S., ‘Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices’, SIAM J. Optim. 7 (1997), 86–125.CrossRefGoogle Scholar
[8] Monteiro, R. D. C., ‘Primal-dual path following algorithms for semidefinite programming’, SIAM J. Optim. 7 (1997), 663–678.CrossRefGoogle Scholar
[9] Monteiro, R. D. C. and Zhang, Y., ‘A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming’, Math. Program. 81 (1998), 281–299.CrossRefGoogle Scholar
[10] Qi, L. Q. and Sun, J., ‘A nonsmooth version of Newton’s method’, Math. Program. 58 (1993), 353–368.CrossRefGoogle Scholar
[11] Qi, L. Q., Sun, D. F. and Zhou, G. L., ‘A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities’, Math. Program., Ser. A 87 (2000), 1–35.CrossRefGoogle Scholar
[12] Toh, K. C., ‘Solving large scale semidefinite programs via an iterative solver on the agumented systems’, SIAM J. Optim. 14 (2004), 670–698.CrossRefGoogle Scholar
[13] Toh, K. C. and Kojima, M., ‘Solving some large scale semidefinite programs via the conjugate residual method’, SIAM J. Optim. 12 (2002), 669–691.CrossRefGoogle Scholar
[14] Tseng, P., ‘Merit functions for semidefinite complementarity problems’, Math. Program. 83 (1998), 159–185.CrossRefGoogle Scholar
[15] Wolkowicz, H., Bibliography on semidefinite programming, http://liinwww.ira.uka.de/bibliography/math/psd.html.Google Scholar
[16] Wolkowicz, H., Saigal, R. and Vandenberghe, L., Handbook of Semidefinite Programming (Kluwer Academic, Boston, MA, 2000).CrossRefGoogle Scholar
[17] Zhang, Y., ‘On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming’, SIAM J. Optim. 8(2) (1998), 365–386.CrossRefGoogle Scholar
[18] Zhang, L. P. and Gao, Z. Y., ‘Superlinearly/quadratic one-step smoothing Newton method for P 0-NCP without strict complementarity’, Math. Methods Oper. Res. 56 (2002), 231–241.CrossRefGoogle Scholar
[19] Zhang, L. P., Han, J. Y. and Huang, Z. H., ‘Superlinear/quadratic one-step smoothing Newton method for P 0-NCP’, Acta Math. Sin., Engl. Ser. 21(1) (2005), 117–128.CrossRefGoogle Scholar