A numerical study of an infeasible interior-point algorithm for convex quadratic semi-definite optimization

Yasmina Bendaas and Mohamed Achache
(Date: July 2, 2024; accepted: November 11, 2024; December 18, 2024.)
Abstract.

The focus of this research is to apply primal-dual interior-point path-following methods, specifically those derived from Newton’s method for solving convex quadratic semidefinite optimization (CQSDO) problems. In this paper, we present a numerical study of an infeasible primal-dual interior-point method for tackling this class of optimization problems. Unlike the feasible interior-point algorithms, the proposed algorithm can be start with any initial positive definite matrix and does not require the strictly feasible initial points. Under certain conditions, the Newton system is well defined and its Jacobian is nonsingular at the solution. For computing an iteration throughout the algorithm, a Newton direction and a step-size are determined. Here, our search direction is based on Alizadeh-Haeberly-Overton (AHO) symmetrization. However, for the step size along this direction two alternatives are suggested. Preliminary numerical results demonstrate the efficiency of our algorithm.

Key words and phrases:
Convex quadratic semidefinite optimization, Interior-point methods, Primal-dual algorithm, Newton method.
2005 Mathematics Subject Classification:
90C05, 90C51
Fondamental and Numerical Mathematics Laboratory, Sétif 1 University-Ferhat ABBAS, Sétif 19000. ALGERIA, e-mail: yasmina.bendaas@univ-setif.dz.    ORCID: 0009-0007-0656-2062, e-mail: achache_m@univ-setif.dz.
 The work of this author has been supported by La Direction Générale de la Recherche Scientifique et du Développement Technologique (DGRSDT-MESRS), under projects PRFU number C00L03UN190120190004.

1. Introduction

Let 𝒮n and 𝒮+n denote the cones of n×n real symmetric and symmetric positive semi-definite matrices, respectively. The convex quadratic semidefinite optimization (CQSDO) problem is defined as follows

(𝒫)p=minX𝒮nf(X) s.t.AiX=bi,i=1,,m,X0,

and its dual

(𝒟)d=maxym,Z𝒮ng(y,Z)s.t.i=1myiAi+Z=C+𝒬(X),Z0,

where

f(X)=12X𝒬(X)+CX,

and

g(y,Z)=12X𝒬(X)+by,

b,ym,X,Z𝒮+n,C,Ai𝒮n,i=1,,m, 𝒬(X) is a given linear transformation on 𝒮n and the inequality M0 means that M𝒮+n. Recall that the notation AB=tr(AB), A,B𝒮n denotes the trace inner product.

The CQSDO problem has wide applications such as the computation of nearest correlation matrix problem (NCMP) also it arises in nearest Euclidean distance matrix problems and other matrix least square problems (SDLS) (see [17]). Many problems in metric embeddings, covariance estimations, eigenvalues and max-cut problems and molecular conformations can also be restated as CQSDO. It also includes the semidefinite optimization (SDO) as a special case when 𝒬(X)=0.

Over the last decades, many feasible primal-dual interior-point algorithms (FIPA) for solving CQSDO have been proposed (see, e.g., [20, 22, 6, 9, 15]). These algorithms are of Newton type methods and which enjoy certain property such as the locally quadratic convergence and have polynomial complexity. Further they are highly efficient in practice. It is well-known that FIPAs are iterative methods and start with a strictly feasible starting point and follow the central-path with keeping feasibility and centrality during the solution process. However, experimental issue of these algorithms show that getting a strictly feasible centered point is a hard task and even impossible. Therefore, to overcome this drawback many remedies are suggested. Among them, infeasible interior-point (IFIPA) algorithms which require that the starting initial point is any arbitrary symmetric positive definite matrix where feasibility is reached as optimality is approached [24, 27].

The main aim of this work is to deal with the numerical implementation of an IFIPAs for solving the CQSDO problems. Here, the determination of Newton search directions is based on the symmetrization of Alizadeh-Haeberly-Overton (AHO) [8]. Further, efficient step-size are suggested to keep iterations positive definite during Newton’s process. Our tested examples of CQSDO are reformulated from some known optimization problems such as SDO, SDLS, NCMP, the computation of the smallest eigenvalue of a symmetric positive definite matrix and the Max-cut problem.

Throughout the paper, the following notations are used. n×n denotes the set of all n×n real matrices. The trace inner-product and the Frobenius norm in 𝒮n are denoted, respectively, by: AB=tr(AB)=i,jaijbijandAF=(tr(A2))12,A,B𝒮n. For a matrix A, λi(A) denote its eigenvalues with λmin(A) (λmax(A)) as the smallest (largest) one, respectively, and detA stand for its determinant. The square root matrix of any X𝒮+n is denoted by X1/2 and the identity matrix is denoted by I, and e is the vector of all l’s.

The paper is organized as follows. In Section 2, preliminaries, the concept of the central-path and the AHO symmetrization search directions for CQSDO are discussed. Further, the numerical computation of the step-size and the search directions are stated. We described in Section 3 the generic primal-dual IFIPA. In Section 4, some numerical results are reported. In Section 5, a conclusion and future remarks end the paper.

2. A primal-dual IFIPA for CQSDO

2.1. Preliminaries

In this subsection, we first provide some mathematical useful tools which are crucial for the development of our proposed algorithm.

Lemma 1 (Lemma 2.1 in [22]).

If X,Z𝒮+n. Then the following statements

  1. 1)

    XZ=0,

  2. 2)

    XZ=0,

  3. 3)

    XZ+ZX2=0

are equivalent.

Let A and B two matrices, their Kronecker product is denoted by AB. For a matrix An×n, vec(A) is the n2×1 vector given by

vec(A)=(a11,a21,,ann).

We make use of the functions svec and smat, formally defined as follows

Definition 2.

For A𝒮n,svec12n(n+1) is given by

svec(A)=(a11,2a21,,2an1,a22,2a32,,2an2,,ann).

Further, the operator smat is the inverse operator of svec. That is,

smat(svec(A))=A.

In all the paper, the feasible sets and the strict feasible sets of 𝒫 and 𝒟 are the subsets of 𝒮n and m×𝒮n, respectively,

𝒫 ={X𝒮+n:AiX=bi,i=1,,m},
𝒫0 ={X𝒫:X𝒮++n},
𝒟 ={(y,Z)m×𝒮+n:C+𝒬(X)i=1myiAi=Z},
𝒟0 ={(y,Z)𝒟:Z𝒮++n}.

The optimal sets of 𝒫 and 𝒟 are the sets

Sopt𝒫={X𝒮n:X0,AiX=bi,i=1,,m,f(X)=p},

and

Sopt𝒟={(y,Z)m×𝒮+n:C+𝒬(X)i=1myiAi=Z,g(y,Z)=d}.

It is assumed that the two problems satisfy the following conditions:

  • -

    𝒫0×𝒟0 is nonempty.

  • -

    The Ai,i=1,,m, are linearly independent.

  • -

    The linear transformation 𝒬(X) is monotone and self-adjoint, i.e.,
    X𝒬(X)0andX𝒬(Y)=𝒬(X)Y,X,Y𝒮n.

The first assumption implies

  • -

    <p=d<.

  • -

    Sopt𝒫 and Sopt𝒟 are two non empty bounded convex sets.

Meanwhile, the second assumption is only to ensure that the dual variables Z and y are in one to one correspondence. By assumption three, 𝒫 and 𝒟 are two convex optimization problems, therefore the set of primal and dual optimal solutions consists of all solutions (X,y,Z)𝒮+n×m×𝒮+n of the following Karush-Khun-Tucker optimality system:

(1) {AiXbi=0,i=1,,m,X0,C+𝒬(X)i=1myiAiZ=0𝒮n,Z0,XZ=0.

Therefore, by Lemma 1 finding an optimal solution for 𝒫 and 𝒟 is equivalent to solving the system

(2) {AiX=bi,i=1,,m,X0,C+𝒬(X)Zi=1myiAi=0𝒮n,Z0,XZ+ZX2=0.

2.2. The central-path of CQSDO

The basic idea behind primal-dual IPAs is to replace the third equation in (2) by the parameterized equation

XZ+ZX2=σμI,

with μ>0. Thus we consider the system

(3) {AiXbi=0,i=1,,m,X0,C+𝒬(X)Zi=1myiAi=0𝒮n,Z0,XZ+ZX2=σμI,μ>0,

where σ(0,1) is the centrality parameter. Under our assumptions, system (3) has a unique solution (X(μ),y(μ),Z(μ)), for each μ>0. The set

𝒞={(X(μ),y(μ),Z(μ)):μ>0}

of μ-centers is called the central-path of 𝒫 and 𝒟. If μ tends to zero then the limit of 𝒞 exists and since the limit point satisfies the complementarity condition, the limit yields an approximated optimal solution of 𝒫 and 𝒟 (e.g., [8, 10]).

2.3. The Newton search directions for CQSDO

Next, we want to define search directions (ΔX,Δy,ΔZ)that move in the direction of the central-path 𝒞. Applying Newton’s method for (3), for a given μ>0 and an infeasible point (X0,y,Z0). Then the Newton direction (ΔX,Δy,ΔZ) at this point is the unique symmetric solution of the linear system:

(4) {AiΔX=𝒫,i=1,,m,i=1m(Δy)iAi+ΔZ𝒬(ΔX)=𝒟,ΔXZ+XΔZ+ΔZX+ZΔX=𝒞,X0,Z0,

with

𝒫=biAiX,i=1,,m,
𝒟=C(Z𝒬(X)+i=1myiAi),
𝒞=2σμI(XZ+ZX).

The search direction obtained via system (4) is named as the AHO-direction. It is worth mentioning that beside the AHO direction, there are other important search directions such as Kojima et al. [16], Helmberg et al. [12], Monteiro and Nesterov and Todd (NT) [19].

We will refer to the assignment:

X+=X+αΔX,y+=y+αΔy,Z+=Z+αΔZ

as a damped Newton step with α>0 is the step-size along this direction.

2.4. Computation of AHO directions

We have seen that the direction of AHO is given by system (4). So to compute this direction, we apply the ”svec” operator to the three equations of (4). For the first equation

AiΔX = 𝒫,i=1,,m,
svec(Ai)svec(ΔX) = 𝒫,i=1,,m,
𝒜svec(ΔX) = 𝒫,

such that

𝒜=[svec(A1)svec(Am)]m×n¯ and svec(ΔX)n¯,withn¯=n(n+1)2.

The second equation

svec(i=1m(Δy)iAi+ΔZ)svec[12(𝒬(X)ΔX+ΔX𝒬(X))] = 𝒟,
i=1msvec(Ai)(Δy)i+svec(ΔZ)(𝒬(X)sI)svec(ΔX), = 𝒟,
𝒜Δy+svec(ΔZ)𝒬(X)svec(ΔX) = 𝒟,

such that

𝒜=[svec(A1),,svec(Am)]n¯×m.

The third equation becomes

(ZΔX+ΔXZ)+(XΔZ+ΔZX) = 𝒞,
Esvec(ΔX)+Fsvec(ΔZ) = 𝒞,

such that

E=(ZsI),F=(XsI),𝒞=svec(μσI12(XZ+ZX)),

where s denotes the symmetric Kronecker product.

Finally, we obtain the following system

{𝒜svec(ΔX)=𝒫,𝒜Δy+svec(ΔZ)𝒬svec(ΔX)=𝒟,Esvec(ΔX)+Fsvec(ΔZ)=𝒞,

which can be written as the following matrix form:

(5) [0𝒜0𝒜𝒬In¯0EF][Δysvec(ΔX)svec(ΔZ)]=[𝒫𝒟𝒞].

We note that the system (5) is a linear system whose blocked matrix is a square matrix of order (m+2n¯), by using any linear system solver we get

(svec(ΔX),Δy,svec(ΔX)).

Then, we introduce smat the reciprocal application of svec to this last result.

2.5. Computation of a step-size α

For computing the step size α>0 in each iteration such that

X+αΔX0andZ+αΔZ0,

we need to determine the maximum step-size αmax so that if 0<ααmax then X+αΔX0 and Z+αΔZ0. Let αX and αZ be the maximum possible step-size in the direction ΔX and ΔZ, respectively. The natural step length for a Newton direction is α=1, but a step length of 1 may cause us to exceed the positive definite region to which we are constrained. Therefore, we need to determine the maximum possible step length αmax such that if 0<α<αmax, then Z+αΔZ0. and X+αΔX0. The maximum step length in the direction ΔX can easily be seen as being the smallest positive number αX such that

det(X+αΔX)=0,

or αX= if no positive solutions exist. Similarly, the maximum step length in the direction ΔZ is defined as the smallest positive number αZ such that

det(Z+αΔZ)=0,

or αZ= if no positive solutions exist. Our maximum possible step length is then the minimum of these two numbers:

αmax=min(αX,αZ).

We can compute αX and αZ as the minimum positive eigenvalues of the respective generalized eigenvalue problems

Xν=λ(ΔX)ν andZν=λ(ΔZ)ν.

Since algorithms for solving generalized eigenvalue problems prefer to have the matrix on the right-hand-side be positive definite [17], it is better computationally to find the maximum eigenvalues λmax and λmax of the respective problems

ΔXν=λXν andΔZν=λZν.

Thus

αX={1λmaxifλmax>0otherwise,

and

αZ={1λmaxifλmax>0otherwise.

Once these two allowed maximum step-sizes are determined, then the step size α is taken as follows

α=min(1,ρmin(αX,αZ)):ρ(0,1).

For specifying the barrier parameter μ>0, it is easily seen from the last equation in (3) that μ=XZσn.

3. An infeasible path-following algorithm for CQSDO

We present an infeasible path-following interior-point algorithm for computing an optimal solution of CQSDO that uses the primal-dual interior-point framework proposed by many authors. In each iteration the algorithm starts with guesses (matrices) X0,Z00,y0m not necessarily feasible but only symmetric positive definite. We would like to update these matrices until we are within our desired tolerance of satisfying equations. We will stop our algorithm when the

max(𝒟F,𝒫2,nμ)

is small enough.

Algorithm 1 The generic IFIPA for CQSDO.
Input:
  An accuracy parameter ϵ>0;
  initial guesses (X0,Z00,y0m) and μ>0;
begin
k:=0;
While max(𝒟kF,𝒫k2,nμk)>ϵ do
Compute (ΔXk,Δyk,ΔZk) by solving system (5);
Determine a step-size α>0 s.t. Xk+αΔXk0 and Zk+αΔZk0;
Update Xk+1:=Xk+αΔXk, yk+1:=yk+αΔyk, Zk+1:=Zk+αΔZk;
k:=k+1;
endWhile
end.

4. Numerical results

In this section, we implemented Algorithm 1 in the software Matlab environment and run it on a personal computer. In the implementation, we take ϵ[104, 106] as our tolerance and (X00,y0,Z00) stand for the initial guessing point of the algorithm. In below tables of the obtained numerical results, the number of iterations and the time obtained by the algorithm are denoted by “Iter” and “CPU”, respectively. Our testing examples are inspired from different well known optimization problems. For each example, (X,y,Z) denotes an approximated primal-dual optimal solution for CQSDO problems.

Example 1.

Consider the CQSDO problem whose primal-dual pair 𝒫 and 𝒟 have the following data:

𝒬(X)=0𝒮4,A1=[0.9001.5030.75000.751.09801.5000.5],

A2=[1.4141.386001.3861.7321001200002],C=[1.70710.69310.100.69311.3660.50.020.10.52000.0200]

A3=diag(1, 0.5, 1.333,0.333),b=[7, 4, 2].

The initial point is defined as follows

X0=[100.1000.500.020.101000.0201],y0=[00.50],Z0=I.

The obtained primal-dual optimal solution is

X=[0.44191.00910.38490.23361.00912.30440.87900.53350.38490.87900.33530.20350.23360.53350.20350.1235],y=[0.20150.16560.1603],

Z=[1.13140.46360.10000.30230.46360.39460.51440.02000.10000.51441.233800.30230.020000.4853].

Example 2 ([4]).

The semidefinite least squares optimization, (SDLS) is a convex optimization problem which is defined as follows:

{minXf(X)=12BXNF2s.t.AiX=bi,i=1,,m,X0,

where bm and N,B𝒮n. Because

12BXNF2=12B2XX(NBX+BNX)/2+12NN,

then, the SDLS can be restated as a CQSDO problem with

f(X)=CX+12X𝒬(X)+12NN,𝒬(X)=B2XandC=(NB+BN)/2.

For the size (m=5,n=7), the data of the SDLS is stated as follows:
A1=diag(6.4, 1.03, 1.03, 8.21, 1.69, 0, 4.2),b=[4, 4, 9, 2.16, 3],A2=diag(1.22, 3, 3.33, 0, 0, 0,2, 0),A3=diag(0, 0, 6.67, 4, 1, 0,8, 0),

A4=[0.6645.60005.940001.6005.608.8800000003.9300001.600000000003.0305.9000009],

A5=[0.110.20002.8281.410.226.701.50006.77.60000000000001.5000002.82800007.601.4000008],
N=[1.37619.7582.7110.10205.421.48519.7583.50111.2870.0323.4870.004302.71111.28727.2520.06700.2870.1750.1020.03290.0674.70480.0150003.487500.0150.50.000805.42050.00430.287700.000816.072501.48500.17500023.678]
B=[0.994710.20.3705002.32841.410.20.33356.70.02091.50.000800.37056.78.1762000000.020900.445200001.5000.5002.32840.00080007.101.4000006.945].

The initial point is defined as follows

X0=[1.400.25000000.5500.0200.00100.2501.7000000.0201.7000000010000.001000100000001],y0=[0.0.7500.750],

Z0=[2.10600.017000.5001.181800.00160000.01700.9000000.00160100000001000.50000100000001.9].

The approximated primal-dual optimal solution is

X=[0.9380.14640.3680.20520.08550.03590.0020.14640.25920.0410.0480.12110.09260.0720.3680.04191.4940.0440.08570.17020.0430.20520.04800.0442.28750.27400.06160.0520.08550.12110.0850.2740.10100.06680.0020.03590.09260.1700.06160.06680.75940.0410.00210.07290.0430.05230.00180.04131.337]

Z=[00.000700.00020.0010.000200.00070.09830.00580.02110.1960.0260.005400.00580.00040.00130.0110.00150.00030.00020.02110.00130.00450.0420.00560.00120.0010.1960.01170.04220.3930.0520.0110.00020.0260.00150.00560.050.00690.001400.00540.00030.00120.0110.00140.0003]

y=[0.0849, 0.7007, 0.1591, 1.0552, 0.0357].

Example 3.

This example is reformulated from the following Nearest Correlation Matrix Problem (NCMP):

(𝒫){minXf(X)=12XNF2s.t.AiX=bi,i=1,,m,X0.

Here, f(X)=NX+12X𝒬(X)+12NN, 𝒬(X)=XandC=N.

For the size m=4, n=8, the data of NCMP is given by

A1=[1.200.30.2200010205.300000.30001.870000.225.3000000001.8701000000003.5400000040010000003]

,

A3=[62.55006.30002.555000700001.1000000004.4006.0306.30000000070002000006.03000.22000000002],
A4=[0.110.20002.8281.4310.226.701.5000007.6000000000000001.50000001.732100007.6001.4000001.05030000003],

b=[0.441114.5],A2=[0.6645.60009.50400010.60005.608.8000000003.30000010.6000000000003.03009.5000006.9000000004],

N=[0.77210.654.201001.3046.0752.2510.652.76800.00059.0750.001004.201012.2860000000.000502.461000009.0750000001.3040.0010007.972006.075000004.44602.250000005.25].

The initial point is defined as follows:
X0=[0.90400.00250000000.5500.001900.001000.002501.0070000000.001901.00700000000100000.0010001000000001.03000000001],

y0=[0, 0.25, 0, 0.3, 0],

Z0=[1.10600.0013000.0050001.81800.001400000.001300.9930000000.001400.9930000000010000.500001000000000.9708000000001].
An approximated optimal solution is:

X=[0.42530.19030.02510.06330.14880.17090.08910.15360.19030.09320.00440.04190.0560.13390.03710.06170.02510.00440.60.00060.05430.00080.00010.00140.06330.04190.00060.22190.01070.00160.19560.00090.14880.0560.05430.01070.07410.00060.0180.06000.17090.13390.00080.00160.00060.55760.10370.01690.08910.03710.00010.19560.0180.10370.20440.02370.15360.06170.00140.00090.06000.01690.02370.0644]


Z=[0.34860.66080.00080.05690.10090.04660.04230.09970.66081.46890.00440.11340.13790.14460.03710.06170.00080.00440.00010.00060.00070.00080.00010.00140.05690.11340.00060.04290.01070.00160.04340.00090.10090.13790.00070.01070.04470.00060.0180.060.04660.14460.00080.00160.00060.02250.01390.01690.04230.03710.00010.04340.0180.01390.05590.02370.09970.06170.00140.00090.060.01690.02370.1096]

y=[0.0294, 0.2472, 0.0396, 0.3746].

Example 4.

This example of CQSDO is reformulated from the computation of the smallest eigenvalue of a symmetric positive definite matrix denoted by (EVP):

λmin(B)={minxf(x)=xBxs.t.x2=1.

The EVP becomes a CQSDO as follows:

λmin(B)={minXf(X)=BXs.t.IX=1,X0,

since

xBx=tr(xBx)=tr(Bxx)=tr(BX)=BX,

and

x22=xx=tr(xx)=tr(xx)=tr(XI)=IX

with X=xx. For the size n=8, we consider the following EVP where its data is given by

B=[7.290104.3010040013.2907.2020021015.386900003.3007.205.69000004.3010004.496900000200013.250010000006.7600403.30000100020001001].

The initial point is defined as follows: Z0=2I,y0=0.5, and

X0=[9.2116.75111104.4111.112511.484512.91036.75110.14111100.511.484513.92611110311112110312.911121031111115030000000104.430.53333010].

An approximated optimal primal-dual solution is:

X=[00000000000.145800.185400.0007000.300300000000000.185400.235700.0008000.381800000000000.000700.000800000.001300000000000000000000.300300.381800.0013000.6185]


Z=[7.26340104.3010040013.263407.2020021015.360300003.3007.205.6634000004.3010004.470300000200013.22340010000006.733400403.300009.97340020001000.9734]

y=0.0266,

finally we get p=d=λmin(B)=0.0266. With the help of Matlab, the exact spectrum of B, denoted by Sp B is given by

Sp(B)={0.0266,0.693,1.991,6.76,6.9907,11.6838,12.7608,17.805,18.4509}.

So it is clear that our algorithm gives the exact smallest eigenvalue of B.

Example 5 ([12]).

This example is reformulated from the following Max-cut problem (MCP):

(𝒞𝒫){maxxf(x)=14xCxs.t.xi{1,1}n,

where its reformulation as a CQSDO is as follows:

{maxXf(X)=CXs.t.diag(X)=14e,X0,

with X=14xx, the matrix C is called the Laplacian matrix associated with the graph. For the size n=m=6, we consider the following MCP where

C=[0.52250.10.0750.3325000.10.592500.10.27500.07500.250.275000.33250.10.2750.9750.33480.325000.27500.33480.51520.25750000.3250.25750.25].

The initial point is defined as follows

Z0=2I,y0=0.2e,

and

X0=[0.50.7250.12500.27500.7251.7150.57500.522500.1250.5750.42250000000.25000.2750.5225000.552570.2500000.250.5].

An approximated optimal primal-dual solution is:

X=14[111111111111111111111111111111111111]
Z=[0.50770.10.0750.3325000.10.476800.10.27500.07500.34960.275000.33250.10.2751.36810.33470.32500.27500.33470.86710.25750000.3250.25750.5806],
y=[1.0302, 1.0693, 0.5996, 2.3431, 1.3823, 0.8305].

In Table 1, the number of iterations and the elapsed time for each problem are summarized.

Algorithm 1
(n,m) ITER CPU
Example 1 (4,3) 11 0.0528
Example 2 (7,5) 15 0.3887
Example 3 (8,4) 12 0.5901
Example 4 (9,1) 13 0.0506
Example 5 (6,6) 40 0.0279
Table 1. Number of iterations and CPU time for the previous examples.

4.1. Comparison study

In this subsection, in order to compare our obtained numerical results, we suggest beside the first alternative described in subsection 2.5 where we denote it by Alternative 1, a second alternative.

4.1.1. Alternative 2

The latter was suggested by Touil et al. [23] for solving the SDO problems using a feasible starting point. Here we adapted it for our IFIPA.

This alternative is described as follows, let

αX={1λ¯XδXn1ϵif1λ¯XδXn1>0andmini=1nλi(ΔX)<0ωif1λ¯XδXn1<0andmini=1nλi(ΔX)<01ifmini=1nλi(ΔX)>0, such that

λ¯X=1ni=1n(LX1ΔXLX)ii,
δX2=1ni=1nj=1n(LX1ΔXLX)ii2λ¯X2,

λi(X),i=1,,n, are the eigenvalues of LX1ΔXLX,ω is a small positive real and X=LXLX is the Cholesky factorization.

We mention that the same formula αZ with respect to the dual variable Z. The numerical results obtained through these enhancements are presented in Table 2. For consistency, all experiments were conducted under the same parameters, μ, ϵ, and ρ, to ensure a fair comparison.

Alter 1 Alter 2
Example 1 (4, 3) Iter       11       23
CPU       0.0528       0.0877
Example 2 (7, 5) Iter       15       24
CPU       0.3887       0.6201
Example 3 (8, 4) Iter       12       21
CPU       0.5901       1.1124
Example 4 (9, 1) Iter       13       32
CPU       0.0506       0.1536
Example 5 (6, 6) Iter       40       67
CPU       0.0279       0.0651
Table 2. Number of iterations and CPU time for the ameliorated Algorithm.

4.2. Analysis

Results indicate that Alter 1 often demonstrates improved convergence rates across multiple problem types, especially in cases involving complex data matrices or stricter tolerance levels. While Alter 2 is competitive, particularly in problems with simpler structure or fewer constraints, where it shows fewer iterations yet longer CPU times. Overall, these findings emphasize that Alter 1 (Algorithm 1) offers significant advantages for CQSDO problems, balancing computational efficiency with robustness. These comparatives confirm that this algorithm is effective and show that it could be useful for a wide range of complex tasks in semidefinite programming.

5. Conclusion and future work

In this paper, we implemented an infeasible primal-dual IPA for solving CQSDO based on AHO search directions and on efficient step-sizes for computing an approximated optimal solution of it. The advantage of this algorithm is that it can be started with any initial arbitrary symmetric positive definite matrix. The obtained numerical results on a set of problems which are taken from different benchmarked examples like NCMP, SDLS, the Max-Cut problem and eigenvalue problems are very encouraging. Finally, using other symmetrization scheme for computing the search directions remains a good topic of research in the future.

References