The DDS code is implementing a primal-dual infeasible-start interior-point algorithm for convex optimization problems, specifically designed for problems given in the Domain-Driven formulation .
A convex optimization problem is said to be in the Domain-Driven setup if it is in the form \begin{eqnarray} \label{main-p} \inf _{x} \{\langle c,x \rangle : Ax \in D\}, \end{eqnarray} where \(x \mapsto Ax : \mathbb R^n \rightarrow \mathbb R^m \) is a linear embedding, with \(A\) and \(c \in \mathbb R^n\) are given, and \(D \subset \mathbb R^m\) is a convex set defined as the closure of the domain of a given \(\vartheta\)-self-concordant (s.c.) barrier \(\Phi\). S.c. functions and s.c. barriers were introduced in the seminal book of Nesterov and Nemirovskii .
A s.c. barrier is a convex function whose second derivative regulates its third and first derivatives. Every open convex set is the domain of a s.c. barrier. Thus, in principle, every convex optimization problem can be treated in the Domain-Driven setup. In applications, the restrictive part of the above Definition is that a "computable" s.c. barrier is not necessarily available for a general convex set. However, for many interesting convex sets (each of which allows us to handle a class of convex optimization problems), we know how to construct an efficient s.c. barrier. Specifically, the feasible region of many classes of problems that arise in practice is the direct sum of small dimensional convex sets with known, computable s.c. barriers. In the case of linear programming, for example, consider the 1-dimensional set \(\{z \in \mathbb R: z \geq \beta\}\) for \(\beta \in \mathbb R\). It is well-known that \(-\ln(z-\beta)\) is a s.c. barrier for this set. Using this simple function and the fact that if convex sets \(D_1\) and \(D_2\) have s.c. barriers \(f_1\) and \(f_2\), respectively, then \(f_1+f_2\) is a s.c. barrier for the direct sum of \(D_1\) and \(D_2\), we can construct a s.c. barrier for any polyhedron; for \(A \in \mathbb R^{m \times n}\) and \(b \in \mathbb R^m\), a s.c. barrier for \[ \{x \in \mathbb R^n: Ax \leq b\}=\{x \in \mathbb R^n: Ax \in D\}, \] where \(D:=b-\mathbb R^m_+\), is \(-\sum_{i=1}^m \ln(b_i-a_i^\top x)\), where \(a_i^\top\) is the \(i\)th row of \(A\). This discussion for LP exemplifies the fact that knowing a s.c. barrier for small dimensional convex sets combined with the direct sum operator lets us solve problems with an arbitrarily large number of variables and constraints (of the same type).
The power of the Domain-Driven setup is further accentuated when we consider the possibility of direct summing (or alternatively, intersecting) convex sets of different types. As you can see in the users' guide, Domain-Driven form covers many set constraints/functions. In the following we show two popular examples. Many of these s.c. functions can be found in Nesterov and Nemirovski's book.
optimization over symmetric cones is a special case of the Domain-Driven setup. The following table shows the constraints that specify \(D\) and a s.c. barrier associated with the convex set defined by the constraint.
| class | constraint | s.c. barrier \(\Phi\) |
|---|---|---|
| LP | \(z \leq \beta, \ \ z, \beta \in \mathbb R\) | \(-\ln(\beta-z)\) |
| SOCP | \(|z\| \leq t, \ \ z \in \mathbb R^n, \ \ t \in \mathbb R\) | \(-\ln(t^2 - z^\top z)\) |
| SDP | \(Z \preceq B, \ \ Z,B \in \mathbb S^n\) | \(-\ln(\det(B-Z))\) |
For example, if our problem has a constraint of the form \(a^\top x \leq \beta\) for \(a \in \mathbb R^n, \beta \in \mathbb R\), the convex set defined by this constraint is the set of \(x \in \mathbb R^n\) such that \(a^\top x \in \{z: z \leq \beta\}\).
The Domain-Driven setup allows inequalities of the form \begin{eqnarray} \label{intro-3} \sum_{i=1}^\ell \alpha_i f_i(a_i^\top x + \beta_i) + g^\top x + \gamma \leq 0, \ \ \ a_i, g \in \mathbb R^{n}, \ \ \beta_i, \gamma \in \mathbb R, \ \ i \in \{1,\ldots,\ell\}, \end{eqnarray} where \(\alpha_i \geq 0\) and \(f_i(x)\), \(i \in \{1,\ldots,\ell\}\), can be any univariate convex function whose epigraph is a 2-dimensional set equipped with a known s.c. barrier. Three popular examples are given in the following table, and several more can be found in Nesterov and Nemirovski's book. The fact that constraints of the above form fit into the Domain-Driven setup is implied by the following relation: \begin{eqnarray} \label{eq:DD-example-1} \begin{array}{rcl} &&\left \{ x : \sum_{i=1}^\ell \alpha_i f_i(a_i^\top x + \beta_i) + g^\top x + \gamma \leq 0 \right \} \\ &=&\left \{ x : \exists u \in \mathbb R^\ell \ \text{such that} \ \sum_{i=1}^\ell \alpha_i u_i + g^\top x + \gamma \leq 0, \ \ f_i(a_i^\top x + \beta_i) \leq u_i, \ \forall i \right \}. \end{array} \end{eqnarray} Note that Geometric Programming and Entropy Programming with vast applications in engineering are constructed with constraints of the above form when \(f_i(z)=e^z\) for \(i\in\{1,\ldots,\ell \}\) and \(f_i(z)=z\ln(z)\) for \(i\in\{1,\ldots,\ell \}\), respectively.
| set \((z,t)\) | s.c. barrier \(\Phi(z,t)\) |
|---|---|
| \(e^z \leq t\) | \(-\ln(\ln(t)-z)-\ln(t)\) |
| \(z \ln(z) \leq t, \ z>0\) | \(-\ln(\ln(t)-z)-\ln(t)\) |
| \(|z|^p \leq t, \ p \geq 1\) | \(-\ln(t^{\frac 2p} - z^2) - 2\ln(t)\) |