\section{Introduction}\label{sec-introduction}

The complementarity partitions for linear programming and linear complementarity problems are well understood and are utilised heavily in the analysis of optimisation problems as well as in numerical methods. In addition to the strong duality, linear programming problems exhibit strict complementarity: in an appropriately formulated pair of primal and dual problems each primal variable has a dual counterpart, and a fully complementary pair, such that exactly one variable in the pair is positive and the other one is zero. The situation is much more complex for general linear conic problems. Even in the absence of the duality gap it may happen that both primal and dual variables are zero, or as it happens in the case of a multifold system, both lie on the boundary of component cones. Moreover, there are several different definitions of complementarity that do not coincide and lead to different characterisations.

In some special cases, especially when a homogeneous feasibility problem is considered, complementarity partition can be identified via an algorithm. The polyhedral (linear programming) case was considered in \cite{JavierNegar,Vavasis}, and it was shown in \cite{Terlaky} that it is possible to identify the partition of \cite{BonRam} via a variant of an interior point method for second-order conic programming. The complementarity partition is related to generalised condition measures for multifold conic systems, see \cite{CuckerPena}.

Recall that in the linear case the complementarity partition has a simple and well-studied structure. Consider the primal-dual pair of linear programming problems
\begin{equation} \label{pb:PL}
\begin{split}
\min_{x\in \mathbb{R}^n} \quad & c^\top x \notag \\
 \text{s.t.} \quad  & Ax \geq  b,   
\end{split} \quad \text{(LP)}\qquad \quad 
\begin{split}
\max_{y\in \mathbb{R}^m} \quad & b^\top y \notag \\
 \text{s.t.} \quad  & A^\top y =  c,\\
 & y\geq 0.   
\end{split} \quad \text{(LD)}
\end{equation}
Here $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^m$, $c\in \mathbb{R}^n$. The classical Goldman-Tucker theorem \cite{GoldmanTucker} (also see \cite[Proposition 17.16]{BGLSa} for modern treatment) states that when either one of the problems has a finite optimal value, there exists a unique partition $(B,N)$ of the index set $J=\{1,\dots, m\}$ that is of maximal complementarity. In other words, there is a  pair  $(\bar x, \bar y)$ of optimal solutions to (LP) and (LD) such that for $\bar s= A\bar x-b$ and $\bar y$ we have $\bar s_B>0$, $\bar y_N>0$, and moreover for any optimal solution $(s = A x-b,y) $ always $ y_B = 0$, $ s_N = 0$.  

The optimal partition also features in the study of monotone linear complementarity problems. Let $Q$ and $R$ be $n\times n$ matrices, and let $h\in \mathbb{R}^n$. The linear complementarity problem 
$$
\begin{cases}
xs = 0,\\
Qx+Rs = h,\\
x\geq 0, \quad s\geq 0,
\end{cases}
$$
is called monotone if $Qu+Rv = 0$ yields $u^\top v\geq 0$. For monotone linear complementarity problems the optimal partition is of the form $(B,N,T)$, where $T$ corresponds to the subset of indices for which both $s$ and $x$ components are zero for every solution. 

The linear complementarity partition is reminiscent of the situation encountered in multifold conic systems. When the system of linear inequalities is replaced by a product of general closed convex cones (as in the case of second-order cone programming for instance), the partition of indices becomes more complex since the component variables may end up on the boundary of the cones. 

In \cite{BonRam} a four-set partition was introduced for general multifold conic systems, based on regularity conditions involving normal cones. In \cite{PR2012} a refined six-set partition was suggested for homogeneous feasibility problems and a geometric characterization of such partition was obtained. Our goal is to generalize the latter partition to multifold conic optimization problems and compare the two partitions. 

We focus on the case when strong duality holds for the primal-dual pair of conic optimization problems. In case this condition does not hold, primal problem can be rewritten by means of the facial reduction approach. This leads to an equivalent primal problem for which Slater condition holds as well as the strong duality provided an ad-hoc dual problem is considered. We refer the reader to recent works on facial reduction \cite{PatakiStrong,FRedPolyh,WakiMuramatsu} and Ramana Duals \cite{StrongDuality,Ramana} for modern approaches to inducing the Slater condition and the strong duality in ill-posed conic problems.

We introduce the two types of partitions in Section~\ref{sec:partitions}, show the relations between them in Lemma~\ref{lem:RinC}, treat the special case of second-order cones in Lemma~\ref{lem:partsoc}  and provide some illustrative examples. In Section~\ref{sec:hom} we relate the geometric relations of  \cite{PR2012} to the four-set partition of \cite{BonRam} in Lemma~\ref{thm:RDualChar}. We finish with a study of the relations between partitions of reformulated (lifted) problems in Section~\ref{sec-dual-socp-b}, strengthening some results of \cite{BonRam}.


Throughout the paper we work in a Hilbert finite dimensional (Euclidean) setting. By $x\cdot y$ we denote the standard inner product of two vectors $x,y\in \mathbb{R}^n$, $x\cdot y := \sum_{i=1}^n x_i y_i$, where $x= (x_1, \dots, x_n)$, $y = (y_1,\dots, y_n)$, and use standard Euclidean norm $\|x\| = \sqrt{x\cdot x}$.


\section{Partitions for multifold conic optimization problems}\label{sec:partitions}



Consider a general linear conic optimization
problem with constraints in product form, i.e.,
\begin{align}
\label{pb:cop}
 \min_{x\in \mathbb{R}^n} \quad &  c\cdot x \notag \\
 \text{s.t.} \quad  &    A^j x - b^j  \in K_j \quad  \forall j\in J,\tag{P}
\end{align}
where $K_j$ is a closed convex cone in $\mathbb{R}^{q_j}$, $q_i \in \mathbb{N}$ for every $j\in J$, and $J = \{1,\dots, r\}$ is a finite index set.
We set $K :=K_1\times\cdots\times K_r$, and define
$A=(A^1;\cdots;A^r)$ as the matrix
whose rows are those of $A^1$ to $A^r$, and $b := \mathop{\rm vec}(b^1,\ldots,b^r)$
so that \eqref{pb:cop} is equivalent to
$$
\min_{x\in \mathbb{R}^n} \{ c\cdot x; \; Ax-b \in K\}.
$$
The dual problem is 
\begin{align}
\label{pb:dcop}
\max_{y^1,\ldots,y^r} \quad & 
 \sum_{j=1}^r b^j\cdot y^j\notag \\ 
\text{s.t.}\quad &  \sum_{j=1}^r (A^j)^\top y^j = c,\tag{D}\\
& y^j \in K_j^+ \quad \forall j\in J,\notag
\end{align}
where the (positive) polar of a set $C\subset \mathbb{R}^m$
is defined as
$C^+ :=\{ y\in \mathbb{R}^{m}; \; y\cdot z \geq 0, \;
\forall  z \in C\}$.
Generally speaking, such primal-dual pairs of linear conic problems may have a nonzero duality gap (see \cite[Section~11.6]{Guler} for a detailed discussion and \cite[Section~3.2]{Renegar} for examples). The Slater condition together with the bounded objective for either \eqref{pb:cop} or \eqref{pb:dcop} guarantees zero duality gap. If the primal and dual optimal values are equal, a pair $(x,y)$ of optimal solutions to primal and dual problems is characterized by the
complementarity system
\begin{align}
\label{pb:copos}
A^j x - b^j & \in K_j, \notag \\
 y^j & \in K_j^+,\notag \\
y^j \cdot (A^j x - b^j)& =0 \quad  \forall  j\in  J,\tag{C}\\ 
A^\top y & = c.\notag
\end{align}
We denote by $S\eqref{pb:copos}$ the set of solutions for relations \eqref{pb:copos}. Observe that $S\eqref{pb:copos}$ is nonempty if and only if the pair \eqref{pb:cop}--\eqref{pb:dcop} has zero duality gap. This condition will be assumed throughout the manuscript.




We say that {\em strict primal (resp. dual) feasibility} holds for
$j \in J$ if there exists
$x \in F\eqref{pb:cop}$ such that $A^j x-b^j \in \mathop{\rm int} K_j$
(resp. $y\in F\eqref{pb:dcop}$ such that $y^j \in \mathop{\rm int} K_j^+$). Here by $F\eqref{pb:cop}$ and $F\eqref{pb:dcop}$ we denote the set of feasible solutions to the problems \eqref{pb:cop} and \eqref{pb:dcop} respectively.


\if{

\begin{lema}
\label{strict-local}
Let $j$ be strictly primal (resp. dual) feasible.
Then the set
$\{y^j; y\in S\eqref{pb:dcop} \}$
(resp. $\{A^j x-b^j; x\in S\eqref{pb:cop} \}$)
is bounded.
\end{lema}

\begin{proof}
If $j$ is strictly primal feasible, there exists $x\in F\eqref{pb:cop}$ and
$\varepsilon >0$ such that $s=A x-b$ satisfies $s^j + \varepsilon B \subset
K_j$, or equivalently $\varepsilon B \subset s^j - K_j$. Let $y \in
S\eqref{pb:dcop}$. Since $y^j\in K_j^+$, it follows that $\varepsilon \|y^j\|
\leq y^j \cdot s^j$. Using also $y^{j'} \cdot s^{j'} \geq 0$, for
all $j'$, we get
$$
0= x\cdot ( c-A^\top y) = c\cdot x - y\cdot Ax
  = c\cdot x - b\cdot y - y\cdot s
  \leq c\cdot x - b\cdot y - \varepsilon \|y^j\|.
$$
In other words,
$\varepsilon \|y^j\| \leq c\cdot x - b\cdot y = c\cdot x -  \mathop{\rm val}\eqref{pb:dcop}$,
which gives the desired estimate.
The proof for the dual statement is similar.
\end{proof}



Note that the hypothesis of the above lemma does not imply the absence
of a duality gap.

}\fi

One says
(e.g., \cite[Def. 4.74]{BSbook})
that the {\em strict complementarity hypothesis}
holds for problem \eqref{pb:cop} if there exists a pair
$(x,y)$ solution of the optimality system \eqref{pb:copos}, such that
$-y \in \mathop{\rm ri} N_K(Ax-b)$, where $N_K$ is the normal cone of convex
analysis (see \cite[Section~A.5.2]{JBHULem}). Since $K$ is a closed convex cone, we have for $s\in K$ that
\begin{equation}
\label{formul-nk}
N_K(s) = \left\{
\begin{array}{cc}
(-K^+) \cap s^\perp, & s\in \partial K,\\
\emptyset, & s\notin K,\\
\{0\}, & s\in \mathop{\rm int} K,\\
\end{array}
\right.
\end{equation}
where $s^\bot$ denotes the orthogonal complement to the linear span of $s$.

For problems with constraints in the product form as in \eqref{pb:cop}, we introduce the notion of {\em componentwise strict complementarity}, which means that for each component $j$ there exists
a pair $(x,y) \in S\eqref{pb:copos}$, such that $-y^j \in \mathop{\rm ri}
N_{K_j}(A^jx-b^j)$. It is shown in Corollary~\ref{cor:compequal} that the two notions are equivalent.

In \cite{BonRam} the notion of optimal partition, well known for linear programming and
monotone linear complementarity problems
(see e.g. \cite[Section 18.2.4]{BGLSa}), was extended to the abstract framework.
Let 
\begin{align*}
B   &= \{j\,|\, \exists (x,y) \in S\eqref{pb:copos}\; \text{s.t.}\; A^j x-b^j \in \mathop{\rm int} K_j\}\\
N   &= \{j\,|\, \exists (x,y) \in S\eqref{pb:copos}\; \text{s.t.}\; y^j \in \mathop{\rm int} K_j^+\}\\
R^0 &= \{j,|\, \exists (x,y) \in S\eqref{pb:copos}\; \text{s.t.}\; -y^j \in  \mathop{\rm ri} N_{K_j}(A^j x - b^j)\}.
\end{align*}
Define $R:= R^0\setminus (B\cup N)$, $T:=J\setminus (R^0\cup B \cup N)$.
The next statement follows from \cite[Lemma 3]{BonRam}.
\begin{lema}
\label{mcopos.l3}
If $S\eqref{pb:copos}$ is not empty, the partition $(B,N,R,T)$ is a disjoint partition of the index set $J$. 
\end{lema}



\begin{defi}
Any pair $(x,y) \in S\eqref{pb:copos}$ satisfying the relations below is
said to be of maximal complementarity:
\begin{equation}
\label{pb:copri}
\left\{ \ba{lll}
{\rm (i)} \;
A^j x-b^j \in \mathop{\rm int} K_j, \; \;\forall j\in B,\\
{\rm (ii)}  \;
y^j \in \mathop{\rm int} K_j^+, \; \;\forall j\in N,
\\
{\rm (iii)}  \;
-y^j \in \mathop{\rm ri} N_{K_j}(A^j x-b^j), \; \;\forall j\in R.
\ea \right.
\end{equation}
\end{defi}

For each $j\in B\cup N\cup R$ let $(x(j),y(j)) \in S\eqref{pb:copos}$ be such that
$$ 
\begin{cases}
A^j x^j(j)-b^j \in \mathop{\rm int} K_j & \text{if}\quad j \in B,\\
y^j(j) \in \mathop{\rm int} K_j & \text{if}\quad j \in N,\\
-y^j(j) \in \mathop{\rm ri} N_{K_j}(A^j x(j)-b^j) & \text{if}\quad j \in R.
\end{cases}
$$
We define
\begin{equation}\label{eq:maxcomconstr}
\hat{x} := (|B|+|R|)^{-1}\sum_{j\in B\cup R} x(j); \quad
\hat{y} := (|N|+|R|))^{-1}\sum_{j\in N\cup R} y(j).
\end{equation}

\if{

Let us state some properties of the set of
maximal complementarity solutions.
We need a preliminary lemma.


\begin{lema}
\label{mcopos.l4a}
Let $K$ be a closed convex cone.
Let $s^i \in K$, for $i=1,2$,
$- y^1 \in N_K(s^1)$, and $- y^2 \in \mathop{\rm ri} N_K(s^2)$.
Given $\alpha \in ]0,1[$, set
$(s,y) := \alpha (s^1,y^1) + (1-\alpha) (s^2,y^2)$.
If $-y\in N_K(s)$, then $-y\in \mathop{\rm ri} N_K(s)$.
\end{lema}

\begin{proof}
Since $-N_K(s)=K^+\cap s^\perp$, we have that
$-y \in \mathop{\rm ri} N_K(s)$ iff, for all $z\in N_K(s)$,
$y \pm \varepsilon z \in K^+$ for small enough $\varepsilon>0$.
As $K^+$ is a cone, $y + \varepsilon z \in K^+$
always holds. Therefore we have to prove that for
$z\in N_K(s)$,
$y - \varepsilon z \in K^+$ for small enough $\varepsilon>0$.
Using
$N_K(s) = N_K(s^1) \cap N_K(s^2)$,
obtain $z \in N_K(s^2)$, and hence,
$y^2 - \varepsilon' z \in K^+$ for some $\varepsilon'>0$.
Let $\varepsilon:= (1-\alpha)\varepsilon'$. Then
$
y - \varepsilon z = \alpha y^1 + (1-\alpha)(y^2 - \varepsilon' z)
$
belongs to $K^+$.
The conclusion follows.
\end{proof}
}\fi

The next result can be found in \cite[Lemma 7]{BonRam}.

\begin{lema}
\label{mcopos.l4b} The pair $(\hat{x},\hat{y})$ defined in \eqref{eq:maxcomconstr} is of maximal complementarity. Moreover, any pair $(x,y) \in \mathop{\rm ri} S\eqref{pb:cop} \times \mathop{\rm ri} S\eqref{pb:dcop}$ is of maximal complementarity.
\end{lema}

An immediate consequence of Lemma~\ref{mcopos.l4b} is that componentwise strict complementarity yields strict complementarity, therefore the two notions are equivalent.

\begin{cor}\label{cor:compequal} Componentwise strict complementarity of \eqref{pb:cop} is equivalent to strict complementarity.
\end{cor}
\begin{proof}
Observe that strict complementarity yields componentwise strict complementarity, as we have $\mathop{\rm ri} N_K(Ax-b) = \mathop{\rm ri} N_{K_1}(A^1 x- b^1)\times \mathop{\rm ri} N_{K_2}(A^2 x- b^2)\times \cdots \times\mathop{\rm ri} N_{K_r}(A^r x- b^r)$. Any pair of strictly complementary solutions is hence componentwise strictly complementary. 
 
On the other hand, Lemma~\ref{mcopos.l4b} provides a construction for maximal complementary pair that proves the reverse inclusion.
\end{proof}


\if{

\begin{proof}
(i)
That $A^j \hat{x} -b^j \in \mathop{\rm int} K_j$, for all
$j\in B$, is a classical property. Similarly,
$\hat{y}^j \in \mathop{\rm int} K_j^+$, for all $j\in N$.
Finally, that
$-\hat{y}^j \in \mathop{\rm ri} N_{K_j}(A^j \hat{x} -b^j)$, for all $j\in R$,
is consequence of lemma \ref{mcopos.l4a}.
\\
(ii)
Let $(\hat{x},\hat{y}) \in \mathop{\rm ri} S\eqref{pb:copos}$, and
$(\tilde{x},\tilde{y}) \in S\eqref{pb:copos}$
be of maximal complementarity. Then there exists $\varepsilon >0$
such that
$(\hat{x},\hat{y}) - \varepsilon (\tilde{x},\tilde{y}) \in S\eqref{pb:copos}$.
Set
$\alpha = 1/(1+\varepsilon) \in (0,1)$.
We may write
$$
\alpha (\hat{x},\hat{y}) = \alpha [(\hat{x},\hat{y}) - \varepsilon (\tilde{x},\tilde{y})] +
(1-\alpha)(\tilde{x},\tilde{y}).
$$
Similarly, setting
$\hat{s} := A \hat{x} -b$ and $\tilde{s} := A \tilde{x} -b$,
we have that
$$
\alpha (\hat{s}^j,\hat{y}^j) = \alpha [(\hat{s}^j,\hat{y}^j) - \varepsilon (\tilde{s}^j,\tilde{y}^j)] +
(1-\alpha)(\tilde{s}^j,\tilde{y}^j).
$$
We conclude by applying lemma \ref{mcopos.l4a} to the above relation.
\end{proof}

}\fi


In a separate development \cite{PR2012} a different partition for a homogeneous feasibility problem was suggested.  In what follows we extend this definition to optimization problems, and relate it to the previously defined four-sets partition. Define the index subsets $B^0$  and $N^0$ as follows:
\begin{align*}
& B^0 = \{j\,|\, \forall (x,y) \in S\eqref{pb:copos}\quad   y^j = 0\},\\ 
& N^0 = \{j\,|\, \forall (x,y) \in S\eqref{pb:copos}\quad  A^j x-b^j = 0\}. 
\end{align*}
Define the following four sets:
$$
B' = B^0\setminus(N^0\cup B), \quad  N' = N^0\setminus(B^0\cup N), \quad O = B^0\cap N^0, C = J\setminus(N^0\cup B^0).
$$
It follows immediately from the complementarity conditions of \eqref{pb:copos} that $B\subset B^0$ and $N\subset N^0$, and that $B'\cap N' = \emptyset $. Therefore, it is not difficult to observe that the sets $B,N,B',N',O,C$ form a disjoint partition of the index set $J$. To avoid confusion, we will refer to this partition as the six-partition, whereas the four-set partition introduced before will be referred to as the four-partition. 


\begin{lema}\label{lem:RinC} The following relations between the four- and six-partitions hold.
\begin{equation}\label{eq:RinC}
T \supset B'\cup N' \cup O = (N^0\cup B^0)\setminus (N\cup B);\quad R \subset C=J\setminus(B^0\cup N^0);
\end{equation}
\end{lema}
\begin{proof} It is enough to show that $R\subset C$. Assume it is not so. Then there exists an index $j^*\in R\setminus C$. Since $C=J\setminus(B^0\cup N^0)$, $j^* \in B^0\cup N^0$.

Since $j^*\in R$, there exists a solution  $(x(j^*),y(j^*)) \in S\eqref{pb:copos}$ with 
\begin{equation}\label{eq:pf01}
- y^{j^*}(j^*) \in \mathop{\rm ri} N_{K_{j^*}}(A^{j^*} x(j^*) - b^{j^*}).
\end{equation} 

First assume that $j^* \in B^0\cap R$. This yields $y_{j^*}(j^*)=0$, and hence 
$$
0\in \mathop{\rm ri} N_{K_{j^*}}(A^{j^*} x(j^*) - b^{j^*}).
$$
This is only possible when either $N_{K_{j^*}}(A^{j^*} x(j^*) - b^{j^*})=\{0\}$ or $N_{K_{j^*}}(A^{j^*} x(j^*) - b^{j^*})$ contains lines. In the first case $A^{j^*} x(j^*) - b^{j^*}\in \mathop{\rm int} K_{j^*}$, and $j^*\in B$, and that contradicts the definition of $R$. The second case is impossible by our assumption that all cones $K_j$, $j\in J$ have a nonempty interior.

Now assume that $j^* \in N^0\cap R$. We have $A^{j^*} x(j^*) - b^{j^*}=0$, hence, \eqref{eq:pf01} yields
$$
-y^{j^*}(j^*)\in \mathop{\rm ri} N_{K_{j^*}}(A^{j^*} x(j^*) - b^{j^*}) = \mathop{\rm ri} N_{K_{j^*}}(0) = \mathop{\rm ri} (-K^+_{j^*}) = -\mathop{\rm int} K^+_{j^*},
$$ 
which yields $j^*\in N$, and contradicts the fact that $j^*$ is in $R$. We therefore conclude that 
\begin{equation}\label{eq:pf2}
R\subset C = J\setminus(N^0\cup B^0).
\end{equation}
\end{proof}

We demonstrate the relations of Lemma~\ref{lem:RinC} using a Venn diagram in Fig.~\ref{fig:venn}.
\begin{figure}[ht]
{\centering \includegraphics{main-diagram}\\}
\caption{The relations between index sets (see Lemma~\ref{lem:RinC}).}
\label{fig:venn}
\end{figure}

The next example shows that the sets $R$ and $C$ can be different.

\begin{ej}
Consider the following linear semidefinite problem:
\begin{equation*}
\min_{x=(x_{1},x_{2},x_{3},x_{4})^{\top}\in \mathbb{R}^{4} } x_{1} \, ; \, 
 \left[
\begin{matrix}
-x_{1} &   -x_{3} & -x_{2} \\
-x_{3} & -x_{2} & -x_{1} \\
-x_{2} & -x_{4} & 1-x_{3}  
\end{matrix}
\right] \in S^{3}_{+},
\end{equation*}
where $ S^{n}_{+}$ stands for set of symmetric  semidefinite positive matrices of dimension $n$.
It is easy to see that the only solution of this problem is $x_{1}=x_{2}=x_{3}=x_{4}=0$.

On the other hand, its dual is as follows
\begin{equation*}
\max_{Y=(Y_{ij}) \in S^{3}_{+} } -Y_{33} \, ; \, Y_{11}=1, \;  -2Y_{13} - Y_{22}=0, \;  -2Y_{12} - Y_{33}=0, \;  Y_{23}=0, 
 \if{
 \left[
\begin{matrix}
Y_{11} &   -x_{3} & -x_{2} \\
-x_{3} & -x_{2} & -x_{1} \\
-x_{2} & -x_{4} & 1-x_{3}  
\end{matrix}
\right] \in S^{3}_{+}.
}\fi
\end{equation*}
which unique solution is given by
$$
Y=\left[
\begin{matrix}
1 &0 &0 \\
0 &0 &0 \\
0 &0 & 0
\end{matrix}
\right].
$$
Consequently, it is clear that strict complementarity does not hold for this unique block (so, $R=\emptyset$). However, this clearly belongs to $C$.
\end{ej}


We next show that in the case of second-order cone programming the complementarity partition has special properties. Recall that a Lorentz cone $L_n$ is a closed convex cone in $\mathbb{R}^{n+1}$ (for some $n\geq 1$) defined as follows,
$$
L_n = \{x=(x_0,\bar x)\in \mathbb{R}\times \mathbb{R}^n\,|\, x_0\geq \|\bar x\|\}.
$$
For consistency, we also let $L_0:= \mathbb{R}_+ = \{x\in \mathbb{R}\,|\, x\geq 0\}$. Second-order conic programming problems are of type \eqref{pb:cop} and \eqref{pb:dcop}, where each cone $K_j$, for $j\in J$, is a Lorentz cone. Notice that linear programming case can be cast a special case of second-order conic programming when $K_j=L_0$ for all $j\in J$.
\begin{lema}\label{lem:partsoc} If for every $j\in J$ the cone $K_j$ is a Lorentz cone, then 
\begin{equation}\label{eq:RisC}
 R = C=J\setminus(B^0\cup N^0).
\end{equation} 
\end{lema}
\begin{proof}
Let $j\in C$. Then there exists a solution  $(x(j),y(j)) \in S\eqref{pb:copos}$ with both 
$y_j(j)$ and $s = A^{j} x(j) - b^{j}$ nonzero. 
Since $y_j(j)\perp s$, we have $y_j(j)\in (K^+_j)\cap s^\perp = -N_{K_j}(s)$. Observe that for a second-order cone the 
normal cone  $N_{K_j}(s)$ is one-dimensional provided $s\neq 0$, hence, $\mathop{\rm ri} N_{K_j}(s) = N_{K_j}(s)\setminus \{0\}\ni y_j(j)$, and
therefore $j\in R$. We have then shown that $C\subset R$. The reverse inclusion follows from Lemma~\ref{lem:RinC}
\end{proof}

We next show a simple example of mixed polyhedral and SOCP cones in which it can happen that $R\neq C$. 
\begin{ej} We consider a feasibility problem, so in this case $b=0$ and $c=0$. We let $K = L_3\times \mathbb{R}^1_+\times \mathbb{R}_+^3$, and 
$$
A^\top  = \left[
\begin{array}{cccccccc}
0 &   1 & 0 & 0& 0& 1 &  0 & 0 \\
0 & 0 & 1 & 0 & -1 &  1 &  1 & 1 \\
1 & 0 & 0 & 1 &   0 &  0 &  0 & 1 
\end{array}
\right].
$$
Solving the problem analytically, we obtain all possible solutions as the parametric family
$$
x = (0,0,\alpha)^\top , \;  Ax = (\alpha, 0 , 0, \alpha, 0, 0, 0, \alpha)^\top ,\; y = (\beta, 0, 0, -\beta,\gamma, 0, \gamma, 0)^\top , 
$$
where $\alpha, \beta,\gamma\geq 0.$
We deduce that $1,3 \in C$, $2\in N$. Now observe that 
$$
N_{K_3}(A_3x) = N_{\mathbb{R}^3_+}(0,0,\alpha) = -\mathbb{R}^2_+\times\{0\},
$$ 
and hence
$$
\mathop{\rm ri} N_{K_3}(A_3x) = -\mathop{\rm int} \mathbb{R}_+^2 \times \{0\}.
$$
The only possible solution is $y_3 = (0,\gamma,0)$. Clearly, $-y_3\notin \mathop{\rm ri} N_{K_3}(A_3x)$, hence, $3\notin R$.


Observe that in this problem we did not consider the `maximal' possible decomposition, i.e. the equivalent formulation when 
$$
K = L_3\times \mathbb{R}_+^1\times \mathbb{R}_+^1\times\mathbb{R}_+^1\times \mathbb{R}_+^1.
$$
In this case $1\in C$, $2,4\in N$, $3\in O$, $5\in B$, and $R = \{1\}$, since the first cone is a SOC.
\end{ej}


\if{

{\tt MAKE NOTATION CONSISTENT FOR THE SOCs}

{\tt Ve It is interesting to find the conditions under which $C=R$


ONE ANSWER IS WHEN WE CAN ENSURE THAT $S\eqref{pb:copos}=S\eqref{pb:cop}\times S\eqref{pb:dcop}$}.

}\fi

\section{Homogeneous feasibility problems}\label{sec:hom}

Homogeneous feasibility problems are of special interest in duality theory. We obtain such problems as a special case of \eqref{pb:cop}--\eqref{pb:dcop} when $b=0$, $c=0$. In this case the primal problem consists of finding an $x$ such that  
\begin{equation}
\label{pb:fcop}\tag{FP}
 A^j x  \in K_j \quad \forall j\in J,
\end{equation}
and the dual problem consists of finding $y$ satisfying
\begin{equation}
\label{pb:dfcop}\tag{FD}
\sum_{j=1}^r (A^j)^\top y^j = 0, \qquad 
y^j \in K_j^+ \quad \forall  j\in J.
\end{equation}

Observe that in the case of the homogeneous feasibility problems we always have strong duality. The relevant complementarity conditions can be obtained from \eqref{pb:copos},
\begin{align}
\label{pb:fcopos}
A^j x & \in K_j, \notag \\
 y^j & \in K_j^+,\notag \\
y^j \cdot A^j x & =0 \quad  \forall  j\in  J,\tag{FC}\\ 
A^\top y & = 0.\notag
\end{align}

Denote by ${\rm Lin\,} C$ the lineality space of a convex set $C$. In \cite[Theorem 1]{PR2012} a dual characterization of the homogeneous six-partition was obtained.
\begin{teo}\label{thm:BNDualChar} The sets $B$, $N$, $B^0$ and $N^0$ can be described as follows.
\begin{align*}
& B = \{j\in J \,|\,  A_j^\top ( K_j^+\setminus \{0\}) \cap {\rm Lin\,} (\overline{A^\top  K^+})= \emptyset\},\\
& N = \{j\in J \,|\, \mathop{\rm ri} A_j^\top  K_j^+ \cap {\rm Lin\,} (A^\top  K^+)\neq \emptyset\},\\
& B^0 = \{j\in J \,|\,  A_j^\top ( K_j^+\setminus \{0\}) \cap {\rm Lin\,} (A^\top  K^+)= \emptyset\},\\
& N^0 = \{j\in J \,|\, \mathop{\rm ri} A_j^\top  K_j^+ \cap {\rm Lin\,} (\overline{A^\top  K^+})\neq \emptyset\}.
\end{align*}
\end{teo}

It appears that in the case of feasibility problem the set $R^0$ has a similar dual characterization.
\begin{lema}\label{thm:RDualChar} In the case of feasibility problem 
$$
R^ 0 \subset \tilde R  := \{j\in J \,|\,   A_j^\top  K_j^+\cap {\rm Lin\,} (\overline{A^\top  K^+}) =  A_j^\top  K_j^+\cap {\rm Lin\,} (\overline{A^\top  K^+})\}.
$$
\end{lema}
\begin{proof} Fix an index $j\in J$ and consider the linear subspaces 
$$
 L = \{y\,|\, A_j^\top  y \in {\rm Lin\,} (A^\top  K^+)\}, \qquad \bar L = \{y\,|\, A_j^\top  y \in {\rm Lin\,} (\overline{A^\top  K^+})\},
$$
and let 
$$
F = L\cap K^+_j,\quad  \bar F = \bar L\cap K^+_j.
$$

Pick an arbitrary solution $x$ and any $v\in \bar F$. Since $v\in \bar F$, we have 
$A_j^\top  v\in {\rm Lin\,}(\overline{A^\top  K^+})$, hence, $-A_j^\top  v\in {\rm Lin\,}(\overline{A^\top  K^+})\subset \overline{A^\top  K^+}$. 
Then there exist sequences $\{v^+_k\}$, $\{v_k^-\}$ such that $v_k^-,v_k^+\in K^+$, $A^\top  v_k^-, A^\top  v_k^+\in A^\top  K^+$, $A^\top  v_k^\pm \to \pm A^\top _j v$. Since $A^\top  v_k^-,A^\top  v_k^+ \in A^\top  K^+$, and since $x$ is a solution (i.e. $Ax\in K$), we have
$$
0 \leq (Ax)^\top \cdot v_k^{-} = x \cdot A^\top  v_k^- = x \cdot v_k^-,  
$$
and analogously $0\leq x \cdot v_k^+$ for all $n$. Hence, passing to the limit, we have $A_j x\cdot v = 0$. Therefore, 
$\bar F \subset (A_j x)^\perp$. By definition, $\bar F \subset K^+_j$, hence,
$$
\bar F \subset K^+_j \cap (A_jx)^\perp.
$$

Now assume that $j\in R^0\setminus \tilde R$. Since $j\in R^0$, there exists a pair of feasible solutions $(x,y)$ such that 
\begin{equation}\label{eq:yinriN01}
y_j \in -\mathop{\rm ri} N_{K_j}(A_j x) = K^+_j \cap (A_jx)^\perp.
\end{equation}
Let $\bar y \in \mathbb{R}^n$ be such that $\bar y_i = 0 $ for all $i\neq j$, and $\bar y_j= y_j$. Observe that $\bar y\in K^+$, hence, $A^\top _j y_j = A^\top  \bar y \in A^\top K^+$, and since $A^\top  y = 0$,  we have $-A^\top_j y_j \in A^\top K$, hence, $A^\top _j y_j \in {\rm Lin\,}(AK)$, and therefore $y_j\in F$.  

Since $y_j \in F\subsetneq \bar F \subset  K^+_j \cap (A_jx)^\perp$, $F = \bar F \cap L$, and all three sets $F$, $\bar F$ and $K^+_j \cap (A_jx)^\perp$ are cones, their affine hulls are linear subspaces, moreover, we have the following representations
$$
{\rm Aff\,} F = L_1, \quad {\rm Aff\,} \bar F = L_2, \quad {\rm Aff\,} (K^+_j \cap (A_jx)^\perp) = L_3,
$$
where $L_1, L_2, L_3$ are linear subspaces, $L_1 \subsetneq L_2\subset  L_3$. Observe that $L_1 \subsetneq L_2$ follows from the fact that $ F = \bar F\cap L$, where $L$ is a linear subspace and $F\neq \bar F$. Also note that since $F = L\cap \bar F$, and $\bar F = \bar L \cap (K^+\cap (A_j x)^\perp$, we have $F = \bar F \cap L_1$, $\bar F = L_2\cap (K^+\cap (A_j^\top  x)^\perp)$.


From \eqref{eq:yinriN01} we deduce that there exists $\varepsilon>0$ such that $(y_j+ B_\varepsilon)\cap L_3 \subset K^+_j \cap (A_jx)^\perp$. Observe that since ${\rm Aff\,} F = L_1\oplus(L_2\cap L_1^perp)$, there exists a unit vector $u$ in $L_1^\perp\cap L_2$ such that  $y_j +\varepsilon u\in \bar F\subset L_2\subset L_3$, therefore $y_j-\varepsilon u \in L_3$, and since $\pm \varepsilon u \in B_\varepsilon$, we have $y_j\pm \varepsilon u \in L_2\cap( K^+_j \cap (A_jx)^\perp)$, hence, $y_j\pm \varepsilon u\in \bar F$, as $\bar F = \bar L_2\cap (K^+ \cap (A_jx)^\perp )$. Therefore, $A^\top _j(y_j\pm \varepsilon u) \in A^\top K^+$. Since $A_j^\top y_j \in {\rm Lin\,}(AK)$, we have $-A^\top _j y_j \in A^\top K^+$,  and therefore  we deduce that $-A_j^\top y_j\pm \varepsilon u \in AK$, and hence $A_j^\top (y_j\pm u)\in {\rm Lin\,}(AK)$, which means that $y_j\pm \varepsilon u \notin F$, which contradicts the construction of $u$. Therefore, our assumption that there exist $j\in R^0\setminus \tilde R$ is wrong, and hence $R^0\subset \tilde R$.

\end{proof}





\section{Equivalent optimization problems}\label{sec-dual-socp-b}


We now introduce another problem related to \eqref{pb:cop}.
Let ${\cal K}= {\cal K}_1 \times \cdots \times {\cal K}_r$ be another finite family of
closed convex cones in $\mathbb{R}^{r_j}$, $j\in J$, and $M^j$ be
$r_j\times q_j$ matrices such that
\begin{equation}
\label{copos1}
s^j\in K_j \;\; \text{ iff } \;\; M^j s^j \in {\cal K}_j, \; j=1,\ldots,J.
\end{equation}
The latter is inspired by the relation between Lorentz cones and the cone of the semidefinite positive matrices. Indeed, denote these cones by $L_m$ and $\mathcal{S}^{m+1}_+$, respectively, when their dimensions are $m+1$. For $s=(s_0,\bar{s})\in \mathbb{R}\times\mathbb{R}^m$ it is easy to check that 
\begin{equation}
\label{eq:equivArw} s\in L_m  \;\;\text{ iff } \;\; 
\mathop{\rm Arw}(s) := 
\begin{pmatrix} s_0 & \bar{s}^\top
                   \\ \bar{s} &  I_m
\end{pmatrix} \in \mathcal{S}^{m+1}_+.
\end{equation}
Linear function $\mathop{\rm Arw}(\cdot)$ is the so-called \emph{arrow function} and it has several interesting properties that will be exploited in the next sections.

Let $M = (M^1;\cdots;M^r)$ be the matrix whose rows are those of
$M^j$. Then, \eqref{pb:cop} is equivalent to the linear conic problem
\if {
\begin{equation}
\label{pb:mcop
\mathop{\rm Min}_{x\in \mathbb{R}^n}
 c\cdot x\, ;\, M(A x - b )\in {\cal K},
\end{equation}
or equivalently
}\fi
\begin{equation}
\label{pb:mcopa}\tag{MP}
\mathop{\rm Min}_{x\in \mathbb{R}^n}
 c\cdot x\, ;\, M^j(A^j x - b^j )\in {\cal K}_j, \; j\in J,
\end{equation}
whose dual is
\begin{equation}
\label{pb:dmcop}\tag{MD}
\mathop{\rm Max}_{z\in {\cal K}^+}
\sum_{j=1}^r b^j\cdot (M^j)^\top z^j; \; \;
\sum_{j=1}^r (A^j)^\top (M^j)^\top z^j = c; \; \; z^j\in {\cal K}_j^+,
\; j\in J.
\end{equation}
If the primal and dual values are equal, an optimal pair
$(x,y)$ of the primal and dual problems is characterized by the
optimality system
\begin{equation}
\label{pb:mcopos}\tag{MC}
\left\{ \ba{lll}
 M^j(A^j x - b^j) \in {\cal K}_j,  \; \;
z^j\in {\cal K}_j^+, \;\; z^j \cdot M^j (A^j x - b^j)=0,
\; j\in J;
\\
\sum_{j=1}^r (A^j)^\top (M^j)^\top z^j = c.
\ea \right.
\end{equation}

We first recall some known results from \cite{BonRam} in the following lemma.
\begin{lema}
\label{mcopos.l1} The following relations hold: 

{\rm (i)} $
S\eqref{pb:cop} = S(MP)$, $M^\top {\cal K}^+ \subset K^+$, and $M^\top
S(MD) \subset S\eqref{pb:dcop}$. 

{\rm (ii)} If $M^\top{\cal K}^+$ is
closed, then $M^\top {\cal K}^+ = K^+$ and $M^\top S(MD) =
S\eqref{pb:dcop}$. 

{\rm (iii)} Closedness of $M^\top{\cal K}^+$ holds if
$M^\top$ is coercive on ${\cal K}^+$, i.e., if there exists $\gamma
>0$ such that $\| M^\top z \| \geq \gamma \|z\|$ for all $z\in
{\cal K}^+$. In that case, $S(MD)$ is bounded iff $S\eqref{pb:dcop}$
is bounded.

 {\rm (iv)} Assume in addition  that $M$ is one to one. Then,
$M^\top \mathop{\rm int} {\cal K}^+ = \mathop{\rm int} K^+$
and \\
$M^\top \mathop{\rm int} S(MD) = \mathop{\rm int} S\eqref{pb:dcop}$.
Moreover,   for all $s\in K$,
$M^\top \mathop{\rm ri} ({\cal K}^+ \cap (Ms)^\perp) \subset \mathop{\rm ri} (K^+\cap s^\perp)$.
\end{lema}

\begin{proof}
See Lemmas 8 and 9 of \cite{BonRam}.
\end{proof}

Let $(B_{\ref{pb:cop}},N_{\ref{pb:cop}},R_{\ref{pb:cop}},T_{\ref{pb:cop}})$
denote the optimal partition of \eqref{pb:cop},
and adopt a similar convention for $(MP)$. 
The next result strengths  Lemma 10 of \cite{BonRam}.

\begin{lema}
\label{mcopos.l5}
Assume that $M^\top {\cal K}^+$ is closed, that
$M$ is one to one, and that
\begin{equation}
\label{eq-lema.l5-1}
\text{ For all } s^j \in K_j, \;
M^j s^j \in  \mathop{\rm bd} {\cal K}_j \text{ iff } s^j \in  \mathop{\rm bd} K_j.
\end{equation}
Then, the
four-partition of problems \eqref{pb:cop} and $(MP)$ coincide, that is
\begin{equation}
\label{eq:partition-coincide}
\left\{\begin{array}{lll}
B_{\ref{pb:cop}} = B_{MP}, &
N_{\ref{pb:cop}} = N_{MP},
\\
R_{\ref{pb:cop}} =R_{MP}, &
T_{\ref{pb:cop}} = T_{MP}.
\end{array}\right.
\end{equation}
In particular, the strict complementarity hypothesis holds for
\eqref{pb:cop} iff it holds for $(MP)$.
\end{lema}
\begin{proof}
Due to Lemma 10 of \cite{BonRam} it only remains to prove that $R_{\ref{pb:cop}} \subset R_{MP}$. Let  $j\in R_{\ref{pb:cop}}$. This implies the existence of $(x,y)\in S\eqref{pb:copos}$ such that  $s^j:=A^jx^j-b^j\in  \mathop{\rm bd} K_j\setminus\{0\}$ and $y^j(j)\in  \mathop{\rm bd} K_j^+\setminus\{0\}$.
It follows from Lemma \ref{mcopos.l1}, Parts (i) and (ii), that $x \in S(MP)$ and that there exist $z \in S(MD)$ such that $y=M^\top z $, respectively. In particular, $y^j=(M^j)^\top z^j $ and
\begin{equation}\label{eq:aux}
0=s^j \cdot y^j =s^j \cdot (M^j)^\top z^j =M^j s^j\cdot z^j.
\end{equation}
Moreover, from \eqref{eq-lema.l5-1} and the fact that $M$ is one to one, we deduce that  $M^js^j$ is a nonzero element of $ \mathop{\rm bd} \mathcal{K}_j$. This in particular implies that $z^j \not\in  \mathop{\rm int} (\mathcal{K}_j^+)$ (because otherwise  \eqref{eq:aux} yields to $M^js^j=0$). Finally, since $(M^j)^\top z^j =y^j \neq 0$ it directly follows that $z^j \neq 0$. Summarizing, we have proved that $(x,z) \in S(MC)$, and $M^js^j$ and $z^j$ are nonzero elements of $ \mathop{\rm bd} \mathcal{K}_j$ and $ \mathop{\rm bd} \mathcal{K}_j^+$, respectively. This means that $j\in R_{MP}$, which concludes our proof.
\end{proof}



Let us study now the relation with the six-partition.

\begin{lema}\label{lem:16} Assume that $M^\top {\cal K}^+$ is closed. Then 
$$
B^0_{\ref{pb:cop}} \supset B^0_{MP}.
$$
If, in addition, for all $z\in \mathcal{K}^{+}$ such that $M^\top z =0 $ yields $z=0$, then 
$$
B^0_{\ref{pb:cop}} = B^0_{MP}.
$$
\end{lema}
\begin{proof}
The relation $B^0_{\ref{pb:cop}} \supset B^0_{MP}$ follows directly from Lemma~\ref{mcopos.l1}(ii). If for every 
$(x,z)\in S(MC)$ we have $z_j=0$, then $y_j = M^\top_j(z_j )=0$.

Now assume that $j\in B^0_{\eqref{pb:cop}}$. Then every solution $(x,z)\in S(MC)$ satisfies 
$M_j^\top  z_j =0$. By assumption  this yields $z_j =0$.
\end{proof}

\begin{lema}\label{lem:18} We have 
$$
N^0_{\ref{pb:cop}} \subset N^0_{MP}.
$$
If, in addition, $M$ is one-to-one, then
$$
N^0_{\ref{pb:cop}} = N^0_{MP}.
$$
\end{lema}
\begin{proof} From Lemma~\ref{mcopos.l1}~(i) we have $MS(\ref{pb:cop}) = S(MP)$, hence, the first relation $N^0_{\ref{pb:cop}} \subset N^0_{MP}$ is obvious. With the assumption that $M$ is one-to-one, $M_j(A_j x-b_j)=0$ yields  $A_j x-b_j=0$, hence, the equality $N^0_{\ref{pb:cop}} = N^0_{MP}$.
\end{proof}


\begin{lema}\label{lem:17} Under the assumptions of Lemma~\ref{mcopos.l5}, 
\begin{equation}
\label{eq:lem17}
\left\{\begin{array}{lll}
B_{\ref{pb:cop}} = B_{MP}, &
N_{\ref{pb:cop}} = N_{MP},
\\
N^0_{\ref{pb:cop}} = N^0_{MP}, &
B^0_{\ref{pb:cop}} \supset B^0_{MP}.
\end{array}\right.
\end{equation}
If, in addition,  for all $z\in \mathcal{K}^{+}$ such that $M^\top z =0 $ yields $z=0$, then $B^0_{\ref{pb:cop}} = B^0_{MP}$.
\end{lema}
\begin{proof}
Follows directly from Lemmas~\ref{lem:16} and \ref{lem:18}.
\end{proof}

The latter in particular implies that, if all the assumptions of Lemma~\ref{lem:17}  hold true, then the six-partition of problems  \eqref{pb:cop} and  $(MP)$ coincide.

We finally provide alternative hypotheses to those in Lemma \ref{mcopos.l5} to prove that  the four-partition of problems  \eqref{pb:cop} and  $(MP)$ coincide.

 \begin{cor}\label{lem:19} Suppose that the assumptions of Lemma~\ref{mcopos.l5} are fulfilled. Suppose also that for all $z\in \mathcal{K}^{+}$ such that $M^\top z =0 $ yields $z=0$,  $R_{\ref{pb:cop}}=C_{\ref{pb:cop}}$ and $R_{MP}=C_{MP}$. Then 
$$
R_{\ref{pb:cop}} = R_{MP}, \quad T_{\ref{pb:cop}} = T_{MP}
$$ 
\end{cor}
\begin{proof}
Follows directly from Lemma~\ref{lem:17} and definition of the index set $C$.
\end{proof}




We next show that the assumptions of  Lemma~\ref{lem:17} are crucial for the equality between partitions.

\begin{ej}

Consider a pair of feasibility problems
$$
Ax \in K, \quad (P) \qquad A^\top y = 0, y\in K^+,\quad (D)
$$
where
$$
K = K^+ = L_2\times \mathbb{R}_+^1,
$$
and $L_2$ is the three-dimensional Lorentz cone.
Let 
$$
A^\top  = \left[
\begin{array}{cccc}
0 & 1 & 0 & 1\\
1 & 0 & 1 & 0
\end{array}
\right].
$$
We can solve this feasibility problem directly and obtain the parametric family of solutions
$$
x^* = (0,\alpha)^\top , \alpha \geq 0, \text{ with } Ax^* = (\alpha, 0,\alpha, 0)^\top ; \qquad 
y^* = (\beta, 0, -\beta, 0)^\top , \beta \geq 0.  
$$
It is not difficult to see that for the first index the solutions lie on the boundary of the cones, hence, $1\in C=R$.
For the second index, both primal and dual components are zero, hence, $2\in O$.


Now we transform our problem into a higher-dimensional one. We let 
$$
M_1 = I_3  = \left[\begin{array}{ccc}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 &0 & 1\end{array}\right], \quad M_2 = \left[\begin{array}{c} 1 \\ 1\end{array}\right].
$$
For the transformed problem, we let $\mathcal{K}_1 = K_1 = L_2$, $\mathcal{K}_2 = L_1$.
Observe that for every $y\in \mathbb{R}$ we have 
$$
M_2 y = (y,y)^\top ,
$$
and hence $M_2 y \in \mathcal{K}_2= L_1$ iff $y\in K_2=\mathbb{R}_+^1$.
Further,
$$
\mathcal{A}_1 = M_1 A_1 = A_1 = \left[
\begin{array}{ccc}
0& 1 \\
1 & 0 \\
0 & 1
\end{array}
\right], \quad \mathcal{A}_2  = M_2 A_2 = \left[
\begin{array}{ccc}
1 \\
1 
\end{array}
\right] [1\; 0] = \left[
\begin{array}{cc}
1& 0 \\
1 & 0 
\end{array}
\right].
$$
Let $\mathcal{A} = [\mathcal{A}_1;\mathcal{A}_2]$, then we can write the transformed feasibility problem as
$$
\mathcal{A} u \in \mathcal{K}, \quad (P') \qquad \mathcal{A}^\top v = 0, v\in \mathcal{K}^+.\quad (D')
$$
Solving the problem directly, we obtain the family of optimal solutions
$$
u = (\lambda, 0), \lambda \geq 0 \text{ with } \mathcal{A} u  = (\lambda, 0 , \lambda, 0, 0); \qquad v= (\mu,0,-\mu, \gamma, -\gamma), \mu, \gamma \geq 0.
$$
Therefore, we conclude that $1_M\in C$, $2_M \in N^0 \setminus (B^0 \cup N) = N'$, and hence the partition has changed. 

The situation above ocurrs is because $M_2$ does not satisfy that $M_2^\top z =0 $ yields $z=0$ for all $z\in \mathcal{K}^{+}=L_1$. Indeed, it is enough to take $z=(1,-1)^\top$ to check this hypothesis fails.
\end{ej}



\subsection{Application to SOCP-SDP conversion}\label{sec-dual-socp-c}

\medskip


The aim of this section is to apply apply the results of the above section to
the (LSOCP) and (LSDP).
For this, let us consider the following sets
$K_j:=L_{m_j+1}$, ${\cal K}_j := \mathcal{S}^{m_j+1}_+$,
and $M^j s^j = \mathop{\rm Arw}^j s^j$, where the arrow function $\mathop{\rm Arw}^j: \mathbb{R}^{m_j+1}\to \mathcal{S}^{m_j+1}$
was defined in \eqref{eq:equivArw}, and $ \mathcal{S}^{m+1}$ denotes the set of square symmetric matrices of dimension  ${m+1}$.

In what follows consider a generic nonnegative integer value $m$ and omit index $j$ from the arrow function.
Note that we can write
\begin{equation}
\label{propm}
\mathop{\rm Arw}(s) = (s_0 - \| \bar{s} \|) I_{m+1} +
\begin{pmatrix} \| \bar{s} \| & \bar{s}^\top
                   \\ \bar{s} & \| \bar{s} \| I_m
\end{pmatrix}.
\end{equation}
This shows that for $s\in L_{m+1}\setminus \{0\}$,
$\mathop{\rm Arw}(s)$ is of rank $m$ iff
$s \in  \mathop{\rm bd} L_{m+1}$, and of rank $m+1$ otherwise.
In particular,
$\mathop{\rm Arw}  \mathop{\rm bd} L_{m+1} \subset   \mathop{\rm bd} \mathcal{S}^{m+1}_+$, and
$\mathop{\rm Arw} \mathop{\rm int} L_{m+1} \subset  \mathop{\rm int} \mathcal{S}^{m+1}_+$.
Therefore
\eqref{eq-lema.l5-1}
holds. Also $\mathop{\rm Arw}$ is clearly one-to-one.


Let us decompose any matrix $Y\in \mathcal{S}^{m+1}$ as follows
\begin{equation}
\label{eq:decomposition_Y}
Y=\left(\begin{matrix} Y_{00} & \bar Y_{0}^\top\\ \bar Y_{0} & \bar Y \end{matrix}\right) ,
\end{equation}
where $ Y_{00}\in \mathbb{R}$, $ \bar Y_{0} \in \mathbb{R}^m$ and $ \bar Y \in \mathcal{S}^m$. We
note that for any $s\in \mathbb{R}^{m+1}$ we get
\begin{equation}\label{eq:operation_Arw}
\mathop{\rm Arw}(s)\cdot Y= s_{0} \mathop{\rm Tr}(Y) +2 \bar{s}\cdot\bar Y_{0}.
\end{equation}
It follows that
$\mathop{\rm Arw}^\top:\mathcal{S}^{m+1}\rightarrow \mathbb{R}^{m+1}$
is nothing but
\begin{equation}
\label{eq:defarwt}
\mbox{$\mathop{\rm Arw}^\top$}
Y:= \left( \begin{matrix}   \mathop{\rm Tr}( Y) \\ 2 \bar Y_{0}  \end{matrix}\right).
\end{equation}
Consequently
\begin{equation}
\label{eq:defarwt2}
M^\top (Y^1,\ldots,Y^r) = \mathop{\rm vec}
\left(
\left( \begin{matrix}   \mathop{\rm Tr}( Y^1) \\ 2 \bar Y_{0}^1  \end{matrix}\right),
\ldots,
\left( \begin{matrix}   \mathop{\rm Tr}( Y^r) \\ 2 \bar Y_{0}^r  \end{matrix}\right)
\right).
\end{equation}
Then, $M^{\top}{\cal K}$ is clearly closed. Moreover, since $\mathop{\rm Arw}^\top Y=0$ implies $ \mathop{\rm Tr}(Y) =0$, when $Y\in \mathcal{S}^{m+1}_{+}$ the latter yields $Y=0$. Hence, all the assumptions of Lemma \ref{mcopos.l5},  and of Lemma \ref{lem:17}, are fulfilled. We thus obtain as a consequence of those statements the following result.

\begin{prop}
Problems $(LSOCP)$ and $(LSDP)$ have the same four and six-partition.
\end{prop}





\if{

\begin{prop}
\label{applic}
{\rm (i)}
We have that $y$ is solution of $(LSOCP^*)$ iff there exists
$z$ solution of $(LSDP^*)$ such that $y=M^\top z$.
{\rm (ii)}
One of these dual problems has a bounded set of solutions iff the
other one has the same property.
{\rm (iii)}
One of these dual problems has an interior feasible point
iff the other one has the same property.
{\rm (iv)}
Problems $(LSOCP)$ and $(LSDP)$ have the same optimal partition.
\end{prop}

\begin{proof}
Since
$\mathop{\rm Arw}^\top$ is coercive on $\mathcal{S}^{m+1}_+$,
$M^\top$ is also coercive.
By lemma \ref{mcopos.l1}, we have that
$S(LSOCP^*) = M^\top S(LSDP^*)$ and
$S(LSDP^*)$ is bounded iff $S(LSOCP^*)$ is bounded.
This proves points i) and (ii).
Point (iii) is consequence of lemma  \ref{mcopos.l2}(ii).
We now prove (iv).
By lemma \ref{mcopos.l5},
$B_{LSOCP} = B_{LSDP}$, $N_{LSOCP} = N_{LSDP}$, and
$R_{LSOCP} \supset R_{LSDP}$;
it remains to prove that $R_{LSOCP} \subset R_{LSDP}$
since $(B,N,R,T)$ is a partition.
Let $j\in R_{LSOCP}$. Then there is a pair
$(x,y)$ solution of \eqref{KKT:linear_socp}
such that $s^j\neq 0\neq y^j$, and both $s^j$ and $y^j$
belong to the boundary of $Q_{m^j+1}$.
As observed after \eqref{propm},
this implies that
$\mathop{\rm Arw} s^j$ is of rank $m^j$, and hence, the corresponding set
of normals is a half line (of rank one semidefinite positive matrices,
orthogonal to $\mathop{\rm Arw} s^j$). Since the corresponding multiplier
$Y$ for problem $(LSDP)$ is such that $0 \neq y^j = \mathop{\rm Arw}^\top Y^j$,
we have that $Y^j \neq 0$, proving that
 $-Y^j$ belongs to the relative interior of the normal
cone (to the set of semidefinite positive matrices) at $\mathop{\rm Arw} s^j$.
\end{proof}

The above analysis shows that strong duality holds for problem
\eqref{pb:socp} iff it holds for problem \eqref{pb:lsdp}.
The next proposition states an interesting relation between the
solutions of \eqref{pb:socp_dual} and \eqref{pb:sdp_dual}.


\begin{prop}
\label{prop:SZhao3}
Let the strong duality property hold for problem \eqref{pb:socp}.
Let
$I$ be the set of indexes in  $J$ such that there exists
$x^* \in S\eqref{pb:socp}$ satisfying
$A^jx^*\neq b^j$.
Then every $Y \in S\eqref{pb:sdp_dual}$
is such that, for some $y \in S\eqref{pb:socp_dual}$,
the following relation holds:
\begin{equation}\label{eq:sol_Y^*}
Y^j=  \, 0, \, \textrm{ if } y^j = 0; \qquad
Y^j= \frac{1}{2} \left( \begin{matrix}
\|\bar{y}^j\| &(\bar{y}^j)^\top \\
\bar{y}^j & \bar{y}^j (\bar{y}^j)^\top /  \|\bar{y}^j\|
\end{matrix}\right), \,\textrm{ otherwise.}
 \end{equation}
\end{prop}

\begin{proof}
Let $j\in I$, $x^*$ be the associated solution of
$\eqref{pb:socp}$, and let $Y \in S\eqref{pb:sdp_dual}$.
We claim  that
\begin{equation}\label{eq:null_dec_Y^*}
Y^j_{00}\bar Y^j -(\bar Y_{0}^j)({\bar Y_{0}}^j)^\top= 0,
\end{equation}
where $Y^j_{00}$, $\bar Y^j$ and $\bar Y^j_0$ are given by
\eqref{eq:decomposition_Y}. Since
$Y^j\in \mathcal{S}^{m_j+1}_+$, by Schur complement the matrix
$Y^j_{00}\bar Y^j -(\bar Y^j_0)(\bar Y^j_0)^\top$ is positive semidefinite,
and hence, it is enough to show that
\begin{equation}\label{eq:trace_dec_Y^*}
 \mathop{\rm Tr}\left( Y^j_{00}\bar Y^j -(\bar Y^j_0 )(\bar Y^j_0)^\top \right) \leq 0.
\end{equation}
By strong duality, any primal-dual solution $(x^*,y^*)$
of \eqref{pb:socp} is solution of
$\eqref{KKT:linear_socp}$.
Since $A^jx^*\neq b^j$,  the complementarity condition
implies that any
$y \in S\eqref{pb:socp_dual}$
satisfies $y^j_0=\|\bar{y}^j\|$.
Taking $y^j = \mathop{\rm Arw}^\top Y^j$,
we deduce

 \mathop{\rm Tr}(Y^j)= y^j_0=\|\bar{y}^j\|= 2\|\bar Y^j_0\|, $
 which implies
\begin{equation}
\label{eq:aux_trace_Y^*}
\begin{array}{ll}
 \mathop{\rm Tr}\left( Y^j_{00}\bar Y^j -(\bar Y^j_0)(\bar Y^j_0)^\top\right)
& =
Y^j_{00} \mathop{\rm Tr}\left( Y^j\right) -(Y^j_{00})^2 - \|\bar Y^j_0\|^2
\\
& =
-\left(Y^j_{00}- \|\bar Y^j_0\|\right)^2\leq 0,
\end{array}
\end{equation}
proving \eqref{eq:trace_dec_Y^*} and therefore also
\eqref{eq:null_dec_Y^*}.
Combining \eqref{eq:defarwt} and \eqref{eq:aux_trace_Y^*},
obtain
\begin{equation}\label{eq:aux1_trace_Y^*}
 Y^j_{00}=\|\bar Y^j_0\|= \frac{1}{2} \|\bar y^j\|
 \end{equation}\noindent Now, we distinguish two cases:
a) If $Y^j_{00}=0$, we obtain from \eqref{eq:aux1_trace_Y^*} that
 $\bar Y^j_0=\bar{y}^j=0$ and then $ \mathop{\rm Tr}(Y^j)=y_0^j=0$.
Hence, since $Y^j$ is positive semidefinite
this implies $Y^j=0$.
b) Else if $Y^j_{00}\neq 0$, we get directly from
\eqref{eq:null_dec_Y^*} and \eqref{eq:aux1_trace_Y^*} that
$$
\bar Y^j=(Y^j_{00})^{-1}(\bar Y^j_0)(\bar Y^j_0)^\top
=\frac{2}{\|\bar{y}^j\|}(\bar
y^j/2)(\bar{y}^j/2)^\top=  \frac{1}{2} (\bar{y}^j)(\bar{y}^j)^\top/\|\bar{y}^j\|,
$$
which, combined with \eqref{eq:aux1_trace_Y^*},
allows to conclude the proof.
\end{proof}

}\fi




\section{Acknowledgements}

The research was partially supported by Australian Research Council grant DE150100240.
The second author was supported by FONDECYT regular project 1160567 and Basal Program CMM-AFB 170001, both from CONICYT (Chile).

\bibliographystyle{plain}
