The ConicBundle Library for Convex Optimization
Copyright (C) 2005-2020 Christoph Helmberg
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:
The library comes with three variants of interfaces:
- 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.
- 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.
An Online-Manual is available.
Please give me
your feedback on errors and misleading explanations ...
Installation: After having downloaded the file do the following:
- CB_v1.a.1.tgz ( 5242 kB packed, 06.09.2020)
tested with g++ (GCC) 7.5.0 and 9.2.0 (Ubuntu Linux)
tar xzvf CB_v1.a.1.tgz
Follow the instructions in the README file.
- CB_v0.3.11.tgz ( 1109 kB packed, 28.10.2011)
tested with g++ (GCC) 4.5.1 (SuSE Linux)