DECOPT – DEcomposition Convex OPTimization

Overview

DECOPT is a MATLAB software package for the generic constrained convex optimization problems. Details on example problems are given in the following file:

Decopt

Download

DECOPT can be downloaded at:

References

The full algorithms and theory of DECOPT can be found in the following references:

  • Q. Tran-Dinh and V. Cevher, “Constrained convex minimization via model-based excessive gap“. Proceedings of the annual conference on Neural Information Processing Systems Foundation (NIPS), Montreal, Canada, (2014).

Available at: https://infoscience.epfl.ch/record/201842

Abstract: Abstract We introduce a model-based excessive gap technique to analyze first-order primal- dual methods for constrained convex minimization. As a result, we construct first-order primal-dual methods with optimal convergence rates on the primal objec-tive residual and the primal feasibility gap of their iterates separately. Through a dual smoothing and prox- center selection strategy, our framework subsumes the augmented Lagrangian, alternating direction, and dual fast-gradient methods as special cases, where our rates apply.

  • Q. Tran-Dinh, and V. Cevher. “A Primal-Dual Algorithmic Framework for Constrained Convex Minimization”, LIONS Tech. Report EPFL-REPORT-199844, (2014).

Available at: https://infoscience.epfl.ch/record/199844

Abstract: We present a primal-dual algorithmic framework to obtain approximate solutions to a prototypical constrained convex optimization problem, and rigorously characterize how common structural assumptions affect the numerical efficiency. Our main analysis technique provides a fresh perspective on Nesterov’s excessive gap technique in a structured fashion and unifies it with smoothing and primal-dual methods. For instance, through the choices of a dual smoothing strategy and a center point, our framework subsumes decomposition algorithms, augmented Lagrangian as well as the alternating direction method-of-multipliers methods as its special cases, and provides optimal convergence rates on the primal objective residual as well as the primal feasibility gap of the iterates for all.