The dual simplex method for solving linear semidefinite programming problem is considered. For finding the starting point in this method, which must be an extreme point of the feasible set, two approaches are proposed. The first approach is based on application of reduced gradient technique. The second one is borrowed from the dual affine scaling method for semidefinite optimization.
To date the most popular numerical methods for solving linear semidefinite programming problems are interior point techniques. Nevertheless there are some methods which are generalization of primal simplex method for linear programming [Lasserre, 1996], [Pataki, 1996], [Kosolap, 2009], [Zhadan, 2015]. In [Zhadan, 2016a] the dual simplex method had been proposed. The starting point at this dual method must be an extreme point of the feasible set, and all subsequent points are extreme points too. The aim of this paper is to describe two approaches for finding such extreme point in the case where only the feasible point is known. First of all we formulate the primal and dual linear semidefinite programs. In Section 1, we briefly describe the main iteration of dual simplex method. Two approaches for finding starting extreme points are considered in Sections 2 and 3. The first approach is generalization of the procedure, which is well known in linear programming and can be treated as reduced gradient technique. The second approach is based on movement in faces of the feasible set with step-by-step decreasing dimension of these faces. The similar way had been used in dual affine scaling method with steepest descent [Zhadan, 2016b].
Let Sn denote the space of real symmetric matrices of order n, and let Sn+ denote the cone of positive semidefinite matrices from Sn. The following inequality M ≽ 0 means also that M ∈ Sn+. The dimension of Sn is equal to so-called n-th triangular number n△ = n(n + 1)=2. The zero n-dimensional vector and the zero m × n matrix are denoted by 0n and 0nm, respectively.
Linear semidefinite programming refers to the optimization problem that can be expressed in the form Ai • X = bi; min C • X; 1 ≤ i ≤ m;
X ≽ 0; (1) where b = [b1; : : : ; bm]T , V ∈ Sn. It is assumed that matrices Ai, 1 ≤ i ≤ m, are linear independent, and both problems (1) and (2) have solutions. We denote by FD the feasible set at problem (2) and by FD;u the set The set FD;u is a projection of FD at the space of the variable u.
The optimality conditions for problems (1) and (2) are as follows
X • V = 0; where angle brackets indicate the Euclidean inner product in finite-dimensional vector space, and Asvec denotes the m × n△ matrix with svecAi as its rows, 1 ≤ i ≤ m. Matrices X and V must be positively semidefinite. m } ∑ uiAi ≽ 0 : i=1 AsvecB svecBXH = b:
H
(2) (3) (4) (5) The dual simplex method can be treated as a special way of solving system (4). Assume that the starting point u0, which is an extreme point of the set FD;u, is given. Assume also that after some iterations we obtain the point u = uk, which is an extreme point of FD;u too. We define the dual slack V = V (u), where V (u) = C −∑im=1 uiAi. Also, we make the following decomposition
V = HD( )HT ; where H is an orthogonal matrix, with the vector at its diagonal.
Let a rank of the matrix V be equal s < n. The point u is an extreme point of FD;u if and only if s△ ≤ n△ −m. We call the extreme point u regular, if s△ = n△ − m. Otherwise, we call it irregular. In what follows, we will use the matrices AH = HT AiH instead of Ai, 1 ≤ i ≤ m, and we will use the matrix CH instead of C. We denote also by AsHvec thie m × n△ matrix with rows svecAiH , 1 ≤ i ≤ m.
Suppose that = [ B; N ], where B = 0n−s and N > 0s. Here and in what follows we use punctuation mark [ ; ] in concatenation of vectors for adjoining them in a column. According to decomposition of the vector the matrix AsHvec can be decomposed into two submatrices: AsHvec = [AsHvecB ; AsHvecN ], where the second matrix AsvecN has the dimension m × (n△ − s△). We partition also the vector svecXH , where XH = HT XH, on two H
= [ 1; : : : ; n]T is a vector of eigenvalues, and D( ) is a diagonal matrix parts: svecXH = [svecBXH ; svecN XH ]T with svecBXH ∈ Rn△−s△ . The same partition will be used for other n△-dimensional vectors.
If we put svecN XH = 0s△ , then the second equality from (4) is reduced to
In the case, where the point u is regular and nondegenerate
AsvecB 0s△ bT uk+1 = bT uk − k ik > bT uk: VkH+1 = VkH + k∆VkH ;
m ∆VkH = ∑ ∆uikAiH : i=1 (6) (7) (8) (9) The step-size k is chosen as large as possible under condition that the matrix VkH+1 is positive semidefinite. The rank of matrix VkH+1 does not exceed the rank of VkH . Therefore, the point uk+1 is an extreme point of FD;u too.
In the case where uk is an irregular extreme point of FD;u, the system (5) is underdetermined, and we take svecBXkH = ( H
AsvecB )T [ H ( H
AsvecB AsvecB )T ]−1 b as its solution. On the contrary, system (7) is overdetermined. In order to overcome this difficulty we pass from the direction ∆uk in Rm to the direction ∆Vk in the space Sn, for which the following expression is used ∆Vk = [qik HN ] [ 1 w wT ] [ qiTk ] ∆Z HNT : Here HN is a submatrix of the matrix H, composed from the last s columns of H, and w = W y, where columns wj of the matrix W are such that qiTk HN wj = 0. Using relation between ∆uk and ∆Vk from (9), it is possible to find ∆uk, for which formula (8) is preserved.
Theorem 1 Let solutions X∗ and V∗ = V (u∗) of problems (1) and (2) be strictly complementary, i.e. for eigenvalues ∗i and ∗i of X∗ and V∗ respectively the following inequalities ∗i + ∗i > 0, 1 ≤ i ≤ n, hold. Then the sequence {uk}, generated by method (6), converges to u∗. 2
Initial Stage of the Method. The First Approach Consider the problem of finding a starting extreme point in the dual simplex method. In order to obtain such point we apply generalization of the approach using in linear programming. First of all we examine the case, where the feasible point u ∈ FD;u can be easily obtained.
Assume that among all equality-type constraints in problem (1) there is the equality Ai1 • X = bi1 with the positive definite matrix Ai1 . Then the following point u0 = [0; : : : ; 0; ui01 ; 0; : : : ; 0]
T belongs to the feasible set FD;u and can be taken as starting point. Indeed, if ui01 is negative and sufficiently large by absolute value, then the following inequality
C − is fulfilled, i.e. the point u0 is feasible. Our aim now is to pass from u0 to another extreme point of FD;u, using the reduced gradient technique.
Let now u0 be a feasible point from FD;u. We take the corresponding dual slack V0 = V (u0) = C − ∑im=1 Aiui0 and decompose it
V0 = H0D( 0)H0T ; where H0 is an orthogonal matrix, and 0 is a vector of eigenvalues.
Let also V0 be the matrix of rank s, and the following representation 0 = [ 0B; 0N ] be valid for the vector of eigenvalues, in which 0B N > 0s. As in the previous section, we pass from V0 to the matrix V0H0 = H0T V0H0. The matrix=V00Hn0−iss, a 0representation of V0 at the basis defined by columns of the orthogonal matrix H0. We have
V0H0 = [ 0 0
0 D( 0N ) where svecBV0H0 = 0l, svecN V0H0 = svecD( 0N ).
Suppose that u0 is not an extreme point of the set FD;u, i.e. the rank s does not satisfy to the inequality: s△ ≤ n△ − m. Then l < m. In this case the system of linear equations where the matrix AsHv0ecB consists of the first l columns of AsHv0ec, is undetermined. The point u0 is satisfied to this system.
Let a rank of system (10) be equal l. We partition the vector u0 onto two subvectors: u0 = [u0P ; u0Z ], where u0P is a l-dimensional vector, and u0Z is a (m − l)-dimensional vector. According to partition of u0 the matrix AsHv0ecB can be also to decomposed into two submatrices (AsHv0ecB )T u = svecBCH0 ;
H0 AsvecB = [
H0;P ] AsvecB AsHv0e;cZB : We rewrite this function as f (uZ ) = ⟨¯bZ ; uZ ⟩ + c¯; Solving this system with respect to uP , we obtain ( H0;P )T uP = svecBCH0 − AsvecB
( H0;Z )T uZ :
AsvecB uP = uP (uZ ) = [(AsHv0e;cPB )T ]−1 [svecBCH0 − (AsHv0e;cZB )T uZ ] :
We assume that the first quadratic matrix AsHv0e;cPB of order l is nonsingular. Then system (10) can be rewritten In particular, for u = u0 we derive that u0P = uP (u0Z ).
Furthermore, splitting the vector b = [bP ; bZ ] and substituting the partition of the vector u onto two subvectors at the goal function of problem (2), we come to conclusion, that values of this function depends on only the second variable uZ , namely:
⟨b; u⟩ = ⟨bP ; uP ⟩ + ⟨bZ ; uZ ⟩ = ⟨bP ; uP (uZ )⟩ + ⟨bZ ; uZ ⟩ = f (uZ ): where The function (12) is linear by uZ .
Let us pass to the updated point ¯bZ = bZ
H0;Z ( − AsvecB
H0;P )−1 bP ; AsvecB
c¯ = [(AsHv0e;cPB )T ]−1 svecBCH0 : uZ = uZ ( ) = u0Z + ¯bZ : Here > 0. Then, taking u( ) = [uP ( ); uZ ( )], where uP ( ) = uP (uZ ( )), and using (11), we come to conclusion that u( ) can be written in the form u( ) = u0 + ∆u; ∆u =
− [(AsHv0e;cPB )T ]−1 (AsHv0e;cZB )T ] ¯bZ : V H0 (u( )) = [ 0 0
0 D( 0N ) −
Im−l ¯ ΩNN Therefore the dual slack V H0 (u( )) changes by the following manner Here Ω¯ NN = ∑m i
i=1 AiH; N0 ∆ui, and AiH; N0 is the lower right block of AH0 of order s.
The matrix D( 0) − Ω¯ NN is positive definite, if = 0. It remains positive definite, when is positive and small enough. The maximal possible step length ∗ is determined by the case, when among all eigenvalues of D( 0)− Ω¯NN the null eigenvalue appears at the first time. Then the rank of the matrix V H0 (u( ∗)) becomes less with respect to the rank of V H0 . At the same time the value of the goal function increases: ⟨b; u( ∗)⟩ > ⟨b; u0⟩. If u( ∗) is not an extreme point, then we must proceed calculations. Theoretically there exists possibility that the matrix D( 0) − Ω¯ NN stays positive definite at any > 0. If ¯bZ ̸= 0, it means that problem (2) has not solution.
In the case, where not a matrix Ai is positive definite, but it is known by some reasons, that the solution X∗ of problem (1) is restricted, for example trX∗ < bm+1 for some sufficiently large bm+1 > 0, then additional inequality type constraint can be introduced in problem (1) (13) (14) Now we can take u¯0 = [u0; u0m+1] as the starting point. The number u0m+1 > 0 must be sufficiently large in order that the matrix inequality C + um+1In ≽ 0 holds.
Further calculations for finding a feasible extreme point are the same as in the previous case. Moreover, the inequality um+1 ≥ 0 must be taken into account, when we choose the step length . When we obtain, that um+1 = 0, then the additional inequality in (14) is deleted, and we pass to solve the initial dual problem (2). As a starting point we take the first component from two-component point [u; um+1], in which um+1 = 0. 3
Initial Stage of the Method. The Second Approach Consider the other approach for finding a starting extreme point. Suppose that we have the feasible point u, which is not an extreme point of FD;u. If the corresponding matrix V = V (u) has the rank s < n, then u is a boundary point. Thus, it belongs to some face of FD;u with non-zero dimension. Suppose additionally, that the decomposition V = HD( )HT is valid, where H is an orthogonal matrix, and = [ B; N ] is the vector of eigenvalues with B = 0n−s, N > 0s. The matrix H can also be decomposed into two submatrices H = [HB; HN ].
According to this decomposition of H, we partition the space Sn into two linear subspaces SnB and SnN , where SnB consists of matrices M ∈ Sn with the zero lower right block of order s. On the contrary, the subspace SnN tcwonossisutbssopfamceastarirceemsMutu∈alSlynoirnthwohgiocnhaol,nalyndthaenylowmeartrriixghMtb∈loSckn ocfaonrdbeerrsepcraensecnotnedtaains nthoenzseurmo eolfemtweontms.atTrihceesse, one of which is in SnB and other — in SN . For example, V = VB + VN , where
n VB = [ VBB
VNB Moreover, if we require XBH ≽ 0 and XNH ≽ 0 and take into account, that VNH ≽ 0, then equality (15) splits into two equalities
XBH • VBH = 0;
XNH • VNH = 0: Since VBH is zero matrix the first equality from (17) holds true for any matrix XBH .
Denote by X ◦ V the symmetrized product of two symmetric matrices X and V , i.e. X ◦ V = (XV + V X) =2. Under XNH ≽ 0 and VNH ≽ 0 the equality XNH • VNH = 0 takes place iff XNH ◦ VNH = 0nn. Therefore, the second equality from optimality conditions (17) can be replaced by the latter matrix equality. We rewrite it in vector form as
(V˜NH )⊗svecX = 0n△ :
Here (V˜NH )⊗ = L˜n(VNH )⊗D˜n, and (VNH )⊗ = (In ⊗ VNH + VNH ⊗ In) =2 is the Kronecker sum of matrix VNH . The
matrix L˜n is the elimination matrix, which performs the transformation L˜nvecM = svecM for any matrix
M ∈ Sn
We denote by Θ˜ N the lower right submatrix of order s△ of the matrix (V˜NH )⊗. The matrix Θ˜ N is diagonal with nonzero diagonal entries. In addition, we partition vectors svecXBH and svecXNH onto two parts, namely: svecXBH = [svecBXBH ; svecN XBH ]; svecXNH = [svecBXNH ; svecN XNH ]; where svecN XBH ∈ R △ and svecN XNH ∈ Rs△ . This partition we will use for other n△-dimensial vectors. Then s equality (18) is reduced to ˜ ΘN svecN XNH = 0s△ : We denote also by AsvecB the m × (n△ − s△) matrix with rows svecBAiH , 1 ≤ i ≤ m. Similarly, let AsvecN
H H denote the m × s△ matrix formed by the vectors svecN AiH . With the help of these matrices the equality (16) can be written as
AsvecB svecBXBH + AsvecN svecN XNH = b:
H H Multiplying equality (20) by matrices (AsHvecB )T and (AsHvecN )T respectively and summing them with equality (19), we obtain the system of linear equations with respect svecBXBH and svecN XNH , (15) (16) (17) (18) (19) (20) (21) where the matrix Φ has the form Φ [svecBXBH ; svecN XNH ] = [(AsHvecB )T b; (AsHvecN )T b]; Φ = [ (AsHvecB )T AsHvecB
T H (AsHvecN ) AsvecB
(AsHvecB )T AsHvecN (AsHvecN )T AsHvecN + Θ˜ N ] :
H
We say that the point u ∈ FD;u is strongly nondegenerate, if columns of the matrix AsvecB are linear independent. In [Zhadan, 2016b] the following result had been proved.
Proposition 1 Let the point u ∈ FD;u be strongly nondegenerate. Then the matrix Φ is nonsingular. GN = AsHvecN Θ˜ −N1(AsHvecN )T ;
WN = (Im + GN )−1 ; GB = (AsHvecB )T WN AsHvecB ;
WB = AsHvecB GB−1(AsHvecB )T : Then solving the system (21), we obtain svecBXBH = GB−1 (AsHvecB )T WN b; svecN XNH = Θ˜ −N1(AsvecN )T [WN − WN WBWN ] b:
H After substitution these expressions at the left hand side of (20) we get that (20) can be written as [WN − WN WBWN ] b = 0m: (22) This is a system of m nonlinear equations with respect of m unknowns, which are components of the vector u.
Let ∆u = [WN − WN WBWN ] b. It can be shown that ⟨b; ∆u⟩ ≥ 0. The direction ∆u in the u-space determines the direction ∆V H = − ∑im=1(∆u)iAiH in the V -space. Moreover, considering the point u¯( ) = u + ∆u, which depends on > 0, we have the corresponding point V¯ H ( ) = V + ∆V H . Since (AsHvecB )T ∆u = 0n△−s△ , the following formula
V¯ H ( ) = holds, where ΩN is a symmetric matrix having the vector representation svec ΩN = (AsHvecN )T ∆u:
The matrix V¯ H ( ) remains positive semidefinite if is sufficiently small. The maximal possible step ∗ can be found from the condition that some eigenvalue of the matrix D( N ) − ∗ΩN becomes zero. In this case the point u¯( ∗) ∈ FD;u is such that the rank of the matrix V (u¯( ∗)) is less than the rank of V (u). If the point u¯( ∗) is not extreme, it is necessary to repeat the procedure.
Acknowledgements This work was supported by the Russian Foundation for Basic Research (project no. 15-01-08259) and by the Scientific Schools Program (project no. NSh-8860.2016.1)