Conic programming duality - relative interior

119 Views Asked by At

Consider the primal/dual conic programming problems $$ \newcommand{\ip}[1]{\left< #1 \right>} \newcommand{\myvec}[1]{\mathbf{#1}} \newcommand{\bvec}[0]{\mathbf{b}} \newcommand{\cvec}[0]{\mathbf{c}} \newcommand{\xvec}[0]{\mathbf{x}} \newcommand{\yvec}[0]{\mathbf{y}} \newcommand{\zvec}[0]{\mathbf{z}} \begin{align} \textrm{(Primal)} \quad \max &\{ \ip{\cvec, \xvec} : \bvec - A\xvec \in L, \xvec \in K \} \tag{1} \label{eq:P} \\ \textrm{(Dual)} \quad \min &\{ \ip{\bvec, \yvec} : A^T\yvec - \cvec \in K^*, \yvec \in L^* \} \tag{2} \label{eq:D} \end{align}$$ where $K$ and $L$ are closed convex cones. Such a formulation is given in e.g. section 4.7 of Gärtner and Matousek's "Approximation Algorithms and Semidefinite Programming". They state that if the primal has finite value $\gamma$ and has an interior point then the dual is feasible and has the same value $\gamma$ (strong duality).

They define an interior point as a feasible point such that:

  • (IP:1) in the case that $L$ is full dimensional, $\bvec-A\xvec \in \operatorname{int}(L)$
  • (IP:2) if $L=\{0\}$ then $x \in \operatorname{int}(K)$.

Is there a more general statement that can be made in the case that $L$ is not full dimensional and not $\{0\}$?

For example, I would think that one could obtain strong duality by defining an interior point to be one in which $\bvec-A\xvec\in\operatorname{relint}(L)$ and $\xvec\in\operatorname{relint}(K)$, where $\operatorname{relint}$ is the relative interior. My reasoning on this is as follows: one could define the slack variable $\zvec=\bvec-A\xvec$ in order to obtain the program $$\begin{align} \max \{ \ip{\cvec, \xvec} : \bvec - A\xvec - \zvec=0, \xvec \oplus \zvec \in K \oplus L \}. \tag{3}\label{eq:Aeq} \end{align}$$ Now characterization (IP:2) applies since $A$ only appears in the equality constraints. Unfortunately, $\operatorname{int}(K \oplus L)$ will be empty if either cone is not of full dimension. But $K$ and $L$ will be full dimension within their affine subspaces (which will be some subspace of the vector space that $K \oplus L$ is in). The components of $\xvec \oplus \zvec$ orthogonal to that space are forced zero and so these variables can be removed from the problem with no effect. Consequently, strong duality for $\eqref{eq:Aeq}$ holds if there is an $\xvec \oplus \zvec \in \operatorname{relint}(K \oplus L) = \operatorname{relint}(K) \oplus \operatorname{relint}(L)$ with $\bvec - A\xvec - \zvec=0$. Equivalently, strong duality holds for $\eqref{eq:P}$ if there is an $x \in \operatorname{relint}(K)$ such that $\bvec-A\xvec \in \operatorname{relint}(L)$. And the dual of $\eqref{eq:Aeq}$ is equivalent to $\eqref{eq:D}$.

Is this reasoning sound? If so, is there a citeable reference that spells this out? And, is there some even more general statement? My characterization is strictly more general than (IP:2) but does not include (IP:1), since that does not require $x\in\operatorname{relint}(K)$, only $x \in K$.