# Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method

Authors: Shafiu Jibrin
Journal: Journal of Mathematics
 (2015)

---

## Abstract

We study the problem of computing weighted analytic center for system of linear matrix inequality constraints. The problem can be solved using Standard Newton’s method. However, this approach requires that a starting point in the interior point of the feasible region be given or a Phase I problem be solved. We address the problem by using Infeasible Newton’s method applied to the KKT system of equations which can be started from any point. We implement the method using backtracking line search technique and also study the effect of large weights on the method. We use numerical experiments to compare Infeasible Newton’s method with Standard Newton’s method. The results show that Infeasible Newton’s method moves in the interior of the feasible regions often very quickly, starting from any point. We recommend it as a method for finding an interior point by setting each weight to be 1. It appears to work better than Standard Newton’s method in finding the weighted analytic center when none of weights is very large relative to the other weights. However, we find that Infeasible Newton’s method is more sensitive than Standard Newton’s method to large variation in the weights.


---

## Body

## 1. Introduction

We consider a system of linear matrix inequality constraints given as follows:(1)subject toAjx≔A0j+∑i=1nxiAij⪰0,j=1,2,…,q,where x∈Rn is a variable and each Ai(j) is an mj×mj symmetric matrix. Linear matrix inequality (LMI) constraints have been well studied especially in the field of semidefinite programming [1, 2]. LMI constraints have applications in a variety of fields including engineering, geometry, and statistics. We assume that feasibility determined by the constraints is bounded and has a nonempty interior. This means that the set diag⁡A11,…,A1q,…,diag⁡An1,…,Anq is linearly independent [3].In this paper, we are concerned with computing weighted analytic center for LMIs using Infeasible Newton’s method. A feasible starting point is not required to start the method. In the special case of linear constraints, weighted analytic center has been studied extensively in the past (e.g., [4]). A weighted analytic center for LMIs which extends the definition given in [4] was given in [5, 6]. The study weighted analytic center is of interest in its own right. Many algorithms for linear programming and semidefinite programming are based on weighted analytic centers [2, 3, 7, 8].Weighted analytic center for linear matrix inequalities can be found using Standard Newton’s method by minimizing the barrier function. This approach has the drawback that a starting in the interior of the feasible region must be given. Also, Newton’s method does not work well when some of the weights are relatively very large relative to the other weights. Infeasible Newton’s method for analytic center for single LMI constraint is given in [9]. We present Infeasible Newton’s method for finding weighted analytic center that can be started from any point. The method is applied to the Karush-Kuhn-Tucker (KKT) system of equations for the weighted analytic center problem. We implement the method using backtracking line search technique and also study the effect of large weights on the method. We use numerical experiments to compare Infeasible Newton’s method with Standard Newton’s method.We find that Infeasible Newton’s method moves very quickly into the interior of the feasible regions for most of our test problems. It seems to be a suitable method for finding an interior point for the system by setting each weight to be 1. It works better than Standard Newton’s method if none of the weights is relatively very large with respect to the other weights. We also find that Infeasible Newton’s method is more sensitive to large variations in the weights than Standard Newton’s method. In the case of very large variation in the weights, we recommend using Infeasible Newton’s method to get into the interior with each weight set to 1 and then switching to Standard Newton’s method for convergence to the weighted analytic center using the original weights and starting from the interior.


## 2. Weighted Analytic Center for Linear Matrix Inequalities

LetR denote the feasible region defined by inequalities (1). Given ω>0, define the barrier function ϕω(x):Rn→R by(2)ϕωx=∑j=1qωjlog⁡det⁡Ajx-1,ifx∈int⁡R,∞,otherwise.Theweighted analytic center for system (1) is defined by [5, 6](3)xacω=arg⁡min⁡ϕωx∣x∈Rn.This definition extends that given in [4] for linear constraints. When ω=[1,…,1], xac(ω) is called theanalytic center. Weighted analytic center has been used in interior point methods for linear programs and semidefinite programs [2, 3, 7, 8, 10]. The primal-dual central path in semidefinite programming converges to the analytic center of the optimal solution set [11].Standard Newton’s method has the choice for finding weighted analytic center. The gradient and Hessian of the barrier functionϕω(x) are given by [6] the following:fori,j=1,…,n(4)∇iϕωx=-∑j=1qωjAjx-1•Aij,Hijx=∑k=1qωkAkx-1AikT•Akx-1Ajk.Standard Newton’s Method for Computing Weighted Analytic CenterInput: An interior point x, tolerance TOL>0Setk=1Repeat
(1)
Compute the Newton’s directions=-Hx-1∇ϕωx(2)
Computed=sTH(x)s(3)
Do line search to get stepsizeh(4)
Updatex≔x+hs(5)
Updatek=k+1Untild≤TOL.Line search technique such as backtracking line search technique can be used in Newton’s method to find weighted analytic center [9].


## 3. Infeasible Newton’s Method for Computing Weighted Analytic Center

In this section, we describe Infeasible Newton’s method for finding weighted analytic center. The problem of computing the weighted analytic center in (3) is a more general form of the determinant maximization problem [3]. Its dual is given by the following:(5)maximize∑j=1qωjlog⁡det⁡1ωj+∑j=1qωjmj-∑j=1qA0j•Zjsubject to∑j=1qAij•Zj=0,i=1,…,n,Zj⪰0,j=1,…,q,where the bullet • is the matrix dot-product. Theorem 1 gives optimality conditions for computing the weighted analytic center xac(ω).Theorem 1 (see [3]).
Suppose both primal problem (3) and dual problem (5) are strictly feasible. The set of primal optimal solutions x and dual optimal solutions Z is the set of feasible solutions to the system(6)A0j+∑i=1nxiAij-Yj=0,j=1,…,q,∑j=1qAij•Zj=0,i=1,…,n,ZjYj=wjImj,j=1,…,q,Yj⪰0,j=1,…,q,Zj⪰0,j=1,…,q.The optimality conditions in Theorem1 can be written equivalently as(7)A01+∑i=1nxiAi1-Y1⋮A0q+∑i=1nxiAiq-Yq∑j=1qA1j•Zj⋮∑j=1qAnj•ZjZ1Y1-w1Im1⋮ZqYq-wqImq=0,(8)Zj⪰0,j=1,…,q,(9)Yj⪰0,j=1,…,q.Now, as in [3], let(10)zj=vec⁡Zj,yj=vec⁡Yj,Bj=vec⁡A1jT⋮vec⁡AnjT,Rpj=Yj-A0j-mat⁡BjTx,Rd=-∑j=1qA1j•Zj⋮-∑j=1qAnj•Zj,Rcj=ωjImj-ZjYj,rpj=vec⁡Rpj=yj-vec⁡A0j-BjjTx,rd=vec⁡Rd=-∑j=1qBjzj,rcj=vec⁡Rc=vec⁡ωjImj-Imj⊗Zjyj,rcj=vec⁡Rc=vec⁡ωjImj-Yj⊗Imjzj,Gx,y1,…,yq,z1,…,zq=-rp1⋮-rpq-rd-rc1⋮-rcq,where vec⁡ is the map that stacks the columns of a matrix on top of each other into a single vector and mat is the inverse map. Also, let(11)rp=rp1⋮rpq,rc=rc1⋮rcq,y=y1⋮yq,z=z1⋮zq,A=B1,…,Bq,E=diag⁡Y1⊗Im1,…,Yq⊗Imq,F=diag⁡Im1⊗Z1,…,Imq⊗Zq,I=diag⁡Im12,…,Imq2.Then, the system of (7) becomes G(x,y,z)=0. Newton’s directions for the system are found by solving the linear system:(12)AT-I000A0FEΔxΔyΔz=rprdrc.Using block elimination, we get(13)MΔx=AE-1Frp+rc-rd,Δz=E-1Frp-ATΔx+rc,Δy=F-1rc-EΔz,where(14)M=AE-1FAT.The matrix M is positive definite. The following is an iteration of Infeasible Newton’s method. In Step 2, the iterate ΔZ(j) is not symmetric. We symmetrize ΔZ(j) in Step 3.An Iteration of Infeasible Newton’s Method for Computing Weighted Analytic CenterStep 1.
Compute Newton’s direction(Δx,Δy,Δz) using (13).
This gives(Δx,Δy(1),…,Δy(q),Δz(1),…,Δz(q)).Step 2.
For eachj, determine(15)ΔYj=mat⁡Δyj,ΔZj=mat⁡Δzj.Step 3.
SymmetrizeΔZ(j).
ReplaceΔZ(j) by 1/2(ΔZj+(ΔZj)T)(j=1,…,q).Step 4.
Do line search to get stepsizeh.Step 5.
Update the iterates(16)x⟵x+hΔx,Yj⟵Yj+hΔYj,j=1,…,q,Zj⟵Zj+hΔZj,j=1,…,q.Any pointx∈Rn can be picked as a starting point. Then, for j=1,…,q choose(17)Yj=Ajx,ifAjx≻0,Imj,otherwise,Zj=ωjYj-1.The above iteration is repeated until r(x,y,z)<TOL, where r=(rp,rd,rc) is the residual and TOL is a given tolerance. One can use backtracking line search [9] or other techniques to get the stepsize h.


## 4. Numerical Experiments

In this section, we give numerical experiments to compare Infeasible Newton’s method with Standard Newton’s method. We also investigate the effects of large weights on the two methods.Table1 describes the 35 random test problems used for our numerical experiments. The second column of Table 1 gives the dimension n of the ambient space and the third column is the number q of constraints. The dimensions mj of the matrices are given in the fourth column. For each random problem, n, q, and mj are given and the LMI A0(j)+∑i=1n‍xiAi(j)⪰0 was generated randomly as follows: A0(j) is an mj×mj diagonal matrix with each diagonal entry chosen from U(0,1). Each Ai(j) (1≤i≤n) is a random mj×mj symmetric and sparse matrix with approximately 0.8∗mj2 nonzero entries generated using the MATLAB command sprandsym⁡(mj,0.8). Each problem has a nonempty interior.Table 1
Test problems.
LMI test problem
n
q
m
1
2
2
[2,  1]
2
3
4
[3,  4,  1,  2]
3
2
2
[2,  2]
4
5
3
[4,  1,  3]
5
4
3
[5,  4,  3]
6
4
5
[4,  3,  1,  1,  4]
7
3
3
[4,  2,  3]
8
3
4
[4,  2,  2,  5]
9
5
3
[4,  1,  1]
10
3
5
[5,  3,  5,  1,  4]
11
2
7
[2,  5,  3,  5,  2,  5,  1]
12
5
6
[5,  1,  3,  4,  1,  4]
13
14
5
[5,  1,  3,  4,  2]
14
20
5
[5,  2,  5,  1,  5]
15
3
8
[5,  4,  1,  5,  3,  5,  1,  3]
16
9
7
[1,  4,  2,  4,  4,  2,  2]
17
6
5
[4,  4,  2,  1,  4]
18
10
2
[3,  5]
19
15
9
[2,  5,  3,  1,  2,  3,  3,  1,  2]
20
8
2
[4,  5]
21
19
7
[5,  2,  2,  2,  5,  5,  5]
22
9
10
[3,  4,  1,  1,  3,  5,  5,  4,  5,  2]
23
3
4
[2,  3,  2,  5]
24
8
2
[5,  1]
25
2
8
[5,  2,  1,  1,  1,  5,  3,  3]
26
13
8
[4,  1,  4,  2,  3,  1,  2,  1]
27
24
10
[5,  4,  5,  1,  4,  2,  3,  5,  5,  2]
28
5
6
[4,  1,  4,  2,  1,  3]
29
16
3
[2,  2,  3]
30
2
2
[4,  5]
31
2
4
[1,  5,  5,  5]
32
4
4
[5,  1,  4,  5]
33
4
4
[1,  2,  3,  5]
34
17
9
[1,  5,  2,  1,  2,  5,  1,  4,  3]
35
20
5
[5,  2,  5,  1,  5]Our codes were written in MATLAB and ran on Dell OPTIPLEX 880 computer. Both Infeasible Newton’s method and Standard Newton’s method were implemented using a tolerance ofTOL=10-4 and up to a maximum of 500 iterations. The starting point is random such that each of its components is chosen from a normal distribution with mean 0 and variance 106. We use the backtracking line search technique in the two methods. Table 2 compares Infeasible Newton’s method with Standard Newton’s method for different sets of weights. In each of Problems 1–15, one weight was set at 1012, which is a very high value relative to the others. For Problems 16–35, none of the weights was relatively very large. In Table 2, the third and the fourth columns give the number of iterations and time required to find the first point in the interior of the feasible region (resp.) by Infeasible Newton’s method. The fourth and the fifth columns give the number of iterations and time required to find the weighted analytic center (resp.) starting from the first interior point found. The sixth and the seventh columns in Table 2 give the number of iterations and time required to find the weighted analytic center (resp.) by Standard Newton’s method. Standard Newton’s method is started from the same interior point as in Infeasible Newton’s method. Infeasible Newton’s method and Standard Newton’s method are compared in Table 3 with weights ω=[1,1,…,1].Table 2
Infeasible Newton’s versus Standard Newton’s methods using different weightsω.
Problem
Weightsω
Inf. Newton1st feas. point iter.
Inf. Newton1st feas. pointtime (sec)
Inf. Newtoniter.
Inf. Newtontime (sec)
St. Newtoniter.
St. Newton time (sec)
1
[
1
0
12, 10]
2
0.0185
4
0.0096
2
0.0056
2
[
1
0
12, 100, 100, 1]
3
17.2562
∗
∗
3
0.0161
3
[
1
0
12, 1000]
51
0.3771
46
0.1690
41
0.1042
4
[
1
0
12, 10, 1]
20
10.8898
∗
∗
9
0.0687
5
[
1
0
12, 1, 10]
2
8.8548
∗
∗
4
0.0215
6
[1,  1012, 1, 10, 100]
∗
∗
∗
∗
∗
∗
7
[100, 10,  1012]
129
9.5582
∗
∗
33
0.1810
8
[1, 1000,  1012, 10]
∗
∗
∗
∗
∗
∗
9
[
1
0
12, 1000, 1000]
1
8.5943
∗
∗
4
0.0278
10
[
1
0
12, 1000, 100, 1000, 100]
6
25.3801
∗
∗
2
0.0158
11
[
1
0
12, 10, 100, 1000, 1000, 10, 100]
∗
∗
∗
∗
∗
∗
12
[
1
0
12, 1, 100, 10, 1, 10]
3
17.5497
∗
∗
5
0.0701
13
[1000,  1012, 1000, 100, 100]
∗
∗
∗
∗
∗
∗
14
[1, 1000,  1012, 1000, 1]
∗
∗
∗
∗
∗
∗
15
[1, 1, 1, 100,  1012, 100, 100, 10]
∗
∗
∗
∗
∗
∗
16
[10, 1, 10, 1000, 1000, 10, 1]
24
0.2885
3
0.0234
5
0.2108
17
[100, 100, 10, 1, 1000]
3
0.0508
4
0.0252
3
0.0534
18
[1, 1000]
2
0.0286
6
0.0182
4
0.0579
19
[100, 10, 1000, 1, 1000, 100, 100, 1000, 10]
10
0.2117
7
0.0749
8
0.9943
20
[1000, 1000]
1
0.0180
4
0.0125
7
0.0664
21
[1, 1, 10, 1, 100, 10, 1]
21
0.3301
3
0.0342
3
0.4761
22
[1, 1000, 100, 10, 1000, 1, 100, 100, 100, 1]
7
0.2006
3
0.0491
3
0.2011
23
[100, 10, 1, 1]
4
0.0609
5
0.0231
6
0.0297
24
[1000, 1]
12
0.0564
2
0.0052
3
0.0348
25
[1, 1, 10, 1, 1000, 1, 1, 10]
8
0.1360
3
0.0280
3
0.0224
26
[100, 1, 100, 1, 1, 1, 1, 1]
20
0.2815
2
0.0208
3
0.3256
27
[1, 1, 1, 10, 1, 10, 1, 100, 1, 10]
8
0.3212
4
0.0945
6
2.1028
28
[10, 10, 100, 1, 1, 1]
7
0.0986
3
0.0246
4
0.0718
29
[1, 1, 10]
1
0.0092
∗
∗
∗
∗
30
[10, 1]
2
0.0268
4
0.0149
3
0.0121
31
[1, 10, 1, 1]
1
0.0444
4
0.0326
4
0.0270
32
[100, 1, 10, 1]
8
0.0994
4
0.0278
4
0.0444
33
[100, 100, 1, 10]
6
0.0612
3
0.0168
3
0.0318
34
[1, 100, 1, 1, 1, 10, 100, 100, 10]
7
0.1870
3
0.0426
5
0.9478
35
[1, 10, 100, 1, 1]
31
0.3678
2
0.0175
2
0.3845Table 3
Infeasible Newton’s versus Standard Newton’s methods using weightsω=[1,1,…,1].
Problem
Inf. Newton 1st feas. point  iter.
Inf. Newton1st feas. point  time (sec)
Inf. Newton iter.
Inf. Newtontime (sec)
St. Newtoniter.
St. Newton time (sec)
1
1
0.0115
3
0.0068
3
0.0059
2
2
0.0327
4
0.0188
3
0.0177
3
1
0.0318
9
0.0271
10
0.0180
4
2
0.0230
3
0.0114
3
0.0249
5
1
0.0250
4
0.0180
4
0.0239
6
1
0.0348
4
0.0248
4
0.0355
7
1
0.0271
5
0.0206
7
0.0247
8
1
0.0284
4
0.0202
3
0.0170
9
1
0.0215
4
0.0145
3
0.0224
10
1
0.0641
6
0.0532
8
0.0520
11
1
0.0451
3
0.0311
3
0.0207
12
2
0.0460
3
0.0237
3
0.0461
13
2
0.0555
4
0.0268
6
0.3949
14
13
0.1481
4
0.0302
6
0.8056
15
1
0.0805
5
0.0629
3
0.0330
16
2
0.0599
4
0.0339
7
0.2742
17
2
0.0370
3
0.0185
3
0.0508
18
2
0.0184
3
0.0088
4
0.0569
19
3
0.0933
4
0.0390
3
0.4423
20
1
0.0196
4
0.0134
7
0.0665
21
12
0.2080
4
0.0463
5
0.7110
22
2
0.1079
4
0.0659
3
0.2002
23
1
0.0276
4
0.0196
3
0.0164
24
4
0.0281
4
0.0123
6
0.0616
25
2
0.0553
3
0.0286
3
0.0217
26
13
0.1980
3
0.0303
3
0.3295
27
3
0.1791
2
0.0902
2
1.6525
28
3
0.0612
3
0.0262
3
0.0567
29
1
0.0102
∗
∗
∗
∗
30
2
0.0275
4
0.0157
3
0.0140
31
1
0.0359
3
0.0231
3
0.0210
32
2
0.0431
3
0.0212
2
0.0264
33
4
0.0573
4
0.0240
6
0.0543
34
2
0.0992
4
0.0550
4
0.7863
35
13
0.1795
4
0.0367
6
0.8997Figure1 shows the iterates taken by Infeasible Newton’s method to converge in Problem 3 with ω=[1012,1000]. It is clear from the figure that Infeasible Newton’s method slowed down considerably before converging to the weighted analytic center. On the other hand, as seen in Figure 2, the method converged quickly with ω=[1,1]. Figure 3 shows how the norm of the gradient varies with the number of iterations for the two values of the weights. In Table 2, the entry ∗ means that Infeasible Newton’s method has failed to converge after the maximum number of 500 iterations in Problems 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, and 29. However, it managed to find an interior point of (1) in Problems 2, 4, 5, 7, 9, 10, 12, and 29. We see from the table that both methods might not work well when some of the weights are relatively larger than the other weights. The results also show that Standard Newton’s method performs better than Infeasible Newton’s method in this case. In Infeasible Newton’s method, the Jacobian of the residual function becomes increasingly ill conditioned near the boundary of systems (8) and (9) due to matrices E and F as the variation among the weights increases. Observe that Infeasible Newton’s method failed to converge in 8 problems, even though it found a point in the interior of the feasible region (1). Standard Newton’s method converged (within the 500 iterations’ limit) for each of the 8 problems except in Problem 29. Standard Newton’s method converged after 536 iterations in Problem 29.Figure 1
Iterates (51+46=97) taken by Infeasible Newton’s method to converge in Problem 3 with ω=[1012,1000]. The graph on the right is the graph on the left zoomed and showing the last iterate ∗ in the interior, but near the boundary of the feasible region.Figure 2
Iterates (1+9=10) taken by Infeasible Newton’s method to converge in Problem 3 with ω=[1,1]. The graph on the right is the graph on the left zoomed and showing the last iterate ∗ well inside the interior of the feasible region.Figure 3
The graph on the left gives the number of iterations versus norm of the residual in Problem 3 withω=[1012,1000] using Infeasible Newton’s method. The graph on the right gives the number of iterations versus norm of the residual of the method with ω=[1,1].In Table3, the entry ∗ in Problem 29 indicates that Infeasible Newton’s method has failed to converge to the analytic center after the maximum number of 500 iterations. However, it managed to find an interior point of (1) after 1 iteration. Problem 29 shows both Infeasible Newton’s method and Standard Newton’s method may fail to converge (within 500 iterations) even if the weights are all equal and an interior point is found. We see from Table 3 that Infeasible Newton’s method took a fewer number of iterations in 12 out of 35 problems while Standard Newton’s method took a fewer number of iterations in 9 out of 35 problems. Infeasible Newton’s method took less time in 23 out of 35 problems and Standard Newton’s method took less time in 11 out of 35 problems. It is interesting to note from the table that Infeasible Newton’s method found an interior point of (1) within 1–3 iterations on most of the test problems.The results from Tables2 and 3 suggest that when none of the weights is relatively very large, Infeasible Newton’s method is a better method than Standard Newton’s method to find the weighted analytic center. When one weight is relatively very large, one could use Infeasible Newton’s method with ω=[1,1,…,1] to find an interior point and then switch to Standard Newton’s method using the original weights and starting from the interior point found.


## 5. Conclusion

We presented Infeasible Newton’s method for computing weighted analytic center for system of linear matrix inequalities and compared it with Standard Newton’s method.We found that Infeasible Newton’s method finds a point in the interior point fairly quickly, starting from any point, especially when none of the weights is relatively very large. When none of the weights is relatively very large, Infeasible Newton’s method seems to work better than Standard Newton’s method to find the weighted analytic center. However, Infeasible Newton’s method does not work well when some of the weights are very large relative to others, but it still often finds a point in the interior, starting from any point. We find that Infeasible Newton’s method is suitable for finding an interior point for the system by setting each weight to be 1. We recommend that when some weights are relatively very large, one should use Infeasible Newton’s method to find a point in the interior withω=[1,1,…,1] to find an interior point and then switch to Standard Newton’s method using the original weights and starting from the interior point found.To improve the efficiency of Infeasible Newton’s method for finding weighted analytic center, it would be useful to exploit the block-diagonal structure of matricesA, E, and F in future implementation. We would like to investigate how the method could handle weights where some are relatively much larger than the other weights. Furthermore, it would be of interest to study the application of Infeasible Newton’s method for weighted analytic center to the SDP-CUT algorithm for semidefinite programming, presented in [8]. Implementing Infeasible Newton’s method for weighted analytic center using different search directions is currently under investigation. The problem of weighted analytic center is a determinant maximization problem and can be solved with the algorithms for those problems. It would be of interest to compare the performance of those algorithms with the method presented in this paper.



---

*Source: 456392-2015-10-27.xml*