cddlib

What is cddlib?

In order to generate search directions in certain cases (see below), we use the library cddlib, which is a C implementation of the Double Description Method of Motzkin et al.. The library is written by Komei Fukuda. The cddlib library may be used to transform a H-representation of a polyhedron into a V-representation and visa versa.

The H-representation of a polyhedron ${\cal P}$ describes ${\cal P}$ in terms of intersecting half-spaces:
${\cal P} = \{ x \in {\rm R}^n : Ax \le b \}$
where is an $(m \times n)$ matrix.
The V-representation of a polyhedron ${\cal P}$
${\cal P} = \{ x \in {\rm R}^n: x = W\gamma + Y\lambda,\; {\rm where } \sum_i \gamma_i = 1 \; {\rm and }\; \lambda \ge 0 \}$
where and are $(n \times d)$ and $( n \times s)$ matrices respectively.

The version of cddlib that is included with APPSPACK is version 0.94, which was downloaded from http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html on Sept. 14, 2005. Specifically, we are using the following files: cdd.h, cddcore.c, cddio.c, cddlib.c, cddlp.c, cddmp.c, cddmp.h, cddproj.c, cddtypes.h, setoper.c, setoper.h.

How cddlib is used within APPSPACK

When only variable bounds are present, generating a set of search directions that are tangential to nearby constraints is simple and straightforward, i.e. one may always choose from the compass search directions

$\{\pm e_1, \pm e_2, \ldots, \pm e_n\}.$

However, in the presence of general linear constraints, generating tangential search directions becomes more difficult. If the nearby constraints are nondegenerate, we can use basic linear algebra to compute an appropriate set of search directions. If not, however, APPSPACK solves the problem using cddlid with the compute_cone_generators() interface written by Robert Michael Lewis.

Diagram for computing directions within APPSPACK