An Infeasible Interior-Point Algorithm for Stochastic Second-Order Cone Optimization

Abstract

Alzalg (J Optim Theory Appl 163(1):148–164, 2014) derived a homogeneous self-dual algorithm for stochastic second-order cone programs with finite event space. In this paper, we derive an infeasible interior-point algorithm for the same stochastic optimization problem by utilizing the work of Rangarajan (SIAM J Optim 16(4), 1211–1229, 2006) for deterministic symmetric cone programs. We show that the infeasible interior-point algorithm developed in this paper has complexity less than that of the homogeneous self-dual algorithm mentioned above. We implement the proposed algorithm to show that they are efficient.

1 Introduction

Two-stage stochastic second-order cone programs [1] have been defined to formulate many applications of second-order cone programs [2] that involve uncertainty in data. General and different classes of optimization problems, such as stochastic linear programs, stochastic quadratic programs, and quadratically constrained stochastic quadratic programs, can be recast as stochastic second-order cone programs [1, 2]. In [1], the reader can find various application models of stochastic second-order cone programs, namely the stochastic Euclidean facility location problem, the portfolio optimization problem with loss risk constraints, the optimal covering random ellipsoid problem, and an application in structural optimization.

Alzalg and Ariyawansa [3] (see also Alzalg [4, 5]) proposed polynomial-time decomposition-based interior-point algorithms for stochastic programs over all symmetric cones including second-order cones. While the decomposition-based interior-point algorithms exploit the structure in a problem, there are other classes of algorithms such as infeasible interior-point algorithms and homogeneous self-dual algorithms, which are particularly designed for general problems. However, when applied to problems with structure, in many cases homogeneous and infeasible interior-point algorithms can be designed to exploit the structure by carefully tailoring the operations of the algorithm. In [6], Alzalg has derived a homogeneous self-dual algorithm for stochastic second-order cone programs with finite event space of their random variables. In this paper, the focus is on developing an infeasible interior-point algorithm for stochastic second-order cone programs.

For deterministic nonlinear programming problems, several infeasible interior-point methods have been proposed. See, for examples, the work of Nesterov [7] in nonlinear programming, the work of Rangarajan [8] over symmetric cones, the work of Potra and Sheng [9] over the semidefinite cone, and the work of Xiaoni and Sanyang [10] over the second-order cone. See also the work of Castro [11] and that of Castro and Cuesta [12] which present interior-point methods for large-scale deterministic optimization problems by exploiting block-angular structures. As mentioned earlier, we are concerned to derive an infeasible interior-point algorithm for stochastic second-order cone programs with finite event space of their random variables by utilizing the work of Rangarajan [8]. We will see that the infeasible algorithm developed for these problems has complexity less than that of the homogeneous algorithm developed in [6] for the same problems.

We organize this paper as follows. In Sect. 2, we briefly review some preliminary definitions, symbols, and notations from the theory of the Jordan algebra associated with the second-order cone. Section 3 presents the definition of a stochastic second-order cone programming with finite event space in primal standard form as defined in [1]. In Sect. 4, we exploit the special structure in our stochastic second-order cone programming problem to present a method for computing the search direction. In Sect. 5, we state the infeasible interior-point algorithm for solving the stochastic second-order cone programming problem and estimate its computational complexity with the method presented and analyzed in Sect. 4 and applied on our problem. In Sect. 6, we test the generic infeasible interior-point algorithm for stochastic second-order cone programs with some numerical examples. Section 7 gives some concluding remarks.

2 The Algebra of the Second-Order Cone: Definitions and Notations

The definitions and notations presented in this section are necessary to proceed with our subsequent development. Those who are not familiar with the basics of the theory of algebra of the second-order cone are highly encouraged to read [2, Section 4].

We use “,” for adjoining vectors and matrices in a row and use “;” for adjoining them in a column. For each vector $\varvec{x} \in {\mathbb R}^n$ whose first entry is indexed with 0, we write $\tilde{\varvec{x}}$ for the subvector consisting of entries 1 through $n-1$ (therefore $\varvec{x} = (x_0, \tilde{\varvec{x}}^{\textsf {T}})^{\textsf {T}}\in {\mathbb R}\times {\mathbb R}^{{n}-1}$). We let $\mathcal {E}^{n}$ denote the $n^\text {th}$-dimensional real vector space ${\mathbb R}\times {\mathbb R}^{{n}-1}$ whose elements $\varvec{x}$ are indexed from 0.

In Table 1, we list some symbols and notations of the theory of the Jordan algebra associated with the second-order cone. This table presents these notations and definitions in both single and block-settings. The nth-dimensional second-order cone, which is denoted by $\mathcal {E}^n_+$ and defined in Table 1, is the norm cone for the Euclidean norm.

Table 1 Notations of the theory of the Jordan algebra associated with the second-order cone

We point out that the direct sum (of two square matrices A and B) used in Table 1 is the block diagonal matrix

$$\begin{aligned} A \oplus B := \left[ \begin{array}{cc} A&{}\quad O\\ \hat{O}&{}\quad B\\ \end{array} \right] . \end{aligned}$$

where O and $\hat{O}$ are zero matrices with appropriate dimensions.

Note that the idempotents $\varvec{c}_1(\varvec{x})$ and $\varvec{c}_2(\varvec{x})$ defined in Table 1 satisfy the properties

$$\begin{aligned} \begin{array}{lll} \varvec{c}_1(\varvec{x}) \circ \varvec{c}_2(\varvec{x}) &{}=&{} \varvec{0},\\ \varvec{c}_1(\varvec{x})\circ \varvec{c}_1(\varvec{x}) &{}=&{} \varvec{c}_1(\varvec{x}),\\ \varvec{c}_2(\varvec{x})\circ \varvec{c}_2(\varvec{x})&{}=&{} \varvec{c}_2(\varvec{x}),\\ \varvec{c}_1(\varvec{x}) + \varvec{c}_2(\varvec{x}) &{}=&{} \varvec{e}. \end{array} \end{aligned}$$

Any pair of vectors $\{\varvec{c}_1, \varvec{c}_2\}$ that satisfies the above properties is called a Jordan frame. We say that elements $\varvec{x}$ and $\varvec{y}$operator commute iff they share a Jordan frame, i.e., $\varvec{x} = \lambda _1 \varvec{c}_1 + \lambda _2 \varvec{c}_2$ and $\varvec{y} = \omega _1 \varvec{c}_1 + \omega _2 \varvec{c}_2$ for a Jordan frame $\{\varvec{c}_1, \varvec{c}_2\}$. In block-setting, the vectors $\varvec{x} = (\varvec{x}_1; \varvec{x}_2; \ldots ; \varvec{x}_r)$ and $\varvec{y} = (\varvec{y}_1; \varvec{y}_2; \ldots ; \varvec{y}_r)$ operator commute iff $\varvec{x}_i$ and $\varvec{y}_i$ operator commute for each $i=1, 2, \ldots , r$.

3 Stochastic Second-Order Cone Programs with Finite Event Space

We first write the stochastic second-order cone programming (SSOCP) problem in its general definition as defined in [1, Section 2], and then we consider the special case in which the event space is finite with K realizations.

Let $r \ge 1$ be an integer. For $i=1, 2, \ldots , r$, let $m_0, m_1, n_0, n_{0 i}, \bar{n}, \bar{n}_{i}$ be positive integers such that $n_0=\sum _{i=1}^{r}n_{0i}$ and $\bar{n}=\sum _{i=1}^{r} \bar{n}_{i}$. The two-stage SSOCP with recourse is the problem:

$$\begin{aligned} \begin{array}{lll} \text{ min } &{} \eta (\varvec{x}_0) := \varvec{c}_0^{\textsf {T}}\varvec{x}_0 + {\mathbb E}\ [ Q (\varvec{x}_0, \omega ) ] &{} \\ \text{ s.t. } &{} W_0 \varvec{x}_0 = \varvec{h}_0, &{} \\ &{}\varvec{x}_0 \succeq \varvec{0}, &{} \end{array} \end{aligned}$$

(1)

where ${\mathbb E}[Q(\varvec{x}_0, \omega )] := \int _{\Omega } Q(\varvec{x}_0, \omega ) P(d\omega )$ and $Q(\varvec{x}_0,\omega )$ is the minimum value of the problem

$$\begin{aligned} \begin{array}{lll} \text{ min } &{}\varvec{c}(\omega )^{\textsf {T}}\varvec{x}(\omega ) &{} \\ \text{ s.t. } &{}W(\omega ) \varvec{x}(\omega ) = \varvec{h} (\omega ) - B(\omega ) \varvec{x}_0, &{} \\ &{}\varvec{x}(\omega ) \succeq \varvec{0}, &{} \end{array} \end{aligned}$$

(2)

where $\varvec{x}_0 := (\varvec{x}_{01}; \varvec{x}_{02}; \ldots ; \varvec{x}_{0r}) \in \mathcal {E}^{n_{01}} \times \mathcal {E}^{n_{02}} \times \cdots \times \mathcal {E}^{n_{0r}}$ is the first-stage decision variable, $\varvec{x}(\omega ) := (\varvec{x}_{1}(\omega ); \varvec{x}_{2}(\omega );$$\ldots ; \varvec{x}_{r}(\omega )) \in \mathcal {E}^{\bar{n}_{1}} \times \mathcal {E}^{\bar{n}_{2}} \times \cdots \times \mathcal {E}^{\bar{n}_{r}}$ is the second-stage variable, the matrix $W_0 := (W_{01}, W_{02}, \ldots , W_{0r}) \in {\mathbb R}^{m_0 \times n_0}$ (with $W_{0i} \in {\mathbb R}^{m_0 \times n_{0i}}$) and the vectors $\varvec{h}_0 \in {\mathbb R}^{m_0}$ and $\varvec{c}_0 := (\varvec{c}_{01}; \varvec{c}_{02}; \ldots ; \varvec{c}_{0r}) \in {\mathbb R}^{n_0}$ (with $\varvec{c}_{0i} \in \mathcal {E}^{n_{0i}}$) are deterministic data, and the matrices $W(\omega ) := (W_{1}(\omega ), W_{2}(\omega ), \ldots , W_{r}(\omega )) \in {\mathbb R}^{m_1 \times \bar{n}}$ (with $W_{i}(\omega ) \in {\mathbb R}^{m_1 \times \bar{n}_{i}}$) and $B(\omega ) := (B_{1}(\omega ), B_{2}(\omega ), \ldots , B_{r}(\omega )) \in {\mathbb R}^{m_1 \times \bar{n}}$ (with $B_{i}(\omega ) \in {\mathbb R}^{m_1 \times \bar{n}_{i}}$) and the vectors $\varvec{h} (\omega ) \in {\mathbb R}^{m_1}$ and $\varvec{c} (\omega ) := (\varvec{c}_{1} (\omega ); \varvec{c}_{2} (\omega ); \ldots ; \varvec{c}_{r} (\omega )) \in {\mathbb R}^{\bar{n}}$ (with $\varvec{c}_{i} (\omega ) \in \mathcal {E}^{\bar{n}_{i}}$) are random data whose realizations depend on an underlying outcome $\omega$ in an event space $\Omega$ with a known probability function P.

To write the extensive formulation of the SQSOCP problems (1) and (2), we examine problems (1) and (2) when the event space $\Omega$ is finite.

Let $\{(B_l, W_l, \varvec{h}_l, \varvec{c}_l): l = 1, \ldots , K \}$ be the set of the possible values of the random variables $\big (B(\omega ), W(\omega ),\varvec{h}(\omega )$, $\varvec{c}(\omega )\big )$ and let $p_l :=P \big (B(\omega ), W(\omega ), \varvec{h}(\omega ), \varvec{c}(\omega )\big ) = \big (B_l, W_l, \varvec{h}_l, \varvec{c}_l \big )$ be the associated probability for $l = 1, 2, \ldots , K$. For $i=1, 2, \ldots , r$ and $l=1, 2, \ldots , K$, let $n_l$ and $n_{l i}$ be positive integers such that $n_l=\sum _{i=1}^{r}n_{li}$.

Thus, in analogue to the above notations, the matrices $B_{l i} \in {\mathbb R}^{m_1 \times n_{l i}}$ and $W_{l i} \in {\mathbb R}^{m_1 \times n_{l i}}$ and the vectors $\varvec{c}_{l i} \in \mathcal {E}^{n_{l i}}$ are realizations of random data such that $B_l := (B_{l 1}, B_{l 2}, \ldots , B_{l r})$, $W_l := (W_{l1}, W_{l2}, \ldots , W_{lr})$, and $\varvec{c}_l := (\varvec{c}_{l1}; \varvec{c}_{l2}; \ldots ; \varvec{c}_{lr})$. Then, problems (1) and (2) become

$$\begin{aligned} \begin{array}{lll} \text{ min } &{}\eta (\varvec{x}_0) := \varvec{c}_0^{\textsf {T}}\varvec{x}_0 + \displaystyle \sum _{k = 1}^{K} p_l Q_l( \varvec{x}_0 )\\ \text{ s.t. } &{}W_0 \varvec{x}_0 = \varvec{h}_0, &{} \\ &{}\varvec{x}_0 \succeq \varvec{0}, &{} \end{array} \end{aligned}$$

(3)

where, for $l = 1, 2, \ldots , K,\ Q_l( \varvec{x}_0 )$ is the minimum value of the problem

$$\begin{aligned} \begin{array}{lll} \text{ min } &{}{\varvec{c}_l}^{\textsf {T}}\varvec{x}_l &{} \\ \text{ s.t. } &{} W_l \varvec{x}_l = \varvec{h}_l - B_l \varvec{x}_0, &{} \\ &{}\varvec{x}_l \succeq \varvec{0}. &{} \end{array} \end{aligned}$$

(4)

For convenience, we redefine $\varvec{c}_l$ as $\varvec{c}_l:=p_l \varvec{c}_l$ for each $l = 1, 2, \ldots , K$ and consequently rewrite the objective function of Problem (3) as $\eta (\varvec{x}_0) := \varvec{c}_0 ^{\textsf {T}}\varvec{x}_0 + \displaystyle \sum _{l = 1}^{K} Q_l( \varvec{x}_0 ).$

We write the SSOCP problems (3) and (4) as an SSOCP problem with finite event space in primal standard form and get

$$\begin{aligned} \begin{array}{lllllllllllllllllll} \text{ min } &{} \varvec{c}_0 ^{\textsf {T}}\varvec{x}_0 &{}+&{} \varvec{c}_1 ^{\textsf {T}}\varvec{x}_1 &{}+&{} \cdots &{}+&{} \varvec{c}_K ^{\textsf {T}}\varvec{x}_K&{}&{}\\ \text{ s.t. } &{} W_0 \varvec{x}_0 &{}&{}&{}&{}&{}&{} &{}=&{} \varvec{h}_0,\\ &{} B_1 \varvec{x}_0 &{}+&{} W_1 \varvec{x}_1 &{}&{}&{}&{} &{}=&{} \varvec{h}_1,\\ &{}~~~~ \vdots &{}&{}&{}&{}\ddots &{}&{}&{}&{} \vdots \\ &{} B_K \varvec{x}_0 &{}+&{} &{}&{}&{}&{} W_K \varvec{x}_K &{}=&{} \varvec{h}_K,\\ &{}~~~~ \varvec{x}_0,&{}&{}~~~~ \varvec{x}_1,&{}&{} \ldots , &{}&{}~~~~~ \varvec{x}_K &{} \succeq &{} \varvec{0}, \end{array} \end{aligned}$$

(5)

where the variable $\varvec{x}_0 := (\varvec{x}_{01}; \varvec{x}_{02}; \ldots ; \varvec{x}_{0r}) \in \mathcal {E}^{n_{01}} \times \mathcal {E}^{n_{02}} \times \cdots \times \mathcal {E}^{n_{0r}}$ is the first-stage decision variable, and $\varvec{x}_l := (\varvec{x}_{l 1}; \varvec{x}_{l 2}; \ldots ; \varvec{x}_{l r}) \in \mathcal {E}^{n_{l 1}} \times \mathcal {E}^{n_{l 2}} \times \cdots \times \mathcal {E}^{n_{l r}}$, for $l=1, 2, \ldots , K$, are the second-stage decision variables.

The dual of (5) is the problem

$$\begin{aligned} \begin{array}{lllllllllllllllllllllll} \text{ max } &{} \varvec{h}_0 ^{\textsf {T}}\varvec{y}_0 &{}+&{} \varvec{h}_1 ^{\textsf {T}}\varvec{y}_1 &{}+&{} \cdots &{}+&{} \varvec{h}_K ^{\textsf {T}}\varvec{y}_K&{}&{}\\ \text{ s.t. } &{} W_0^{\textsf {T}}\varvec{y}_0 &{}+&{}B_1^{\textsf {T}}\varvec{y}_1&{}+&{}\cdots &{}+&{}B_K^{\textsf {T}}\varvec{y}_K &{}+&{} \varvec{s}_0&{}=&{} \varvec{c}_0,\\ &{}&{}&{} W_1^{\textsf {T}}\varvec{y}_1 &{}&{}&{}&{} &{}+&{} \varvec{s}_1 &{}=&{} \varvec{c}_1,\\ &{}&{}&{}&{}&{}\ddots &{}&{}&{}&{}&{}&{} \vdots \\ &{}&{}&{}&{}&{}&{}&{} W_K^{\textsf {T}}\varvec{y}_K &{}+&{} \varvec{s}_K&{}=&{} \varvec{c}_K,\\ &{}~~~~~~ \varvec{s}_0,&{}&{}~~~~~~ \varvec{s}_1,&{}&{} \ldots , &{}&{} ~~~~~~~ \varvec{s}_K &{}&{}&{} \succeq &{} \varvec{0}, \end{array} \end{aligned}$$

(6)

where $\varvec{y} := (\varvec{y}_0; \varvec{y}_1; \ldots ; \varvec{y}_K) \in {\mathbb R}^{m_0+K m_1}$ is a dual variable and $\varvec{s}_k := (\varvec{s}_{k1}; \varvec{s}_{k2}; \ldots ; \varvec{s}_{kr}) \in \mathcal {E}^{n_{k1}} \times \mathcal {E}^{n_{k2}} \times \cdots \times \mathcal {E}^{n_{kr}}$ are dual slacks for $k=0, 1, \ldots , K$.

Note that the programs in (5) and (6) are SSOCPs in primal and dual standard forms, respectively, with block diagonal structures [2, Definition 2]. It will become clear in our subsequent development (see, in particular, Theorems 5.1, 5.2) that the size of problems (5) and (6) increases with K, and thus is huge in practice since K is typically very large.

The infeasible interior-point algorithm in [8] can be directly applied to the primal-dual pair (5) and (6), but we emphasize that doing so is not good from a computational point of view because the computation of the search direction is very expensive. In fact, algorithms that exploit the special structures in problems (5) and (6) are very important specially when K is large, which is the case in practice. In the remaining part of this paper, we will see that this computational work can be significantly reduced by exploiting the special structure of problems (5) and (6).

4 Computation of Search Directions

In this section, we present a method for computing the search direction for the infeasible algorithm that exploits the special structures in (5) and (6). This method decomposes the problem into K smaller computations that can be performed in parallel. We start by making some assumptions about the primal-dual pair (5) and (6):

Assumption 4.1

The $m_0$ rows of the matrix $W_0 = (W_{01}, W_{02}, \ldots , W_{0r})$, the $m_1$ rows of $W_l = (W_{l 1}, W_{l 2}, \ldots , W_{l r})$ , and the $m_1$ rows of $B_l = (B_{l 1}, B_{l 2}, \ldots , B_{l r})$ are linearly independent for each $l=1, 2, \ldots , K$.

Assumption 4.2

Both primal and dual problems are strictly feasible, that is, there exist primal feasible vectors $\varvec{x}_0, \varvec{x}_1, \ldots , \varvec{x}_K$ such that $\varvec{x}_k \succ \varvec{0}$ for $k=0, 1, \ldots , K$, and there exist dual-feasible vectors $\varvec{y}$ and $\varvec{s}_0, \varvec{s}_1, \ldots , \varvec{s}_K$ such that $\varvec{s}_k \succ \varvec{0}$ for $k=0, 1, \ldots , K$.

Assumption 4.1 is of fundamental importance to ensure nonsingularity. Assumption 4.2 guarantees strong duality for the primal-dual pair (5) and (6).

Given Assumptions 4.1 and 4.2, the optimality conditions for the pair (5) and (6) are as follows:

$$\begin{aligned} \begin{array}{lrr} W_0 \varvec{x}_0 = \varvec{h}_0;&{}~~~~~~~~~~~~~~~~~(7\hbox {a})\\ B_l \varvec{x}_0 + W_l \varvec{x}_l = \varvec{h}_l, \quad l = 1, 2, \ldots , K;&{}(7\hbox {b})\\ W_0 ^{\textsf {T}}\varvec{y}_0 + \displaystyle \sum _{l=1}^{K} B_l ^{\textsf {T}}\varvec{y}_l+ \varvec{s}_0= \varvec{c}_0;&{}(7\hbox {c})\\ W_l ^{\textsf {T}}\varvec{y}_l + \varvec{s}_l = \varvec{c}_l, \quad l = 1, 2, \ldots , K;&{}(7\hbox {d})\\ \varvec{s}_k \circ \varvec{x}_k = \varvec{0}, \quad k = 0, 1, \ldots , K;&{}(7\hbox {e})\\ \varvec{x}_k, \varvec{s}_k \succeq \varvec{0}, \quad k = 0, 1, \ldots , K.&{}(7\hbox {f}) \end{array} \end{aligned}$$

(7)

Note that using (7a–d) we have that

$$\begin{aligned} \displaystyle \sum _{k=0}^{K} \varvec{c}_k ^{\textsf {T}}\varvec{x}_k - \sum _{k=0}^{K} \varvec{h}_k^{\textsf {T}}\varvec{y}_k= & {} \left( W_0 ^{\textsf {T}}\varvec{y}_0 + \displaystyle \sum _{l=1}^{K} B_l ^{\textsf {T}}\varvec{y}_l+ \varvec{s}_0\right) ^{\textsf {T}}\varvec{x}_0 + \displaystyle \sum _{l=1}^{K} (W_l ^{\textsf {T}}\varvec{y}_l + \varvec{s}_l) ^{\textsf {T}}\varvec{x}_l\\&-\, (W_0 \varvec{x}_0)^{\textsf {T}}\varvec{y}_0 - \displaystyle \sum _{l=1}^{K} (B_l \varvec{x}_0 + W_l \varvec{x}_l)^{\textsf {T}}\varvec{y}_l\\= & {} \displaystyle \sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k \ge 0. \end{aligned}$$

Hence, for given primal feasible vectors $\varvec{x}_0, \ldots , \varvec{x}_K$ and dual-feasible vectors $\varvec{y}$ and $\varvec{s}_0, \ldots , \varvec{s}_K$, $\sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k = 0$ is sufficient for optimality, and therefore $\sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k$ is called the duality gap. By using [2, Lemma 15], for $\varvec{x}_k, \varvec{s}_k \succeq \varvec{0}, k = 0, 1, \ldots , K$, $\sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k = 0$ is equivalent to (7e).

The key idea of the path-following interior-point algorithms is to replace the complementarity equation (7e) by the parameterized equation $\varvec{x}_k \circ \varvec{s}_k = \mu \varvec{e}_k$, for $\mu > 0$ where $e_k$ be the identity element of $\mathcal {E}^{n_{k1}} \times \mathcal {E}^{n_{k2}} \times \cdots \times \mathcal {E}^{n_{kr}}$ for $k = 0, 1, \ldots , K$, we then obtain the so-called perturbed optimality conditions. We accordingly consider the system

$$\begin{aligned} \begin{array}{lrr} W_0 \varvec{x}_0 = \varvec{h}_0;&{}\\ B_l \varvec{x}_0 + W_l \varvec{x}_l = \varvec{h}_l,\quad l = 1, 2, \ldots , K;&{}\\ W_0 ^{\textsf {T}}\varvec{y}_0 + \displaystyle \sum _{l=1}^{K} B_l ^{\textsf {T}}\varvec{y}_l+ \varvec{s}_0= \varvec{c}_0;&{}\\ W_l ^{\textsf {T}}\varvec{y}_l + \varvec{s}_l = \varvec{c}_l,\quad l = 1, 2, \ldots , K;&{}\\ \varvec{x}_k \circ \varvec{s}_k = \mu \varvec{e}_k,\quad k = 0, 1, \ldots , K;&{}\\ \varvec{x}_k, \varvec{s}_k \succ \varvec{0},\quad k = 0, 1, \ldots , K.&{} \end{array} \end{aligned}$$

(8)

Under Assumptions 4.1 and 4.2, system (8) has a unique solution denoted by $\left( \left( \varvec{x}_0(\mu ),\varvec{y}_0(\mu ),\varvec{s}_0(\mu )\right) , \ldots \right.$, $\left. \left( \varvec{x}_K(\mu ),\varvec{y}_K(\mu ),\varvec{s}_K(\mu )\right) \right)$ for any $\mu > 0$. We call $\varvec{x}_0(\mu ), \dots , \varvec{x}_K(\mu )$ and $\left( y_0(\mu ),s_0(\mu )\right) , \dots , \left( y_K(\mu ),s_K(\mu )\right)$ as the $\mu$-centers of primal and dual problems, respectively. The set of all $\mu$-centers is called the central path of primal and dual. If $\mu$ approaches 0, then the limit of the central path exists, and since the limit points do satisfy the complementarity condition, they produce an $\varepsilon$-approximate optimal solution of primal and dual problems.

In order to solve system (8), we apply Newton’s method to find an $\varepsilon$-approximate optimal solution of our problem. That is, we compute the Newton search direction $\left( \left( \Delta \varvec{x}_0,\Delta \varvec{s}_0, \Delta \varvec{y}_0\right) , \ldots , \left( \Delta \varvec{x}_K,\Delta \varvec{s}_K, \Delta \varvec{y}_K\right) \right)$ and make a step in this direction to obtain the new iterate $\left( \left( \varvec{x}_0(\alpha ),\varvec{y}_0(\alpha ),\varvec{s}_0(\alpha )\right) , \ldots , \left( \varvec{x}_K(\alpha ),\varvec{y}_K(\alpha ),\varvec{s}_K(\alpha )\right) \right)$ belong to the sufficiently small neighborhood of the central path. The corresponding Newton equations are:

$$\begin{aligned} \begin{array}{llllrr} W_0 \Delta \varvec{x}_0 = \varvec{r}_{p0}; \quad \text {where}~~~&{} \varvec{r}_{p0} := \varvec{h}_0 - W_0 \varvec{x}_0;&{}~~~\\ B_l \Delta \varvec{x}_0 + W_l \Delta \varvec{x}_l = \varvec{r}_{p_l};&{} \varvec{r}_{pl} := \varvec{h}_l - B_l \varvec{x}_0 - W_l \varvec{x}_l;&{}~~\\ W_0^{\textsf {T}}\Delta \varvec{y}_0 + \displaystyle \sum _{l=1}^{K} B_l^{\textsf {T}}\Delta \varvec{y}_l+ \Delta \varvec{s}_0= \varvec{r}_{d0};&{} \varvec{r}_{d0} := \varvec{c}_0 - W_0^{\textsf {T}}\varvec{y}_0 - \displaystyle \sum _{l=1}^{K} B_l^{\textsf {T}}\varvec{y}_l - \varvec{s}_0;&{}~~\\ W_l^{\textsf {T}}\Delta \varvec{y}_l + \Delta \varvec{s}_l = \varvec{r}_{d l};&{} \varvec{r}_{dl} := \varvec{c}_l - W_l^{\textsf {T}}\varvec{y}_l - \varvec{s}_l;&{}~~\\ \varvec{s}_k \circ \Delta \varvec{x}_k + \Delta \varvec{s}_k \circ \varvec{x}_k = \varvec{r}_{ck},&{} \varvec{r}_{ck} := \sigma \mu \varvec{e}_k - \varvec{s}_k \circ \varvec{x}_k.&{}~~ \end{array} \end{aligned}$$

(9)

Here, l varies from 1 to K and k varies from 0 to K, and $\sigma \in ]0, 1[$ is a parameter.

Short-, semi-long-, and long-step algorithms are associated with the following centrality measures defined for each pair $(\varvec{x}_k, \varvec{s}_k)$:

$$\begin{aligned} \begin{array}{lll} d_{F}(\varvec{x}_k, \varvec{s}_k)&{}:= \sqrt{\displaystyle \sum _{i=1}^{r} \left( \left( \lambda _{ 1}\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) - \mu \right) ^2 + \left( \lambda _{ 2}\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) - \mu \right) ^2 \right) },\quad k=0, 1, \ldots , K,\\ d_{2}(\varvec{x}_k, \varvec{s}_k)&{}:= \displaystyle \max _{1 \le i \le r} \left\{ \left| \lambda _{ 1}\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) - \mu \right| ,\;\; \left| \lambda _{ 2}\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) - \mu \right| \right\} ,\quad k=0, 1, \ldots , K,\\ d_{-\infty }(\varvec{x}_k, \varvec{s}_k) &{} := \mu - \displaystyle \min _{1 \le i \le r} \left\{ \lambda _1\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) , \lambda _2\left( Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}\right) \right\} ,\quad ~~ k=0, 1, \ldots , K. \end{array} \end{aligned}$$

Let $\gamma \in ]0,1[$ be a given constant. We define the following neighborhoods of the central path for our problem:

$$\begin{aligned} \begin{aligned} \mathcal {N}_{F}(\gamma )&:= \left\{ (\varvec{x}_0, \varvec{y}_0, \varvec{s}_0, \ldots , \varvec{x}_K, \varvec{y}_K, \varvec{s}_K): d_{F}(\varvec{x}_k, \varvec{s}_k) \le \gamma \mu , \;\;\varvec{x}_k \succ \varvec{0}, \varvec{s}_k \succ \varvec{0}, k = 0, 1, \ldots , K\right\} ,\\ \mathcal {N}_{2}(\gamma )&:= \left\{ (\varvec{x}_0, \varvec{y}_0, \varvec{s}_0, \ldots , \varvec{x}_K, \varvec{y}_K, \varvec{s}_K): d_{2}(\varvec{x}_k, \varvec{s}_k) \le \gamma \mu , \;\;\varvec{x}_k \succ \varvec{0}, \varvec{s}_k \succ \varvec{0}, k = 0, 1, \ldots , K\right\} ,\\ \mathcal {N}_{-\infty }(\gamma )&:= \left\{ (\varvec{x}_0, \varvec{y}_0, \varvec{s}_0, \ldots , \varvec{x}_K, \varvec{y}_K, \varvec{s}_K): d_{-\infty }(\varvec{x}_k, \varvec{s}_k) \le \gamma \mu , \;\;\varvec{x}_k \succ \varvec{0}, \varvec{s}_k \succ \varvec{0}, k = 0, 1, \ldots , K\right\} .\\ \end{aligned} \end{aligned}$$

(10)

Here, $\mu = \frac{1}{2(K+1)} \sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k$. The iterates of our algorithm will be restricted to a specific neighborhood, namely the minus-infinity neighborhood, $\mathcal {N}_{-\infty }(\cdot )$, of the central path, which is defined above based on the minus-infinity centrality measure $d_{-\infty }(\varvec{x}_k, \varvec{s}_k)$.

Note that for each $k=0, 1, \ldots , K$, the elements $\varvec{x}_k$ and $\varvec{s}_k$ of the Newton equations given in (9) may not operator commute. For this reason, system (11) may not have unique solution. In order to overcome this difficulty, we scale the variables used in the Newton system (11) in a way that the scaled variables operator commute and the perturbed complementarity equation is preserved (see Lemma 4.2). In other words, we form different, but fully compatible, perturbed optimality conditions, and consequently lead ourselves to different Newton equations shown in (11) where their scaled elements, $\underline{\varvec{s}_k}$ and $\overline{\varvec{x}_k}$, operator commute as will be seen in Lemma 4.1. The way of scaling that we use is well known and proposed originally by Monteiro [13] and Zhang [14] (called Monteiro-Zhang family of directions) for semidefinite programming and generalized later by Schmieta and Alizadeh to symmetric programming [15].

Let $\varvec{p} \in \mathcal {E}$ be such that $\varvec{p} \succ \varvec{0}$. With the quadratic form of $\varvec{p}$, we define $\overline{\varvec{w}} := Q_{\varvec{p}} \varvec{w}$, and $\underline{\varvec{w}} := Q_{\varvec{p}^{-1}} \varvec{w}$. From [15, Lemma 8], we have that $Q_{\varvec{p}} Q_{\varvec{p}^{-1}} = I$, so the operators $\overline{\varvec{\cdot }}$ and $\underline{\varvec{\cdot }}$ are inverse of each other. Furthermore, from [2, Theorem 8], the existence of $\varvec{w}^{-1}$ indicates the existence of $\overline{\varvec{w}}^{-1}$ and $\underline{\varvec{w}}^{-1}$.

The above definitions are also applied to multiple block cases as follows:

$$\begin{aligned} \overline{\varvec{w}} := (\overline{\varvec{w}}_1; \overline{\varvec{w}}_2; \ldots ; \overline{\varvec{w}}_r),\quad \underline{\varvec{w}} := (\underline{\varvec{w}}_1; \underline{\varvec{w}}_2; \ldots ; \underline{\varvec{w}}_r)\;\;\text {and}\;\; \underline{A} := (\underline{A}_1, \underline{A}_2, \ldots , \underline{A}_r), \end{aligned}$$

where $\underline{A}_i := A_i Q_{\varvec{p}^{-1}}$ for $i=1, 2, \ldots , r$.

For each $k=0, 1, \ldots , K$, an invertible vector $\varvec{p}_k$ is chosen as a function of $\varvec{x}_k$ and $\varvec{s}_k$, and for each choice of $\varvec{p}_k$ we get a different search direction. The following three choices of $\varvec{p}_k$ are the most common in practice [15]:

• Choice I (The HRVW/KSH/M direction) We may choose $\varvec{p}_k = {\varvec{s}_k}^{1/2}$ and obtain $\underline{\varvec{s}_k} = \varvec{e}_k$. This choice is analogue of the XS direction in semidefinite programming and is known as the HRVW/KSH/M direction (it was introduced by Helmberg, Rendl, Vanderbei, and Wolkowicz [16], and Kojima, Shindoh, and Hara [17] independently, and then rediscovered by Monteiro [13]).

• Choice II (The dual HRVW/KSH/M direction) We may choose $\varvec{p}_k = {\varvec{x}_k}^{-1/2}$ and obtain $\overline{\varvec{x}_k} = \varvec{e}_k$. This choice of directions arises by switching the roles of X and S; it is analogue of the SX direction in semidefinite programming and is known as the dual HRVW/KSH/M direction.

• Choice III (The NT direction) We choose $\varvec{p}_k$ in such a way that ${\overline{\varvec{x}_k}} = {\underline{\varvec{s}_k}}$. In this case, we choose

  $$\begin{aligned} \varvec{p}_k = \left[ Q_{{\varvec{x}_k}^{1/2}} \left( Q_{{\varvec{x}_k}^{1/2}} {\varvec{s}_k}\right) ^{-1/2}\right] ^{-1/2} = \left[ Q_{{\varvec{s}_k}^{-1/2}} \left( Q_{{\varvec{s}_k}^{1/2}} {\varvec{x}_k}\right) ^{1/2}\right] ^{-1/2}. \end{aligned}$$

  This choice of directions was introduced by Nesterov and Todd [18] and is known as the NT direction.

The following lemma is due to the discussion after Definition 32 in [2].

Lemma 4.1

Suppose that $\varvec{x}_k, \varvec{s}_k \succ \varvec{0}, k=0, 1, \ldots , K$. Then, for each of the choices I, II and III of $\varvec{p}_k$, $\overline{\varvec{x}_k}$ and $\underline{\varvec{s}_k}$ operator commute.

We have the following proposition, where the first item is based on the fact that $Q_{\varvec{x}_{ki}^{1/2}}\varvec{s}_{ki}$ and $Q_{\varvec{s}_{ki}^{1/2}}\varvec{x}_{ki}$ have the same spectrum [2, Proposition 2.11] and the second item follows from [8, Proposition 3.2].

Proposition 4.1

Let $\gamma \in [0, 1]$ be a given constant, then

• 1. $d_{-\infty }(\varvec{x}_k, \varvec{s}_k)$ is symmetric with respect to $\varvec{x}_k$ and $\varvec{s}_k$, that is $d_{-\infty }(\varvec{x}_k, \varvec{s}_k) = d_{-\infty }(\varvec{s}_k, \varvec{x}_k), k=0, \ldots , K$, and so is $\mathcal {N}_{-\infty }(\gamma )$.

• 2. $\mathcal {N}_{-\infty }(\gamma )$ is scaling invariant, that is $(\varvec{x}_0, \varvec{y}_0, \varvec{s}_0, \ldots , \varvec{x}_K, \varvec{y}_K, \varvec{s}_K) \in \mathcal {N}_{-\infty }(\gamma )$ iff $(\overline{\varvec{x}}_0, \varvec{y}_0, \underline{\varvec{s}}_0, \ldots ,$$\overline{\varvec{x}}_K, \varvec{y}_K, \underline{\varvec{s}}_K) \in \mathcal {N}_{-\infty }(\gamma )$.

We also have the following lemma, where item 1 follows from $Q_{\varvec{p}}Q_{\varvec{p}^{-1}}=I$ and item 2 follows from [15, Lemma 28].

Lemma 4.2

Let $\varvec{x}_k, \varvec{s}_k \succ \varvec{0}, k=0, 1, \ldots , K$, and $\varvec{p}_k$ be invertible. Then, for each $k=0, 1, \ldots , K$, we have $\varvec{x}_k^{\textsf {T}}\varvec{s}_k = \overline{\varvec{x}_k}^{\textsf {T}}\underline{\varvec{s}_k}$. Moreover, $\varvec{s}_k \circ \varvec{x}_k = \mu \varvec{e}_k$ iff $\underline{\varvec{s}_k} \circ \overline{\varvec{x}_k} = \mu \varvec{e_k}$.

As a result, we have the following lemma.

Lemma 4.3

(Lemma 31, [2]) The search directions $(\Delta \varvec{x}_k, \Delta \varvec{y}_k, \Delta \varvec{s}_k), k=0, 1, \ldots , K$, solve the Newton equations (9) iff the search directions $(\Delta \overline{\varvec{x}_k}, \Delta \varvec{y}_k, \Delta \underline{\varvec{s}_k}), k=0, 1, \ldots , K$, solves the scaled Newton equations:

$$\begin{aligned} \begin{array}{llllrr} \underline{W_0} \Delta \overline{\varvec{x}_0} = \hat{\varvec{r}}_{p0}; \quad \text {where}~~~&{} \hat{\varvec{r}}_{p0} &{}:=&{} \varvec{h}_0 - \underline{W_0} \overline{\varvec{x}_0};&{}~(11\mathrm{a})\\ \underline{B_l} \Delta \overline{\varvec{x}_0} + \underline{W_l} \Delta \overline{\varvec{x}_l} = \hat{\varvec{r}}_{p_l};&{} \hat{\varvec{r}}_{pl} &{}:=&{} \varvec{h}_l - \underline{B_l} \overline{\varvec{x}_0} - \underline{W_l} \overline{\varvec{x}_l};&{}~(11\mathrm{b})\\ \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + \displaystyle \sum _{l=1}^{K} \underline{B_l}^{\textsf {T}}\Delta \varvec{y}_l+ \Delta \underline{\varvec{s}_0}= \hat{\varvec{r}}_{d0};&{} \hat{\varvec{r}}_{d0} &{}:=&{} \underline{\varvec{c}_0} - \underline{W_0}^{\textsf {T}}\varvec{y}_0 - \displaystyle \sum _{l=1}^{K} \underline{B_l}^{\textsf {T}}\varvec{y}_l - \underline{\varvec{s}_0};&{}~(11\mathrm{c})\\ \underline{W_l}^{\textsf {T}}\Delta \varvec{y}_l + \Delta \underline{\varvec{s}_l} = \hat{\varvec{r}}_{d l};&{} \hat{\varvec{r}}_{dl} &{}:=&{} \underline{\varvec{c}_l} - \underline{W_l}^{\textsf {T}}\varvec{y}_l - \underline{\varvec{s}_l};&{}~(11\mathrm{d})\\ \underline{\varvec{s}_k} \circ \Delta \overline{\varvec{x}_k} + \Delta \underline{\varvec{s}_k} \circ \overline{\varvec{x}_k} = \hat{\varvec{r}}_{ck},&{} \hat{\varvec{r}}_{ck} &{}:=&{} \sigma \mu \varvec{e}_k - \underline{\varvec{s}_k} \circ \overline{\varvec{x}_k}. &{}~(11\mathrm{e}) \end{array} \end{aligned}$$

(11)

Using Assumption 4.2 and using part 5 of Theorem 8 in [2], we conclude that $\overline{\varvec{x}_k}, \underline{\varvec{s}_k} \succ \varvec{0}$ for $k=0, 1, \ldots , K$. Since $\overline{\varvec{x}_k}$ and $\underline{\varvec{s}_k}$ operator commute, it follows that $\overline{\varvec{x}_k} \circ \underline{\varvec{s}_k} \succ \varvec{0}$. This under Assumption 4.1 validates the operations described in our upcoming computations. In particular, the matrix $M_l$ defined in (13a) is nonsingular and positive definite for each $l=1, 2, \ldots , K$, and the matrix $M_0$ defined in (13c) and the matrix $W_0 M_0^{-1} W_0^{\textsf {T}}$ in (13e) are also nonsingular and positive definite.

Our main result in this section is the following proposition.

Proposition 4.2

The solution of the scaled Newton equations in (11) at $(\overline{\varvec{x}_k}, \varvec{y}_k, \underline{\varvec{s}_k})$ is

$$\begin{aligned} \big (\Delta \overline{\varvec{x}_k}, \Delta \varvec{y}_k, \Delta \underline{\varvec{s}_k}\big ) = \big (\varvec{\beta }_k,\varvec{\alpha }_k, - \overline{\varvec{x}_k}^{-1} \circ (\underline{\varvec{s}_k} \circ \varvec{\beta }_k) + \overline{\varvec{x}_k}^{-1} \circ \hat{\varvec{r}}_{ck} \big ), k=0, 1, \ldots , K, \end{aligned}$$

(12)

where

$$\begin{aligned} \begin{array}{lllrr} M_l &{}:=&{} \underline{W_l} \text {Arw}(\underline{\varvec{s}_l})^{-1} {\text {Arw}(\overline{\varvec{x}_l}^{-1})}^{-1} \underline{W_l} ^{\textsf {T}};&{}(13\mathrm{a})\\ \varvec{\nu }_l &{}:=&{} M_l^{-1}(\hat{\varvec{r}}_{pl} + \underline{W_l} (\underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ \hat{\varvec{r}}_{dl})) - \underline{W_l}(\underline{\varvec{s}_l}^{-1} \circ \hat{\varvec{r}}_{cl})); &{}(13\mathrm{b})\\ M_0 &{}:=&{} \text {Arw}(\overline{\varvec{x}_0}^{-1}) \text {Arw}(\underline{\varvec{s}_0}) + \displaystyle \sum _{l=1}^{K}\underline{B_l}^{\textsf {T}}M_l^{-1} \underline{B_l}; &{}(13\mathrm{c})\\ \varvec{\nu }_0 &{}:=&{} M_0^{-1} \left( \displaystyle \sum _{l=1}^{K}\underline{B_l}^{\textsf {T}}\varvec{\nu }_l - \hat{\varvec{r}}_{d0} + \overline{\varvec{x}_0}^{-1} \circ \hat{\varvec{r}}_{c0} \right) ; &{}(13\mathrm{d})\\ \varvec{\alpha }_0 &{}:=&{} (\underline{W_0} M_0^{-1}\underline{W_0}^{\textsf {T}})^{-1} (\hat{\varvec{r}}_{p0}- \underline{W_0} \varvec{\nu }_0); &{}(13\mathrm{e})\\ \varvec{\beta }_0 &{}:=&{} M_0^{-1} \underline{W_0}^{\textsf {T}}\varvec{\alpha }_0 + \varvec{\nu }_0; &{}~~~~~~~~~(13\mathrm{f})\\ \varvec{\alpha }_l &{}:=&{} - M_l^{-1} \underline{B_l} \varvec{\beta }_0 + \varvec{\nu }_l; &{}(13\mathrm{g})\\ \varvec{\beta }_l &{}:=&{} \underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ (\underline{W_l}^{\textsf {T}}\varvec{\alpha }_l)) - \underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ \hat{\varvec{r}}_{dl}) + \underline{\varvec{s}_l}^{-1} \circ \hat{\varvec{r}}_{cl}.&{}(13\mathrm{h})\\ \end{array} \end{aligned}$$

(13)

Here, l varies from 1 to K.

Proof

From equation (11e), we obtain

$$\begin{aligned} \Delta \underline{\varvec{s}_k} = - \overline{\varvec{x}_k}^{-1} \circ (\underline{\varvec{s}_k} \circ \Delta \overline{\varvec{x}_k}) + \overline{\varvec{x}_k}^{-1} \circ \hat{\varvec{r}}_{ck}, \end{aligned}$$

(14)

for $k=0, 1, \ldots , K$. Substituting (14) into (11d), we get $-\underline{W_l}^{\textsf {T}}\Delta \varvec{y}_l + \overline{\varvec{x}_l}^{-1} \circ (\underline{\varvec{s}_l} \circ \Delta \overline{\varvec{x}_l}) = - \hat{\varvec{r}}_{d l} + \overline{\varvec{x}_l}^{-1} \circ \hat{\varvec{r}}_{cl}.$ Using the above equality, we can write $\Delta \overline{\varvec{x}_l}$ as

$$\begin{aligned} \Delta \overline{\varvec{x}_l} = \underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ (\underline{W_l}^{\textsf {T}}\Delta \varvec{y}_l)) - \underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ \hat{\varvec{r}}_{d l}) + \underline{\varvec{s}_l}^{-1} \circ \hat{\varvec{r}}_{cl} \end{aligned}$$

(15)

for $l = 1, 2, \ldots , K$. Now, we substitute (15) into (11b) to obtain

$$\begin{aligned} \underline{B_l} \Delta \overline{\varvec{x}_0} + \underline{W_l} (\underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ (\underline{W_l}^{\textsf {T}}\Delta \varvec{y}_l)) - \underline{\varvec{s}_l}^{-1} \circ (\overline{\varvec{x}_l} \circ \hat{\varvec{r}}_{d l}) + \underline{\varvec{s}_l}^{-1} \circ \hat{\varvec{r}}_{cl}) = \hat{\varvec{r}}_{p_l} \end{aligned}$$

for $l = 1, 2, \ldots , K$. It follows that

$$\begin{aligned} \Delta \varvec{y}_l = - M_l^{-1} \underline{B_l} \Delta \overline{\varvec{x}}_0 + \varvec{\nu }_l, \end{aligned}$$

(16)

where $M_l$ and $\varvec{\nu }_l$ are defined in (13a, b) for $l = 1, 2, \ldots , K$. By using (14) and (16) in (11c), we obtain

$$\begin{aligned} \hat{\varvec{r}}_{d0}&= \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + \displaystyle \sum _{l=1}^{K}\underline{B_l}^{\textsf {T}}(- M_l^{-1} \underline{B_l} \Delta \overline{\varvec{x}}_0 + \varvec{\nu }_l)\\&\quad \ - \overline{\varvec{x}_0}^{-1} \circ (\underline{\varvec{s}_0} \circ \Delta \overline{\varvec{x}_0}) + \overline{\varvec{x}_0}^{-1} \circ \hat{\varvec{r}}_{c0}. \end{aligned}$$

Thus,

$$\begin{aligned} \Delta \overline{\varvec{x}_0} = M_0^{-1} \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + M_0^{-1} \left( \displaystyle \sum _{l=1}^{K}\underline{B_k}^{\textsf {T}}\varvec{\nu }_k - \hat{\varvec{r}}_{d0} + \overline{\varvec{x}_0}^{-1} \circ \hat{\varvec{r}}_{c0} \right) . \end{aligned}$$

So, $\Delta \overline{\varvec{x}_0}$ can be written as

$$\begin{aligned} \begin{array}{lll} \Delta \overline{\varvec{x}_0}= & {} M_0^{-1} \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + \varvec{\nu }_0, \end{array} \end{aligned}$$

(17)

where $M_0$ and $\varvec{\nu }_0$ are defined in (13c, d).

Substituting (17) into (11a) we get $\hat{\varvec{r}}_{p0} = \underline{W_0} (M_0^{-1} \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + \varvec{\nu }_0)$, which then is used to express $\Delta \varvec{y}_0$ as

$$\begin{aligned} \Delta \varvec{y}_0 = (\underline{W_0} M_0^{-1} \underline{W_0}^{\textsf {T}})^{-1} (\hat{\varvec{r}}_{p0}- \underline{W_0} \varvec{\nu }_0). \end{aligned}$$

(18)

By substituting (17) in (16), $\Delta \varvec{y}_l$ can be expressed as

$$\begin{aligned} \Delta \varvec{y}_l = - M_l^{-1} \underline{B_l} (M_0^{-1} \underline{W_0}^{\textsf {T}}\Delta \varvec{y}_0 + \varvec{\nu }_0) + \varvec{\nu }_l, \end{aligned}$$

(19)

for $l= 1, 2, \ldots , K$. Hence, we can denote $\Delta \varvec{y}_k = \varvec{\alpha }_k, \Delta \overline{\varvec{x}}_k = \varvec{\beta }_k, \; \text {and}\; \Delta \underline{\varvec{s}_k} = - \overline{\varvec{x}_k}^{-1} \circ (\underline{\varvec{s}_k} \circ \varvec{\beta }_k) + \overline{\varvec{x}_k}^{-1} \circ \hat{\varvec{r}}_{ck},$ where $\varvec{\alpha }_k$ and $\varvec{\beta }_k$ are defined in (13e–h) for $k= 0, 1, \ldots , K$. The proof is complete. $\square$

5 Infeasible Interior-Point Algorithm for SSOCPs and Its Complexity Estimates

The generic infeasible algorithm for the primal-dual pair (5) and (6) is stated formally in Algorithm 5.1.

Note that we can provide different values for the primal step lengths $\alpha _{p0}^{(j)}, \alpha _{p1}^{(j)}, \ldots , \alpha _{pK}^{(j)}$, the dual step lengths $\alpha _{d0}^{(j)}, \alpha _{d1}^{(j)}, \ldots , \alpha _{dK}^{(j)}$, and the largest step length $\hat{\alpha }^{(j)}$ as long as we can satisfy all the required conditions. However, if we choose $\alpha _{p0}^{(j)}=\alpha _{p1}^{(j)}=\cdots =\alpha _{pK}^{(j)}= \alpha _{d0}^{(j)}=\alpha _{d1}^{(j)}=\cdots =\alpha _{dK}^{(j)}=\hat{\alpha }^{(j)},$ we can satisfy all the required conditions and remain inside the neighborhood while making a comparable progress toward feasibility and complementarity.

Note that the Rangarajan’s results in [8] apply to all types of symmetric cones. Because it is well known that the second-order cone is a particular symmetric cone with the standard inner product, we can apply the Rangarajan’s result in [8, Theorem 3.11] for iteration bound to our problem setting and obtain a bound for the number of iterations required to obtain $\epsilon$-approximate optimal solution as we will see below. For this reason, Algorithm 5.1 is well defined and it converges.

An immediate result motivated by [8, Theorem 3.3] is that if $\hat{\alpha }^{(j)} \ge \alpha ^\star$ for all j and for some $\alpha ^\star > 0$, then Algorithm 5.1 will terminate with $\big (\varvec{x}_0^{(j)}, \varvec{y}_0^{(j)}, \varvec{s}_0^{(j)}, \ldots , \varvec{x}_K^{(j)}, \varvec{y}_K^{(j)}, \varvec{s}_K^{(j)}\big )$ such that $\big \Vert \hat{\varvec{r}}_{pk}^{(j)} \big \Vert \le \epsilon ^\star \big \Vert \hat{\varvec{r}}_{pk}^{(0)}\big \Vert$ and $\big \Vert \hat{\varvec{r}}_{dk}^{(j)} \big \Vert \le \epsilon ^\star \big \Vert \hat{\varvec{r}}_{dk}^{(0)}\big \Vert$, for $k=0, 1, \ldots , K$, and $\displaystyle \sum _{k=0}^{K} \varvec{x}_k^{(j)^{\textsf {T}}}\varvec{s}_k^{(j)} \le \epsilon ^\star \sum _{k=0}^{K} \varvec{x}_k^{(0)^{\textsf {T}}}\varvec{s}_k^{(0)}$ in $\displaystyle \mathcal {O}\left( \frac{1}{\alpha ^\star } \ln \left( \frac{1}{\epsilon ^\star }\right) \right)$ iterations.

Rangarajan [8] proved that such a lower bound on $\alpha ^\star$ exists and established an estimate of the lower bound. Taking into account such bounds in [8] and applying this to our problem setting, we define

$$\begin{aligned} \alpha ^\star := \min \left( 1, \displaystyle \frac{\gamma \sigma }{((K+1)r+1-\gamma )\omega \sqrt{\kappa }}, ~\displaystyle \frac{2 \sigma }{\omega \sqrt{\kappa }}, ~\displaystyle \frac{2(\beta -\sigma )}{\omega \sqrt{\kappa }} \right) , \end{aligned}$$

where $\kappa := \frac{(K+1)r}{1-\gamma }, ~\omega := \left( \xi + \sqrt{\xi + \zeta } \right) ^2, ~\zeta \le 9 + \frac{1}{1-\gamma }, ~\text {and}~\xi \le \sqrt{\kappa }(5+4 \Psi ) ~\text {for some constant}~ \Psi >0$. This leads to the following theorem which gives polynomial convergence results for Algorithm 5.1.

Theorem 5.1

Algorithm 5.1 will terminate in $\mathcal {O}(((K+1)r)^2 \ln (\frac{1}{\epsilon ^\star }))$ iterations if the NT direction is used at every iteration, and will terminate in $\mathcal {O}(((K+1)r)^{2.5} \ln (\frac{1}{\epsilon ^\star }))$ iterations if the HRVW/KSH/M direction or the dual HRVW/KSH/M direction is used at every iteration.

The above theorem is a consequence of [8, Theorem 3.11] where the underlying symmetric cone is replaced by the product $\large \prod _{k=0}^{K} \mathcal {E}^{n_{k1}}_+ \times \mathcal {E}^{n_{k2}}_+ \times \cdots \times \mathcal {E}^{n_{kr}}_+.$

Table 2 Complexity estimates for dominant steps in method of Sect. 4

We estimate the computational complexity of Algorithm 5.1 for computing the search directions with the method described in Sect. 4 applied to problems (5) and (6). The dominant computations occur at (13) in Proposition 4.2. In Table 2, we list the corresponding numbers of arithmetic operations for these computations where $m_1 = m_0$ and $n_0= n_1=\cdots = n_K$. Note that the most expensive steps in each iteration are the computations of $M_0^{-1}$ in (13c, d). In particular, we analyze the computational work in (13c, d) and also (13a, b) in detail. For any $\varvec{\varrho } := (\varvec{\varrho }_{1}; \varvec{\varrho }_{2}; \ldots ; \varvec{\varrho }_{r})$ with $\varvec{\varrho }_{i} \in \mathcal {E}^{n_{i}}$, the $j^{\text {th}}$ block of $B^{\textsf {T}}_l M_l^{-1} B_l \varvec{\varrho }$ is written as

$$\begin{aligned} (B^{\textsf {T}}_l M_l^{-1} B_l \varvec{\varrho })_j = B^{\textsf {T}}_{l j} (M_l^{-1} B_l \varvec{\varrho }) = B^{\textsf {T}}_{l j} M_l^{-1} \left( \displaystyle \sum _{i=1}^{r} B_{l i} \varvec{\varrho }_i \right) = \displaystyle \sum _{i=1}^{r} B^{\textsf {T}}_{l j} M_l^{-1} B_{l i} \varvec{\varrho }_i. \end{aligned}$$

The number of arithmetic operations required to compute $B^{\textsf {T}}_{l j} M_l^{-1} B_{l i}$ is $\mathcal {O}(m_0^2 n_{0i} n_{0j})$ for all $i, j = 1, 2, \dots , r$. Accordingly, the number of arithmetic operations required to compute $B^{\textsf {T}}_l M_l^{-1} B_l$ is $\mathcal {O}(m_0^2 n_{0i} n_{0j} r^2) = \mathcal {O}(m_0^2 n_0^2)$ (noting that $\sum _{i=1}^{r} n_{0i} = n_0$). The inverse of $M_0$ requires $\mathcal {O}(n_0^3)$ arithmetic operations. Thus, the number of arithmetic operations required for $M_0^{-1}$ is $\mathcal {O}(K m_0^2 n_0^2 + n_0^3)$ as listed in Table 2. Similarly, the number of arithmetic operations required to compute $M_l=\underline{W_l} \text {Arw}(\underline{\varvec{s}_l})^{-1} \text {Arw}(\overline{\varvec{x}_l}) \underline{W_l}^{\textsf {T}}$ is $\mathcal {O}(m_0^2 n_0)$, since when we make a column-wise decomposition of $\underline{W_l}$, we can compute $\text {Arw}(\overline{\varvec{x}_l}) \underline{W_l}^{\textsf {T}}$ in $\mathcal {O}(m_0 n_0)$ by $\text {Arw}(\overline{\varvec{x}_l}) \underline{W_l}^{\textsf {T}}= [\overline{\varvec{x}_l}\circ \varvec{w}_1 \ldots \overline{\varvec{x}_l}\circ \varvec{w}_{m_0}].$

In addition, the number of arithmetic operations required to compute $\text {Arw}(\underline{\varvec{s}_l})^{-1} \underline{W_l}^{\textsf {T}}$ is $\mathcal {O}(m_0 n_0)$. The inverse of $M_l$ requires $\mathcal {O}(m_0^3)$ arithmetic operations. Thus, the number of arithmetic operations required for $M_l^{-1}$ is $\mathcal {O}(m_0^2 n_0 + m_0^3)$ for each $l=1, 2, \ldots , K$. Accordingly, the number of arithmetic operations for (13c, d) in each iteration is dominated by $\mathcal {O}(K(m_0^2 n_0 + n_0^3))$. From the data presented in Table 2, it follows that the total number of arithmetic operations in each iteration is dominated by $\mathcal {O}(K(m_0^2 n_0^2 + n_0^3))$ for any choice of $\varvec{p}$ stated in Sect. 4. We then have the following theorem.

Theorem 5.2

Suppose that $m_1 = m_0$ and $n_0= n_1=\cdots = n_K$. By utilizing Proposition 4.2 for computing the search directions in Algorithm 5.1, we have that the number of arithmetic operations in each iteration of Algorithm 5.1 is $\mathcal {O}(K(m_0^2 n_0^2 +n_0^3))$.

We investigate the comparison between Algorithm 5.1 and the homogeneous self-dual algorithm presented in [6].

First, we provide an evidence of a clear superiority of Algorithm 5.1 over the homogeneous self-dual algorithm in terms of complexity estimates of the number of arithmetic operations needed per iteration. Theorem 5.2 is the counterpart of Theorem 5.1 in [6]. In [6, Theorem 5.1], the number of arithmetic operations in each iteration of the homogeneous self-dual algorithm is $\mathcal {O}(K(m_0^2 n_0^3 +m_0^3))$. Therefore, the Theorem 5.2 in this paper demonstrates that Algorithm 5.1 for our problem has complexity less than that of the homogeneous algorithm developed for the same problem in [6]. The reason of this superiority of Algorithm 5.1 is probably due to the fact that the homogeneous algorithm is based on embedding the original problem into the larger problem that is always feasible. From this point of comparison stems the importance of the results of this paper.

Another point of comparison is to look at the number of iterations needed to obtain $\epsilon$-approximate optimal solution. As far as the homogeneous self-dual algorithm is concerned for comparison purposes, there is no confirmed evidence of a clear preference of Algorithm 5.1 over the homogeneous self-dual algorithm in terms of the number of iterations needed to obtain $\epsilon$-approximate optimal solution because the latter has also a polynomial convergence [19, 20]. However, numerically speaking, in the next section we will demonstrate through a simple numerical example (Example 6.1) such a clear preference of Algorithm 5.1 over the homogeneous self-dual algorithm in terms of both: the number of iterations needed to obtain $\epsilon$-approximate optimal solution and the number of arithmetic operations needed per iteration.

It is known that the homogeneous self-dual algorithm begins with a solution that is feasible with respect to both the linear equalities and the second-order cone constraints, but Algorithm 5.1 begins with a solution that may be infeasible with respect to the linear equalities but is feasible with respect to the second-order cone constraints. In fact, on the other side of the comparison mirror, the main advantage of the homogeneous algorithm is to be able to detect infeasibility since the homogeneous self-dual model produces a problem with a strictly feasible starting point and has a relatively simple certificate of infeasibility. In fact, Algorithm 5.1 does not have this advantage, but it is worth mentioning that Algorithm 5.1 can also be modified to detect infeasibility by extending the constraint set and adding extra variables to make the so-called self-dual embedding (see for example [21]), where the original primal and dual problems are embedded in a larger problem with a known strictly feasible starting point on the central path.

6 Implementation of the Algorithm

In this section, we implement the generic infeasible interior-point algorithm to solve some two-stage SSOCP problems. To obtain our numerical experiments, we used MATLAB version R2013b on Windows 7 Ultimate, which were carried out on a PC with Intel(R) Core(TM) i5-4210U CPU at 2.40 GHz and 6 GB of physical memory. Our numerical results are presented and discussed in the following three examples. In these examples, “Iter” denotes the number of iterations, “CPU(s)” denotes the CPU time (in seconds) required to get an approximate optimal solution of the underlying problem, and “Gap” denotes the value of duality gap with a step length $\alpha ^*$.

Example 6.1

In this example, for simplicity, we consider the simple case of $K=5$ scenarios of SSOCP problems where the matrices $W_0, W_l, B_0$, and $B_l$ and the vectors $\varvec{c}_0, \varvec{c}_l,\varvec{h}_0$, and $\varvec{h}_l$, with $p_l = \frac{1}{K}= \frac{1}{5}$ as the associated probability for each $l=1, 2, \ldots , 5$, are as follows:

$W_0$	$W_1$	$W_2$	$W_3$	$W_4$	$W_5$
$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\\ 0 &{}0 &{}0 &{}1 \end{array} \right)$	$\left( \begin{array}{ccc} 1 &{}0 &{}0 \\ 0 &{}1 &{}0 \\ 0 &{}0 &{}1 \end{array} \right)$	$\left( \begin{array}{ccc} 1 &{}0 &{}0 \\ 0 &{}1 &{}0 \\ 0 &{}0 &{}1 \end{array} \right)$	$\left( \begin{array}{ccc} 1 &{}0 &{}0 \\ 0 &{}1 &{}0 \\ 0 &{}0 &{}1 \end{array} \right)$	$\left( \begin{array}{ccc} 1 &{}0 &{}0 \\ 0 &{}1 &{}0 \\ 0 &{}0 &{}1 \end{array} \right)$	$\left( \begin{array}{ccc} 1 &{}0 &{}0 \\ 0 &{}1 &{}0 \\ 0 &{}0 &{}1 \end{array} \right)$

	$B_1$	$B_2$	$B_3$	$B_4$	$B_5$
	$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\end{array} \right)$	$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\end{array} \right)$	$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\end{array} \right)$	$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\end{array} \right)$	$\left( \begin{array}{cccc} 1 &{}0 &{}0 &{}0\\ 0 &{}1 &{}0 &{}0\\ 0 &{}0 &{}1 &{}0\end{array} \right)$

$\varvec{c}_0$	$\varvec{c}_1$	$\varvec{c}_2$	$\varvec{c}_3$	$\varvec{c}_4$	$\varvec{c}_5$
$\left( \begin{array}{c} 0.2 \\ 0.5\\ 1.5 \\ 1 \end{array} \right)$	$\left( \begin{array}{c} 2\\ 2\\ 2 \end{array} \right)$	$\left( \begin{array}{c} 2\\ 2\\ 2 \end{array} \right)$	$\left( \begin{array}{c} 2\\ 2\\ 2 \end{array} \right)$	$\left( \begin{array}{c} 2\\ 2\\ 2 \end{array} \right)$	$\left( \begin{array}{c} 2\\ 2\\ 2 \end{array} \right)$

$\varvec{h}_0$	$\varvec{h}_1$	$\varvec{h}_2$	$\varvec{h}_3$	$\varvec{h}_4$	$\varvec{h}_5$
$\left( \begin{array}{c} 0.020 \\ 0.005 \\ 0.005 \\ 0.005 \end{array} \right)$	$\left( \begin{array}{c} 0.05 \\ 0.01 \\ 0.01 \end{array} \right)$	$\left( \begin{array}{c} 0.06 \\ 0.01 \\ 0.01 \end{array} \right)$	$\left( \begin{array}{c} 0.07 \\ 0.01 \\ 0.01 \end{array} \right)$	$\left( \begin{array}{c} 0.08 \\ 0.01 \\ 0.01 \end{array} \right)$	$\left( \begin{array}{c} 0.09 \\ 0.01 \\ 0.01 \end{array} \right)$

Fig. 1

The relationship between the duality gap and the number of iterations in Example 6.1

The parameters of problems (1) and (2) 5.1 are given by $\epsilon =0.1$, $\beta = 0.3$, $\gamma =0.9$ and $\sigma =0.25$. With the initial values $\varvec{x}_k^{(0)}=\varvec{e}$, $\varvec{s}_k^{(0)}=\varvec{e}$, $\varvec{y}_k^{(0)}=\varvec{0}$, for $k=0, 1, \ldots , 5$, and with optimal $\alpha =0.7$, the solution is reached after 3 iterations with $Gap= 0.0147$ and $CPU= 0.0936$. The curve in Fig. 1 illustrates the relationship between the duality gap and the number of iterations for this example. After running the algorithm, we obtain the following results:

$\varvec{x}_0$	$\varvec{x}_1$	$\varvec{x}_2$	$\varvec{x}_3$	$\varvec{x}_4$	$\varvec{x}_5$
$\left( \begin{array}{c} 0.0279\\ 0.0050\\ 0.0050\\ 0.0050 \end{array} \right)$	$\left( \begin{array}{c} 0.0361\\ 0.0043\\ 0.0043 \end{array} \right)$	$\left( \begin{array}{c} 0.0433\\ 0.0035\\ 0.0035 \end{array} \right)$	$\left( \begin{array}{c} 0.0500\\ 0.0028\\ 0.0028 \end{array} \right)$	$\left( \begin{array}{c} 0.0562\\ 0.0023\\ 0.0023 \end{array} \right)$	$\left( \begin{array}{c} 0.0622\\ 0.0018\\ 0.0018 \end{array} \right)$

$\varvec{s}_0$	$\varvec{s}_1$	$\varvec{s}_2$	$\varvec{s}_3$	$\varvec{s}_4$	$\varvec{s}_5$
$\left( \begin{array}{c} 0.9070\\ -0.0970\\ -0.0970\\ -0.0970 \end{array} \right)$	$\left( \begin{array}{c} 0.7584\\ -0.0419\\ -0.0419 \end{array} \right)$	$\left( \begin{array}{c} 0.6751\\ -0.0231\\ -0.0231 \end{array} \right)$	$\left( \begin{array}{c} 0.6165\\ -0.0132\\ -0.0132 \end{array} \right)$	$\left( \begin{array}{c} 0.5717\\ -0.0075\\ -0.0075 \end{array} \right)$	$\left( \begin{array}{c} 0.5356\\ -0.0040\\ -0.0040 \end{array} \right)$

$\varvec{y}_0$	$\varvec{y}_1$	$\varvec{y}_2$	$\varvec{y}_3$	$\varvec{y}_4$	$\varvec{y}_5$
$\left( \begin{array}{c} -7.3966\\ -11.4556\\ -10.4637\\ 1.4251 \end{array} \right)$	$\left( \begin{array}{c} 1.2369\\ 2.0375\\ 2.0375 \end{array} \right)$	$\left( \begin{array}{c} 1.3403\\ 2.0202\\ 2.0202 \end{array} \right)$	$\left( \begin{array}{c} 1.4190\\ 2.0107\\ 2.0107 \end{array} \right)$	$\left( \begin{array}{c} 1.4819\\ 2.0052\\ 2.0052 \end{array} \right)$	$\left( \begin{array}{c} 1.5338\\ 2.0021\\ 2.0021 \end{array} \right)$

It is important to point out that a very similar numerical example has been reported in [20, Subsection 5.1] to test the performance of the algorithm proposed in [6]. The following remark demonstrates that Algorithm 5.1 is more efficient than the homogeneous algorithm proposed in [6].

Remark 6.1

The following observations compare the performance of Algorithm 5.1 and the algorithm proposed in [6].

• 1. The optimal solution in Example 6.1 obtained by Algorithm 5.1 has been reached after 3 iterations, while the optimal solution in [20, Subsection 5.1] obtained by the homogeneous self-dual algorithm proposed in [6] has been reached after 6 iterations.

• 2. Solving Example 6.1 using Algorithm 5.1, we have

  $$\begin{aligned}&\displaystyle \sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k= 0.1762,\;\;\text {and}\;\; \displaystyle \sum _{k=0}^{K} \varvec{c}_k ^{\textsf {T}}\varvec{x}_k - \varvec{h}_k ^{\textsf {T}}\varvec{y}_k=0.1755, \;\; \text {and hence}\\&\left| \sum _{k=0}^{K}\varvec{x}_k ^{\textsf {T}}\varvec{s}_k -\left( \varvec{c}_k ^{\textsf {T}}\varvec{x}_k -\varvec{h}_k ^{\textsf {T}}\varvec{y}_k\right) \right| =7.0000e-04, \end{aligned}$$

  while solving the same example using the homogeneous self-dual algorithm proposed in [6], we get

  $$\begin{aligned}&\displaystyle \sum _{k=0}^{K} \varvec{x}_k ^{\textsf {T}}\varvec{s}_k= 0.03900232,\;\text {and}\; \displaystyle \sum _{k=0}^{K} \varvec{c}_k ^{\textsf {T}}\varvec{x}_k - \varvec{h}_k ^{\textsf {T}}\varvec{y}_k=0.049936, \; \text {and hence} \\&\left| \sum _{k=0}^{K}\varvec{x}_k ^{\textsf {T}}\varvec{s}_k -\left( \varvec{c}_k ^{\textsf {T}}\varvec{x}_k -\varvec{h}_k ^{\textsf {T}}\varvec{y}_k\right) \right| =0.01093368. \end{aligned}$$

• 3. According to Theorem 5.2, for any choice of $\varvec{p}$, the number of arithmetic operations in each iteration is dominated by $\mathcal {O}(K(m_0^2 n_0^2 +n_0^3))$, which in our case is $K(m_0^2 n_0^2 +n_0^3)=1600$. Solving this problem using the homogeneous self-dual algorithm, the number of arithmetic operations in each iteration is dominated by $\mathcal {O}(K(m_0^2 n_0^3 +n_0^3))$, which in that case is $K(m_0^2 n_0^3 +n_0^3)=5440$.

In the following example, we consider K scenarios of our problem where K varies from 5 to 50.

Remark 6.2

Consider K scenarios of SSOCP problems where $K=10, 15, \ldots , 50$ and $p_l = \frac{1}{K}$ as the associated probability for $l=1, 2, \ldots , K$. We let $W_0=I_{m_0\times n_0}, W_l=I_{ m_1 \times n_l}$ and $B_l= \left[ I_{m_1 \times m_1} O_{m_1 \times (n_l-m_1)} \right]$. We also let

$$\begin{aligned} \varvec{c}_0= & {} \left( \begin{array}{c} 0.2 \\ 0.5\\ \vdots \\ 0.5\\ 1.5 \\ 1 \end{array} \right) \in {\mathbb R}^{n_0}, \quad \varvec{c}_l= \left( \begin{array}{c} 2\\ 2\\ \vdots \\ 2 \end{array} \right) \in {\mathbb R}^{n_l},\quad \varvec{h}_0= \left( \begin{array}{c} 0.020 \\ 0.005 \\ 0.005 \\ \vdots \\ 0.005 \end{array} \right) \in {\mathbb R}^{m_0}\;\text {and}\;\\ \varvec{h}_l= & {} \left( \begin{array}{c} 0.04+\frac{l}{100} \\ 0.01 \\ 0.01 \\ \vdots \\ 0.01 \end{array} \right) \in {\mathbb R}^{m_l}, l=1, 2, \ldots , K. \end{aligned}$$

As in Example 6.1, the parameters of Algorithm 5.1 are given as $\epsilon =0.1$, $\beta = 0.3$, $\gamma =0.9$ and $\sigma =0.25$. With the initial values $\varvec{x}_k^{(0)}=\varvec{e}$, $\varvec{s}_k^{(0)}=\varvec{e}$, $\varvec{y}_k^{(0)}=\varvec{0}$, for $k=0, 1, \ldots , K$, the solutions are reached and the numerical results of Algorithm 5.1 are summarized in Table 3.

Table 3 The numerical results of Example 6.2

Finally, Fig. 2 illustrates the relationship between the duality gap and the number of iterations for some numerical results with fixed $\alpha =0.0003$ in Table 3. It is interesting to note that the duality gaps decrease in a linear pace as the number of iterations increases.

Fig. 2

The duality gap versus the number of iterations [Table 3 for which $\alpha$ is fixed ($\alpha =0.0003$)]

Table 4 The numerical results of Example 6.3 with optimal values for $\alpha$

Remark 6.3

The algorithm is performed with the accuracy $\epsilon = 10^{-1}$ for a number of SSOCPs in which their data are generated randomly. We input $(m_0, n_0)$ and $(m_1,n_1)$ as the dimensions of coefficient matrices $W_0$ and $W_l$, respectively, $l=0, 1, \ldots , K$. For suitability, we assume $(m_0,n_0) =(m_1, n_1)$. In each problem, we also consider a finite event space with K scenarios. The algorithm proceeds to generate the deterministic data $W_0, h_0$ and $c_0$ and random data $B_l,W_l, h_l$ and $c_l$ for $l = 1, 2, \dots ,K$, with $p_l =\frac{1}{K}$ as the associated probability. We summarize the numerical results of Algorithm 5.1 for this example in Table 4.

7 Conclusions

Interior-point methods are one of the most effective classes of algorithms for solving SSOCPs. In this paper, we have developed an infeasible interior-point algorithm for solving SSOCPs as an alternative to the homogeneous self-dual algorithm proposed in [6]. We have presented a method for computing the search direction by exploiting the special structure in the SSOCP problem. The polynomial convergence of the proposed algorithm has been demonstrated for three important directions: the NT direction, the HRVW/KSH/M direction, and the dual HRVW/KSH/M direction. More specifically, we have seen that given a Cartesian product of r second-order cones with appropriate dimensions in the first-stage problem, a Cartesian product of r second-order cones with appropriate dimensions in the second-stage problem, K number of realizations, and a stopping criterion $\epsilon ^\star >0$, we need at most $\mathcal {O}(((K+1)r)^2 \ln (\frac{1}{\epsilon ^\star }))$ iterations to terminate the algorithm if the NT direction is used, and at most $\mathcal {O}(((K+1)r)^{2.5} \ln (\frac{1}{\epsilon ^\star }))$ iterations to terminate the algorithm if any of the other two directions is used.

We have also estimated the number of arithmetic operations in each iteration of the proposed algorithm. More specifically, by assuming that the dimensions of the underlying second-order cones in each stage have the same sum which equals $n_0$ and that the number of linear equalities in each stage equals $m_0$, and by utilizing our method for computing the search directions, we need at most $\mathcal {O}(K(m_0^2 n_0^2 +n_0^3))$ arithmetic operations in each iteration of the algorithm. Given this result, we have concluded that the algorithm developed in this paper for SSOCPs has complexity less than that of the homogeneous self-dual algorithm developed in [6] for the same problem. Finally, we have also presented computational results on three simple problems for the algorithm and have shown that the proposed algorithm is efficient. Our numerical results show also a clear superiority of the infeasible interior-point algorithm developed in this paper over the homogeneous self-dual algorithm developed in [6].

Future work is devoted to develop an infeasible interior-point algorithm for solving stochastic convex optimization problems over nonsymmetric cones (non-self-scaled cones). Despite widespread applications of nonsymmetric programming problems, they have been studied narrowly in comparison with symmetric programming problems such as linear programming, second-order cone programming, and semidefinite programming. This probably is due to the fact that there is a unifying theory based on Euclidean Jordan algebras that connects all symmetric cones. This makes developing an infeasible interior-point algorithm for nonsymmetric optimization problems more challenging. However, this could be achieved for instance by adopting local Hessian norms on the underlying nonsymmetric cone and its dual cone and by using properties based on skew-symmetry of the constraint system of the resulting model.