×

zbMATH — the first resource for mathematics

Conic optimization via operator splitting and homogeneous self-dual embedding. (English) Zbl 1342.90136
Summary: We introduce a first-order method for solving very large convex cone programs. The method uses an operator splitting method, the alternating directions method of multipliers, to solve the homogeneous self-dual embedding, an equivalent feasibility problem involving finding a nonzero point in the intersection of a subspace and a cone. This approach has several favorable properties. Compared to interior-point methods, first-order methods scale to very large problems, at the cost of requiring more time to reach very high accuracy. Compared to other first-order methods for cone programs, our approach finds both primal and dual solutions when available or a certificate of infeasibility or unboundedness otherwise, is parameter free, and the per-iteration cost of the method is the same as applying a splitting method to the primal or dual alone. We discuss efficient implementation of the method in detail, including direct and indirect methods for computing projection onto the subspace, scaling the original problem data, and stopping criteria. We describe an open-source implementation, which handles the usual (symmetric) nonnegative, second-order, and semidefinite cones as well as the (non-self-dual) exponential and power cones and their duals. We report numerical results that show speedups over interior-point cone solvers for large problems, and scaling to very large general cone programs.

MSC:
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
49M29 Numerical methods involving duality
49M05 Numerical methods based on necessary conditions
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley, London (2011)
[2] Sturm, J, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[3] Skajaa, A., Ye, Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. http://www.stanford.edu/yyye/nonsymmhsdimp.pdf (2012) · Zbl 1309.90078
[4] Glowinski, R; Marrocco, A, Sur l’approximation, par elements finis d’ordre un, et la resolution, par penalisation-dualité, d’une classe de problems de Dirichlet non lineares, Rev. Fr. d’Autom. Inf. Rech. Opér., 9, 41-76, (1975) · Zbl 0368.65053
[5] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2, 17-40, (1976) · Zbl 0352.65034
[6] Gabay, D; Fortin, M (ed.); Glowinski, R (ed.), Applications of the method of multipliers to variational inequalities, 299-331, (1983), Amsterdam
[7] Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, Massachusetts Institute of Technology (1989) · Zbl 1077.65055
[8] Boyd, S; Parikh, N; Chu, E; Peleato, B; Eckstein, J, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122, (2011) · Zbl 1229.90122
[9] He, B; Yuan, X, On the \({O(1/n)}\) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50, 700-709, (2012) · Zbl 1245.90084
[10] Ye, Y; Todd, M; Mizuno, S, An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 53-67, (1994) · Zbl 0799.90087
[11] Xu, X; Hung, P; Ye, Y, A simplified homogeneous and self-dual linear programming algorithm and its implementation, Ann. Oper. Res., 62, 151-171, (1996) · Zbl 0848.90095
[12] Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia (1994) · Zbl 0824.90112
[13] Wen, Z; Goldfarb, D; Yin, W, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2, 203-230, (2010) · Zbl 1206.90088
[14] Lan, G; Lu, Z; Monteiro, R, Primal-dual first-order methods with \({\cal O}(1/ϵ )\) iteration-complexity for cone programming, Math. Program., 126, 1-29, (2011) · Zbl 1208.90113
[15] Aybat, N., Iyengar, G.: An augmented Lagrangian method for conic convex programming. Preprint (2013). arXiv:1302.6322v1 · Zbl 1251.90303
[16] Boyle, J; Dykstra, R; Dykstra, R (ed.); Robertson, T (ed.); Wright, F (ed.), A method for finding projections onto the intersection of convex sets in Hilbert spaces, No. 37, 28-47, (1986), New York
[17] Bauschke, H; Borwein, J, Dykstra’s alternating projection algorithm for two sets, J. Approx. Theory, 79, 418-443, (1994) · Zbl 0833.46011
[18] Censor, Y; Chen, W; Combettes, P; Davidi, R; Herman, G, On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints, Comput. Optim. Appl., 51, 1065-1088, (2012) · Zbl 1244.90155
[19] Censor, Y; Elfving, T, A multiprojection algorithm using Bregman projections in a product space, Numer. Algorithms, 8, 221-239, (1994) · Zbl 0828.65065
[20] Bauschke, H., Koch, V.: Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces. arXiv:1301.4506 (2013) · Zbl 1325.65080
[21] Eckstein, J; Bertsekas, D, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[22] Combettes, P; Pesquet, J, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20, 307-330, (2012) · Zbl 1284.47043
[23] Combettes, P, Systems of structured monotone inclusions: duality, algorithms, and applications, SIAM J. Optim., 23, 2420-2447, (2013) · Zbl 1314.47105
[24] Komodakis, N., Pesquet, J.: Playing with duality: an overview of recent primal-dual approaches for solving large-scale optimization problems. arXiv:1406.5429 (2014)
[25] Glowinski, R., Le Tallec, P.: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989) · Zbl 0698.73001
[26] Lions, P; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[27] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, Berlin (1984) · Zbl 0536.65054
[28] Fortin, M., Glowinski, R.: Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. North-Holland, Amsterdam (1983) · Zbl 0525.65045
[29] Douglas, J; Rachford, H, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Trans. Am. Math. Soc., 82, 421-439, (1956) · Zbl 0070.35401
[30] Rockafellar, R, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[31] Spingarn, J, Partial inverse of a monotone operator, Appl. Math. Optim., 10, 247-265, (1983) · Zbl 0524.90072
[32] Spingarn, J, Applications of the method of partial inverses to convex programming: decomposition, Math. Program., 32, 199-223, (1985) · Zbl 0565.90058
[33] Spingarn, J, A primal-dual projection method for solving systems of linear inequalities, Linear Algebra Appl., 65, 45-62, (1985) · Zbl 0564.65044
[34] Eckstein, J.: The Lions-Mercier splitting algorithm and the alternating direction method are instances of the proximal point algorithm. Tech. Rep. LIDS-P-1769, Massachusetts Institute of Technology (1989) · Zbl 1177.65088
[35] Byrne, C, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probab., 18, 441, (2002) · Zbl 0996.65048
[36] Censor, Y; Motova, A; Segal, A, Perturbed projections and subgradient projections for the multiple-sets split feasibility problem, J. Math. Anal. Appl., 327, 1244-1256, (2007) · Zbl 1253.90211
[37] Censor, T.: Sequential and parallel projection algorithms for feasibility and optimization. In: Multispectral Image Processing and Pattern Recognition, pp. 1-9. Bellingham: International Society for Optics and Photonics (2001) · Zbl 0564.65044
[38] Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. arXiv:1407.7400 (2014) · Zbl 1372.65186
[39] Combettes, P, The convex feasibility problem in image recovery, Adv. Imaging Electron Phys., 95, 155-270, (1996)
[40] Goldstein, T; Osher, S, The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2, 323-343, (2009) · Zbl 1177.65088
[41] O’Connor, D; Vandenberghe, L, Image deblurring by primal-dual operator splitting, SIAM J. Imaging Sci., 7, 1724-1754, (2014) · Zbl 1309.65069
[42] Lin, F., Fardad, M., Jovanovic, M.: Design of optimal sparse feedback gains via the alternating direction method of multipliers. In: Proceedings of the 2012 American Control Conference, pp. 4765-4770 (2012) · Zbl 1253.90211
[43] Annergren, M., Hansson, A., Wahlberg, B.: An ADMM algorithm for solving \(ℓ _1\) regularized MPC (2012)
[44] O’Donoghue, B., Stathopoulos, G., Boyd, S.: A splitting method for optimal control. IEEE Trans. Control Syst. Technol. 21(6), 2432-2442 (2013) · Zbl 0426.65050
[45] Mota, J., Xavier, J., Aguiar, P., Puschel, M.: Distributed ADMM for model predictive control and congestion control. In: 2012 IEEE 51st Annual Conference on Decision and Control (CDC), pp. 5110-5115 (2012)
[46] O’Donoghue, B.: Suboptimal control policies via convex optimization. Ph.D. thesis, Stanford University (2012) · Zbl 0106.31604
[47] Wahlberg, B., Boyd, S., Annergren, M., Wang, Y.: An ADMM algorithm for a class of total variation regularized estimation problems. In: Proceedings 16th IFAC Symposium on System Identification (to appear) (2012)
[48] Combettes, P; Wajs, V, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2006) · Zbl 1179.94031
[49] Combettes, P; Pesquet, J, A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. Sel. Top. Sign. Proces., 1, 564-574, (2007)
[50] Combettes, P., Pesquet, J.: Proximal splitting methods in signal processing. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185-212. Springer, Berlin (2011) · Zbl 1242.90160
[51] Yang, J; Zhang, Y, Alternating direction algorithms for \(ℓ _1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 250-278, (2011) · Zbl 1256.65060
[52] Boyd, S; Mueller, M; O’Donoghue, B; Wang, Y, Performance bounds and suboptimal policies for multi-period investment, Found. Trends Optim., 1, 1-69, (2013)
[53] Parikh, N., Boyd, S.: Block splitting for distributed optimization. Math. Program. Comput. 6(1), 77-102 (2013) · Zbl 1305.90291
[54] Kraning, M; Chu, E; Lavaei, J; Boyd, S, Dynamic network energy management via proximal message passing, Found. Trends Optim., 1, 70-122, (2014)
[55] Chambolle, A; Pock, T, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 120-145, (2011) · Zbl 1255.68217
[56] Becker, S., Candès, E., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3(3), 1-54 (2010) · Zbl 0106.31604
[57] Gondzio, J, Matrix-free interior point method, Comput. Optim. Appl., 51, 457-480, (2012) · Zbl 1241.90179
[58] Monteiro, R., Ortiz, C., Svaiter, B.: An inexact block-decomposition method for extra large-scale conic semidefinite programming. Optimization-online preprint 4158, 1-21 (2013) · Zbl 0172.18704
[59] Monteiro, R; Ortiz, C; Svaiter, B, Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems, Comput. Optim. Appl., 57, 45-69, (2014) · Zbl 1312.90052
[60] Monteiro, R; Ortiz, C; Svaiter, B, A first-order block-decomposition method for solving two-easy-block structured semidefinite programs, Math. Program. Comput., 6, 103-150, (2014) · Zbl 1342.49045
[61] Zhao, X; Sun, D; Toh, K, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765, (2010) · Zbl 1213.90175
[62] O’Donoghue, B., Candès, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715-732 (2015) · Zbl 0946.90050
[63] Esser, E; Zhang, X; Chan, T, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3, 1015-1046, (2010) · Zbl 1206.90117
[64] Parikh, N; Boyd, S, Proximal algorithms, Found. Trends Optim., 1, 123-231, (2014)
[65] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[66] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[67] Franklin, G., Powell, J., Emami-Naeini, A.: Feedback Control of Dynamic Systems, vol. 3. Addison-Wesley, Reading, MA (1994) · Zbl 0615.93001
[68] Gol’shtein, E., Tret’yakov, N.: Modified Lagrangians in convex programming and their generalizations. Point-to-Set Maps Math. Program. 10, 86-97 (1979) · Zbl 1030.90080
[69] Eckstein, J, Parallel alternating direction multiplier decomposition of convex programs, J. Optim. Theory Appl., 80, 39-62, (1994) · Zbl 0797.90075
[70] Pataki, G., Schmieta, S.: The DIMACS library of mixed semidefinite-quadratic-linear programs. dimacs.rutgers.edu/Challenges/Seventh/Instances · Zbl 0828.65065
[71] Mittelmann, H, An independent benchmarking of SDP and SOCP solvers, Math. Program. (Ser. B), 95, 407-430, (2003) · Zbl 1030.90080
[72] Golub, G., Van Loan, C.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[73] Davis, T.: Direct Methods for Sparse Linear Systems. SIAM Fundamentals of Algorithms. SIAM, Philadelphia (2006) · Zbl 1119.65021
[74] Vanderbei, R, Symmetric quasi-definite matrices, SIAM J. Optim., 5, 100-113, (1995) · Zbl 0822.65017
[75] Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006) · Zbl 1104.65059
[76] Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003) · Zbl 1031.65046
[77] Bauer, F, Optimally scaled matrices, Numer. Math., 5, 73-87, (1963) · Zbl 0107.10501
[78] Bauer, F, Remarks on optimally scaled matrices, Numer. Math., 13, 1-3, (1969) · Zbl 0172.18704
[79] Sluis, A, Condition numbers and equilibration of matrices, Numer. Math., 14, 14-23, (1969) · Zbl 0182.48906
[80] Ruiz, D.: A scaling algorithm to equilibrate both rows and columns norms in matrices. Tech. Rep., Rutherford Appleton Laboratories (2001) · Zbl 0182.48906
[81] Osborne, E, On pre-conditioning of matrices, JACM, 7, 338-345, (1960) · Zbl 0106.31604
[82] Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV), pp. 1762-1769. IEEE (2011) · Zbl 1253.90211
[83] Giselsson, P., Boyd, S.: Diagonal scaling in Douglas-Rachford splitting and ADMM. In: Proceedings of the 54th IEEE Conference on Decision and Control, pp. 5033-5039 (2014) · Zbl 1241.90179
[84] Giselsson, P; Boyd, S, Metric selection in fast dual forward backward splitting, Automatica, 62, 1-10, (2015) · Zbl 1330.49032
[85] Toh, K; Todd, M; Tütüncü, R, SDPT3: A Matlab software package for semidefinite programming, Optim. Methods Softw., 11, 545-581, (1999) · Zbl 0997.90060
[86] SCS: Splitting conic solver v1.1.0. https://github.com/cvxgrp/scs (2015)
[87] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx (2013)
[88] Diamond, S., Boyd, S.: CVXPY: A python-embedded modeling language for convex optimization. http://web.stanford.edu/boyd/papers/cvxpy_paper.html (2015) · Zbl 1360.90008
[89] Udell, M., Mohan, K., Zeng, D., Hong, J., Diamond, S., Boyd, S.: Convex optimization in Julia. SC14 Workshop on High Performance Technical Computing in Dynamic Languages (2014)
[90] Lofberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: IEEE International Symposium on Computed Aided Control Systems Design, pp. 294-289 (2004)
[91] Davis, T, Algorithm 849: a concise sparse Cholesky factorization package, ACM Trans. Math. Softw., 31, 587-591, (2005) · Zbl 1136.65311
[92] Amestoy, P; Davis, T; Duff, I, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Trans. Math. Softw., 30, 381-388, (2004) · Zbl 1070.65534
[93] OpenMP Architecture Review Board: OpenMP application program interface version 3.0. http://www.openmp.org/mp-documents/spec30.pdf (2008)
[94] Nickolls, J; Buck, I; Garland, M; Skadron, K, Scalable parallel programming with CUDA, Queue, 6, 40-53, (2008)
[95] Nesterov, Y.: Towards nonsymmetric conic optimization. http://www.optimization-online.org/DB_FILE/2006/03/1355.pdf (2006). CORE discussion paper · Zbl 1136.65311
[96] Skajaa, A., Ye, Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Program. 150(2), 391-422 (2015) · Zbl 1309.90078
[97] Khanh Hien, L.: Differential properties of Euclidean projection onto power cone. http://www.optimization-online.org/DB_FILE/2014/08/4502.pdf (2014) · Zbl 1342.90183
[98] Tibshirani, R, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 267-288, (1996) · Zbl 0850.62538
[99] Daubechies, I; Defrise, M; De Mol, C, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57, 1413-1457, (2004) · Zbl 1077.65055
[100] Demanet, L., Zhang, X.: Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit. arXiv preprint arXiv:1301.0542 (2013) · Zbl 1329.49050
[101] Lobo, M; Vandenberghe, L; Boyd, S; Lebret, H, Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228, (1998) · Zbl 0946.90050
[102] Markowitz, H, Portfolio selection, J. Finance, 7, 77-91, (1952)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.