×

On degenerate doubly nonnegative projection problems. (English) Zbl 1501.90045

Summary: The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large-scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. Such a failure results in the singularity of the Jacobian of the nonsmooth equation representing the Karush-Kuhn-Tucker optimality condition that prevents the semismooth Newton-conjugate gradient method from solving it with a desirable convergence rate. In this paper, we overcome the aforementioned difficulty by solving a sequence of better conditioned nonsmooth equations generated by the augmented Lagrangian method (ALM) instead of solving one aforementioned singular equation. By leveraging the metric subregularity of the normal cone associated with the positive semidefinite cone, we derive sufficient conditions to ensure the dual quadratic growth condition of the underlying problem, which further leads to the asymptotically superlinear convergence of the proposed ALM. Numerical results on difficult randomly generated instances and from the semidefinite programming library are presented to demonstrate the efficiency of the algorithm for computing the DNN projection to a very high accuracy.

MSC:

90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
90C25 Convex programming

Software:

SDPNAL+; QSDPNAL

References:

[1] [1] Arnold VI (1971) On matrices depending on parameters. Russian Math. Surveys 26(2):29-43.Crossref, Google Scholar · Zbl 0259.15011 · doi:10.1070/RM1971v026n02ABEH003827
[2] [2] Artacho FJA, Geoffroy MH (2008) Characterization of metric regularity of subdifferentials. J. Convex Anal. 15(2):365-380.Google Scholar · Zbl 1146.49012
[3] [3] Bauer FL, Fike CT (1960) Norms and exclusion theorems. Numerische Mathematik 2(1):137-141.Crossref, Google Scholar · Zbl 0101.25503 · doi:10.1007/BF01386217
[4] [4] Bauschke HH, Borwein JM (1996) On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3):367-426.Crossref, Google Scholar · Zbl 0865.47039 · doi:10.1137/S0036144593251710
[5] [5] Bauschke HH, Borwein JM, Li W (1999) Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization. Math. Programming 86(1):135-160.Crossref, Google Scholar · Zbl 0998.90088 · doi:10.1007/s101070050083
[6] [6] Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183-202.Crossref, Google Scholar · Zbl 1175.94009 · doi:10.1137/080716542
[7] [7] Bomze IM, Dür M, De Klerk E, Roos C, Quist AJ, Terlaky T (2000) On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4):301-320.Crossref, Google Scholar · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[8] [8] Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems (Springer, New York).Crossref, Google Scholar · Zbl 0966.49001 · doi:10.1007/978-1-4612-1394-9
[9] [9] Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479-495.Crossref, Google Scholar · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[10] [10] Cui Y (2016) Large scale composite optimization problems with coupled objective functions: theory, algorithms and applications, Unpublished PhD thesis, National University of Singapore.Google Scholar
[11] [11] Cui Y, Ding C, Zhao XY (2017) Quadratic growth conditions for convex matrix optimization problems associated with spectral functions. SIAM J. Optim. 27(4):2332-2355.Crossref, Google Scholar · Zbl 1376.65094 · doi:10.1137/17M1116325
[12] [12] Cui Y, Sun DF, Toh KC (2019a) Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone. SIAM J. Optim. 29(4):2785-2813.Crossref, Google Scholar · Zbl 1431.90109 · doi:10.1137/18M1175562
[13] [13] Cui Y, Sun DF, Toh KC (2019b) On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. Math. Programming 178(1):381-415.Crossref, Google Scholar · Zbl 1423.90171 · doi:10.1007/s10107-018-1300-6
[14] [14] De Klerk E, Pasechnik DV (2002) Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4):875-892.Crossref, Google Scholar · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[15] [15] Dickinson PJ, Gijben L (2014) On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2):403-415.Crossref, Google Scholar · Zbl 1330.90103 · doi:10.1007/s10589-013-9594-z
[16] [16] Dontchev AL, Rockafellar RT (2009) Implicit Functions and Solution Mappings (Springer, New York).Crossref, Google Scholar · Zbl 1178.26001 · doi:10.1007/978-0-387-87821-8
[17] [17] Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3):919-948.Link, Google Scholar · Zbl 1440.90046
[18] [18] Dür M (2010) Copositive programming—A survey. Diehl M, Glineur F, Jarlebring E, Michiels W, eds. Recent Advances in Optimization and Its Applications in Engineering (Springer, Berlin, Heidelberg), 3-20.Crossref, Google Scholar · doi:10.1007/978-3-642-12598-0_1
[19] [19] Dykstra RL (1983) An algorithm for restricted least squares regression. J. Amer. Statist. Assoc. 78(384):837-842.Crossref, Google Scholar · Zbl 0535.62063 · doi:10.1080/01621459.1983.10477029
[20] [20] Facchinei F, Pang J-S (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I (Springer, New York).Google Scholar · Zbl 1062.90001
[21] [21] Gaffke N, Mathar R (1989) A cyclic projection algorithm via duality. Metrika 36(1):29-54.Crossref, Google Scholar · Zbl 0676.90054 · doi:10.1007/BF02614077
[22] [22] Han DR, Sun DF, Zhang LW (2018) Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2):622-637.Link, Google Scholar · Zbl 1440.90047
[23] [23] Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J. Res. National Bureau Standards 49(4):263-265.Crossref, Google Scholar · doi:10.6028/jres.049.027
[24] [24] Kim S, Kojima M, Toh K-C (2016) A Lagrangian-DNN relaxation: A fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Programming 156(1-2):161-187.Crossref, Google Scholar · Zbl 1342.90123 · doi:10.1007/s10107-015-0874-5
[25] [25] Kort BW, Bertsekas DP (1976) Combined primal-dual and penalty methods for convex programming. SIAM J. Control Optim. 14(2):268-294.Crossref, Google Scholar · Zbl 0332.90035 · doi:10.1137/0314020
[26] [26] Li XD, Sun DF, Toh K-C (2018) QSDPNAL: A two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming. Math. Programming Comput. 10(4):703-743.Crossref, Google Scholar · Zbl 1411.90213 · doi:10.1007/s12532-018-0137-6
[27] [27] Luo ZQ, Tseng P (1992) On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Control Optim. 30(2):408-425.Crossref, Google Scholar · Zbl 0756.90084 · doi:10.1137/0330025
[28] [28] Mangasarian OL (1988) A simple characterization of solution sets of convex programs. Oper. Res. Lett. 7(1):21-26.Crossref, Google Scholar · Zbl 0653.90055 · doi:10.1016/0167-6377(88)90047-8
[29] [29] Maxfield JE, Minc H (1962) On the matrix equation X′X=A. Proc. Edinburgh Math. Soc. 13(2):125-129.Crossref, Google Scholar · Zbl 0112.25101 · doi:10.1017/S0013091500014681
[30] [30] Murty KG, Kabadi SN (1987) Some NP-complete problems in quadratic and non-linear programming. Math. Programming 39(2):117-129.Crossref, Google Scholar · Zbl 0637.90078 · doi:10.1007/BF02592948
[31] [31] Nesterov Y (1983) A method of solving a convex programming problem with convergence rate O(1/k2). Doklady Akademii Nauk SSSR 27(2):372-376.Google Scholar · Zbl 0535.90071
[32] [32] Povh J, Rendl F (2007) A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1):223-241.Crossref, Google Scholar · Zbl 1143.90025 · doi:10.1137/050637467
[33] [33] Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3):231-241.Crossref, Google Scholar · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[34] [34] Powell MJD (1972) A method for nonlinear constraints in minimization problems. Fletcher R, ed. Optimization (Academic, New York), 283-298.Google Scholar · Zbl 0194.47701
[35] [35] Robinson SM (1981) Some continuity properties of polyhedral multifunctions. Math. Oper. Res. 14:206-214.Google Scholar · Zbl 0449.90090
[36] [36] Robinson SM (1984) Local structure of feasible sets in nonlinear programming, Part II: Nondegeneracy. Math. Programming Stud. 22:217-230.Crossref, Google Scholar · Zbl 0573.90075 · doi:10.1007/BFb0121018
[37] [37] Robinson SM (2003) Constraint nondegeneracy in variational analysis. Math. Oper. Res. 28(2):201-232.Link, Google Scholar · Zbl 1082.90116
[38] [38] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · Zbl 0932.90001 · doi:10.1515/9781400873173
[39] [39] Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97-116.Link, Google Scholar · Zbl 0402.90076
[40] [40] Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, New York).Crossref, Google Scholar · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[41] [41] Shapiro A (2003) Sensitivity analysis of generalized equations. J. Math. Sci. (New York) 115(4):2554-2565.Crossref, Google Scholar · Zbl 1136.90482 · doi:10.1023/A:1022940300114
[42] [42] Sun DF (2006) The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31(4):761-776.Link, Google Scholar · Zbl 1278.90304
[43] [43] Sun DF, Sun J (2002) Semismooth matrix valued functions. Math. Oper. Res. 27(1):150-169.Link, Google Scholar · Zbl 1082.49501
[44] [44] Tseng P (2010) Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Programming 125(2):263-295.Crossref, Google Scholar · Zbl 1207.65084 · doi:10.1007/s10107-010-0394-2
[45] [45] Yang LQ, Sun DF, Toh K-C (2015) SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Programming Comput. 7(3):1-36.Crossref, Google Scholar · Zbl 1321.90085 · doi:10.1007/s12532-015-0082-6
[46] [46] Zhao XY, Sun DF, Toh K-C (2010) A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4):1737-1765.Crossref, Google Scholar · Zbl 1213.90175 · doi:10.1137/080718206
[47] [47] Zhou ZR, So AMC (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 165(2):689-728.Crossref, Google Scholar · Zbl 1380.65109 · doi:10.1007/s10107-016-1100-9
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.