Newton’s method for computing the nearest correlation matrix with a simple upper bound. (English) Zbl 1229.90118
A semismooth Newton method is extended to the nearest correlation matrix problem with a simple upper bound. Unlike the original semismooth Newton method proposed by H. Qi and D. Sun [SIAM J. Matrix Anal. Appl. 28, No. 2, 360–385 (2006; Zbl 1120.65049)] for the unbounded nearest correlation matrix problem, constraint nondegeneracy does not always hold for the optimal solution and thereby the method may lose its quadratic convergence property. The primal nondegeneracy is shown to be equivalent to the positive definiteness of every generalized Hessian (in the sense of Clarke) of the dual objective function. The authors show a quadratic convergence result for a modified semismooth Newton algorithm by adding a perturbation term to the generalized Hessian. Extensive numerical experiments are included.
Reviewer: Satoshi Ito (Tokyo)
MSC:
| 90C22 | Semidefinite programming |
| 49M15 | Newton-type methods |
| 65K05 | Numerical mathematical programming methods |
Keywords:
semismooth Newton method; nearest correlation matrix; constraint nondegeneracy; quadratic convergenceCitations:
Zbl 1120.65049References:
| [1] | Higham, N.J.: Computing the nearest correlation matrix–a problem from finance. IMA J. Numer. Anal. 22, 329–343 (2002) · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329 |
| [2] | Malick, J.: A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26, 272–284 (2004) · Zbl 1080.65027 · doi:10.1137/S0895479802413856 |
| [3] | Boyd, S., Xiao, L.: Least-squares covariance matrix adjustment. SIAM J. Matrix Anal. Appl. 27, 532–546 (2005) · Zbl 1099.65039 · doi:10.1137/040609902 |
| [4] | Toh, K.C., Tütüncü, R.H., Todd, M.J.: Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pac. J. Optim. 3, 135–164 (2007) · Zbl 1136.90026 |
| [5] | Toh, K.C.: An inexact primal-dual path-following algorithm for convex quadratic SDP. Math. Program. 112, 221–254 (2008) · Zbl 1136.90027 · doi:10.1007/s10107-006-0088-y |
| [6] | Qi, H.-D., Sun, D.F.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360–385 (2006) · Zbl 1120.65049 · doi:10.1137/050624509 |
| [7] | Borsdorf, R., Higham, N.J.: A preconditioned Newton algorithm for the nearest correlation matrix. IMA J. Numer. Anal. 94, 94–107 (2010) · Zbl 1188.65055 · doi:10.1093/imanum/drn085 |
| [8] | Gao, Y., Sun, D.F.: Calibrating least squares covariance matrix problems with equality and inequality constraints. SIAM J. Matrix Anal. Appl. 31, 1423–1457 (2010) · Zbl 1201.49031 · doi:10.1137/080727075 |
| [9] | Qi, H.-D., Sun, D.F.: Correlation stress testing for value-at-risk: an unconstrained convex optimization approach. Comput. Optim. Appl. 45, 427–462 (2010) · Zbl 1198.91091 · doi:10.1007/s10589-008-9231-4 |
| [10] | Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974) · Zbl 0296.90036 |
| [11] | Deutsch, F.: Best Approximation in Inner Product Spaces. CMS Books in Mathematics, vol. 7. Springer, New York (2001) · Zbl 0980.41025 |
| [12] | Borwein, J., Lewis, A.S.: Partially finite convex programming I: Quasi relative interiors and duality theory. Math. Program. 57, 15–48 (1992) · Zbl 0778.90049 · doi:10.1007/BF01581072 |
| [13] | Sun, D.F., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002) · Zbl 1082.49501 · doi:10.1287/moor.27.1.150.342 |
| [14] | Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275 |
| [15] | Kummer, B.: Newton’s method for nondifferentiable functions. In: Guddat, J., Bank, B., Hollatz, H., Kall, P., Klatte, D., Kummer, B., Lommatzsch, K., Tammer, L., Vlach, M., Zimmerman, K. (eds.) Advances in Mathematical Optimization, pp. 114–125. Academie Verlag, Berlin (1988) |
| [16] | Werner, R., Schöettle, K.: Calibration of correlation matrices–SDP or not SDP. Technical Report, Munich University of Technology (2007) |
| [17] | Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimizations. SIAM J. Optim. 5, 13–51 (1995) · Zbl 0833.90087 · doi:10.1137/0805002 |
| [18] | Dattorro, J.: Convex Optimization and Euclidean Distance Geometry. Meboo Publishing USA, California (2005) · Zbl 1142.15014 |
| [19] | Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000) · Zbl 0966.49001 |
| [20] | Bonnans, J.F., Shapiro, A.: Nondegeneracy and quantitative stability of parameterized optimization problems with multiple solutions. SIAM J. Optim. 8, 940–946 (1998) · Zbl 0912.90266 · doi:10.1137/S1052623497316518 |
| [21] | Shapiro, A., Fan, M.K.H.: On eigenvalue optimization. SIAM J. Optim. 5, 552–569 (1995) · Zbl 0838.90115 · doi:10.1137/0805028 |
| [22] | Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111–128 (1997) · Zbl 0890.90141 |
| [23] | Chan, Z.X., Sun, D.F.: Constraint nondegeneracy, strong regularity and nonsingularity in semidefinite programming. SIAM J. Optim. 19, 370–396 (2008) · Zbl 1190.90116 · doi:10.1137/070681235 |
| [24] | Sun, D.F.: The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31, 761–776 (2006) · Zbl 1278.90304 · doi:10.1287/moor.1060.0195 |
| [25] | Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1735–1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206 |
| [26] | Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409–436 (1952) · Zbl 0048.09901 |
| [27] | Kočvara, M., Stingl, M.: PENNON: a generalized augmented Lagrangian method for semidefinite programming. Optim. Method. Softw. 18, 317–333 (2003) · Zbl 1037.90003 · doi:10.1080/1055678031000098773 |
| [28] | Zhao, X.Y.: A semismooth Newton-CG augmented Lagrangian method for large scale linear and convex quadratic SDPs. Ph.D. thesis, National University of Singapore (2009) |
| [29] | Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20, 336–356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575 |
| [30] | Chen, X., Qi, L., Sun, D.F.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998) · Zbl 0894.90143 · doi:10.1090/S0025-5718-98-00932-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
