nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

20. Projection Methods in Conic Optimization

verfasst von : Didier Henrion, Jérôme Malick

Erschienen in: Handbook on Semidefinite, Conic and Polynomial Optimization

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Block Coordinate Descent Methods for Semidefinite Programming

Nächstes Kapitel SDP Relaxations for Non-Commutative Polynomial Optimization

Al-Homidan, S.: Solving Hankel matrix approximation problem using semidefinite programming. Journal of Computational and Applied Mathematics 202(2), 304–314 (2007)

Alizadeh, F., Haeberly, J.-P., Overton, M: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(2), 111–128 (1997)

Anjos, M.F., Higham, N.J., Takouda, P.L., Wolkowicz, H.: A semidefinite programming approach for the nearest correlation matrix problem. Technical report, Combinatorics and Optimization, University of Waterloo, September 2003.

Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Linear and Nonlinear Programming. Stanford University Press (1959)

Bolte, J., Daniilidis, A., Lewis, A.: Tame functions are semismooth. Math. Program. 117(1), 5–19 (2008)

Bertsekas, D.P.: Nonlinear Programming. Athena Scientific (1995)

Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory. Studies in Applied Mathematics. SIAM (1994)

Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Springer Verlag (2003)

Borsdorf, R., Higham, N.: A preconditionned Newton algorithm for the nearest correlation matrix. IMA J. Numer. Anal. 30(1), 94–107 (2010)

10.

Bellman, R., Kalaba, R., Lockett, J.: Numerical Inversion of the Laplace Transform. Elsevier (1966)

11.

Brigo, D., Mercurio, F.: Interest rate models: theory and practice. Springer-Verlag (2006)

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.

13.

Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Verlag (2000)

14.

Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press (2004)

15.

Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM Journal on Optimization 16, 726–750 (2006)

16.

Boyd, S., Xiao, L.: Least-squares covariance matrix adjustment. SIAM Journal on Matrix Analysis and Applications 27(2) (2005)

17.

Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Mathematical Programming 62(2), 261–275 (1993)

18.

Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley (1983); reprinted by SIAM, (1983)

19.

Dembo, R., Eisenstat, S., Steihaug, T.: Inexact Newton methods. SIAM Journal on Numerical Analysis 19(2) (1982)

20.

Deutsch, F.: Best Approximation in Inner Product Spaces. Springer, New York (2001)

21.

Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Amer. Math. Soc. 82, 421–439 (1956)

22.

Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Mathematical Programming 109, 345–365 (2007)

23.

Dumitrescu, B.: Positive Trigonometric Polynomials and Signal Processing Applications. Springer Verlag (2007)

24.

Dykstra, R.L.: An algorithm for restricted least-square regression. Journal of the American Statistical Association 78, 837–842, (1983)

25.

Gilbert, J.Ch., Lemaréchal, C.: Some numerical experiments with variable-storage quasi-Newton algorithms. Mathematical Programming 45, 407–435 (1989)

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)

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)

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)

30.

Henrion, D., Garulli, A. (eds.): Positive polynomials in control. LNCIS, Springer Verlag (2005)

31.

Higham, N.: Computing a nearest symmetric positive semidefinite matrix. Linear Algebra and its Applications 103, 103–118 (1988)

32.

Higham, N.: Computing a nearest symmetric correlation matrix — a problem from finance. IMA Journal of Numerical Analysis 22(3), 329–343 (2002)

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)

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)

35.

Hiriart-Urruty, J.-B. Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer Verlag, Heidelberg (1993) Two volumes.

36.

Hiriart-Urruty, J.-B., Strodiot, J.J., Nguyen, H.V.: Generalized hessian matrix and second-order optimality conditions for problems with C^1, 1 data. Applied Mathematics and Optimization 11, 43–56 (1984)

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)

39.

Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, 11-13 October 1993. American Mathematical Society, Boston, MA, USA (1996)

40.

Kočvara, M., Stingl, M.: PENNON: a code for convex nonlinear and semidefinite programming. Optimisation Methods and Sofware 18(3), 317–333 (2003)

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)

42.

Lasserre, J.-B.: A sum of squares approximation of nonnegative polynomials. SIAM J. Optim. 16, 751–765 (2006)

43.

Lasserre, J.-B.: Moments, Positive Polynomials and Their Applications. Imperial College Press (2009)

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)

45.

Lin, F., Jovanović, M.R.: Least-squares approximation of structured covariances. IEEE Trans. Automat. Control 54(7), 1643–1648 (2009)

46.

Lewis, A., Luke, D., Malick, J.: Local linear convergence for alternating and averaged nonconvex projections. Foundations of Computational Mathematics 9, 485–513 (2009)

47.

Lewis, A., Malick, J.: Alternating projections on manifolds. Mathematics of Operations Research 33(1), 216–234 (2008)

48.

Lovász, L.: On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25, 1–7 (1979)

49.

Li, Q., Qi, H.: A sequential semismooth Newton method method for the nearest low-rank correlation matrix problem. Technical report (2003)

50.

Malick, J.: A dual approach to semidefinite least-squares problems. SIAM Journal on Matrix Analysis and Applications 26(1), 272–284 (2004)

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)

52.

Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM Journal on Optimization 20(1), 336–356 (2009)

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)

54.

Micchelli, C.A., Utretas, F.I.: Smoothing and interpolation in a convex subset of an Hilbert space. SIAM J. Sci. Stat. Comput. 9, 728–746 (1988)

55.

Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005)

56.

Nie, J.: Regularization methods for sum of squares relaxations in large scale polynomial optimization. Technical report, ArXiv (2009)

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)

58.

Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Verlag, New York (2006)

59.

Nouralishahi, M., Wu, C., Vandenberghe, L.: Model calibration for optical lithography via semidefinite programming. Optimization and Engineering 9, 19–35 (2008)

60.

Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semidefinite programs. Computing 78, 277–286 (2006)

61.

Polyak, B.T., Tretjakov, N.V.: On an iterative method for linear programming and its economical interpretations. Èkonom. i Mat. Methody 8, 740–751 (1972)

62.

Qi, L.Q., Sun, J.: A nonsmooth version of Newton’s method. Mathematical Programming 58(3), 353–367 (1993)

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)

64.

Qi, H., Sun, D.: An augmented Lagrangian dual approach for the h-weighted nearest correlation matrix problem. IMA Journal of Numerical Analysis (2003)

65.

Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research 1, 97–116 (1976)

66.

Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization 14, 877–898 (1976)

67.

Schwertman, N., Allen, D.: Smoothing an indefinite variance-covariance matrix. Journal of Statistical Computation and Simulation 9, 183–194 (1979)

68.

Sun, D., Sun, J.: Semismooth matrix valued functions. Mathematics of Operations Research 57 (2002)

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)

70.

Saigal, R., Vandenberghe, L., Wolkowicz, H.: Handbook of Semidefinite-Programming. Kluwer (2000)

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)

72.

Toh, K.: An inexact primal-dual path following algorithm for convex quadratic SDP. Math. Program. 112(1), 221–254 (2008)

73.

Tutuncu, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Mathematical Programming B 95, 189–217 (2003)

74.

Tutuncu, R.H., Toh, K.C., Todd, M.J.: Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pacific Journal on Optimization (2006)

75.

Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented lagrangian method for semidefinite programming. SIAM J. Optim 20(4) (2003)

Titel: Projection Methods in Conic Optimization
verfasst von: Didier Henrion
Jérôme Malick
Verlag: Springer US
Buch: Handbook on Semidefinite, Conic and Polynomial Optimization
Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-1-4614-0769-0_20