Projection methods in conic optimization. (English) Zbl 1334.90105
Anjos, Miguel F. (ed.) et al., Handbook on semidefinite, conic and polynomial optimization. New York, NY: Springer (ISBN 978-1-4614-0768-3/hbk; 978-1-4614-0769-0/ebook). International Series in Operations Research & Management Science 166, 565-600 (2012).
Summary: There exist efficient algorithms to project a point onto the intersection of a convex conic and an affine subspace. Those conic projections are in turn the work-horse of a range of algorithms in conic optimization, having a variety of applications in science, finance and engineering. This chapter reviews some of these algorithms, emphasizing the so-called regularization algorithms for linear conic optimization, and applications in polynomial optimization. This is a presentation of the material of several recent research articles; we aim here at clarifying the ideas, presenting them in a general framework, and pointing out important techniques.
For the entire collection see [Zbl 1235.90002].
For the entire collection see [Zbl 1235.90002].
MSC:
| 90C22 | Semidefinite programming |
| 90C90 | Applications of mathematical programming |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
References:
| [1] | Al-Homidan, S., Solving Hankel matrix approximation problem using semidefinite programming, Journal of Computational and Applied Mathematics, 202, 2, 304-314 (2007) · Zbl 1117.65083 · doi:10.1016/j.cam.2006.02.033 |
| [2] | Alizadeh, F.; Haeberly, J-P, Overton, M: Complementarity and nondegeneracy in semidefinite programming. Math. Program., 77, 2, 111-128 (1997) · Zbl 0890.90141 |
| [3] | Anjos, MF; Higham, NJ; Takouda, PL; Wolkowicz, H., A semidefinite programming approach for the nearest correlation matrix problem (2003), Combinatorics and Optimization, University of Waterloo, September: Technical report, Combinatorics and Optimization, University of Waterloo, September |
| [4] | Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Linear and Nonlinear Programming. Stanford University Press (1959) · Zbl 0091.16002 |
| [5] | Bolte, J.; Daniilidis, A.; Lewis, A., Tame functions are semismooth. Math. Program., 117, 1, 5-19 (2008) · Zbl 1158.49030 |
| [6] | Bertsekas, D.P.: Nonlinear Programming. Athena Scientific (1995) · Zbl 0935.90037 |
| [7] | Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory. Studies in Applied Mathematics. SIAM (1994) · Zbl 0816.93004 |
| [8] | Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Springer Verlag (2003) · Zbl 1014.65045 |
| [9] | Borsdorf, R.; Higham, N., A preconditionned Newton algorithm for the nearest correlation matrix, IMA J. Numer. Anal., 30, 1, 94-107 (2010) · Zbl 1188.65055 · doi:10.1093/imanum/drn085 |
| [10] | Bellman, R., Kalaba, R., Lockett, J.: Numerical Inversion of the Laplace Transform. Elsevier (1966) · Zbl 0147.14003 |
| [11] | Brigo, D., Mercurio, F.: Interest rate models: theory and practice. Springer-Verlag (2006) · Zbl 1109.91023 |
| [12] | Burer, S., Monteiro, R., Zhang, Y.: A computational study of a gradient-based log-barrier algorithm for a class of large-scale sdps. Mathematical Programming Series B, 359-379, 2001. · Zbl 1030.90076 |
| [13] | Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Verlag (2000) · Zbl 0966.49001 |
| [14] | Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press (2004) · Zbl 1058.90049 |
| [15] | Burer, S.; Vandenbussche, D., Solving lift-and-project relaxations of binary integer programs, SIAM Journal on Optimization, 16, 726-750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574 |
| [16] | Boyd, S., Xiao, L.: Least-squares covariance matrix adjustment. SIAM Journal on Matrix Analysis and Applications 27(2) (2005) · Zbl 1099.65039 |
| [17] | Correa, R.; Lemaréchal, C., Convergence of some algorithms for convex minimization, Mathematical Programming, 62, 2, 261-275 (1993) · Zbl 0805.90083 · doi:10.1007/BF01585170 |
| [18] | Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley (1983); reprinted by SIAM, (1983) · Zbl 0582.49001 |
| [19] | Dembo, R., Eisenstat, S., Steihaug, T.: Inexact Newton methods. SIAM Journal on Numerical Analysis 19(2) (1982) · Zbl 0478.65030 |
| [20] | Deutsch, F., Best Approximation in Inner Product Spaces (2001), New York: Springer, New York · Zbl 0980.41025 |
| [21] | Douglas, J.; Rachford, HH, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82, 421-439 (1956) · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4 |
| [22] | Dukanovic, I.; Rendl, F., Semidefinite programming relaxations for graph coloring and maximal clique problems, Mathematical Programming, 109, 345-365 (2007) · Zbl 1278.90299 · doi:10.1007/s10107-006-0026-z |
| [23] | Dumitrescu, B.: Positive Trigonometric Polynomials and Signal Processing Applications. Springer Verlag (2007) · Zbl 1126.93005 |
| [24] | Dykstra, RL, An algorithm for restricted least-square regression, Journal of the American Statistical Association, 78, 837-842 (1983) · Zbl 0535.62063 · doi:10.2307/2288193 |
| [25] | Gilbert, JCh; Lemaréchal, C., Some numerical experiments with variable-storage quasi-Newton algorithms, Mathematical Programming, 45, 407-435 (1989) · Zbl 0694.90086 · doi:10.1007/BF01589113 |
| [26] | Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Computers and Mathematics with Applications 2 (1976) · Zbl 0352.65034 |
| [27] | Gao, Y.; Sun, D., Calibrating least squares semidefinite programming with equality and inequality constraints, SIAM J. Matrix Anal. Appl., 31, 3, 1432-1457 (2009) · Zbl 1201.49031 · doi:10.1137/080727075 |
| [28] | Gao, Y., Sun, D.: A majorized penalty approach for calibrating rank constrained correlation matrix problems. Technical report, Univ. of Singapore (2003) |
| [29] | Goemans, M.; Williamson, D., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 6, 1115-1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [30] | Henrion, D.; Garulli, A., Positive polynomials in control (2005), Springer Verlag: LNCIS, Springer Verlag · Zbl 1059.93002 |
| [31] | Higham, N., Computing a nearest symmetric positive semidefinite matrix, Linear Algebra and its Applications, 103, 103-118 (1988) · Zbl 0649.65026 · doi:10.1016/0024-3795(88)90223-6 |
| [32] | Higham, N., Computing a nearest symmetric correlation matrix — a problem from finance, IMA Journal of Numerical Analysis, 22, 3, 329-343 (2002) · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329 |
| [33] | Henrion, D., Lasserre, J.-B.: Detecting global optimality and extracting solutions in gloptipoly. In: Henrion, D., Garulli, A., (eds.) Positive polynomials in control, LNCIS. Springer (2005) · Zbl 1119.93301 |
| [34] | Henrion, D.; Malick, J., Projection methods for conic feasibility problems; application to sum-of-squares decompositions, Optimization Methods and Software, 26, 1, 23-46 (2011) · Zbl 1228.90071 · doi:10.1080/10556780903191165 |
| [35] | Hiriart-Urruty, J.-B. Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer Verlag, Heidelberg (1993) Two volumes. · Zbl 0795.49001 |
| [36] | Hiriart-Urruty, J-B; Strodiot, JJ; Nguyen, HV, Generalized hessian matrix and second-order optimality conditions for problems with C^1, 1 data, Applied Mathematics and Optimization, 11, 43-56 (1984) · Zbl 0542.49011 · doi:10.1007/BF01442169 |
| [37] | He, B., Xu, M., Yuan, X.: Solving large-scale least-squares covariance matrix problems by alternating direction methods. Technical report (2009) |
| [38] | Jarre, F., Rendl, F.: An augmented primal-dual method for linear conic problems. SIAM Journal on Optimization (2008) · Zbl 1173.90497 |
| [39] | Johnson, DJ; Trick, MA, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, 11-13 October 1993 (1996), Boston, MA, USA: American Mathematical Society, Boston, MA, USA · Zbl 0875.68678 |
| [40] | Kočvara, M.; Stingl, M., PENNON: a code for convex nonlinear and semidefinite programming, Optimisation Methods and Sofware, 18, 3, 317-333 (2003) · Zbl 1037.90003 · doi:10.1080/1055678031000098773 |
| [41] | Kočvara, M.; Stingl, M., On the solution of large-scale sdp problems by the modified barrier method using iterative solvers, Math. Program., 109, 2, 413-444 (2007) · Zbl 1177.90312 · doi:10.1007/s10107-006-0029-9 |
| [42] | Lasserre, J-B, A sum of squares approximation of nonnegative polynomials, SIAM J. Optim., 16, 751-765 (2006) · Zbl 1129.12003 · doi:10.1137/04061413X |
| [43] | Lasserre, J-B, Moments (2009), Imperial College Press: Positive Polynomials and Their Applications, Imperial College Press |
| [44] | Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: M. Putinar and S. Sullivant, editors, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications. Springer (2009) · Zbl 1163.13021 |
| [45] | Lin, F.; Jovanović, MR, Least-squares approximation of structured covariances, IEEE Trans. Automat. Control, 54, 7, 1643-1648 (2009) · Zbl 1367.93730 · doi:10.1109/TAC.2009.2017976 |
| [46] | Lewis, A.; Luke, D.; Malick, J., Local linear convergence for alternating and averaged nonconvex projections, Foundations of Computational Mathematics, 9, 485-513 (2009) · Zbl 1169.49030 · doi:10.1007/s10208-008-9036-y |
| [47] | Lewis, A.; Malick, J., Alternating projections on manifolds, Mathematics of Operations Research, 33, 1, 216-234 (2008) · Zbl 1163.65040 · doi:10.1287/moor.1070.0291 |
| [48] | Lovász, L., On the Shannon capacity of a graph, IEEE Transactions on Information Theory, 25, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985 |
| [49] | Li, Q., Qi, H.: A sequential semismooth Newton method method for the nearest low-rank correlation matrix problem. Technical report (2003) · Zbl 1236.49070 |
| [50] | Malick, J., A dual approach to semidefinite least-squares problems, SIAM Journal on Matrix Analysis and Applications, 26, 1, 272-284 (2004) · Zbl 1080.65027 · doi:10.1137/S0895479802413856 |
| [51] | B. Martinet. Régularisation d’inéquations variationnelles par approximations successives. Revue Française d’Informatique et Recherche Opérationnelle R-3, 154-179 (1970) · Zbl 0215.21103 |
| [52] | Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM Journal on Optimization, 20, 1, 336-356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575 |
| [53] | Malick, J.; Sendov, H., Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices, Set-Valued Analysis, 14, 3, 273-293 (2006) · Zbl 1100.49033 · doi:10.1007/s11228-005-0005-1 |
| [54] | Micchelli, CA; Utretas, FI, Smoothing and interpolation in a convex subset of an Hilbert space, SIAM J. Sci. Stat. Comput., 9, 728-746 (1988) · Zbl 0651.65046 · doi:10.1137/0909048 |
| [55] | Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 1, 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [56] | Nie, J., Regularization methods for sum of squares relaxations in large scale polynomial optimization (2009), ArXiv: Technical report, ArXiv |
| [57] | Caprara, A.; Oswald, M.; Reinelt, G.; Schwarz, R.; Traversi, E., Optimal linear arrangements using betweenness variables, Mathematical Programming (Series C), 3, 3, 261-280 (2011) · Zbl 1257.90081 |
| [58] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer Verlag, New York · Zbl 1104.65059 |
| [59] | Nouralishahi, M.; Wu, C.; Vandenberghe, L., Model calibration for optical lithography via semidefinite programming, Optimization and Engineering, 9, 19-35 (2008) · doi:10.1007/s11081-007-9026-y |
| [60] | Povh, J.; Rendl, F.; Wiegele, A., A boundary point method to solve semidefinite programs, Computing, 78, 277-286 (2006) · Zbl 1275.90055 · doi:10.1007/s00607-006-0182-2 |
| [61] | Polyak, BT; Tretjakov, NV, On an iterative method for linear programming and its economical interpretations, Èkonom. i Mat. Methody, 8, 740-751 (1972) |
| [62] | Qi, LQ; Sun, J., A nonsmooth version of Newton’s method, Mathematical Programming, 58, 3, 353-367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275 |
| [63] | Qi, H.; Sun, D., Quadratic convergence and numerical experiments of Newton’s method for computing the nearest correlation matrix, SIAM Journal on Matrix Analysis and Applications, 28, 360-385 (2006) · Zbl 1120.65049 · doi:10.1137/050624509 |
| [64] | Qi, H., Sun, D.: An augmented Lagrangian dual approach for the h-weighted nearest correlation matrix problem. IMA Journal of Numerical Analysis (2003) · Zbl 1218.65061 |
| [65] | Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [66] | Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056 |
| [67] | Schwertman, N.; Allen, D., Smoothing an indefinite variance-covariance matrix, Journal of Statistical Computation and Simulation, 9, 183-194 (1979) · doi:10.1080/00949657908810316 |
| [68] | Sun, D., Sun, J.: Semismooth matrix valued functions. Mathematics of Operations Research 57 (2002) · Zbl 1082.49501 |
| [69] | Sturm, J.F.: Using Sedumi 1.02, a Matlab toolbox for optimization over symmetric cones. Optmization Methods and Softwares 11-12, 625-653 (1999) · Zbl 0973.90526 |
| [70] | Saigal, R., Vandenberghe, L., Wolkowicz, H.: Handbook of Semidefinite-Programming. Kluwer (2000) · Zbl 0962.90001 |
| [71] | Sun, J.; Zhang, S., A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European Journal of Operational Research, 207, 3, 1210-1220 (2003) · Zbl 1229.90119 · doi:10.1016/j.ejor.2010.07.020 |
| [72] | Toh, K., An inexact primal-dual path following algorithm for convex quadratic SDP, Math. Program., 112, 1, 221-254 (2008) · Zbl 1136.90027 · doi:10.1007/s10107-006-0088-y |
| [73] | Tutuncu, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming B, 95, 189-217 (2003) · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5 |
| [74] | Tutuncu, RH; Toh, KC, Todd (2006), M.J: Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pacific Journal on Optimization, M.J |
| [75] | Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented lagrangian method for semidefinite programming. SIAM J. Optim 20(4) (2003) · Zbl 1213.90175 |
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.
