MPC

MPC 2011, ISSUE 3



Mathematical Programming Computation, Volume 3, Issue 3, August 2011

Templates for convex cone problems with applications to sparse signal recovery

Stephen R. Becker, Emmanuel J. Candès, Michael C. Grant

This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal first-order method. A merit of this approach is its flexibility: for example, all compressed sensing problems can be solved via this approach. These include models with objective functionals such as the total-variation norm, ||Wx||1 where W is arbitrary, or a combination thereof. In addition, the paper introduces a number of technical contributions such as a novel continuation scheme and a novel approach for controlling the step size, and applies results showing that the smooth and unsmoothed problems are sometimes formally equivalent. Combined with our framework, these lead to novel, stable and computationally efficient algorithms. For instance, our general implementation is competitive with state-of-the-art methods for solving intensively studied problems such as the LASSO. Further, numerical experiments show that one can solve the Dantzig selector problem, for which no efficient large-scale solvers exist, in a few hundred iterations. Finally, the paper is accompanied with a software release. This software is not a single, monolithic solver; rather, it is a suite of programs and routines designed to serve as building blocks for constructing complete algorithms.

Full Text: PDF



Mathematical Programming Computation, Volume 3, Issue 3, August 2011

Pyomo: modeling and solving mathematical programs in Python

Hart E. Hart, Jean-Paul Watson, David L. Woodruff

We describe Pyomo, an open source software package for modeling and solving mathematical programs in Python. Pyomo can be used to define abstract and concrete problems, create problem instances, and solve these instances with standard open-source and commercial solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages such as AMPL, AIMMS, and GAMS. In contrast, Pyomo’s modeling objects are embedded within a full-featured highlevel programming language with a rich set of supporting libraries. Pyomo leverages the capabilities of the Coopr software library, which together with Pyomo is part of IBM’s COIN-OR open-source initiative for operations research software. Coopr integrates Python packages for defining optimizers, modeling optimization applications, and managing computational experiments. Numerous examples illustrating advanced scripting applications are provided.

Full Text: PDF



Mathematical Programming Computation, Volume 3, Issue 3, August 2011

Optimal linear arrangements using betweenness variables

Alberto Caprara, Marcus Oswald, Gerhard Reinelt, Robert Schwarz, Emiliano Traversi

We solve for the first time to proven optimality the small instances in the classical literature benchmark of Minimum Linear Arrangement. This is achieved by formulating the problem as an ILP in a somehow unintuitive way, using variables expressing the fact that a vertex is between two other adjacent vertices in the arrangement. Using (only) these variables appears to be the key idea of the approach. Indeed, with these variables already the use of very simple constraints leads to good results, which can however be improvedwith amore detailed study of the underlying polytope.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).