The ConicBundle Library for Convex Optimization
Copyright (C) 2005-2021 Christoph Helmberg
Description
ConicBundle is a callable library for C/C++ that implements a
bundle method for minimizing the sum of convex functions that
are given by first order oracles or arise from Lagrangean
relaxation of particular conic linear programs.
The library offers a number of special features:
- Upper and lower bounds may be specified for each design variable; in a less efficient and somewhat experimental variant general linear constraints are allowed, as well.
- Instead of one common cutting plane model for the entire sum of functions, each function may either have its own specialized cutting model – this may help to improve convergence – or it may be grouped together with others in a common standard cutting plane model.
- It provides substantial support for Lagrangian relaxation, i.e., if the problem corresponds to finding the optimal dual multipliers obtained by relaxing linear constraints in a relaxation or decomposition of a primal problem.
- It allows to generate approximate primal optimal solutions.
- It supports cutting plane approaches by allowing dynamic addition and deletion of dual variables without loss of quality in the cutting models.
- The code offers special cutting models for linear programs over the second order cone and the cone of real symmetric positive semidefinite matrices.
The library comes with three variants of interfaces:
- Interface to ConicBundle for the Language C
- Interface to ConicBundle for the Language C++
- Interface to ConicBundle for the Language C++ using Matrix Classes
The interface offers the most but may require more time to get acquainted with. It includes
- an abstract first order oracle for general convex functions
- a specialized box oracle with special purpose cutting model which together with supported affine argument transformations supports Lagrangian relaxation of linear programs over box constrained domains
- an abstract positive semidefinite cone oracle (ConicBundle exploits this in a special purpose model for the semidefinite cone or, equivalently, for maximum eigenvalue functions) and an implemented variant for affine matrix functions
- an abstract second order cone oracle (ConicBundle exploits this in a special purpose model for the second order cone) and an implemented variant for affine vector functions
- all oracles can be combined with affine function transformations
- each oracle may be used either as an objective function or as a penalty function with fixed or adaptive penalty factor
- dynamic submodel selection allows to optimize various oracles jointly as a sum of convex functions where each oracle's model moves between being part of a common general cutting model and forming a dedicated cutting model
- support for various quadratic proximal terms with support for variable metric
- regarding the groundset of the design variables there is special support for
- unconstrained ground sets (no constraints on the design variables)
- box constrained ground sets (upper and lower bounds on each variable)
- linearly constrained ground sets (may be significantly slower, testing was limited to simple instances so far)
- dynamic modification support for adding/deleting/modifying variables, oracles and constraints (needed e.g. for Lagrangian relaxations of cutting planes; see also the Tutorial Implementation of the SDP Max-Cut Relaxation with Triangle Separation)
The first two interfaces only use standard types and constructs of the respective languages, the third interface relies heavily on a subpackage of matrix classes also provided with this software.
See the Online-Manual for further details.
Anything free comes without guarantee:
This program is distributed is under the terms of the
Gnu General Public License, Version 3 or any later version,
in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Manual
An Online-Manual is available.
Please give me
your feedback on errors and misleading explanations ...
Source Code
- CB_v1.a.2.tgz ( 5451 kB packed, 05.10.2021)
tested with g++ (GCC) 7.5.0 and 9.2.0 (Ubuntu Linux)
Installation: After having downloaded the file do the following:
tar xzvf CB_v1.a.2.tgz
cd ConicBundle
more README
Follow the instructions in the README file.
Related Ressources
Obsolete Versions
- CB_v0.3.11.tgz ( 1109 kB packed, 28.10.2011)
tested with g++ (GCC) 4.5.1 (SuSE Linux)