A Variant of the Simplex Method for Second-Order Cone Programming

Abstract

The linear second-order cone programming problem is considered. For its solution a variant of the primal simplex-type method is proposed. This variant is a generalization on the cone programming of the standard simplex method for linear programming. At each iteration the dual variable and dual slack are defined, and the move from the given extreme point to another one is realized. Finite and infinite convergence of the method to the solution of the problem having a special form is discussed.

This work was supported partially by the Russian Foundation for Basic Research (project no. 17-07-00510).

1 Introduction

Cone programming is more general setting with respect to linear programming (LP). In cone programming, the requirement that variables must be non-negative is replaced by belonging them to convex cones. The second-order cone programming (SOCP) is the very important special case of cone programming, in which the linear goal function is minimized over the intersection of a linear manifold with direct product of second-order cones [1, 2]. Many optimization problems, including, in particular, quadratically constrained convex quadratic problems, robust optimization and combinatorial optimization problems, may be formulated as SOCP [2, 3].

The most popular methods of solving SOCP are primal-dual interior point techniques, which were developed for LP and were extended for cone programming [4, 5]. The simplex-type algorithms for SOCP are developed essentially less. There are only a few simplex-type methods for SOCP. This situation with simplex-type methods is explained by the presence of infinitely many extreme points in feasible sets. The general approach for constructing simplex-type methods for cone programming was proposed in [6]. In [7] the SOCP problem of special structure with the single second-order cone and other nonnegative variables was considered and the simplex-type algorithm for its solution was developed. The other variant of a simplex-type algorithm for the general linear SOCP problem had been worked out in [8]. This algorithm is based on the reformulation of the SOCP problem as a linear semi-infinite programme and on the consequent application of the dual-simplex primal-exchange method from [9] for solving the reformulated problem. As it is mentioned by authors, their algorithm is more advantage, when it solves the SOCP problems with similar structure.

In the present paper, the general SOCP problem is considered. For its solution, a variant of the primal simplex-type method is proposed. This variant can be treated as the simple extension of the well-known simplex method for LP. In pivoting procedures all variables, belonging to the second-order cone, are taken in the form of a single variable. The method can be interpreted as a special way of solving the system of optimality conditions. The primal feasibility and complementarity between primal variables and dual slack variables are preserved in the course of iterations. The dual slack variable (dual slack) is estimated at each iteration in order to define the primal variable, which must enter the list of basic variables. The similar way of constructing the primal simplex-type method for solving linear semidefinite programming problems had been used in [10].

The paper is organized as follows. In Sect. 2, the statement of SOCP is given. Here we also introduce some notions and notations. Among them definitions of regular and irregular extreme points of the feasible set are rather important. In Sect. 3, the approach to updating regular extreme points is described. Finally, in Sect. 4, the partial case of the SOCP problem is considered. It is shown that the sequence, generated by the proposed algorithm, converges to the solution of the problem.

2 The Problem Statement and Basic Definitions

Let $K^{n}$ denote the second-order (Lorentz) cone in . By its definition

where $\Vert \cdot \Vert$ refers to the standard Euclidean norm and n is the dimension of $K^n$. Here and in what follows we use “;” for adjoining vectors or components of a vector in a column. The cone $K^n$ is self-dual, and it induces a partial order in , namely: $x_1 \succeq _{K^n} x_2$, if $x_1 - x_2 \in K^n$.

Consider the cone programming problem

$$\begin{aligned} \begin{array}{c} \min \ \sum \nolimits _{i=1}^r \langle c_i, x_i \rangle , \\ \sum \nolimits _{i=1}^r A_i x_i = b, \quad x_1 \succeq _{K^{n_1}} 0_{n_1}, \ \ldots , \ x_r \succeq _{K^{n_r}} 0_{n_r}. \end{array} \end{aligned}$$

(1)

Here, , $1\le i\le r$, and . Matrices $A_i$ are of dimensions $m \times n_i$, $1\le i\le r$, and $0_{n_i}$ is a zero vector of dimension $n_i$. The angle brackets denote the usual Euclidean scalar product in .

The dual problem to (1) has the following form

$$\begin{aligned} \begin{array}{c} \max \ \langle b, u \rangle , \\ A_i^T u + y_i = c_i, \ 1\le i\le r; \quad y_1 \succeq _{K^{n_1}} 0_{n_1}, \ \ldots , \ y_r \succeq _{K^{n_r}} 0_{n_r}, \end{array} \end{aligned}$$

(2)

in which .

Let $n = n_1 + \cdots + n_r$. Denoting

and $\mathcal{A}= \left[ A_1, \ldots A_r \right]$, $\mathcal{K}= K^{n_1} \times \cdots \times K^{n_r}$, it is possible to rewrite the pair of problems (1) and (2) as

$$\begin{aligned} \min \ \langle c, x \rangle , \quad \mathcal{A}x = b, \quad x \succeq _{\mathcal{K}} 0_{n}, \end{aligned}$$

(3)

$$\begin{aligned} \max \ \langle b, u\ \rangle , \quad \mathcal{A}^T u + y = c, \quad y \succeq _{\mathcal{K}} 0_{n}. \end{aligned}$$

(4)

We assume that solutions of both problems (3) and (4) exist. Moreover, we assume that $m < n$ and rows of the matrix $\mathcal{A}$ are linear independent. The feasible set in problem (3) is denoted by $\mathcal{F}_P$. Observe, that LP is a special case of (3), (4) with the nonnegative orthant as $\mathcal{K}$.

In order that both problems (3) and (4) have solutions it is necessary that the following system of equalities and inclusions

$$\begin{aligned} \langle x, y \rangle = 0, \quad \mathcal{A}x = b, \quad \mathcal{A}^T u + y = c, \quad x \in \mathcal{K}, \quad y\in \mathcal{K}\end{aligned}$$

(5)

be solvable. The simplex-method under consideration is one of the possible ways for solving this system.

Let $x\in \mathcal{K}$. We split all components $x_i$, composed the vector x, onto zero and nonzero components. In addition, we split nonzero components onto internal components $x_i$, belonging to interior of the cone $K^{n_i}$, and onto boundary components, belonging to the boundary of the cone $K^{n_i}$ (more exactly, to a nonzero face of $K^{n_i}$). From boundary, internal and zero components of the vector x it is possible to compose three blocks of components: $x_F$, $x_I$, $x_N$. Without loss of generality, we assume that these blocks are located in the mentioned order, i.e.

$$\begin{aligned} x = [x_F; x_I; x_N]. \end{aligned}$$

(6)

We suppose also that

$$\begin{aligned} x_F = \left[ x_1; \ldots ; x_{r_F}\right] , \quad x_I = \left[ x_{r_F+ 1}; \ldots ; x_{r_F + r_I} \right] , \quad x_N = \left[ x_{r_F + r_I +1}; \ldots ; x_{r}\right] . \end{aligned}$$

(7)

Thus, the first block of components $x_F$ consists of $r_F = r_F(x)$ components $x_i$. Respectively, the second and the third blocks consist of $r_I= r_I(x)$ and $r_N= r_N(x)$ components $x_i$, respectively. Some blocks may be empty, then the corresponding numbers $r_F$, $r_I$ or $r_N$ are equal to zero. We have $r_F +r_I + r_N = r$.

Let $J^r = [1:r]$. The following partition of the index set $J^r$ onto three subsets

$$\begin{aligned} J^r_F (x) = [1, \ldots , r_F], \quad J^r_I (x) = [r_F + 1, \ldots , r_F + r_I], \quad J^r_N(x) = [r_F + r_I + 1, \ldots , r] \end{aligned}$$

corresponds to the introduced splitting of x onto blocks. Below we use also notations:

$$\begin{aligned} r_B = r_B(x) = r_F(x) + r_I(x), \qquad J^r_B (x) = J^r_F (x)\cup J^r_I (x). \end{aligned}$$

For any nonzero component $x_i$, $i\in J^r_{B}(x)$, the following spectral decomposition

$$\begin{aligned} x_i = \eta _{i,1} \ {\mathbf d}_{i,1} + \eta _{i,n_i} \ {\mathbf d}_{i,n_i} \end{aligned}$$

(8)

takes place (see [2]). In (8) the pair $\left\{ {\mathbf d}_{i,1}, {\mathbf d}_{i,n_i} \right\}$ is the “so-called” Jordan frame. The frame vectors ${\mathbf d}_{i,1}$ and ${\mathbf d}_{i,n_i}$ have the forms

$$\begin{aligned} {\mathbf d}_{i,1} = \frac{1}{\sqrt{2}} \left[ 1; \frac{\bar{x}_i}{\Vert \bar{x}_i\Vert } \right] , \quad {\mathbf d}_{i,n_i} = \frac{1}{\sqrt{2}} \left[ 1; -\frac{\bar{x}_i}{\Vert \bar{x}_i\Vert } \right] , \end{aligned}$$

and

$$\begin{aligned} \eta _{i,1} = \frac{1}{\sqrt{2}}\left( x_i^0+ \Vert \bar{x}_i\Vert \right) , \qquad \eta _{i,n_i} = \frac{1}{\sqrt{2}}\left( x_i^0- \Vert \bar{x}_i\Vert \right) . \end{aligned}$$

Both vectors ${\mathbf d}_{i,1}$ and ${\mathbf d}_{i,n_i}$ are unit vectors and are orthogonal with each other. If $x_i \in K^{n_i}$, then $\eta _{i,1}\ge 0$, $\eta _{i,n_i}\ge 0$.

Introduce in the system of coordinates associated with the current point $x_i$. For this purpose we set

$$\begin{aligned} {\mathbf g}_{i,0} = \left[ 1; 0; \ldots ; 0 \right] , \quad {\mathbf g}_{i,1} = \left[ 0; \frac{\bar{x}_i}{\Vert \bar{x}_i\Vert } \right] . \end{aligned}$$

Both vectors ${\mathbf g}_{i,0}$, ${\mathbf g}_{i,1}$ are unite vectors and

$$\begin{aligned} {\mathbf d}_{i,1} = \frac{1}{\sqrt{2}} \left( {\mathbf g}_{i,0} + {\mathbf g}_{i,1} \right) , \qquad {\mathbf d}_{i,n_i} = \frac{1}{\sqrt{2}} \left( {\mathbf g}_{i,0} - {\mathbf g}_{i,1} \right) . \end{aligned}$$

The vector ${\mathbf g}_{i,0}$ coincides with the basis vector in corresponding to the component with zero index. Furthermore, in the subspace

we take arbitrary unit vectors ${\mathbf g}_{i, 2}, \ldots , {\mathbf g}_{i, n_i -1}$, which are orthogonal to each others and orthogonal to the vector ${\mathbf g}_{i,1}$ too. Then the vectors ${\mathbf g}_{i,j}$, $1\le j \le n_i - 1$, form the orthonormal basis in , and jointly with ${\mathbf g}_{i,0}$—the orthonormal basis in .

Let ${\mathbf G}_i, i\in J^r_B(x)$, denote the orthogonal matrix ${\mathbf G}_i = \big [ {\mathbf g}_{i,0}, \ {\mathbf g}_{i,1}, \ \ldots ,$ ${\mathbf g}_{i, n_i - 1} \big ]$ of order $n_i$. For $i\in J^r_N(x)$ the intrinsic basis is taken as ${\mathbf G}_i$. Then for any point , $i\in J^r$, the representation $x_i = {\mathbf G}_i \nu _i$ is valid, where and $\nu _i = {\mathbf G}_i^T x_i$.

Introduce additionally $n_i \times (n_i -1)$ matrix

and denote , where $e_{i,j}$ is the $j^\mathrm{\scriptstyle th}$ unit orth in . Then for components $x_i$, $i\in J^r_B(x)$, with representations (8), the following equality

$$\begin{aligned} x_i = {\mathbf G}_i \lambda _{i,1} = \nu _{i,1}^0 {\mathbf g}_{i,0} + \nu _{i,1} {\mathbf g}_{i,1}, \end{aligned}$$

(9)

takes place. Moreover, if $i\in J^r_F(x)$, the equality $\nu _{i,0} = \nu _{i,1} = \nu _{i,1}^0 = x_i^0$ holds. All other components $\lambda _{i,j}$, $2\le j \le n_i-1$, are zero vectors. For $i\in J^r_I(x)$ we have: $\nu _{i,1}^0 = x_i^0, \nu _{i,1} = \Vert \bar{x}_i\Vert$ and $\nu _{i,1}^0 > \nu _{i,1}$. If we set $\left[ \nu _{i,1}^0; \nu _{i,1}\right] = \left[ 0; 0\right]$, then, formally, the representation (9) is valid for $x_i$, when $i\in J^r_N(x)$.

Denote by ${\mathbf G}$ and block diagonal matrices

Moreover, denote by ${\mathbf e}_1$ the n-dimensional vector ${\mathbf e}_1 = [e_{1,1}; \, e_{2,1}; \, \ldots ; \, e_{r,1}]$. Then, for the vector $x = [x_F; x_I; x_N]\in \mathcal{F}_P$ with components $x_i$, $i\in J^r$ we obtain where $\mathcal{A}^{\mathbf G}= \mathcal{A}{\mathbf G}$. The matrix $\mathcal{A}^{\mathbf G}$ together with the matrix $\mathcal{A}$ has full rank equal to m.

Consider the sets

By ${\mathbf S}_{i,j}^+$ we denote the following subset of the set ${\mathbf S}_{i,j}$:

The set ${\mathbf S}_{i,j}^+$, being a two-dimensional second-order cone, is the section of the cone $K^{n_i}$.

Let $x_{i,j} = {\mathbf G}_i \lambda _{i,j}\in {\mathbf S}_{i,j}$, $1\le j \le n_i -1$. The cone $K^{n_i}$ is convex, therefore, $x_i = \sum _{j = 1}^{n_i -1} x_{i,j} \in K^{n_i}$, if $x_{i,j} \in {\mathbf S}_{i,j}^+$, $1\le j \le n_i -1$. From the other hand, if $x \in K^{n_i}_2$, then x can be represented as the sum of the vectors $x_{i,j} \in {\mathbf S}_{i,j}$, $1\le j \le n_i-1$, but at nonunique way.

In what follows, we will need in extreme rays of the cone ${\mathbf S}_{i,j}^+$, which are the sets

$$\begin{aligned} {\mathbf l}^+_{i,j} = \left\{ x_i = {\mathbf G}_i \varLambda _i e_{i,j}\in {\mathbf S}_{i,j}^+: \ \nu _{i,j}^0 = \nu _{i,j} \right\} , \end{aligned}$$

$$\begin{aligned} {\mathbf l}^-_{i,j} = \left\{ x_i = {\mathbf G}_i \varLambda _i e_{i,j}\in {\mathbf S}_{i,j}^+: \ \nu _{i,j}^0 = -\nu _{i,j} \right\} . \end{aligned}$$

Both rays ${\mathbf l}^+_{i,j}$ and ${\mathbf l}^-_{i,j}$ belong to the boundary of the cone ${\mathbf S}_{i,j}^+$, and, consequently, belong to the boundary of the cone $K^{n_i}$.

Definition 1

A point $x_{i,j} = {\mathbf G}_i \lambda _{i,j} \in {\mathbf S}_{i,j}^+$ is called interior point of the cone ${\mathbf S}_{i,j}^+$, if the pair $[\nu _{i,j}^0; \nu _{i,j}]$ is such, that $\nu _{i,j}^0 > |\nu _{i,j}|$.

Definition 2

A point $x_{i,j} = {\mathbf G}_i \lambda _{i,j} \in {\mathbf S}_{i,j}^+$ is called nonzero boundary point of the cone $S_{i,j}^+$, if the pair $[\nu _{i,j}^0; \nu _{i,j}]$ is such, that $\nu _{i,j}^0 = |\nu _{i,j}|> 0$.

Proposition 1

Let $x_i = \sum _{j = 1}^{n_i -1} x_{i,j}$, where $x_{i,j} \in {\mathbf S}_{i,j}^+$, $1\le j \le n_i -1$. Let also at least one point $x_{i,j}$ be an interior point of the cone ${\mathbf S}_{i,j}^+$. Then $x_i$ is the interior point of the cone $K^{n_i}$.

Proposition 2

Let $x_i = x_{i,1}$, where $x_{i,1}$ is an interior point of the cone ${\mathbf S}_{i,1}^+$. Let, in addition, $\varDelta x_i = \sum _{j=1}^{n_i-1} \varDelta x_{i,j}$, where $\varDelta x_{i,j}\in {\mathbf S}_{i,j}$, $1\le j \le n_i -1$. Then there is $\alpha _* > 0$, such that $x_i + \alpha \varDelta x_i \in K^{n_i}$ for any $0\le \alpha \le \alpha _*$.

Denote by $F_\mathrm{min}(x \vert \mathcal{K})$ the minimal face of the cone $\mathcal{K}$, containing the point $x\in \mathcal{K}$. Denote also by $\mathcal{N}(\mathcal{A})$ the null space of the matrix $\mathcal{A}$. According to [6] the vector $x\in \mathcal{F}_P$ is an extreme point of the set $\mathcal{F}_P$, if

$$\begin{aligned} \mathrm{lin} \left( F_\mathrm{min}(x \,\vert \,\mathcal{K})\right) \cap \mathcal{N}(\mathcal{A}) = \{0_n\}, \end{aligned}$$

where $\mathrm{lin} \left( F_\mathrm{min}(x \vert \mathcal{K})\right)$ is a linear hull of the face $F_\mathrm{min}(x \vert \mathcal{K})$. Moreover, the following inequality $\mathrm{dim} F_\mathrm{min}(x \,\vert \,\mathcal{K}) \le m$ must hold.

We have

$$\begin{aligned} \mathrm{dim} \, F_\mathrm{min}(x_i \,\vert \, K^{n_i}) = \left\{ \ \begin{array}{c} 1, \quad i\in J^r_F (x), \\ n_{i}, \quad i\in J^r_I (x). \end{array} \right. \end{aligned}$$

Hence, for the dimension of a minimal face, containing the extreme point x, the inequality $\mathrm{dim} \, F_\mathrm{min}(x \,\vert \,\mathcal{F}_P) \le m$ is fulfilled, where

$$\begin{aligned} \mathrm{dim} \, F_\mathrm{min}(x \,\vert \,\mathcal{F}_P) = r_F + n_I, \qquad n_I = n_I(x) = \sum _{i\in J^r_I(x)} n_i. \end{aligned}$$

We call an extreme point $x\in \mathcal{F}_P$ regular, if $\mathrm{dim} \, F_\mathrm{min}(x \,\vert \,\mathcal{F}_P) = m$. In the case, where $\mathrm{dim} \, F_\mathrm{min}(x \,\vert \,\mathcal{F}_P) < m$, we call an extreme point $x\in \mathcal{F}_P$ irregular.

3 Updating of Regular Extreme Point

Let x be a regular extreme point of the feasible set $\mathcal{F}_P$. We want to move from x to another extreme point $\hat{x}\in \mathcal{F}_P$ next to it. Moreover, we want to make this move in such a manner, that the value of the objective function at the updated point $\hat{x}$ is less than at x. To this end, we will determine at first the slack dual variable , satisfying to all equalities from (5). In addition, we require that these equalities be reserved during the move from x to $\hat{x}$.

As a preliminary, we determine the dual vector in order to determine y. Assume that the extreme point $x\in \mathcal{F}_P$ is regular.

Partition (6) of the vector x onto components $x_F$, $x_I$ and $x_N$ generates the partition of the vector y onto corresponding components $y_F$, $y_I$ and $y_N$, where

$$\begin{aligned} y_F = \left[ y_1; \ldots ; y_{r_F}\right] , \quad y_I = \left[ y_{r_F+ 1}; \ldots ; y_{r_B}\right] , \quad y_N = \left[ y_{r_{B} +1}; \ldots ; y_{r_{B} + r_N}\right] . \end{aligned}$$

By analogy with x each component $y_i$, $i\in J^r$, may be represented as $y_i = {\mathbf G}_i \sigma _i$ with . Moreover, for any vector the equality $y = {\mathbf G}\sigma$ is valid, where Thus, $\sigma = {\mathbf G}^Ty$.

The complementary condition $\langle x, \, y \rangle = 0$ from (5) may be rewritten as

$$\begin{aligned} \langle x, \, y \rangle = \sum _{i \in J^r_{B} (x) } \langle x_i, \ y_i \rangle = 0. \end{aligned}$$

It follows from here that this condition is fulfilled, if the following equalities

$$\begin{aligned} \langle x_i, y_i \rangle = 0, \qquad i \in J^r_{B}(x), \end{aligned}$$

(10)

hold. In the case, where $i\in J^r_I(x)$, equality (10) is fulfilled, if, for example, $y_i = 0_{n_i}$. For $i\in J^r_F(x)$, i.e. when $x_i = \eta _{i,1} {\mathbf d}_{i,1}$ is a boundary point of $K^{n_i}$, we may take $y_i = {\mathbf d}_{i, n_i}$. Since ${\mathbf d}_{i,1} \perp {\mathbf d}_{i,n_i}$, the equality (10) is also fulfilled in this case.

Take into account that $y_i = c_i - A_i^T u$. Then conditions $y_i = 0_{n_i}$, $i\in J^r_I(x)$, may be written as the system of linear equations with respect to the dual variable u, that is:

$$\begin{aligned} \left( A_i^{{\mathbf G}_i}\right) ^T u = c_i^{{\mathbf G}_i}, \qquad i\in J^r_I (x). \end{aligned}$$

(11)

Here and in what follows, $A_i^{{\mathbf G}_i} = A_i {\mathbf G}_i$, $c_i^{{\mathbf G}_i} = {\mathbf G}_i^T c_i$.

Consider now the case, where $i\in J^r_F(x)$. In this case $x_i = \eta _{i,1} {\mathbf d}_{i,1}$ and $\eta _{i,1} = \sqrt{2}x_i^0$. From here we have

$$\begin{aligned} \nu _i = {\mathbf G}_i^T x_i = \eta _{i,1} {\mathbf G}_i^T {\mathbf d}_{i,1} = x_i^0 {\mathbf G}_i^T \left( {\mathbf g}_{i,0} + {\mathbf g}_{i,1} \right) = x_i^0 \left[ 1; 1; 0; \ldots ; 0 \right] . \end{aligned}$$

Hence, for $y_i = {\mathbf d}_{i,n_i}$ we obtain

$$\begin{aligned} \sigma _i = {\mathbf G}_i^T y_i = \frac{1}{\sqrt{2}}{\mathbf G}_i^T \left( {\mathbf g}_{i,0} - {\mathbf g}_{i,1} \right) = \frac{1}{\sqrt{2}} \left[ 1; -1; 0; \ldots ; 0 \right] . \end{aligned}$$

Thus, it is sufficient to require $\sigma _{i,0} = -\sigma _{i,1}$ in order to satisfy the equality $\langle x_i, y_i \rangle = 0$.

Let $i\in J^r_F(x)$. Denote by $c_{i,0}^{{\mathbf G}_i}$ and $c_{i,1}^{{\mathbf G}_i}$ the zero and the first components of the vector $c_i^{{\mathbf G}_i}$, respectively. Denote also by $A_{i,0}^{{\mathbf G}_i}$ and $A_{i,1}^{{\mathbf G}_i}$ the zero and the first columns of the matrix $A_i^{{\mathbf G}_i}$. We set $\widetilde{c}^{{\mathbf G}_i}_{i,1} = c_{i,0}^{{\mathbf G}_i} + c_{i,1}^{{\mathbf G}_i}$, $\widetilde{A}_{i,1}^{{\mathbf G}_i} = A_{i,0}^{{\mathbf G}_i} + A_{i,1}^{{\mathbf G}_i}$. Since $\sigma _i = {\mathbf G}_i^T y_i = c_i^{{\mathbf G}_i} - \left( A_i^{{\mathbf G}_i} \right) ^T u$, we derive from here and (11) the following system of linear equations

$$\begin{aligned} \left( \widetilde{A}_{i,1}^{{\mathbf G}_i} \right) ^T u = \widetilde{c}^{{\mathbf G}_i}_{i,1}, \quad i\in J^r_F(x); \qquad \left( {A}_{i}^{{\mathbf G}_i} \right) ^T u = {c}^{{\mathbf G}_i}_{i}, \quad i \in J^r_I(x). \end{aligned}$$

(12)

At the regular point $x\in \mathcal{F}_P$ the system (12) consists of m equations, the number of variables (components of the vector u) is also equal m.

Denoting by $\mathcal{A}_{B}^{{\mathbf G}}$ the square matrix of the order m

$$\begin{aligned} \mathcal{A}_{B}^{{\mathbf G}} = \left[ \widetilde{A}_{1,1}^{{\mathbf G}_i}, \ \ldots , \ \widetilde{A}_{r_F,1}^{{\mathbf G}_i}, \ A^{{\mathbf G}_{r_F+1}}_{r_F+1}, \ \ldots , \ A^{{\mathbf G}_{r_F+r_I}}_{r_F+r_I} \right] , \end{aligned}$$

and denoting by $c_{B}^{{\mathbf G}}$ the m-dimensional vector

$$\begin{aligned} c_{B}^{{\mathbf G}} = \left[ \widetilde{c}^{{\mathbf G}_i}_{1,1}; \ \ldots ; \ \widetilde{c}^{{\mathbf G}_i}_{r_F,1}; \ c^{{\mathbf G}_{r_F+1}}_{r_F+1}; \ \ldots ; \ c^{{\mathbf G}_{r_F+r_I}}_{r_F+r_I} \right] , \end{aligned}$$

rewrite the system of equations (12) as

$$\begin{aligned} \left( \mathcal{A}_{B}^{{\mathbf G}} \right) ^T u = c_{B}^{{\mathbf G}}. \end{aligned}$$

(13)

If the matrix of this system is nonsingular, then, solving (13), we obtain

$$\begin{aligned} u = \left( \mathcal{A}_{B}^{{\mathbf G}} \right) ^{-T} c_{B}^{{\mathbf G}}. \end{aligned}$$

Here and in what follows the notation $M^{-T}$ is used instead of $(M^T)^{-1}$.

Let us give the definition of the non-degenerate point $x\in \mathcal{F}_P$ from [2].

Definition 3

The point $x\in \mathcal{F}_P$ is called non-degenerate, if , where $\mathcal{T}_\mathcal{K}(x)$ is the tangent space to the cone $\mathcal{K}$ at x, and $\mathcal{N}_\mathcal{A}$ is the null-space of the matrix $\mathcal{A}$.

Denote by $\bar{A}_i^{{\mathbf G}_i}$, $i\in J^r_F(x)$, the matrix

$$\begin{aligned} \bar{A}_i^{{\mathbf G}_i} = \left[ A^{{\mathbf G}_i}_{i,0} + A^{{\mathbf G}_i}_{i,1}, A^{{\mathbf G}_i}_{i,2}, \ \ldots , \ A^{{\mathbf G}_i}_{i,n_i-1} \right] , \end{aligned}$$

and by $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$—the matrix

$$\begin{aligned} \bar{\mathcal{A}}^{{\mathbf G}}_{B} = \left[ \bar{A}_1^{{\mathbf G}_1}, \ \ldots , \ \bar{A}_{r_F}^{{\mathbf G}_{r_F}}, \ A^{{\mathbf G}_{r_F+1}}_{r_F+1}, \ \ldots , \ A^{{\mathbf G}_{r_F+r_I}}_{r_F+r_I} \right] . \end{aligned}$$

The matrix $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$ has the dimension $m\times (n_{B}-r_F)$, where $n_{B} = n_{B}(x) = \sum _{i\in J^r_{B}(x)} n_i$.

Proposition 3 (Non-degeneracy criterion)

The point $x = [x_F; x_I; x_N] \in \mathcal{F}_P$ is non-degenerate if and only if the rows of the matrix $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$ are linear independent.

According to Proposition 3, the inequality $m+r_F \le n_{B}$ must hold at the non-degenerate point $x\in \mathcal{F}_P$.

Now, let us give the criterion of extreme point $x\in \mathcal{F}_P$ (see [6]).

Proposition 4 (Criterion of an extreme point)

The point $x\in \mathcal{F}_P$ is an extreme point of the set $\mathcal{F}_P$, if and only if columns of the matrix ${\mathcal{A}}^{{\mathbf G}}_{B}$ are linear independent.

By Proposition 4 the inequality $r_F + n_I \le m$ must hold at any extreme point of $\mathcal{F}_P$.

Proposition 5

Let $x\in \mathcal{F}_P$ be a regular extreme point. Then x is a non-degenerate point.

Proof

Since all columns of the matrix $\mathcal{A}^{{\mathbf G}}_{B}$ are contained in the matrix $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$, and since the row rank of the matrix $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$ coincides with its column rank, all m rows of $\bar{\mathcal{A}}^{{\mathbf G}}_{B}$ are linear independent. Taking into account Proposition 3, we come to conclusion, that any regular extreme point $x\in \mathcal{F}_P$ is a non-degenerate point.    $\square$

Theorem 1

Let x be a regular extreme point of $\mathcal{F}_P$. Then the matrix $\mathcal{A}^{{\mathbf G}}_{B}$ is non-singular.

Proof

The matrix $\mathcal{A}^{{\mathbf G}}_{B}$ consists of m columns. But the extreme point x is regular. Hence, according to the assertion of Proposition 4 these columns are linear independent. We obtain that the square matrix $\mathcal{A}^{{\mathbf G}}_{B}$ is nonsingular.    $\square$

By Theorem 1, columns of the matrix $\mathcal{A}_{B}^{{\mathbf G}}$ are linear independent, and we may regard $\mathcal{A}_{B}^{{\mathbf G}}$ as the matrix of basis at the regular extreme point $x\in \mathcal{F}_P$. In addition, we may regard $x_i$, $i\in J^r_{B}(x)$, as basic variables, and we may regard $x_i$, $i\in J^r_{N}(x)$, as non-basic variables. What is more, we call the basic variables $x_i$, $i\in J^r_F(x)$, by facet basic variables, and we call the basic variables $x_i$, $i\in J^r_I(x)$, by interior basic variables.

Further, we take the obtained dual variable u and define the dual slack

$$\begin{aligned} y = c - \mathcal{A}^T u = c - \mathcal{A}^T \left( \mathcal{A}_{B}^{{\mathbf G}} \right) ^{-T} c_{B}^{{\mathbf G}}. \end{aligned}$$

For the vector of coefficients , we obtain respectively

$$\begin{aligned} \sigma = \left[ \sigma _1; \ldots ; \sigma _r \right] = c^{{\mathbf G}} - (\mathcal{A}^{{\mathbf G}})^T \left( \mathcal{A}_{B}^{{\mathbf G}} \right) ^{-T} c_{B}^{{\mathbf G}}. \end{aligned}$$

In the case, where $y\in \mathcal{K}$, the point x is a solution of problem (3), and [u, y] is a solution of problem (4).

In what follows, we assume that the inclusion $y\in \mathcal{K}$ is violated, that is $y_i \notin K^{n_i}$ for at least one index $1\le i\le r$. Since u satisfies equations (13), we have $\sigma _i = 0_{n_i}$, $i\in J^r_I(x)$. Therefore, $y_i=0_{n_i}$, when $i\in J^r_I(x)$. Hence, the inclusion $y_i \in K^{n_i}$ may be broken only in cases, where $i\in J^r_N(x)$ or $i\in J^r_F(x)$.

Consider firstly the case, where there exists the index $k\in J^r_N(x)$ such that $y_k \notin K^{n_i}$. We take this $y_k$ and make the spectral decomposition

$$\begin{aligned} y_k = \theta _{k,1} \ {\mathbf f}_{k,1} + \theta _{k,n_k} \ {\mathbf f}_{k,n_k}, \end{aligned}$$

(14)

where

$$\begin{aligned} \theta _{k,1} = \frac{1}{\sqrt{2}}\left( y_{k}^0+ \Vert \bar{y}_{k}\Vert \right) , \qquad \theta _{k,n_k} = \frac{1}{\sqrt{2}}\left( y_{k}^0- \Vert \bar{y}_{k}\Vert \right) , \end{aligned}$$

and ${\mathbf f}_{k,1}$, ${\mathbf f}_{k,n_k}$ are frame vectors:

$$\begin{aligned} {\mathbf f}_{k,1} = \frac{1}{\sqrt{2}} \left[ 1; \frac{\bar{y}_k}{\Vert \bar{y}_k\Vert } \right] , \quad {\mathbf f}_{k,n_k} = \frac{1}{\sqrt{2}} \left[ 1; -\frac{\bar{y}_k}{\Vert \bar{y}_k\Vert } \right] . \end{aligned}$$

(15)

Both vectors (3) are unit vectors. Since $y_k \notin K^{n_k}$, at least one of two coefficients $\theta _{k,1}$ or $\theta _{k,n_k}$ is negative. We suppose for definiteness, that $\theta _{k,1} < 0$.

Change components of the vector x, setting

$$\begin{aligned} \hat{x}_i = \hat{x}_i(\alpha ) = x_i + \alpha \varDelta x_i, \quad 1\le i\le r, \end{aligned}$$

(16)

where $\alpha > 0$ is a step length. The vectors $\varDelta x_i$, $i\in J^r$, are defined by different ways, depending on the case, to which set $i \in J^r_N(x)$, $i \in J^r_I(x)$ or $i \in J^r_F(x)$ the index i belongs. First of all, we set

$$\begin{aligned} \varDelta x_i = \left\{ \begin{array}{c} {\mathbf f}_{k,1}, \ \ i = k, \\ 0_{n_i}, \ \ i \not = k. \end{array} \right. , \qquad i\in J^r_N(x). \end{aligned}$$

(17)

Thus, $\hat{x}_i = x_i = 0_{n_i}$, when $i\in J^r_N(x)$ and $i\not = k$. For index k the updated point $\hat{x}_k$ is defined as $\hat{x}_k = \alpha {\mathbf f}_{k,1}$. The vectors $\varDelta x_i$, $i\in J^r_I(x)$, are arbitrary from the space .

For $i\in J^r_F(x)$ we take $\varDelta x_i$ in the form

$$\begin{aligned} \varDelta x_i = \left[ \varDelta x_{i,0}; \varDelta x_{i,1}; 0; \ldots ; 0 \right] \end{aligned}$$

(18)

under the additional condition, that $\varDelta x_{i,0} = \varDelta x_{i,1}$. The vector $\varDelta x_i$ in this case belongs to the linear hull of the ray ${\mathbf l}_{i,1}^+$.

In order to satisfy the equality $\mathcal{A}\hat{x} = b$, we require that

$$\begin{aligned} \sum _{i\in J^r_F(x)} \widetilde{A}_{i,1} \varDelta x_{i,1} + \sum _{i\in J^r_I(x)} A_i \varDelta x_i + A_k {\mathbf f}_{k,1} = 0_m. \end{aligned}$$

(19)

Replacing $\varDelta x_i$, $i\in J^r_B(x)$, by its coefficients $\varDelta \nu _i= {\mathbf G}_i^T \varDelta x_i$, we obtain

$$\begin{aligned} \sum _{i\in J^r_F(x)} \left( \widetilde{A}_{i,1}^{{\mathbf G}_i} \right) \varDelta \nu _{i,1} + \sum _{i\in J^r_I(x)} A_i^{{\mathbf G}_i} \varDelta \nu _i + A_k^{{\mathbf G}_k}\varDelta \sigma _{k,1} = 0_m, \end{aligned}$$

(20)

where $\varDelta \sigma _{k,1} = {\mathbf G}_k^T {\mathbf f}_{k,1}$.

Let

Then the system (20) may be rewritten as

$$\begin{aligned} \mathcal{A}_{B}^{{\mathbf G}} \varDelta \nu _B + A_k^{{\mathbf G}_k} \varDelta \sigma _{k,1} = 0_m. \end{aligned}$$

(21)

According to Theorem 1, the matrix $\mathcal{A}_{B}^{{\mathbf G}}$ of this system is nonsingular. Solving the system (21), we get

$$\begin{aligned} \varDelta \nu _B = - \left( \mathcal{A}_{B}^{{\mathbf G}}\right) ^{-1}A_k^{{\mathbf G}_k} \varDelta \sigma _{k,1}. \end{aligned}$$

(22)

Analyze now, is it possible the case, when $k\in J^r_F(x)$.

Proposition 6

The index k can not belong to the set $J^r_F(x)$.

Proof

Under the assumption that $k\in J^r_F(x)$, we must set $\varDelta x_i = 0_{n_i}$, $i\in J^r_N(x)$. Moreover, as in the case $k\in J^r_N(x)$, we must take $\varDelta x_i$, $i\in J^r_I(x)$, arbitrary from the space .

Consider now situations with $i\in J^r_F(x)$. If $i\not = k$, then we take $\varDelta x_i$ in previous form (18). For $i=k$ we must set

$$\begin{aligned} \varDelta x_k = \left[ \varDelta x_{k,0}; \varDelta x_{k,1}; 0; \ldots ; 0 \right] + {\mathbf f}_{k,1}, \end{aligned}$$

where $\varDelta x_{k,0} = \varDelta x_{k,1}$. Respectively, in the space of coefficients $\nu$ we have

$$\begin{aligned} \varDelta \nu _k = \left[ \varDelta \nu _{k,0}; \varDelta \nu _{k,1}; 0; \ldots , 0 \right] + \varDelta \sigma _{k,1}, \qquad \varDelta \nu _{k,0} = \varDelta \nu _{k,1}. \end{aligned}$$

(23)

Let the following representation $\varDelta \sigma _{k,1} = \left[ \rho _{k,0}; \rho _{k,1}; \ldots ; \rho _{k,n_k-1} \right]$ hold. Note, that $y_k = {\mathbf d}_{k, n_k}$, because of from just this condition and from similar conditions for other dual slacks $y_i$, $i\in J^r_F(x)$, all these dual slacks, including $y_k$, are chosen. Hence, $\rho _{k,0} = 1$, $\rho _{k,1} = -1$. All other coefficient $\rho _{k,j}$, $2 \le j \le n_k-1$, are zeros. Thus, (23) can be rewritten as

$$\begin{aligned} \varDelta \nu _k = \left[ \varDelta \nu _{k,0} + 1; \varDelta \nu _{k,1} - 1; 0; \ldots ; 0 \right] . \end{aligned}$$

(24)

The matrix $A_k^{{\mathbf G}_k}$ is contained as $\widetilde{A}^{{\mathbf G}_k}_{k,1}$ in more general matrix $\mathcal{A}^{{\mathbf G}}_{B}$. Therefore, dropping zero components in (24) and substituting the reduced vector

$$\begin{aligned} \varDelta \nu _k = \left[ \varDelta \nu _{k,0} + 1; \varDelta \nu _{k,1} - 1\right] \end{aligned}$$

in general vector $\varDelta \nu _B$, we obtain the homogeneous system of linear equation

$$\begin{aligned} \mathcal{A}_{B}^{{\mathbf G}} \varDelta \nu _B = 0_m \end{aligned}$$

(25)

with the nonsingular matrix. The solution of the system (25) is $\varDelta \nu _B = 0_m$. Therefore, all components $\varDelta \nu _i$, with the exception of $\varDelta \nu _k$, are zeros. For $\varDelta \nu _k$ we have $\varDelta \nu _{k,0} = -1$ and $\varDelta \nu _{k,1} = 1$. This contradicts to equality: $\varDelta \nu _{k,0}= \varDelta \nu _{k,1}$.

   $\square$

From Proposition 6 we come to conclusion, that index k must belong only to the set $J^r_N(x)$.

Denote by $\mathcal{C}_{\mathcal{K}}(x)$ a cone of feasible directions with respect of $\mathcal{K}$ at the point $x\in \mathcal{K}$. The cone $\mathcal{C}_{\mathcal{K}}(x)$ is the direct product of cones of feasible directions $\mathcal{C}_{K^{n_i}}(x_i)$ at points $x_i \in K^{n_i}$, $i\in J^r$, that is

$$\begin{aligned} \mathcal{C}_{K}(x) = \mathcal{C}_{K^{n_1}}(x_1) \times \cdots \times \mathcal{C}_{K^{n_r}}(x_r). \end{aligned}$$

According to Lemma 3.2.1 from [11], the direction belongs to $\mathcal{C}_{K^{n_i}}(x_i)$ if and only if $h = h_1 + h_2$, where $h_1 \in {lin} \left( F_\mathrm{min}(x_i \vert K^{n_i})\right)$ and $h_2 \in K^{n_i}$. The vector h belongs to cone of feasible directions with respect to the set $\mathcal{F}_P$ at point $x\in \mathcal{F}_P$, if h is a feasible direction with respect to the cone $\mathcal{K}$ and $\mathcal{A}h = 0_m$.

The following result is valid.

Proposition 7

The direction $\varDelta x$, defined by (17), (18) and (19), is a feasible direction with respect to the set $\mathcal{F}_P$.

Proof

Observe that according to (19) the equality $\mathcal{A}\varDelta x = 0_m$ holds. Observe also that the vector ${\mathbf f}_{k,1}$ belongs to the cone $K^{n_k}$ (more exactly, to the boundary of $K^{n_k}$). Hence, $\varDelta x_i \in K^{n_k}$, if $i\in J^r_N(x)$ and $i=k$.

For $i\in J^r_I(x)$ the point $x_i$ is an interior point of the cone $K^{n_i}$. Therefore, the cone of feasible directions at this point with respect to $K^{n_i}$ coincides with the space . At last, the vector $\varDelta x_i$, when $i\in J^r_F(x)$, belongs to the linear hull of the minimal face $F_\mathrm{min}(x_i| K^{n_i})$, which is defined by the frame vector ${\mathbf d}_{i,1}$.

Thus, the assertion, that $\varDelta x$ belongs to the cone of feasible directions with respect to the set $\mathcal{F}_P$, follows from the representation of this cone.    $\square$

Proposition 8

Let $x\in \mathcal{F}_P$ be a regular extreme non-optimal point. Let also $k\in J^r_N(x)$ be such that $y_k\notin K^{n_k}$. Then,

$$\begin{aligned} \langle c, \varDelta x \rangle = \theta _{k,1} < 0, \end{aligned}$$

(26)

where $\theta _{k,1} < 0$ is taken from the decomposition (14).

Proof

We have due to (22)

$$\begin{aligned} \begin{array}{c} \langle c, \varDelta x \rangle = \sum \nolimits _{i\in J^r_{B}(x)} \langle c_i, \varDelta x_i \rangle + \langle c_k, \varDelta x_k \rangle \\ = \sum \nolimits _{i\in J^r_{B}(x)} \langle c_i^{{\mathbf G}_i}, \varDelta \nu _i \rangle + \langle c_k^{{\mathbf G}_k}, \varDelta \sigma _{k,1} \rangle = \langle c_{B}^{{\mathbf G}}, \varDelta \nu _B \rangle + \langle c_k^{{\mathbf G}_k}, \varDelta \sigma _{k,1} \rangle \\ = \langle c^{{\mathbf G}_k}_k, \varDelta \sigma _{k,1} \rangle - \langle \left( \mathcal{A}_{B}^{{\mathbf G}}\right) ^{-T} c_{B}^{{\mathbf G}}, A_k^{{\mathbf G}_k} \varDelta \sigma _{k,1} \rangle \\ = \ \langle c^{{\mathbf G}_k}_k - \left( A_k^{{\mathbf G}_k} \right) ^T u, \varDelta \sigma _{k,1} \rangle = \ \langle \sigma _k, \varDelta \sigma _{k,1} \rangle \\ = \langle \theta _{k,1} {\mathbf f}_{k,1} + \theta _{k,n_k} {\mathbf f}_{k,n_k}, {\mathbf f}_{k,1} \rangle = \theta _{k,1}\Vert {\mathbf f}_{k,1}\Vert ^2 = \theta _{k,1}. \end{array} \end{aligned}$$

Hence, the inequality (26) is correct.    $\square$

The step length $\alpha$ is chosen as large as possible under the condition that the updated point $\hat{x}$ belongs to the feasible set $\mathcal{F}_P$. Since $\mathcal{A}\varDelta x = 0_m$, the step length $\alpha$ is defined as minimal among maximal step lengths, satisfying to conditions: $\hat{x}_i(\alpha )\in K^{n_i}$ for all cones $K^{n_i}$, $i \in J^r_{B}(x)$.

Proposition 9

Let index $k\in J^r_N(x)$ be such that $\varDelta x_i \in K^{n_i}$ for all $i\in J^r_{B}(x)$. Then the set $\mathcal{F}_P$ is unbounded and $\langle c, \hat{x} (\alpha )\rangle \rightarrow - \infty$, when $\alpha \rightarrow +\infty$.

If the assertion of Proposition 9 is not realized, the step length $\alpha$ is finite and it is possible to make the move from the extreme point x to another feasible point $\hat{x}(\alpha ) \in \mathcal{F}_P$ with decreasing the value of goal function.

Proposition 10

Let x be a regular extreme point of $\mathcal{F}_P$, and let the step length $\alpha$ be finite. Then the updated point $\hat{x}(\alpha )$ is an extreme point of $\mathcal{F}_P$ too.

Proof

Since the step length $\alpha$ is finite, there are only two situations, when it is possible:

• (1) There is the index $s\in J^r_F(x)$ such that at updated point $\hat{x}$ this index s belongs to the set $J^r_N(\hat{x})$. In other words, the facet basic variable becomes a non-basic variable.

• (2) There is the index $s\in J^r_I(x)$ such that at the updated point $\hat{x}$ this index s belongs either to the set $J^r_F(\hat{x})$ or to $J^r_N(\hat{x})$. In other words, the interior basic variable becomes either a non-basic variable or a facet basic variable.

In principle, the cases are possible, when each of these situations or both situations happen simultaneously.

Denote $n_B (x) = r_F(x) + n_I(x)$. If x is an extreme point of $\mathcal{F}_P$, then $n_B (x) \le m$. Regardless of the way, how $\alpha$ is defined, we obtain that at the updated point $\hat{x}$ the following inequality $n_B(\hat{x}) \le n_B(x)$ holds. Here we take into account that the non-basis variable $x_k$ becomes the facet basic variable at the updated point. The inequality $n_B(\hat{x}) \le n_B(x)$ is necessary for $\hat{x}$ be an extreme point.

Let us show that Proposition 4 is fulfilled at the point $\hat{x}$. Since x is an extreme point, columns of the matrix $\mathcal{A}^{{\mathbf G}}_{B}$ are linear independent. Moreover, at regular extreme point x the number of these linear independent columns exactly equals to m. The following representation is valid for the right hand side vector

$$\begin{aligned} b = \sum _{i\in J^r_F(x)} \widetilde{A}^{{\mathbf G}_i}_{i,1}\nu _{i,1} + \sum _{i\in J^r_I(x)} A^{{\mathbf G}_i}_{i} \nu _{i}, \end{aligned}$$

(27)

and more, in (27) all $\nu _{i,1} > 0$, $i\in J^r_F(x)$, and all $\nu _i \in K^n_i$, $i\in J^r_I(x)$.

Denote

The set ${\text {pos}}_{K^{n_i}} A_i^{{\mathbf G}_i}$ is an image of the convex cone $K^{n_i}$ under the linear mapping. Thus, ${\text {pos}}_{K^{n_i}} A_i^{{\mathbf G}_i}$ is a convex cone in . Observe, that in (27) $\nu _i \in {\text {int}} K^{n_i}$, where ${\text {int}} K^{n_i}$ is an interior of the cone $K^{n_i}$. Hence, $z_i = A_i^{{\mathbf G}_i}\nu _i$ is an interior point of the convex cone ${\text {pos}}_{K^{n_i}} A_i^{{\mathbf G}_i}$.

Let $\mathcal{W}_i = {\text {cone}} \widetilde{A}^{{\mathbf G}_i}_{i,1}$, $i\in J^r_F(x)$, be a cone hull of the vector $\widetilde{A}^{{\mathbf G}_i}_{i,1}$. In other words, it is the ray generated by $\widetilde{A}^{{\mathbf G}_i}_{i,1}$. Let also $\mathcal{W}_i = {\text {pos}}_{K^{n_{i}}} A_{i}^{{\mathbf G}_{i}}$, $i\in J^r_I(x)$. All these sets are convex cones in , which don’t intersect between themselves. We take the sum of these cones

$$\begin{aligned} \mathcal{W}= \mathcal{W}_1 + \ldots + \mathcal{W}_{r_F} +\mathcal{W}_{r_F+1} + \ldots + \mathcal{W}_{r_F+r_I}. \end{aligned}$$

Since columns of the matrix $\mathcal{A}^{{\mathbf G}}_{B}$ are linear independent, the cone $\mathcal{W}$ has non-empty interior. The point belongs to the interior of $\mathcal{W}$.

In the case, where facet basic variable $x_s$, $s\in J^r_F(x)$ becomes nonbasic, the column $\widetilde{A}^{{\mathbf G}_i}_{s,1}$ is taken out from the decomposition (27), and the column $\widetilde{A}^{{\mathbf G}_k}_{k,1}$ is introduced. If this column $\widetilde{A}^{{\mathbf G}_k}_{k,1}$ together with the rest columns are linear dependent, it means that the vector b belongs to the boundary of the cone $\mathcal{W}$, which is impossible. The same conclusion is valid, when an interior basic variable becomes the facet basic variable.

Thus, the assertion of Proposition 4 is fulfilled at the updated point $\hat{x}$. Therefore, $\hat{x}$ is an extreme point of $\mathcal{F}_P$.    $\square$

By Propositions 8 and 10, we may construct the simplex-type iterative algorithm, in which all points are extreme points of the feasible set, and values of the goal function monotonically decreases from iteration to iteration.

4 Partial Case of SOCP Problem

Consider the partial case of problem (3), when it is known in advance, that the solution of (3) is an extreme point of $\mathcal{F}_P$ with all basic variables being facet basic variables. Then it is possible to take an extreme point $x^0\in \mathcal{F}_P$ with only facet basic variables as a starting point. The move from any extreme point to another one turns out to be such that only facet basic variables are at all these extreme points.

In what follows, we call the sequence of points $\{x^l\}$, generated by the algorithm, regular, if all these points $x^l$ are regular extreme points of $\mathcal{F}_P$. Moreover, denote by $\mathrm{ext}_F (\mathcal{F}_P)$ the subset of all extreme points from $\mathcal{F}_P$ with all basic variables being of facet type. We say that the problem (3) is non-degenerate with respect to $\mathrm{ext}_F (\mathcal{F}_P)$, if all points from this set are non-degenerate.

Proposition 11

Let $x^* \in \mathrm{ext}_F (\mathcal{F}_P)$ be regular unique solution of the problem (3). Let also the starting extreme point $x^0 \in \mathrm{ext}_F (\mathcal{F}_P)$ be such that the sequence $\{x^l\}$ is regular. If $\{x^l\}$ is finite, then the last point of this sequence coincides with $x^*$.

Theorem 2

Let Problem (3) be non-degenerate with respect to the set $\mathrm{ext}_F (\mathcal{F}_P)$. Let also all assumptions of Proposition 11 be fulfilled, except the assumption that $\{x^l\}$ is a finite sequence. Suppose additionally that the starting point $x^0$ is such that the set

$$\begin{aligned} \mathcal{F}_P(x^0) = \left\{ x\in \mathcal{F}_P: \ \langle c, \ x \rangle \le \langle c, \ x^0 \rangle \right\} \end{aligned}$$

is bounded. Then the sequence $\{x^l\}$ converges to $x^*$.

Proof

Since the sequence $\{x^l\}$ is bounded, there exist limit points of $\{x^l\}$. Let $\{x^{l_s}\}$ be a convergent subsequence of $\{x^l\}$, and let $x^{l_s} \rightarrow \bar{x}$. All points of $\{x^{l_s}\}$ are regular extreme points of $\mathcal{F}_P$. Moreover, $x^{l_s} \in \mathrm{ext}_F (\mathcal{F}_P)$ for $s\ge 1$. The point $\bar{x}$ is also an extreme point of $\mathcal{F}_P$, and more: $\bar{x} \in \mathrm{ext}_F (\mathcal{F}_P)$.

The number of all possible sets $J^r_F(x)$, consisting of m indices, is finite. Therefore, we may assume without loss of generality, that sets $J^r_F(x^{l_s})$ are the same for all s. Denote this set by $\bar{J}^r_F$. Because of continuity we have $J^r_F(\bar{x}) \subseteq \bar{J}^r_F$. Moreover, the matrices $\mathcal{A}_B^{{\mathbf G}}$ converge to a certain matrix $\bar{\mathcal{A}}_B^{{\mathbf G}}$, and vectors $c_B^{{\mathbf G}}$ converge to a certain vector $\bar{c}_B^{{\mathbf G}}$. As a matter of fact, $\bar{\mathcal{A}}_B^{{\mathbf G}}$ and $\bar{c}_B^{{\mathbf G}}$ are the matrix and the vector, defined at the extreme point $\bar{x}$. Since $\bar{x} \in \mathrm{ext}_F (\mathcal{F}_P)$, we have that $\bar{x}$ is a non-degenerate point. From here we derive that $\bar{x}$ is a regular extreme point. Hence, the matrix $\bar{\mathcal{A}}_B^{{\mathbf G}}$ is nonsingular.

Let $\bar{u}$ be a dual variable, satisfying the system of linear Eq. (13) with $\bar{\mathcal{A}}_B^{{\mathbf G}}$ and $\bar{c}_B^{{\mathbf G}}$. Let also $\bar{y}$ be the corresponding dual slack. Since $\bar{x}$ is not an optimal point, the coefficient $\bar{\theta }$ in the decomposition of $\bar{y}$ is such that $\bar{\theta }_{1,k} < 0$. Dual variables $u^{l_s}$, being solutions of system (13) at points $x^{l_s}$, converge to $\bar{u}$. Dual slacks $y^{l_s}$ converge to $\bar{y}$ too. We obtain by Proposition 8 that $\langle c, x^{l_s + 1} \rangle \le \langle c, x^{l_s} \rangle + \alpha ^{l_s}\theta ^{l_s}_{1,k} < \langle c, x^{l_s} \rangle$. As $\varDelta x^{l_s}$ are bounded for s sufficiently large, the step lengths $\alpha ^{l_s}$ don’t tend to zero. Thus, we obtain at some iteration that $\langle c, x^{l_s + 1} \rangle < \langle c, \bar{x} \rangle$. This contradicts to monotone decreasing of values of the objective function at each iteration and convergence of the sequence $\{x^{l_s}\}$ to $\bar{x}$. Hence, $\bar{x}$ may be only the optimal point.    $\square$

5 Conclusion

We presented a variant of the simplex method for SOCP problems. The main attention has been given to updating of regular extreme points. In principle, it is possible to develop an approach for updating irregular extreme points. However, this approach is more complicated compared with the regular case.