SCS

SCS: Splitting conic solver: Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding. We introduce a first order method for solving very large cone programs to modest accuracy. 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 lower accuracy. Compared to other first-order methods for cone programs, our approach finds both primal and dual solutions when available and certificates of infeasibility or unboundedness otherwise, it does not rely on any explicit algorithm parameters, and the per-iteration cost of the method is the same as applying the 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 called SCS, 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 SOCPs, and scaling to very large general cone programs.


References in zbMATH (referenced in 38 articles )

Showing results 1 to 20 of 38.
Sorted by year (citations)

1 2 next

  1. Glaser, Lisa; Stern, Abel B.: Reconstructing manifolds from truncations of spectral triples (2021)
  2. Gnacik, Michał; Guzik, Marcin; Kania, Tomasz: Approximate modularity: Kalton’s constant is not smaller than 3 (2021)
  3. Kaluba, Marek; Kielak, Dawid; Nowak, Piotr: On property (T) for (\mathrmAut(F_n)) and (\mathrmSL_n(\mathbbZ)) (2021)
  4. Coey, Chris; Lubin, Miles; Vielma, Juan Pablo: Outer approximation with conic certificates for mixed-integer convex problems (2020)
  5. Eltved, Anders; Dahl, Joachim; Andersen, Martin S.: On the robustness and scalability of semidefinite relaxation for optimal power flow problems (2020)
  6. Fu, Anqi; Zhang, Junzi; Boyd, Stephen: Anderson accelerated Douglas-Rachford splitting (2020)
  7. Hütter, Jan-Christian; Mao, Cheng; Rigollet, Philippe; Robeva, Elina: Estimation of Monge matrices (2020)
  8. Hütter, Jan-Christian; Mao, Cheng; Rigollet, Philippe; Robeva, Elina: Optimal rates for estimation of two-dimensional totally positive distributions (2020)
  9. Liberti, Leo: Distance geometry and data science (2020)
  10. Li, Yongfeng; Liu, Haoyang; Wen, Zaiwen; Yuan, Ya-xiang: Low-rank matrix iteration using polynomial-filtered subspace extraction (2020)
  11. Milz, Johannes; Ulbrich, Michael: An approximation scheme for distributionally robust nonlinear optimization (2020)
  12. Rapoport, L. B.; Tormagov, T. A.: Relaxation methods for navigation satellites set optimization (2020)
  13. Rontsis, Nikitas; Osborne, Michael A.; Goulart, Paul J.: Distributionally ambiguous optimization for batch Bayesian optimization (2020)
  14. Stellato, Bartolomeo; Banjac, Goran; Goulart, Paul; Bemporad, Alberto; Boyd, Stephen: OSQP: an operator splitting solver for quadratic programs (2020)
  15. Zhang, Junzi; O’Donoghue, Brendan; Boyd, Stephen: Globally convergent type-I Anderson acceleration for nonsmooth fixed-point iterations (2020)
  16. Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew: Chordal decomposition in operator-splitting methods for sparse semidefinite programs (2020)
  17. Zohrizadeh, Fariba; Josz, Cedric; Jin, Ming; Madani, Ramtin; Lavaei, Javad; Sojoudi, Somayeh: A survey on conic relaxations of optimal power flow problem (2020)
  18. Banjac, Goran; Goulart, Paul; Stellato, Bartolomeo; Boyd, Stephen: Infeasibility detection in the alternating direction method of multipliers for convex optimization (2019)
  19. Busseti, Enzo; Moursi, Walaa M.; Boyd, Stephen: Solution refinement at regular points of conic problems (2019)
  20. Fu, Anqi; Ungun, Barıṣ; Xing, Lei; Boyd, Stephen: A convex optimization approach to radiation treatment planning with dose constraints (2019)

1 2 next