Overview

FiOrdOs is a Matlab toolbox for automated C-code generation of first-order methods for the class of parametric convex programs


\begin{align*}
&\min \;   \tfrac{1}{2} x^T H x + g^T x + c \\ 
&\quad\begin{aligned} 
\textrm{s.t.} \quad x &\in \mathcal{X} \\
A_\textrm{e}x &= b_\textrm{e}\\
A_\textrm{i}x &\leq b_\textrm{i}
\end{aligned} 
\end{align*}

where all of the problem data can be parametric.

The parametric program has the following properties:

  • a convex objective function with Hessian $H\succeq0$, including $H=0$, e.g. as in linear programming
  • a convex set $\mathcal{X}\subseteq\mathbb{R}^n$ being the Cartesian product of easy-to-project sets $\mathcal{X}_i$, i.e. $\mathcal{X} = \mathcal{X}_1 \times \ldots \mathcal{X}_N$, where each of the sets can be one of
    • nonnegative orthant
    • box
    • Euclidean ball
    • second-order cone
    • simplex
    • hyperplane
    • halfspace
    • l1-ball
  • every set $\mathcal{X}_i$ has type-specific problem data, e.g. radius of the ball
  • every set $\mathcal{X}_i$ can be rotated and/or shifted
  • the equality constraint is optional
  • the inequality constraint is optional

The toolbox implements the gradient method and the fast gradient method. For both methods, also a variant with adaptive step size is available.
In case of an equality and/or an inequality constraint, there are two solution approaches available:

  • Lagrange relaxation
  • Primal-dual approach with preconditioning

More features:

  • problem specification through Matlab objects
  • automated or manual selection of solution method
  • optimal preconditioning
  • certification of iteration count
  • automated C-code generation including
    • interface for Matlab (MEX) and
    • interface for Simulink (S-Function)

Examples

Copyright and License

The copyright is with the Automatic Control Lab, ETH Zurich.

FiOrdOs is licensed under the GPL 3.0. In order to promote the Open Source idea under which this software is licensed, the resulting output from this software or modified output shall also be published under the GPL 3.0. For your convenience, a respective comment line is added to any output that this software generates.

If you are interested in using the generated output commercially, please contact the Automatic Control Lab, ETH Zurich.

Installation

FiOrdOs is available via tbxmanager, which simplifies the installation and update of freely available Matlab toolboxes.

To install FiOrdOs for the first time, follow these steps in Matlab:

  1. Install tbxmanager as described on the tbxmanager homepage.
  2. Install FiOrdOs and optionally other toolboxes that are required for additional features:
    tbxmanager install fiordos yalmip sedumi
  3. Get further information by typing
    • help fiordos (shows the help)
    • fiordos_userguide (opens the user guide in pdf-format)

To update FiOrdOs and other installed toolboxes, simply run

 tbxmanager update

FiOrdOs was tested with Matlab R2010b, R2013a and R2014a.

Release History

  • R20141208
    • bug fixes in primal-dual approach
  • R20140930
    • Version 2.0
    • new primal-dual approach that can handle also positive semidefinite H, including H=0 (e.g. LP's)
    • solves compatibility issues with Matlab R2014 and new Yalmip releases
    • updated user guide in pdf-format
  • R20121210
    • Version 1.2
    • automatic detection if (sub)problem can be solved analytically
    • support of inequality constraints
    • unified iteration count handling for all algorithms
    • bug fixes
  • R20121029
  • R20120921
    • Version 1.1
    • new sets: hyperplane, halfspace, l1-ball
    • algorithms with adaptive step size schemes → no eigenvalue computation anymore
    • optional diagonal structure exploitation for Hessian H
    • modified linear algebra (to allow for larger problems)
      • for-loops for all matrix-vector/matrix-matrix multiplications by default
      • explicit element-by-element matrix-vector multiplications optionally (skipping zero elements)
    • bug fixes and efficiency improvements
  • R20120525
    • initial release

Authors

  • Fabian Ullmann, former MSc student at ETH Zurich (primary developer)
  • Stefan Richter, former PhD student at the Automatic Control Lab, ETH Zurich (advisor)

Contact

If you have suggestions for improvements or encounter any troubles, just send an e-mail to fiordos@control.ee.ethz.ch. We are happy to help!

Publications and Talks

  • F. Ullmann. FiOrdOs: A Matlab Toolbox for C-Code Generation for First Order Methods. Master’s thesis, ETH Zurich, 2011. (abstract, request pdf)
  • S. Richter. Computational Complexity Certification of Gradient Methods for Real-Time Model Predictive Control. PhD thesis, Zurich, Switzerland, November 2012. (E-Collection)
  • S. Richter. FiOrdOs: Code Generation for First-Order Methods. Talk at the Automatic Control Laboratory, EPFL, Lausanne, Switzerland, May 2012. (abstract, request slides)
  • C.N. Jones. FiOrdOs: Code Generation for First-Order Methods. Talk at ACC 2012, Montreal, Canada, June 2012.
  • S. Richter. FiOrdOs: Code Generation for First-Order Methods. Talk at ISMP 2012, Berlin, Germany, August 2012. (abstract, request slides)
  • C.N. Jones. Fast predictive control: Real-time computation and certification. Talk at NMPC12, Noordwijkerhout, The Netherlands, August 2012. (abstract)
  • C.N. Jones. First-Order Optimization for Control. Talk in workshop “Predictive Control for Embedded Systems: State of the Art and Future Challenges” of CDC12, Maui, Hawaii, USA, December 2012. (details)
Last modified: 2014/12/08 22:38
 
© 2012 Automatic Control Laboratory, ETH Zurich