Implicit Redundancy and Degeneracy
in Conic Program

Given a linear map ${\mathcal{T}}$, we let ${\mathcal{T}}^{*}$ be the adjoint of ${\mathcal{T}}$. We use $\langle\cdot,\cdot\rangle_{\mathbb{E}}$ to denote the inner product between two vectors in the Euclidean space $\mathbb{E}$; we omit the subscript $\mathbb{E}$ when the meaning is clear. We use ${\mathcal{R}}({\mathcal{T}})$ to denote the range of the map ${\mathcal{T}}$. Given a matrix $X$, $\operatorname{range}(X)$ denotes the range of $X$, formed by the linear combinations of columns of $X$. $\operatorname{null}(X)$ is used to denote the null-space of $X$.

Given a set ${\mathcal{X}}\subset\mathbb{E}$, $\operatorname{{int}}({\mathcal{X}})$ ($\operatorname{{relint}}({\mathcal{X}})$, resp.) means the interior (relative interior, resp.) of ${\mathcal{X}}$. The dimension and the span of ${\mathcal{X}}$ are denoted $\dim({\mathcal{X}})$ and $\operatorname{{span}}({\mathcal{X}})$, respectively. We use ${\mathcal{X}}^{\perp}$ to indicate the orthogonal complement of ${\mathcal{X}}$. Given a vector $x$, we often use $x^{\perp}$ to mean $\{x\}^{\perp}$. $\mathbb{R}^{n}$ and $\mathbb{S}^{n}$ denote the usual vector spaces of vector of $n$ coordinates and $n$-by-$n$ symmetric matrices, respectively. Given a matrix $A$ of size $m$-by-$n$ and an index set ${\mathcal{I}}$, we use $A(:,{\mathcal{I}})$ for the submatrix of $A$ formed by the columns of $A$ that correspond to ${\mathcal{I}}$.

$\mathbb{R}_{+}^{n}$ is used for the nonnegative orthant $\{x\in\mathbb{R}^{n}:x_{i}\geq 0,\forall i\}$ and $\mathbb{S}_{+}^{n}$ is used for the set of $n$-by-$n$ positive semidefinite matrices, $\{X\in\mathbb{S}^{n}:\langle y,Xy\rangle_{\mathbb{R}^{n}}\geq 0,\forall y\in\mathbb{R}^{n}\}$. When a general conic program is discussed, we omit the subscript and use the symbol ${\mathcal{F}}$. We use the notation ${\mathcal{F}}_{\mathcal{K}}$ to distinguish a particular setting for the cone ${\mathcal{K}}$ from a general conic program. For example, when the feasible region of the semidefinite program is discussed, we use ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$.

The concept of implicit redundancies is introduced recently [18, 15]. Using this notion, [18] shows that every extreme point (basic feasible solution) of ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ is degenerate in the absence of strict feasibility. [15] shows that ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ also contains implicit redundant constraints in the absence of strict feasibility. Using the notion of implicit redundancies, [15] tightens the Barvinok-Pataki bound [3, 21], and further improves the bound presented in [17]. On the degeneracy side, a recent work [16] links the definition of degeneracy introduced by Pataki [34, Definition 3.3.1] to realize that every point in ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ is degenerate. This is done by exploiting the facial structure of $\mathbb{S}_{+}^{n}$. Since a linear program is a special case of a semidefinite program, it immediately implies that every point in ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ is degenerate, not just limited to the extreme points.

A closed convex set ${\mathcal{K}}\subseteq\mathbb{E}$ is said to be a cone if $x\in{\mathcal{K}}$ implies $\alpha x\in{\mathcal{K}}$, $\forall\alpha\geq 0$. The dual cone of ${\mathcal{K}}$ is ${\mathcal{K}}^{*}:=\{z\in\mathbb{E}:\langle z,x\rangle\geq 0,\forall x\in{\mathcal{K}}\}$. A convex set $f$ is called a face of ${\mathcal{X}}\subseteq\mathbb{E}$ (denoted $f\unlhd{\mathcal{X}}$) if

A face $f\unlhd{\mathcal{K}}$ is said to be exposed if $f={\mathcal{K}}\cap\{z\}^{\perp}$ for some $z\in{\mathcal{K}}^{*}$. ${\mathcal{K}}$ is said to be facially exposed if every face of ${\mathcal{K}}$ is exposed. Given a convex set ${\mathcal{X}}\subset{\mathcal{K}}$, the minimal face of ${\mathcal{K}}$ containing ${\mathcal{X}}$, denoted $\operatorname{face}({\mathcal{X}},{\mathcal{K}})$, is the intersection of faces of ${\mathcal{K}}$ that contains $f$, i.e.,

It is known that a point $\hat{x}\in\operatorname{{relint}}({\mathcal{X}})$ provides the characterization $\operatorname{face}({\mathcal{X}},{\mathcal{K}})=\operatorname{face}(\hat{x},{\mathcal{K}})$; see [9, Proposition 2.2.5]. Given a face $f\unlhd{\mathcal{K}}$, the conjugate face of $f$, denoted $f^{\Delta}$, is

Understanding the facial structure of a cone is important for designing a computationally efficient algorithm. Examples of cones that demonstrate great computational powers include the nonnegative orthant $\mathbb{R}_{+}^{n}$, the positive semidefinite cone $\mathbb{S}_{+}^{n}$, and the second-order (Lorentz) cone. Moreover, these cones lead to many successful interior point methods for solving the linear, semidefinite, second-order cone programs and the programs with Cartesian products of these cones [2, 30, 27].

We list facial characterizations of two cones. Every face $f\unlhd\mathbb{R}_{+}^{n}$ has the form

where $V=I_{n}(:,{\mathcal{I}}^{c})$ for some index set ${\mathcal{I}}\subseteq\{1,\ldots,n\}$ and $I_{n}$ is the $n$-by-$n$ identity matrix. Here, ${\mathcal{I}}^{c}=\{1,\ldots,n\}\setminus{\mathcal{I}}$, the complement of ${\mathcal{I}}$. $\mathbb{S}_{+}^{n}$ is another example of a well-understood cone. Every face $f\unlhd\mathbb{S}_{+}^{n}$ has the form

where $\operatorname{range}(Q)=\operatorname{null}(\hat{X})$ for some $\hat{X}\in\operatorname{{relint}}(f)$ and $V\in\mathbb{R}^{n\times\operatorname{{rank}}(\hat{X})}$ satisfies $\operatorname{range}(V)=\operatorname{range}(\hat{X})$. Both $\mathbb{R}_{+}^{n}$ and $\mathbb{S}_{+}^{n}$ are facially exposed. Other examples of facially exposed cones are the second-order cone, the doubly nonnegative cone, the hyperbolocity cone [23, Theorem 23] and the cone of Euclidean distance matrices [29]. On the other hand, not every cone is facially exposed. For example, the exponential cone [19], the completely positive cone [35], and the copositive cone [10] are known to be not facially exposed.

Facial reduction (FR) is first introduced by Borwein and Wolkowicz in the $1980$’s [5, 6]. In-depth analysis for conic programs with linear objective functions, especially for semidefinite programs, has been conducted for the last two decades. Successful applications of FR are the semidefinite relaxations of NP-hard binary combinatorial optimization problems (e.g., see [36, 7]); and an analytical tool for measuring hardness of solving a problem numerically (e.g., see [28, 26]).

Facial reduction seeks to form an equivalent problem that satisfies strict feasibility. FR strives to find the minimal face of ${\mathcal{K}}$ that contains ${\mathcal{F}}$ in order to represent the set

Finding $\operatorname{face}({\mathcal{F}},{\mathcal{K}})$ is often a challenging task and hence we often rely on an auxiliary lemma. Lemma 2.1 below lies in the heart of the FR algorithm.

We note that a solution $y$ to (2.3) yields

In other words, every feasible point $x\in{\mathcal{F}}$ lies in the orthogonal complement of ${\mathcal{A}}^{*}y$, i.e.,

Consequently, we can rewrite the set ${\mathcal{F}}$ by

The ambiant space now reduces from $\mathbb{E}=\operatorname{{span}}({\mathcal{K}})$ to $\operatorname{{span}}({\mathcal{K}}\cap({\mathcal{A}}^{*}y)^{\perp})$; the dimension reduction is an attractive by-product of the FR process. This completes one iteration of the FR algorithm. Then the FR algorithm replaces the cone as in (2.4) (i.e., ${\mathcal{K}}\leftarrow{\mathcal{K}}\cap({\mathcal{A}}^{*}y)^{\perp}$) and solves the system 2.3 repeatedly until a strictly feasible point with respect to the reduced cone is guaranteed. Algorithm 2.1 summarizes the FR process.

Upon the termination of the FR process Algorithm 2.1, we obtain

Thus FR process allows an alternative representation of ${\mathcal{F}}$ that satisfies strict feasibility:

It is important to note that the FR process does not alter the points in the set ${\mathcal{F}}$, i.e.,

where each ${\mathcal{F}}^{i}$ is defined in Algorithm 2.1. We emphasize that the representation of ${\mathcal{F}}^{i}$ is different from ${\mathcal{F}}^{j}$, when $i\neq j$.

The shortest length of FR process is called the singularity degree of ${\mathcal{F}}$, $\operatorname{sd}({\mathcal{F}})$, first proposed by Sturm [28] for the class of semidefinite programs. This implies that Algorithm 2.1 requires at least $\operatorname{sd}({\mathcal{F}})$ number of iterations. Indicated by (2.5), we have ${\mathcal{F}}={\mathcal{F}}^{\operatorname{sd}({\mathcal{F}})}$ and we use the superscript to distinguish the different representations of the set ${\mathcal{F}}$. Hence strict feasibility fails for ${\mathcal{F}}$, $\operatorname{sd}({\mathcal{F}})\neq\operatorname{sd}({\mathcal{F}}^{\operatorname{sd}({\mathcal{F}})})$ and $\operatorname{sd}({\mathcal{F}}^{\operatorname{sd}({\mathcal{F}})})=0$. While it is possible to construct a general conic program that has an arbitrarily large singularity degree, linear programs have $\operatorname{sd}({\mathcal{F}}_{\mathbb{R}_{+}^{n}})\leq 1$ regardless of the problem dimension. $\operatorname{sd}({\mathcal{F}})$ is often used as a measure of the hardness of solving a problem numerically by engaging error bounds; see [26, 28].

Example 2.2 below is an illustration of the FR process. We leave more details on the FR algorithm to [9, 11] for general conic programs, [25, 18] for ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ and ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ and related examples.

It is well-known that FR applied to ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ and ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ generates ${\mathcal{F}}_{\mathbb{R}_{+}^{k}}$ and ${\mathcal{F}}_{{\mathbb{S}^{k}_{+}}\,}$, where $k<n$. In plain language, FR for linear and semidefinite programs produces another semidefinite and linear programs in smaller dimensional spaces. This can be seen from the facial characterizations (2.1) and (2.2). It is because $\mathbb{R}_{+}^{n}$ and $\mathbb{S}_{+}^{n}$ are self-reproducing cones. The FR process illustrated in Example 2.2 shows that the self-reproducibility does not apply a general conic program. Note that $K_{\text{exp}}$ is not polyhedral but the first FR iteration in Example 2.2 produces a polyhedral cone $K_{\text{exp}}\cap(A^{*}\lambda^{1})^{\perp}$.

The feasible system ${\mathcal{F}}$ is known to hold strict feasibility generically [22] and FR may seem unnecessary. However, many practical real-life examples seem to fail strict feasibility, e.g., see [18, 14]. As addressed in [18], a significant number of instances from the well-known NETLIB collection fails strict feasibility. We note that the significance of FR on ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ has only been a recent topic of discussion.

It is important to note that FR enables the restriction of the domain within which we can operate with ${\mathcal{A}}$. Without FR, we cannot restrict the domain of ${\mathcal{A}}$ without any further analysis. We utilize this observation to discuss the main results in Section 3 below.

In this section we introduce a known notion of degeneracy and discuss related results.

Characterizations of Definition 2.3 are available for some cones. Given $\bar{x}\in{\mathcal{F}}_{\mathbb{R}_{+}^{n}}$, let $\operatorname{{supp}}(\bar{x})$ be the support of $\bar{x}$, $\{i\in\{1,\ldots,n\}:\bar{x}_{i}\neq 0\}$. Let $A$ be a matrix representation of ${\mathcal{A}}:\mathbb{R}^{n}\to\mathbb{R}^{m}$. Then $\bar{x}$ is called degenerate if $A(:,\operatorname{{supp}}(\bar{x}))$ has linearly dependent rows; see [34, Example 3.3.1]. We note that the usual degeneracy of a basic feasible solution for the standard linear program agrees with the degeneracy discussed in [34, Example 3.3.1]. A basic feasible solution $x^{\prime}$ of the standard linear program is called degenerate if there is a basic variable equal to $0$; see [4, Section 2]. This implies that $A(:,\operatorname{{supp}}(x^{\prime}))$ (a submatrix of the so-called basis matrix) is a full-column rank matrix with more rows than columns. The characterization immediately indicates that $x^{\prime}$ is degenerate.

A nice characterization of Definition 2.3 customized for ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ is available as well. For $\bar{X}\in{\mathcal{F}}_{\mathbb{S}_{+}^{n}}$, let $\bar{X}=\begin{bmatrix}V_{1}&V_{2}\end{bmatrix}\begin{bmatrix}R&0\\ 0&0\end{bmatrix}\begin{bmatrix}V_{1}^{T}\\ V_{2}^{T}\end{bmatrix}$ be a spectral decomposition of $\bar{X}$, where $R$ is a positive definite matrix of order $\operatorname{{rank}}(\bar{X})$. Let $\langle A_{i},X\rangle_{\mathbb{S}^{n}}=b_{i}$ be the $i$-th equality of the system ${\mathcal{A}}X=b\in\mathbb{R}^{m}$. Then [34, Corollary 3.3.2] states

In [16, Section 2], the degeneracy of each point in ${\mathcal{F}}_{\mathbb{S}_{+}^{n}}$ is realized using the characterization (2.6). We briefly explain the steps for recognizing the degeneracy. Since $\mathbb{S}_{+}^{n}$ is facially exposed, we always obtain $\operatorname{face}({\mathcal{F}},\mathbb{S}_{+}^{n})=V\mathbb{S}_{+}^{r}V^{T}$ for some full column rank matrix $V\in\mathbb{R}^{n\times r}$. Then a solution $y$ to (2.3) is used to detect the linear dependence of the matrices in (2.6) after FR. We leave more details to [16, Section 2].

The characterizations of degeneracies in the case of ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ and ${\mathcal{F}}_{\mathbb{R}_{+}^{n}}$ owe to the computationally amenable facial structures (2.1) and (2.2). This again emphasizes the importance of understanding facial geometry of cones.