# An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers

Authors: John Machacek; Shafiu Jibrin
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We investigate solving semidefinite programs (SDPs) with an interior point method called SDP-CUT, which utilizes weighted analytic centers and cutting plane constraints. SDP-CUT iteratively refines
the feasible region to achieve the optimal solution. The algorithm uses Newton’s method to compute the weighted analytic center. We investigate different stepsize determining techniques. We found that using
Newton's method with exact line search is generally the best implementation of the algorithm. We have also compared our algorithm to the SDPT3 method and found that SDP-CUT initially gets into the neighborhood of the optimal solution in less iterations on all our test problems. SDP-CUT also took less iterations to reach optimality on many of the problems. However, SDPT3 required less iterations on most
of the test problems and less time on all the problems. Some theoretical properties of the convergence of SDP-CUT are also discussed.


---

## Body

## 1. Introduction

We consider the semidefinite programming problem (SDP) as in [1]:
(1.1)minimizecTx,(1.2)subjecttoA(j)(x)≽0forj=1,…,q,
where A(j)(x):=A0(j)+∑i=1n‍xiAi(j). Also, x∈ℝn, c∈ℝn, and each Ai(j) is an mj×mj symmetric matrix. The constraint A(j)(x)≽0 is known as a linear matrix inequality or LMI. For a given matrix A, A≽0 denotes that A is positive semidefinite. The notation ≻0 is used when a matrix is positive definite. Semidefinite Programs (SDPs) are convex optimization problems [2], and they generalize many other convex optimization problems including linear programming. SDPs have applications in engineering and combinatorial optimization and other fields (see [2, 3]).The dual of problem (1.1) is the optimization problem [1]:
(1.3)maximize-∑j=1q‍A0(j)•Zj(1.4)subjectto∑j=1q‍Ai(j)•Zj=cifori=1,…,n(1.5)Zj≽0forj=1,…,q.In the above,A•B denotes the matrix dot product. If A=[aij] and B=[bij] are matrices of size m, then A•B=∑i=1m‍∑j=1m‍aijbij=Tr[ABT], where Tr denotes the trace. We let ℛ={x∣A(j)(x)≽0 for allj=1,…,q} the feasible region and int(ℛ)={x∣A(j)(x)≻0 for all j=1,…,q} the interior of the feasible region. The set int(ℛ) is precisely the set of all strictly feasible points. Let p* be the optimal solution to the primal problem (1.1), and let d* be the optimal solution to the dual problem (1.3). The duality gap p*-d* is zero if either SDP (1.1)-(1.2) or its dual (1.3)–(1.5) is strictly feasible [2].Several interior point methods have been developed for solving SDPs (see [2, 4, 5]). When developing our interior point method in this paper, we assume a strictly feasible interior point x0 is known. There exist methods for finding feasible or near feasible points (see [6–8]). The algorithm we develop uses cutting planes and weighted analytic centers, and it iteratively refines the feasible region until the weighted analytic center approaches the optimal solution. We call our algorithm SDP-CUT. The cutting plane technique was pioneered by Gomory [9], Kelley [10], and also Cheney and Goldstein [11] for solving integer programming problems. An algorithm similar to our SDP-CUT for linear programs (LPs) was proposed by Renegar in his 1988 paper [12].SDP-CUT is implemented using Newton’s method and different line search techniques. We found that Newton’s method with exact line search is the best implementation of our algorithm. The effects of a weight vectorw∈ℝ+ on the algorithm are also studied. A larger weight yields a faster and more accurate solution in theory, but in practice, too large a weight may cause numerical errors. We also experienced numerical errors in computing the Hessian matrices in SDP-CUT, when solving very large problems.Since finding an interior point for an SDP problem is equivalent to solving another SDP problem, we decided to consider test problems with a known interior point and used that point as a starting point for SDP-CUT. We find SDPT3 to be an ideal method for comparison with SDP-CUT because it is known to be efficient and it allows the user to input a starting point. We found SDP-CUT was closer to the actual solution than SDPT3 for the initial iterations on all our test problems. SDP-CUT seems to slow down during later iterations to reach optimality. On the other hand, SDPT3 took less time on all the problems and less iterations on most of them. All codes were written in MATLAB version 7.9.0.


## 2. Weighted Analytic Center

This section discusses weighted analytic center as given in [13] and how to compute it. Other notions of weighted center for semidefinite programming are described in [14].Given a weight vectorω∈ℝ+n, the weighted barrier function for our system of LMIs (1.2) is defined as follows:
(2.1)ϕω(x)={-∑j=1q‍ωjlog det[A(j)(x)]ifA(j)(x)≻0∀j=1,…,q,+∞otherwise.Note that asx approaches the boundary of the feasible region, ϕω(x) approaches ∞. We assume the set {diag(A1(1),…,A1(q)),diag(A2(2),…,A2(q)),diag(An(1),…,An(q))} is linearly independent. The function ϕω is analytic and strictly convex over ℛ (see [13, 15]). The weighted analytic center is defined to be xac(ω)=argmin{ϕω(x)∣x∈ℝn}. We call xac(1) the analytic center, where 1=[1,1,…,1]. In the case of linear constraints and some other more general LMIs, each weight pushes the analytic center away from the boundary of the corresponding constraint. The gradient ∇ϕω(x) and the Hessian ∇2ϕω(x) are given by the following: for i=1,…,n and k=1,…,n(2.2)(∇ϕω(x))i=-∑j=1q‍ωj(A(j)(x))-1•Ai(j),(∇2ϕω(x))ik=∑j=1q‍ωj[(A(j)(x))-1Ai(j)]T•[(A(j)(x))-1Ak(j)].
We will use the following specific example, SDP (2.3), to describe our method:
(2.3)SDP:minimizez=x1+2x2subject toA(1)(x)=[2001]+x1[-1000]+x2[0110]=[2-x1x2x21]≽0,(1)A(2)(x)=[0000]+x1[1001]+x2[-1000]=[x1-x200x1]≽0.(2)Weighted analytic centers for the LMI system (1.2) can be computed with the WAC-NEWTON algorithm described below. (Algorithm 1).Algorithm 1:WAC-NEWTON.
INPUT: pointy0∈int(ℛ), weight vector ω∈ℝq, tolerance WTOL>0, and maximum
number of iterationsMAX
Setl=0
while  l<MAX  do
1.Compute the direction vector sl=-(∇2ϕω(yl))-1(∇ϕω(yl))
2.Compute the Newton decrement d=slT(∇2ϕω(yl))sl
3.Compute stepsize αl
4.yl+1=yl+αlsl
if  d<WTOL  then
break while
5.l←l+1
OUTPUT:xac(ω)=ylAn efficient way to calculate the search vectorsl in WAC-NEWTON is by finding the Cholesky factorization of ∇2ϕω(yl) and using it to solve the linear system ∇2ϕω(yl)sl=-∇ϕω(yl). This is how sl is calculated in the SDP-CUT algorithm to be discussed in the next section and throughout this paper. Figure 1 shows the contours of ϕω(x), the effect of the weight vector ω=[3,1] on the barrier function, and the weighted analytic center. The figure uses the feasible region defined by SDP (2.3) and the associated barrier function. The weight of 3 on constraint (1) pushes the analytic center away from the boundary of constraint (1).ϕ
ω
(
x
) contours and xac(ω) with various weights ω.


## 3. The SDP-CUT Algorithm

This section describes the development of SDP-CUT. We also discuss WAC-NEWTON*, which implements Newton’s method for finding theweighted analytic center for the new system defined in SDP-CUT. The section finishes with algorithms for computing the Newton stepsize (CONSTANT, ELS, and BACKTRACKING).Refer again to the example SDP (2.3). Here, we illustrate one iteration of SDP-CUT. Figure 2 shows the setup. We have the feasible region, an initial point x0*=[1.2633,-0.2292]T, and a cutting constraint of the form cTxk*-cTx+ϵ≥0 that accompanies the point. Figure 3 shows the movement of the point x0* to x1*=xac(1), the (weighted) analytic center of our new feasible region made up of the the cutting constraint and the original LMI constraints. Figure 3 also has the contour lines of the barrier function. The weight on the cutting constraint can be changed from 1 to other larger values.Figure 2
The first cutting constraint and an initial pointx0*.Figure 3
The weighted analytic center of new feasible region.Given a system of LMI’s (1.2) and an objective function as in the primal SDP problem (1.1), we can numerically solve the problem by iteratively reducing the feasible set. Denote the current feasible region determined by our system of LMIs by ℛk, and suppose we know a strictly feasible point xk* in ℛk. Initially, we set ℛ0=ℛ. We can find a new feasible region ℛk+1⊂ℛk, where for allx∈ℛk+1, cTx≤cTxk*. We do this by adding a new constraint cut cTxk*-cTx+ϵ≥0. The ϵ is added to cTxk* to ensure that xk* is “strictly feasible” in the new system. Given weight w∈ℝ+, we define a new barrier function to account for this new constraint:
(3.1)ϕw*(x)=-wlog[cTxk*-cTx+ϵ]-∑j=1q‍logdet[A(j)(x)].
The gradient ∇ϕw*(x) and the Hessian ∇2ϕw*(x) for this new barrier function are given by the following: for i=1,…,n and k=1,…,n:
(3.2)(∇ϕw*(x))i=wci(cTxk*-cTx+ϵ)-∑j=1q‍(A(j)(x))-1•Ai(j),(3.3)(∇2ϕw*(x))ik=wcick(cTxk*-cTx+ϵ)2+∑j=1q‍[(A(j)(x))-1Ai(j)]T•[(A(j)(x))-1Ak(j)].Remark 3.1.
Note that in the definition ofϕw*(x) in (3.1), weight [1,1,…,1] is used on the original LMI constraints. The weight w is used only on the new cutting constraint in order to push our point toward the optimal solution. (see Algorithm 2).Algorithm 2:SDP-CUT.
INPUT:x0*∈int(ℛ), weight w∈ℝ+, ϵ>0, STOL>0, and MAX
Setk=0
While  k<MAX  do
1.Compute cutting plain constraint cTx-cTxk*+ϵ≥0
2.Let xk+1* be the weightedanalyticcenter of new system with barrier function ϕw*(x)
(3.1) to be computed by WAC-NEWTON* starting from the point xk*
Compute∂k+1=cTxk*-cTxk+1*
if  ∂k<STOL  then
break while
3.k←k+1
OUTPUT:xcut*=xk*, pcut*=cTxk*If successful, SDP-CUT terminates with an optimal solutionxcut* and optimal objective function value pcut*. Rather than moving the plane in Step 1 of SDP-CUT, the point xk* could also be moved in the direction of -c to obtain a different starting point xk*-γc for some small γ>0, instead of xk*. However, this can be problematic as we approach the optimal solution and the feasible region gets small. The point xk*-γc may pass over the entire remaining feasible region and thus fail to be feasible. If instead, we move the plane as originally suggested in SDP-CUT, xk* will always be strictly feasible. Note that since the objective is to maximize cTx and xk* is an interior point, then -c is a feasible direction from xk*.We denote by WAC-NEWTON*, the WAC-NEWTON algorithm applied toϕw*(x) (3.1) for determining xk+1* in the SDP-CUT algorithm. WAC-NEWTON* will return the weighted analytic center of the current feasible region, which will be our next iterate for SDP-CUT. In WAC-NEWTON*, the stepsize αl can be computed in a variety of different ways as discussed in the next section.


### 3.1. Line Searches: Computing the Newton Stepsize in WAC-NEWTON* Algorithm

We describe different options for computing the Newton stepsizes in the WAC-NEWTON* algorithm. The algorithm first computes the direction vectorsl. The Newton stepsize αl determines how far we should move in the direction of sl from the point yl.The pure Newton’s method uses a constant stepsizeαl=1. We will refer to this method of choosing the stepsize as “CONSTANT.” The CONSTANT algorithm has the advantage of not using computational time in deciding what stepsize to use. The disadvantage of Newton’s method with CONSTANT is that it usually results in the need to perform more iterations of WAC-NEWTON*, and it is possible to move out the feasible region. To get αl with exact line search, we solve the one-dimensional optimization problem:
(3.4)minimize{g(α)∣α>0},
where g(α)=ϕw*(yl+αsl). Solving (3.4) is relatively easy and may cut the number of WAC-NEWTON* iterations in SDP-CUT, which are computationally harder in comparison
(3.5)g(α)=ϕw*(yl+αsl)=-wlog[cTxk*-cT(yl+αsl)+ϵ]-∑j=1q‍log det[A(j)(yl+αsl)].
Let al=wlog[cTxk*-cT(yl+αsl)+ϵ]. Then
(3.6)g(α)=-al-∑j=1q‍log det[A(j)(yl+αsl)]=-al-∑j=1q‍logdet[A(j)(yl)+∑i=1n‍(αsl)iAi(j)].
Let M0(j)=A(j)(yl) and Ms(j)=∑i=1n‍(sl)iAi(j). Then
(3.7)g(α)=-al-∑j=1q‍logdet[M0(j)+αMs(j)].
Also,
(3.8)g(α)=-al-∑j=1q‍logdet[M0(j)+αMs(j)]=-al-∑j=1q‍logdet[(M0(j))1/2(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)(M0(j))1/2]=-al-∑j=1q‍log[det[(M0(j))1/2]det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]×det[(M0(j))1/2]]=-al-∑j=1q‍log[det[(M0(j))1/2]2det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]]=-al-∑j=1q‍log[det[(M0(j))]det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]]=-al-∑j=1q‍logdet[(M0(j))]-∑j=1q‍logdet[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)].
Let λi(j) be an eigenvalue of (M0(j))-1/2Ms(j)(M0(j))-1/2. Then
(3.9)g(α)=-al-∑j=1q‍logdet[(M0(j))]-∑j=1q‍∑i=1mj‍log[1+αλi(j)].
The function g(α) is convex function over ℝ, and the exact stepsize αl can be found using the Newton’s method. Equations (3.7) and (3.9) give two different ways of computing g(α), when finding the exact stepsize. If one decides to use (3.7), the first and second derivatives of g(α) are required and given by
(3.10)g′(α)=wcTslcTxk*-cT(yl+αsl)+ϵ-∑j=1q‍(M0(j)+αMs(j))-1•Ms(j),g′′(α)=-w(cTsl)2(cTxk*-cT(yl+αsl)+ϵ)2(3.11)+∑j=1q‍[(M0(j)+αMs(j))-1Ms(j)]T•[(M0(j)+αMs(j))-1Ms(j)]
If (3.9) is used, the derivatives are simply given by
(3.12)g′(α)=wcTslcTxk*-cT(yl+αsl)+ϵ-∑j=1q‍∑i=1mj⋋i(j)1+α⋋i(j),(3.13)g′′(α)=w(cTsl)2(cTxk*-cT(yl+αsl)+ϵ)2-∑j=1q‍∑i=1mj(⋋i(j))2(1+α⋋i(j))2.
We will use ELS-MAT to denote the exact line search computations done using (3.7), and ELS-EIG if computations are done from (3.9).In addition to constant stepsize = 1 and exact line search, another way that was considered in computing the Newton stepsize wasbacktracking. This method involves starting with a stepsize >= 1 and then, decreasing the stepsize until a stopping condition is met (see [5, 16]). This technique guarantees a sufficient decrease in g(α), often starting from α=1, in practice. (see Algorithm 3).Algorithm 3:Backtracking.
INPUT: 0< β < 1 and 0 < γ < 0.5
Setα = 1
while  g(α) > g(0) + αγ(∇φw(yl))Tsldo
α⟵βα
OUTPUT:αIt is known that Newton’s method converges quadratically close to the solution. In our case, WAC-NEWTON* converges rapidly for starting points that are not close to the boundary of the feasible regionℛk. Sometimes, we encounter difficulty when the starting point is too close to the boundary. Note that each time we make a new cut, our starting point is near the boundary. It is also the case, when SDP-CUT iterates approaches optimality. When close to the boundary, our direction vector s often is very small, and thus a stepsize of α=1 may not make much progress. So, in these cases, the CONSTANT stepsize may spend many iterations, while making little progress, and each iteration wasting gradient and Hessian computations. Using the ELS algorithm, we find the proper stepsize and move out of this problem area in just one iteration. Consider the plots in Figure 4, which show the situation described above. Here, again, we are using SDP Example 2.3 and the point shown in Figure 2.Need for different stepsizes.As we can see from Figure4 on the left, the best choice of stepsize is much greater than 1. In Figure 4 on the right, we can see that we have now moved into an area where a stepsize of 1 is reasonable. BACKTRACKING will not help with this problem. BACKTRACKING only helps when the optimal stepsize is less than 1. If we try to adapt BACKTRACKING to help in the circumstance described above, we must initialize the BACKTRACKING stepsize to a large number, which creates two problems. First, when the optimal stepsize is close to 1, or smaller, we will waste time backtracking. Secondly, if we use a large initial stepsize, this may cause BACKTRACKING to send our point outside the feasible region, causing our algorithm to diverge. As it will be further shown in the next section, it does appear that ELS has a positive effect on SDP-CUT, while BACKTRACKING does not. Figure 5 has plots comparing how far CONSTANT and ELS move our point towards the optimal solution at each iteration. The plots highlight the “wasted iteration” problem with CONSTANT, which occurs when the optimal stepsize ismuch great than 1.The “wasted iteration” problem.


## 3.1. Line Searches: Computing the Newton Stepsize in WAC-NEWTON* Algorithm

We describe different options for computing the Newton stepsizes in the WAC-NEWTON* algorithm. The algorithm first computes the direction vectorsl. The Newton stepsize αl determines how far we should move in the direction of sl from the point yl.The pure Newton’s method uses a constant stepsizeαl=1. We will refer to this method of choosing the stepsize as “CONSTANT.” The CONSTANT algorithm has the advantage of not using computational time in deciding what stepsize to use. The disadvantage of Newton’s method with CONSTANT is that it usually results in the need to perform more iterations of WAC-NEWTON*, and it is possible to move out the feasible region. To get αl with exact line search, we solve the one-dimensional optimization problem:
(3.4)minimize{g(α)∣α>0},
where g(α)=ϕw*(yl+αsl). Solving (3.4) is relatively easy and may cut the number of WAC-NEWTON* iterations in SDP-CUT, which are computationally harder in comparison
(3.5)g(α)=ϕw*(yl+αsl)=-wlog[cTxk*-cT(yl+αsl)+ϵ]-∑j=1q‍log det[A(j)(yl+αsl)].
Let al=wlog[cTxk*-cT(yl+αsl)+ϵ]. Then
(3.6)g(α)=-al-∑j=1q‍log det[A(j)(yl+αsl)]=-al-∑j=1q‍logdet[A(j)(yl)+∑i=1n‍(αsl)iAi(j)].
Let M0(j)=A(j)(yl) and Ms(j)=∑i=1n‍(sl)iAi(j). Then
(3.7)g(α)=-al-∑j=1q‍logdet[M0(j)+αMs(j)].
Also,
(3.8)g(α)=-al-∑j=1q‍logdet[M0(j)+αMs(j)]=-al-∑j=1q‍logdet[(M0(j))1/2(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)(M0(j))1/2]=-al-∑j=1q‍log[det[(M0(j))1/2]det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]×det[(M0(j))1/2]]=-al-∑j=1q‍log[det[(M0(j))1/2]2det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]]=-al-∑j=1q‍log[det[(M0(j))]det[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)]]=-al-∑j=1q‍logdet[(M0(j))]-∑j=1q‍logdet[(I+α(M0(j))-1/2Ms(j)(M0(j))-1/2)].
Let λi(j) be an eigenvalue of (M0(j))-1/2Ms(j)(M0(j))-1/2. Then
(3.9)g(α)=-al-∑j=1q‍logdet[(M0(j))]-∑j=1q‍∑i=1mj‍log[1+αλi(j)].
The function g(α) is convex function over ℝ, and the exact stepsize αl can be found using the Newton’s method. Equations (3.7) and (3.9) give two different ways of computing g(α), when finding the exact stepsize. If one decides to use (3.7), the first and second derivatives of g(α) are required and given by
(3.10)g′(α)=wcTslcTxk*-cT(yl+αsl)+ϵ-∑j=1q‍(M0(j)+αMs(j))-1•Ms(j),g′′(α)=-w(cTsl)2(cTxk*-cT(yl+αsl)+ϵ)2(3.11)+∑j=1q‍[(M0(j)+αMs(j))-1Ms(j)]T•[(M0(j)+αMs(j))-1Ms(j)]
If (3.9) is used, the derivatives are simply given by
(3.12)g′(α)=wcTslcTxk*-cT(yl+αsl)+ϵ-∑j=1q‍∑i=1mj⋋i(j)1+α⋋i(j),(3.13)g′′(α)=w(cTsl)2(cTxk*-cT(yl+αsl)+ϵ)2-∑j=1q‍∑i=1mj(⋋i(j))2(1+α⋋i(j))2.
We will use ELS-MAT to denote the exact line search computations done using (3.7), and ELS-EIG if computations are done from (3.9).In addition to constant stepsize = 1 and exact line search, another way that was considered in computing the Newton stepsize wasbacktracking. This method involves starting with a stepsize >= 1 and then, decreasing the stepsize until a stopping condition is met (see [5, 16]). This technique guarantees a sufficient decrease in g(α), often starting from α=1, in practice. (see Algorithm 3).Algorithm 3:Backtracking.
INPUT: 0< β < 1 and 0 < γ < 0.5
Setα = 1
while  g(α) > g(0) + αγ(∇φw(yl))Tsldo
α⟵βα
OUTPUT:αIt is known that Newton’s method converges quadratically close to the solution. In our case, WAC-NEWTON* converges rapidly for starting points that are not close to the boundary of the feasible regionℛk. Sometimes, we encounter difficulty when the starting point is too close to the boundary. Note that each time we make a new cut, our starting point is near the boundary. It is also the case, when SDP-CUT iterates approaches optimality. When close to the boundary, our direction vector s often is very small, and thus a stepsize of α=1 may not make much progress. So, in these cases, the CONSTANT stepsize may spend many iterations, while making little progress, and each iteration wasting gradient and Hessian computations. Using the ELS algorithm, we find the proper stepsize and move out of this problem area in just one iteration. Consider the plots in Figure 4, which show the situation described above. Here, again, we are using SDP Example 2.3 and the point shown in Figure 2.Need for different stepsizes.As we can see from Figure4 on the left, the best choice of stepsize is much greater than 1. In Figure 4 on the right, we can see that we have now moved into an area where a stepsize of 1 is reasonable. BACKTRACKING will not help with this problem. BACKTRACKING only helps when the optimal stepsize is less than 1. If we try to adapt BACKTRACKING to help in the circumstance described above, we must initialize the BACKTRACKING stepsize to a large number, which creates two problems. First, when the optimal stepsize is close to 1, or smaller, we will waste time backtracking. Secondly, if we use a large initial stepsize, this may cause BACKTRACKING to send our point outside the feasible region, causing our algorithm to diverge. As it will be further shown in the next section, it does appear that ELS has a positive effect on SDP-CUT, while BACKTRACKING does not. Figure 5 has plots comparing how far CONSTANT and ELS move our point towards the optimal solution at each iteration. The plots highlight the “wasted iteration” problem with CONSTANT, which occurs when the optimal stepsize ismuch great than 1.The “wasted iteration” problem.


## 4. Experiment I: SDP-CUT Implementations

We have implemented SDP-CUT in four ways, varying in how the Newton stepsize is computed: CONSTANT, ELS-MAT, ELS-EIG, and BACKTRACKING. We will compare the performance of these four implementations against various test problems. For each problem, the SDP-CUT parameters were set atϵ=10-6, STOL=10-12, WTOL=10-10, w=7 and MAX=100.


### 4.1. Performance asq Varies

Here, we left the number of variables constant atn=2 and varied the number of constraints q from 2 to 10. The matrices have their sizes fixed at mj=5 for all j. For each value of q, 10 SDP problems were randomly generated, and SDP-CUT was used to solve each problem. The number of SDP-CUT iterations (which we also call WAC-NEWTON* iterations) and run time for SDP-CUT were recorded for each problem. Figures 6 and 7 give plots of the averages with q on the horizontal axis. The vertical axis in Figure 6 contains the total SDP-CUT iterations. In Figure 7, the vertical axis gives the total run time of SDP-CUT in seconds.Figure 6
SDP-CUT iterations against the number of constraintsq.Figure 7
Time as it varies with the number of constraintsq.Figure6 shows there is not a correlation between the number of LMI constraints and the number of SDP-CUT iterations (WAC-NEWTON* iterations) needed to find the optimal solution. Figure 6 also shows that ELS-EIG and ELS-MAT both effectively reduce the number of SDP-CUT iterations needed, while BACKTRACKING has about the same number of iterations as CONSTANT. Figure 7 shows that in the case of n=2, ELS-MAT and ELS-EIG run the fastest, while BACKTRACKING runs far slower than anything else. Time increases as q increases due to the gradient and Hessian computations. As we can see in formulas (3.2) and (3.3), for each constraint, we must perform matrix inverses, dot products, and multiplications. This makes each iteration computationally harder, but does not affect the iterations needed as is seen in Figure 6. BACKTRACKING’s time increases the most with q due to the eigenvalue computation needed for the stopping condition. BACKTRACKING performs these extra computations, but SDP-CUT does not benefit from them, and consequently BACKTRACKING has the highest run time.


### 4.2. Performance asn Varies

Here, we left the number of constraints constant atq=3 and varied the number of variables n from 2 to 10. The matrices sizes were set at mj=5 for all j. For each value of n, 10 SDP problems were randomly generated, and SDP-CUT was used to solve each problem. The number of SDP-CUT iterations (WAC-NEWTON* iterations) and run time for SDP-CUT were recorded for each problem. Figures 8, 9, and 10 are plots of the averages with n on the horizontal axis. The vertical axis contains the SDP-CUT iterations (WAC-NEWTON* iterations) needed in Figure 8. The vertical gives the run time of SDP-CUT in seconds in Figure 9. There is also a third plot, Figure 10, which shows n on the horizontal axis and the average time required to perform an iteration of SDP-CUT on the vertical axis.Figure 8
SDP-CUT iterations against the number of variablesn.Figure 9
SDP-CUT time as it varies with the number of variablesn.Figure 10
Time required to perform an iteration of SDP-CUT.Figure8, again, shows that ELS-EIG and ELS-MAT are effective in reducing the number of SDP-CUT iterations needed, while BACKTRACKING fails to reduce the number of iterations needed. Figure 8 also shows a positive correlation between the number of SDP-CUT iterations (WAC-NEWTON* iterations) and n. From Figure 9, we see that the exact line search reduces the total time needed for our algorithm, especially as n gets larger. This is important, because as n grows, the number of SDP-CUT iterations and the time required per iteration both increase (see Figure 10). For small n, CONSTANT is quicker per SDP-CUT iteration, but as n grows there is no noticeable difference in the time per iteration between CONSTANT or either ELS implementation. This is because the computations needed for the optimization problem (3.4) becomes so small compared to the computations need to compute ∇ϕw*(x) and ∇2ϕw*(x).


### 4.3. Performance asm Varies

Here, we left the number of constraints constant atq=2 and the number of variables fixed at n=2. We varied the matrix sizes mj=m from 5 to 60. The number of SDP-CUT iterations (WAC-NEWTON* iterations) and run time were recorded for each problem. Below are plots of the averages with m on the horizontal axis. The vertical axis in Figure 11 contains the total SDP-CUT iterations (WAC-NEWTON* iterations) used to solve the problem. In Figure 12, the vertical axis gives the total run time of SDP-CUT in seconds. There is also a third plot, Figure 13, which shows m on the horizontal axis and the time required to perform an iteration of SDP-CUT on the vertical axis.Figure 11
SDP-CUT iterations with matrix size.Figure 12
SDP-CUT time as it varies with matrix size.Figure 13
Time required to perform an iteration of WAC-NEWTON*.Figure11, again, shows that ELS reduces the required number of SDP-CUT iterations (WAC NEWTON* iterations). However, as the size of the constraint matrices becomes large, the computations needed for the exact line search grow. Figure 12 shows the ELS-MAT is the fastest in the range of matrix sizes we tested. Unlike our other experiments, CONSTANT beats ELS-EIG. The reason for this is that the time per iteration of ELS-EIG grows very rapidly as is seen in Figure 13. This occurs because the computation of eigenvalues becomes increasingly difficult as the matrix grows in size.ELS appears to be the best implementation of SDP-CUT. ELS is very effective in reducing the number of WAC NEWTON* iterations needed. ELS-MAT outperformed ELS-EIG in general. The eigenvalues allow for fast computation of the gradient and Hessian ofg(α) once the eigenvalues are obtained (see (3.12) and (3.13)). However, the large cost of computing the eigenvalues outweighs this benefit, especially as the matrices become large. ELS-MAT uses a slower means of computing the gradient and Hessian of g(α), but has no eigenvalue calculation overhead (see (3.10) and (3.11)). The slowest operation needed is matrix inversion. Matrix inversion becomes harder as the matrices get large, but it scales much better than finding the eigenvalues. It is conceivable that very large matrix situations could arise in which both ELS-EIG and ELS-MAT are too expensive; in this case it may be best to use CONSTANT. We were unable to find any cases in our test problems in which BACKTRACKING was beneficial. From now onwards, SDP-CUT will always refer to SDP-CUT with ELS-MAT implementation.


### 4.4. Convergence and the Weightw, Leveling Off Effect

Increasing the weightw will decrease the number of SDP-CUT iterations needed to find the optimal solution. A larger weight will also allow us to get closer to the optimal solution. However, if w becomes too large, numerical errors will prevent convergence. Here, we will discuss the role w plays in the rate of convergence, as well as how large we can make w before SDP-CUT fails. Figure 4 graphically demonstrates the convergence of SDP-CUT on our example (SDP (2.3)) as the weight w varies.From the plots in Figure14, we can visibly see that by increasing the weight, SDP-CUT moves toward the optimal solution faster. In attempts to see how fast SDP-CUT converges and what effect the weight has, we performed the following experiment. We ran SDP-CUT on the example and kept track of the iterates xk* at each iteration. Below is a plot of ∥x*-xk*∥ shown on a log scale against iterations as we varied the weight w=1,3,5,7,9, where x* is the optimal solution. We see in Figure 15 that the distance from the estimate to the actual solution decreases exponentially, and linearly when shown on the log scale. We found that in most cases our implementation of SDP-CUT breaks down around w=10.Convergence of SDP-CUT forw=1 and w=5.Figure 15
Convergence for various weightsw on a log scale.As we can see, increasing the weight means quicker convergence. However, Figure15 only shows the first 10 iterations. As we approach the optimal solution, the rate of convergence slows and “levels off.” This is caused by the feasible region becoming very small and by moving the cutting constraint back by ϵ, and thus the SDP-CUT iterates stay in approximately the same place. This problem is demonstrated in Figure 16. We see that larger weights allow us to get closer to the optimal solution, but even with a larger weight our convergence “levels off.”Figure 16
The “leveling off” effect.One way to get closer to the optimal solution before the weighted analytic centers start to “levels off,” is to use a smallerϵ. The difficulty with decreasing ϵ is if ϵ becomes too small, our SDP-CUT iterates come too close to the boundary, giving rise to “numerical problems,” especially in computing the Hessian matrices. We found that SDP-CUT worked with =10-6, but failed when ϵ=10-7 in example SDP (2.3). The “numerical problems” are due to the fact that near the boundary, one of the LMI constraint matrices is near-singular, and we need to compute matrix inverses. Figure 17 shows what the “leveling off” effect looks like over the feasible region of SDP problem (2.3). Notice that the sequence of iterates xk*, from SDP-CUT, reaches a limit before it reaches the boundary of the region.Figure 17
The “leveling off” effect zoomed in on feasible region.


## 4.1. Performance asq Varies

Here, we left the number of variables constant atn=2 and varied the number of constraints q from 2 to 10. The matrices have their sizes fixed at mj=5 for all j. For each value of q, 10 SDP problems were randomly generated, and SDP-CUT was used to solve each problem. The number of SDP-CUT iterations (which we also call WAC-NEWTON* iterations) and run time for SDP-CUT were recorded for each problem. Figures 6 and 7 give plots of the averages with q on the horizontal axis. The vertical axis in Figure 6 contains the total SDP-CUT iterations. In Figure 7, the vertical axis gives the total run time of SDP-CUT in seconds.Figure 6
SDP-CUT iterations against the number of constraintsq.Figure 7
Time as it varies with the number of constraintsq.Figure6 shows there is not a correlation between the number of LMI constraints and the number of SDP-CUT iterations (WAC-NEWTON* iterations) needed to find the optimal solution. Figure 6 also shows that ELS-EIG and ELS-MAT both effectively reduce the number of SDP-CUT iterations needed, while BACKTRACKING has about the same number of iterations as CONSTANT. Figure 7 shows that in the case of n=2, ELS-MAT and ELS-EIG run the fastest, while BACKTRACKING runs far slower than anything else. Time increases as q increases due to the gradient and Hessian computations. As we can see in formulas (3.2) and (3.3), for each constraint, we must perform matrix inverses, dot products, and multiplications. This makes each iteration computationally harder, but does not affect the iterations needed as is seen in Figure 6. BACKTRACKING’s time increases the most with q due to the eigenvalue computation needed for the stopping condition. BACKTRACKING performs these extra computations, but SDP-CUT does not benefit from them, and consequently BACKTRACKING has the highest run time.


## 4.2. Performance asn Varies

Here, we left the number of constraints constant atq=3 and varied the number of variables n from 2 to 10. The matrices sizes were set at mj=5 for all j. For each value of n, 10 SDP problems were randomly generated, and SDP-CUT was used to solve each problem. The number of SDP-CUT iterations (WAC-NEWTON* iterations) and run time for SDP-CUT were recorded for each problem. Figures 8, 9, and 10 are plots of the averages with n on the horizontal axis. The vertical axis contains the SDP-CUT iterations (WAC-NEWTON* iterations) needed in Figure 8. The vertical gives the run time of SDP-CUT in seconds in Figure 9. There is also a third plot, Figure 10, which shows n on the horizontal axis and the average time required to perform an iteration of SDP-CUT on the vertical axis.Figure 8
SDP-CUT iterations against the number of variablesn.Figure 9
SDP-CUT time as it varies with the number of variablesn.Figure 10
Time required to perform an iteration of SDP-CUT.Figure8, again, shows that ELS-EIG and ELS-MAT are effective in reducing the number of SDP-CUT iterations needed, while BACKTRACKING fails to reduce the number of iterations needed. Figure 8 also shows a positive correlation between the number of SDP-CUT iterations (WAC-NEWTON* iterations) and n. From Figure 9, we see that the exact line search reduces the total time needed for our algorithm, especially as n gets larger. This is important, because as n grows, the number of SDP-CUT iterations and the time required per iteration both increase (see Figure 10). For small n, CONSTANT is quicker per SDP-CUT iteration, but as n grows there is no noticeable difference in the time per iteration between CONSTANT or either ELS implementation. This is because the computations needed for the optimization problem (3.4) becomes so small compared to the computations need to compute ∇ϕw*(x) and ∇2ϕw*(x).


## 4.3. Performance asm Varies

Here, we left the number of constraints constant atq=2 and the number of variables fixed at n=2. We varied the matrix sizes mj=m from 5 to 60. The number of SDP-CUT iterations (WAC-NEWTON* iterations) and run time were recorded for each problem. Below are plots of the averages with m on the horizontal axis. The vertical axis in Figure 11 contains the total SDP-CUT iterations (WAC-NEWTON* iterations) used to solve the problem. In Figure 12, the vertical axis gives the total run time of SDP-CUT in seconds. There is also a third plot, Figure 13, which shows m on the horizontal axis and the time required to perform an iteration of SDP-CUT on the vertical axis.Figure 11
SDP-CUT iterations with matrix size.Figure 12
SDP-CUT time as it varies with matrix size.Figure 13
Time required to perform an iteration of WAC-NEWTON*.Figure11, again, shows that ELS reduces the required number of SDP-CUT iterations (WAC NEWTON* iterations). However, as the size of the constraint matrices becomes large, the computations needed for the exact line search grow. Figure 12 shows the ELS-MAT is the fastest in the range of matrix sizes we tested. Unlike our other experiments, CONSTANT beats ELS-EIG. The reason for this is that the time per iteration of ELS-EIG grows very rapidly as is seen in Figure 13. This occurs because the computation of eigenvalues becomes increasingly difficult as the matrix grows in size.ELS appears to be the best implementation of SDP-CUT. ELS is very effective in reducing the number of WAC NEWTON* iterations needed. ELS-MAT outperformed ELS-EIG in general. The eigenvalues allow for fast computation of the gradient and Hessian ofg(α) once the eigenvalues are obtained (see (3.12) and (3.13)). However, the large cost of computing the eigenvalues outweighs this benefit, especially as the matrices become large. ELS-MAT uses a slower means of computing the gradient and Hessian of g(α), but has no eigenvalue calculation overhead (see (3.10) and (3.11)). The slowest operation needed is matrix inversion. Matrix inversion becomes harder as the matrices get large, but it scales much better than finding the eigenvalues. It is conceivable that very large matrix situations could arise in which both ELS-EIG and ELS-MAT are too expensive; in this case it may be best to use CONSTANT. We were unable to find any cases in our test problems in which BACKTRACKING was beneficial. From now onwards, SDP-CUT will always refer to SDP-CUT with ELS-MAT implementation.


## 4.4. Convergence and the Weightw, Leveling Off Effect

Increasing the weightw will decrease the number of SDP-CUT iterations needed to find the optimal solution. A larger weight will also allow us to get closer to the optimal solution. However, if w becomes too large, numerical errors will prevent convergence. Here, we will discuss the role w plays in the rate of convergence, as well as how large we can make w before SDP-CUT fails. Figure 4 graphically demonstrates the convergence of SDP-CUT on our example (SDP (2.3)) as the weight w varies.From the plots in Figure14, we can visibly see that by increasing the weight, SDP-CUT moves toward the optimal solution faster. In attempts to see how fast SDP-CUT converges and what effect the weight has, we performed the following experiment. We ran SDP-CUT on the example and kept track of the iterates xk* at each iteration. Below is a plot of ∥x*-xk*∥ shown on a log scale against iterations as we varied the weight w=1,3,5,7,9, where x* is the optimal solution. We see in Figure 15 that the distance from the estimate to the actual solution decreases exponentially, and linearly when shown on the log scale. We found that in most cases our implementation of SDP-CUT breaks down around w=10.Convergence of SDP-CUT forw=1 and w=5.Figure 15
Convergence for various weightsw on a log scale.As we can see, increasing the weight means quicker convergence. However, Figure15 only shows the first 10 iterations. As we approach the optimal solution, the rate of convergence slows and “levels off.” This is caused by the feasible region becoming very small and by moving the cutting constraint back by ϵ, and thus the SDP-CUT iterates stay in approximately the same place. This problem is demonstrated in Figure 16. We see that larger weights allow us to get closer to the optimal solution, but even with a larger weight our convergence “levels off.”Figure 16
The “leveling off” effect.One way to get closer to the optimal solution before the weighted analytic centers start to “levels off,” is to use a smallerϵ. The difficulty with decreasing ϵ is if ϵ becomes too small, our SDP-CUT iterates come too close to the boundary, giving rise to “numerical problems,” especially in computing the Hessian matrices. We found that SDP-CUT worked with =10-6, but failed when ϵ=10-7 in example SDP (2.3). The “numerical problems” are due to the fact that near the boundary, one of the LMI constraint matrices is near-singular, and we need to compute matrix inverses. Figure 17 shows what the “leveling off” effect looks like over the feasible region of SDP problem (2.3). Notice that the sequence of iterates xk*, from SDP-CUT, reaches a limit before it reaches the boundary of the region.Figure 17
The “leveling off” effect zoomed in on feasible region.


## 5. Experiment II: SDP-CUT versus SDPT3

In this section, the algorithms SDP-CUT and the well-known SDPT3 [17] method are compared on a variety of SDP test problems. Since SDPT3 is known to be efficient, we also used it to find the best possible estimation of the actual optimal objective function values. Another reason for using SDPT3 is its flexibility to allow the user to input a starting point.For the experiment, we tested 20 SDP problems and solved each with SDP-CUT and SDPT3. Each SDP problem was randomly generated, where the dimensionn and number of constraints q are random integers on the intervals [2,20] and [1,20] respectively. The size mj of each LMI is a random integer on [1,10]. The values of n and q are listed in the table below. The values of mj are not given because they are too many. For example, SDP 1 has m=[7,5,9,8,5,1]. The problems were generated in a way that makes the origin, an interior point for all of them. For all problems, we used tolerances STOL=10-3, WTOL=10-6, ϵ=10-7, and a weight of w=7 was used with SDP-CUT. For the first 10 test problems, the iteration limit was MAX=5. For the remaining 10 problem, the iteration limit is raised to MAX=100. We record the total iterations performed for each algorithm as well as the time taken. The last two columns of the table below show the error in the calculated optimal objective function value compared to the actual value pactual* obtained from SDPT3 with no restriction on the number of iterations. In the table below, the suffixescut and SDPT3 are used to distinguish between values pertaining to SDP-CUT and SDPT3, respectively. N, T, and E are used to denote the number of iterations, time, and absolute error, respectively. For example, Ecut=|pcut*-pactual*|.We see in Table1 that after 5 iterations, SDP-CUT gives a more accurate answer in all the first 10 test problems. However, if allowed to run for more iterations all the algorithms successfully found the optimal solutions, but SDPT3 took less number of iterations to reach optimality in 6 out of the 10 problems. Also SDPT3, took less time in all the 20 test problems. We believe the difference in times is partly because SDPT3 has over the years been optimized to run efficiently, while SDP-CUT is at a beginning of its development. It is interesting to note that SDP-CUT took fewer iterations in 4 out of the 10 problems.Table 1
Data for experiment II: SDP-CUT versus SDPT3.
SDP
n
q
N
cut
N
SDPT3
T
cut
T
SDPT3
E
cut
E
SDPT3
1
20
6
5
5
2.6842
0.1134
0.0814
0.8222
2
12
17
5
5
3.2816
0.0954
0.0126
0.7291
3
18
15
5
5
5.0180
0.0905
0.1053
0.1361
4
13
2
5
5
0.5383
0.0732
0.0116
0.0721
5
2
5
5
5
0.0714
0.0600
0.0000
0.0011
6
4
7
5
5
0.2779
0.0814
0.0006
0.1159
7
3
19
5
5
0.4144
0.0766
0.0001
0.4938
8
15
5
5
5
1.5041
0.0969
0.0423
0.1689
9
5
2
5
5
0.1164
0.0603
0.0013
0.5072
10
20
12
5
5
5.2449
0.0906
0.1425
1.3682
11
4
2
10
12
0.1457
0.1324
0
0
12
4
3
8
12
0.1536
0.1322
0
0
13
16
5
20
13
4.8852
0.1791
0
0
14
18
9
25
14
12.1776
0.2330
0
0
15
20
15
22
12
19.7580
0.1971
0
0
16
15
15
19
12
10.4692
0.2117
0
0
17
10
8
14
12
2.2191
0.1759
0
0
18
13
7
16
11
3.4501
0.1647
0
0
19
2
20
8
11
0.4571
0.1552
0
0
20
5
18
9
10
1.0308
0.1747
0
0We need to do more work to make SDP-CUT more efficient. We noticed that the Hessian matrix∇2ϕw*(x) in SDP-CUT is prone to errors in the case of problems that are very large. In those cases, ∇2ϕw*(x) loses its positive definiteness and thus its Cholesky factorization is not possible. That is the main reason why we could not run SDP-CUT on the SDP test problems at SDPLIB [18]. For example, SDP-CUT was not successfully in solving truss2 of SDPLIB, due to numerical problems when computing the Hessian matrices. This problem has n=58 variables and q=133 constraints. However, SDP-CUT was successful in solving truss1, but with w=5.


## 6. Convergence of SDP-CUT

Let{xk*} be the sequence of estimates for x* generated by SDP-CUT. Let ℛk be the feasible region after k-cuts. Thus, xk* is the weighted analytic center of ℛk for all k>0. Let {∂k} be the sequence defined by ∂k=cT(xk*-xk+1*).The following theorem shows that when||c|| and ||xk*-xk+1*|| are both small, then ∂k is also small. Note that when ∂k becomes very small, SDP-CUT is no longer making progress on the objective function values. This is especially true in the case of “leveling off” effect discussed in Section 4. This also indicates that our stopping criterion ∥xk*-xk+1*∥<STOL does not always mean convergence to the optimal solution.Theorem 6.1.
If∥xk*-xk+1*∥<STOL, then ∂k<∥c∥STOL.Proof.
Assume∥xk*-xk+1*∥<STOL and use the Cauchy-Schwartz Inequality
(6.1)∂k=cT(xk*-xk+1*)⇒∂k≤∥c∥∥xk*-xk-1*∥⇒∂k<∥c∥STOL.How close we can get to the optimal solution depends on the parametersw and ϵ. As ϵ becomes smaller we are able to obtain smaller regions, which allows SDP-CUT to get closer to the optimal solution. For a given region, a larger w causes SDP-CUT push the estimate of the optimal solution xk* further in the -c direction. For any choice of iterate xk*, if we consider its limit as →∞, we should be able to push xk* as close to the optimal solution x* as we like. In practice, both the decrease ϵ→0 and w→∞ cause numerical problems. A question we propose is: in the limit as w→∞, how many iterations of SDP-CUT are needed for convergence?Since the cutting plane is a linear constraint, it is possible that only one iteration is needed asw→∞ (at least in some cases). Consider the following SDP (LP) example:
(6.2)SDP: minimizex2subject to1-x1≥01+x1≥01-x2≥01+x2≥0.The feasible region of this example is given in Figure18. Consider the point (0,0) in the feasible region and the cutting constraint through this point. Also, consider the corresponding barrier function ϕw*(x) (3.1) and its gradient ∇ϕw*(x) (3.2). At the weighted analytic center, the gradient is zero. This gives
(6.3)11-x1-11+x1=0,wϵ-x2+11-x2-11+x2=0.
It is clear from Figure 18 that the weighted analytic center has a negative x2 value. So, the above equations show that the weighted analytic center is
(6.4)x1=0,x2=ϵ-ϵ2+2w+w22+w.
We see that the weighted analytic center (x1,x2) converges to the optimal solution (0,-1) as w→∞. This example suggests the following conjecture.Figure 18
Feasible region of LP and the cut through the point(0,0).Conjecture 6.2.
SDP-CUT converges tox* as w→∞.


### 6.1. Scaling the Vectorc

Theorem6.1 shows the dependence of ∂k on ||c||. Here, we will consider the effect of scaling c on SDP-CUT. If we scale c by ν>1 such that we are now trying to optimize νcTx, we do not change the optimal solution x*. We will compare how close SDP-CUT gets when optimizing for various values of ν. Figure 19 is a plot of the results ||x*-xcut*|| on the vertical axis and the scaling factor ν is on the horizontal axis. We used example SDP (2.3) with STOL=10-12, MAX=100, w=10. We can see in Figure 19 that scaling the objective vector c by a factor ν>1 does have a positive effect on the accuracy of SDP-CUT.Figure 19
The effect of scalingc.


## 6.1. Scaling the Vectorc

Theorem6.1 shows the dependence of ∂k on ||c||. Here, we will consider the effect of scaling c on SDP-CUT. If we scale c by ν>1 such that we are now trying to optimize νcTx, we do not change the optimal solution x*. We will compare how close SDP-CUT gets when optimizing for various values of ν. Figure 19 is a plot of the results ||x*-xcut*|| on the vertical axis and the scaling factor ν is on the horizontal axis. We used example SDP (2.3) with STOL=10-12, MAX=100, w=10. We can see in Figure 19 that scaling the objective vector c by a factor ν>1 does have a positive effect on the accuracy of SDP-CUT.Figure 19
The effect of scalingc.


## 7. Conclusion

We have developed and studied a new interior point method, SDP-CUT, for solving SDPs. We found that implementing SDP-CUT using Newton’s method with exact line search, in general, gives the best performance. SDP-CUT appears to be very effective in getting into the neighborhood of the optimal solution as seen in problems 1–10 in Table1. However, there is the “leveling off” effect shown in Figure 16. Future work on SDP-CUT can involve investigating Conjecture 6.2. Implementations that can handle a larger weight w or smaller ϵ will result in better performance.Another area for improvement is the stopping criteria. Currently, the stopping criteria is||xk*-xk-1*||<STOL, which lets us know if we are no longer making progress. However, this does not always guarantee optimality of the solution. We have also shown that scaling the objective vector c by some factor ν>1 could allow SDP-CUT to give a better solution. Also, it is important to investigate how to make all the other components of SDP-CUT work well and efficiently. For example, we would like to find a way to compute the Hessian ∇2ϕw*(x))ik more efficiently and without errors. The way we compute the stepsizes in Newton’s method is an area that requires further attention. The exact line search we preferred over the others is probably too expensive and a better way may be possible. These improvements would allow us to test SDP-CUT on larger problems and compare it with other methods. It is also of interest to study what kind of problems SDP-CUT would work well or fail.



---

*Source: 946893-2012-09-06.xml*