Department of Policy and Planning Sciences
Discussion Paper Series

No.1389

Post-Processing with Projection and Rescaling Algorithms for
Semidefinite ProgrammingbyShin-ichi Kanoh and Akiko Yoshise
January 19, 2024

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPAN

Post-Processing with Projection and Rescaling Algorithms for
Semidefinite Programming
Shin-ichi Kanoh∗and Akiko Yoshise†
January 19, 2024

Abstract
We propose the algorithm that solves the symmetric cone programs (SCPs) by iteratively calling
the projection and rescaling methods the algorithms for solving exceptional cases of SCP. Although
our algorithm can solve SCPs by itself, we propose it intending to use it as a post-processing stepfor interior point methods since it can solve the problems more efficiently by using an approximate
optimal (interior feasible) solution. We also conduct numerical experiments to see the numerical performance of the proposed algorithm when used as a post-processing step of the solvers implementing
interior point methods, using several instances where the symmetric cone is given by a direct productof positive semidefinite cones. Numerical results show that our algorithm can obtain approximate
optimal solutions more accurately than the solvers. When at least one of the primal and dual problems did not have an interior feasible solution, the performance of our algorithm was slightly reduced
in terms of optimality. However, our algorithm stably returned more accurate solutions than thesolvers when the primal and dual problems had interior feasible solutions.

1

Introduction

Let E be a real-valued vector space with an inner product ⟨·, ·⟩. Consider the following symmetric cone
programs (SCPs):
(P)
(D)

inf
x

sup

⟨c, x⟩ s.t. Ax = b,
⊤

b y

s.t.

x ∈ K,∗z = c − A y, (z, y) ∈ K∗ × Rm ,(z,y)

where K ⊆ E is a symmetric cone, K∗ is a dual cone of K, i.e., K∗ = {s ∈ E : ⟨s, x⟩ ≥ 0, ∀x ∈ K},
A : E → Rm is a linear operator, b ∈ Rm , c ∈ E and A∗ : Rm → E is the adjoint operator of A, i.e.,⟨Ax, y⟩ = ⟨x, A∗ y⟩ for all x ∈ E and y ∈ Rm . Note that K∗ = K holds since K is a symmetric cone. If
we choose a positive semidefinite cone as a conic constraint, SCP results in semidefinite programming(SDP). In this study, we are mainly interested in the case where K is a Cartesian product of p simplerr
positive semidefinite cones Sr+1 , . . . , S+p , i.e., K = Sr+1 × · · · × S+p .
Interior point methods are among the most popular and practical algorithms to solve SCPs. In addition
to its practical performance, interior point methods have the theoretical strength of a polynomial-time∗ Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573,
and Japan Society for the Promotion of Science, 5-3-1 Kojimachi, Chiyoda-ku, Tokyo 102-0083, Japan. email:s2130104@s.tsukuba.ac.jp† Corresponding author. Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba, Ibaraki
305-8573, Japan. email: yoshise@sk.tsukuba.ac.jp

1

algorithm and have been implemented in many solvers. Recently, projection and rescaling methods were
proposed as new polynomial-time algorithms for the special case of SCP by Lourenço et al. [15], andKanoh and Yoshise [12]. Their studies were motivated by a work by Chubanov [5]. A similar typeof algorithm, although not a polynomial-time algorithm, was proposed by Peña and Soheili [20]. The
numerical result of [12] showed that projection and rescaling algorithms solved ill-conditioned instances,i.e., instances with feasible solutions only near the boundaries of the cone, more stably than the commercial solver Mosek. It is well known that in iterations of interior point methods, the closer the current
solution moves to the optimal solution, the more difficult it becomes to compute the search direction
accurately. In other words, interior point methods cannot work stably near the boundaries of the cone.
Therefore, the numerical results of [12] motivated us to use projection and rescaling algorithms to solve
general SCPs more accurately.
In this study, we propose the algorithms to find approximate optimal solutions to (P) and (D) using
projection and rescaling algorithms as an inner procedure. Although the proposed methods can findapproximate optimal solutions to (P) and (D) by themselves, they can work more efficiently by using
an approximate optimal (interior feasible) solution. To take advantage of this feature, the proposed
algorithm is designed to be used as a post-processing step for interior point methods. We also conduct
numerical experiments to compare the performance of our algorithm with the solvers.
The main contribution of this study is to provide comprehensive numerical results showing whether
the projection and rescaling algorithms can be used to obtain accurate optimal solutions, which willlead to the development of practical aspects of the projection and rescaling methods. We now mention
two studies [10, 11] focusing on accurately solving SDP. SDPA-GMP [10] is a very accurate SDP solverthat executes the primal-dual interior point method using multiple-precision arithmetic libraries. Using
multiple-precision arithmetic enhances the accuracy of the solution but, at the same time, increases
the computational time. In [11], Henrion, Naldi and Din proposed an algorithm that solves Linear
matrix inequality (LMI) problems in exact arithmetic, which means that their algorithm can be used
to check the feasibility of dual SDPs. Although their algorithm can accurately solve small LMI problems, it is unsuitable for moderate or large problems due to exact computations. This study differsfrom these previous studies in that it focuses on the projection and rescaling methods. Furthermore,this study differs from these studies in that it proposes an algorithm that can be used in a postprocessing step. Our algorithm is available on the website: https://github.com/Shinichi-K-4649/
Post-processing-using-projection-and-rescaling-methods.git
We developed our algorithm for SDP. The theoretical foundations of our algorithm discussed in Section
3 hold for SCP.

1.1

Motivation

The primary motivation for focusing on solving SDP accurately is to address the practical barriers
that prevent the implementation of the Facial Reduction Algorithm (FRA) [4, 3, 19, 32]. The FRA isa regularization technique to address SDP that does not satisfy Slater’s condition and was developed
originally by Browein and Wolkowicz [4, 3].
We say that (P) satisfies Slater’s condition or (P) is strongly feasible if there exists a vector x ∈ intK
satisfying Ax = b, where intK is an interior of K. Similarly, Slater’s condition holds for (D) if there
exists z ∈ intK∗ satisfying c − A∗ y = z. If (P) and/or (D) do not have the interior feasible solutions,
optimal solutions might not exist, and a duality gap might exist [28, 17, 30], which prevents interior
point methods from working stably.
The FRA transforms SDP with no interior feasible solution into SDP satisfying Slater’s condition or
detects its infeasibility, without changing the optimal value by iteratively projecting the cone into a2

specific subspace. Let us briefly see how the FRA works for (P) here. If (P) has no interior feasible
solution, then there exists a vector f ∈ Rm such that b⊤ f ≥ 0 and −A∗ f ∈ K∗ \ {0}, see Proposition 2.4
in Section 2.1. If b⊤ f = 0 holds, f is called a reducing direction for (P). Otherwise, f is an infeasibility
certificate for (P). The FRA first finds such a vector. If a reducing direction is obtained, then the FRA
generates a new problem with a feasible region equivalent to the feasible region of (P) by replacing theconic constraint K with K ∩ {−A∗ f }⊥ , where {−A∗ f }⊥ is the space of elements orthogonal to −A∗ f .
If a reducing direction exists for a new problem, the FRA tries to find it and generates a new reduced
problem again. The FRA repeats the above process until an infeasibility certificate for a reduced problem
or a strongly feasible problem whose feasible region is equivalent to the feasible region of (P). Thus, one
iteration of the FRA is equivalent to solving a certain SDP to find a reducing direction or an infeasibility
certificate. For example, implementation at the initial iteration of the FRA for (P) corresponds tosolving the following auxiliary system.
(AUX-P)find f ∈ Rmb⊤ f ≥ 0, −A∗ f ∈ K∗ \ {0}.

s.t.

Therefore, what is required to implement the FRA is to solve the auxiliary systems exactly. However,this requirement is inaccessible for the current solvers because the auxiliary systems rarely satisfy Slater’s
condition. Despite such a barrier to implementing the FRA, several studies have conducted the facial
reduction scheme for some problems that arise in applications [36, 33, 13, 31]. These studies directly
obtain reducing directions using the structure of the problem without solving the auxiliary systems
numerically.
While these approaches, recently, an implementation of the FRA for any SDP has been studied [22, 37,
21, 16]. Permenter and Parrilo [22], and Zhu, Pataki and Tran-Dinh [37] proposed a practical facial
reduction scheme. The common idea of these two studies is that instead of solving an auxiliary system,
we solve another problem whose feasible region is contained in the feasible region of the original auxiliary
system. Although their algorithms might not recover the interior feasible solutions or detect infeasibility,
we can easily implement them. The algorithms of [22] and [37] can be implemented using only LP solvers
and eigenvalue decomposition, respectively.
Permenter, Friberg and Andersen [21], and Lourenço, Muramatsu and Tsuchiya [16] proposed an algorithm solving for arbitrary SDP based on a facial reduction scheme. Permenter, Friberg and Andersen[21] showed that reducing directions for (P) and (D) can be obtained from relative interior feasible solutions to a self-dual homogenous model of (P) and (D). In addition, based on this result, they proposed atheoretical algorithm for solving arbitrary SDP. We remark that their algorithm finds reducing directions
only when needed, unlike the conventional FRA. Even if (P) and/or (D) do not satisfy Slater’s condition,
their algorithm directly obtains the optimal solution as long as a complementary solution for (P) and(D) exists. However, their algorithm requires an oracle that returns relative interior feasible solutions
to the self-dual homogenous model of (P) and (D). Although such solutions are theoretically obtainedusing an interior point method tracking a central path, the numerical experiments of [21] showed practical barriers. On the other hand, the algorithm of [16] requires only an oracle that returns the optimal
solution to (P) and (D) satisfying Slater’s condition, which is a milder requirement than [21]. In [16],the authors showed that solving the auxiliary systems can be replaced by solving a certain SDP withprimal and dual interior feasible points. This study shows that the first step toward fully implementing
the FRA is to solve SDP with primal and dual interior feasible points as accurately as possible.
One might think this goal is already achievable with the current SDP solvers. However, the accuracyof the solution that satisfies the termination tolerances specified by the solvers will not be sufficient fora stable execution of the FRA. Furthermore, setting the value of the termination tolerances too small
can lead to numerical instability of interior point methods. Thus, it is worth studying how to solve SDP
more accurately than ever before.
To see practical barriers to implementing the FRA, let us consider a simple SDP:

3

Example 1.1.
*1
(Ex1.1) inf 0
x
0

0
1
0

 +
*1
0
1
0 , x
s.t
1
0
*0
0
0
*0
0
1

 +
1 0
0 0 , x = 1,
0 0
+
0 0
1 0 , x = 0,
0 0
+
0 1
0 0 , x = 0,0 2
x ∈ S3+ .

The optimal value of (Ex1.1) is 1. This problem is feasible but not strongly feasible. Indeed, any feasible
solution x ∈ S3+ to (Ex1.1) can be represented as
1 0 −tx =  0 0 0 ,
−t 0 twhere t is a real value such that 0 ≤ t ≤ 1. Thus, using a reducing direction, we can reformulate (Ex1.1)
over a lower dimensional positive semidefinite cone. Any reducing direction f ∈ R3 for (Ex1.1) can be
represented as (0, −k, 0)⊤ , where k > 0. Indeed, the following holds for such a vector f .


0 0 0
b⊤ f = 1 × 0 + 0 × (−k) + 0 × 0 = 0, and − A∗ f = 0 k 0 ∈ S3+ .
0 0 0⊤
Since −A∗ f ∈ S3+ , the region S3+ ∩ {−A∗ f }⊥ can be represented as S3+ ∩ {−A∗ f }⊥ = U S3−r
+ U , where∗
3×3−r
r is a rank of −A f and U ∈ R
is a matrix whose columns are the eigenvectors corresponding to
the zero eigenvalues of −A∗ f . Suppose that U is given by
1 0
U = 0 0 .
0 1

Then, we can generate a reduced problem with interior feasible points as follows:

 

 
1 0
1 0
inf
, x̄
s.t
, x̄ = 1,0 1x̄0 0 
0 0, x̄ = 0,0 0 
0 1, x̄ = 0,
1 2x̄ ∈ S2+ .
Let us apply the FRA to this problem using the commercial solver Mosek. First, we computed the
reducing direction with Mosek by using the formulation proposed in [16] (see Section 4.3.1). Then, thefollowing vectors were obtained.

3.46e-09-3.46e-09 -3.46e-09 1.50e-08.
0fMosek = -4.00e-00 and − A∗ fMosek = -3.46e-09 4.00e-00-1.50e-08
1.50e-0803.00e-08

4

Table 1: Comparison of the reduced problems

Thresholds

S3+ ∩ {−A∗ fMosek }⊥Computed optimal value of the reduced problem

Tλ = 1e-7
Tλ = 1e-8

U S2+ U ⊤U S1+ U ⊤1
infeasible

The eigenvalue decomposition of −A∗ fMosek was computed as follows:-9.20e-0900⊤ PMosek
0
3.57e-08
0−A∗ fMosek = PMosek ,00
4.00e-00
where PMosek ∈ R3×3 is a matrix whose columns are the eigenvectors corresponding to the eigenvalues of−A∗ fMosek . Next, we generated a reduced problem. To identify S3+ ∩ {−A∗ fMosek }⊥ , for each eigenvalueof −A∗ fMosek , we must correctly determine whether it is zero or not. In this example, we estimatedeigenvalues of −A∗ fMosek are zero if they are less than a threshold Tλ . Table 1 shows that the computed
optimal value of the reduced problem is very sensitive to the value of Tλ . If the threshold Tλ is set to
1e-7, the rank of −A∗ fMosek is 1, yielding a reduced problem with an optimal value very close to 1. On
the other hand, if the threshold Tλ is set to 1e-8, the rank of −A∗ fMosek is 2. Then, solving this reduced
problem with Mosek, we obtained the infeasibility certificate.
Let us now compute the reducing direction using our algorithm proposed in Section 4 and the approximate optimal solution returned by Mosek. The computed reducing direction was as follows.

-7.34e-14 -7.34e-14 4.90e-14
7.34e-14.
0fPro = -4.00e-00 and − A∗ fPro = -7.34e-14 4.00e-00
4.90e-1409.80e-14-4.90e-14
The eigenvalue decomposition of −A∗ fPro was computed as follows:-8.67e-1400⊤ PPro0
1.11e-13
0−A∗ fPro = PPro ,00
4.00e-00
where PPro ∈ R3×3 is a matrix whose columns are the eigenvectors corresponding to the eigenvalues of−A∗ fPro . The proposed method found a more accurate solution to the formulation proposed in [16],resulting in a higher accuracy of the computed reducing direction. The behavior of the FRA is morestable if the reduced problem is generated using the vector fPro rather than the vector fMosek . From thisexample, we can see that a more accurate method of solving SDP is very effective in obtaining accurate
reducing directions and that accurate reducing directions are essential for a stable execution of the FRA.

1.2

Structure of this paper

The remainder of this paper is organized as follows. Section 2 is devoted to some preliminaries andnotations. We review the feasibility statuses of SCP and the projection and rescaling algorithm proposedby Kanoh and Yoshise [12]. Section 3 presents the theoretical foundations of our algorithm and explains
our algorithm. We also describe a practical version of our algorithm that employs some implementation
strategies. Section 4 presents numerical results showing that our algorithm stably obtains optimal
solutions with higher accuracy than the solvers. The conclusions are summarized in Section 5.

5

2

Preliminaries and Notations

This section describes the preliminaries and notations used throughout this paper. Section 2.1 provides
an overview of SCP, focusing on the feasibility statuses. Section 2.2 briefly introduces Euclidean Jordan
algebras. Although our algorithm uploaded on the website is an algorithm for solving SDP, its theoreticalfoundations can be extended to SCP without problems. The algorithm for SCP can be concisely describedusing Euclidean Jordan algebras. Thus, we summarize the minimum knowledge of Euclidean Jordan
algebras required to understand this study. Section 2.3 briefly describes the projection and rescaling
algorithm proposed by [12], which is used in our algorithm. Our algorithm employed the algorithm of[12] because the numerical results in [12] showed that their algorithm was superior to the other methods
in terms of computation time.

2.1

Feasibility classes of SCP

Let θp ∈ R ∪ {±∞} and θd ∈ R ∪ {±∞} be the primal and dual optimal values, respectively. If (P)is infeasible, θp takes +∞ and if (D) is infeasible, θd takes −∞. By C ⊥ ⊆ E, we denote the space ofelements orthogonal to a set C ⊆ E. Here, we review four different mutually exclusive feasibility classesof SCP. These feasibility classes are defined in the field of conic linear programming. Therefore, in thissection, we purposely leave K∗ as it is. First, let us look at the definition of strong feasibility.
Definition 2.1 (Strongly feasible). We say that (P) is strongly feasible (or satisfies Slater’s condition)
if there exists x ∈ int K satisfying Ax = b. Similarly, we say that (D) is strongly feasible (or satisfies
Slater’s condition) if there exists y ∈ Rm satisfying c − A∗ y ∈ int K∗ .
If primal and dual problems are strongly feasible, θp = θd and the existence of optimal solutions to bothproblems are guaranteed.
Proposition 2.2.
1. If (P) is strongly feasible, then θp = θd . In addition, if (D) is feasible, then(D) has an optimal solution.
2. If (D) is strongly feasible, then θp = θd . In addition, if (P) is feasible, then (P) has an optimal
solution.
Proof. See Theorems 3.2.6 and 3.2.8 in [23].
We next see the characterization of strong infeasibility.
Definition 2.3 (Strongly infeasible). We say that (P) is strongly infeasible if there exists y ∈ Rm suchthat −A∗ y ∈ K∗ and b⊤ y > 0. Similarly, we say that (D) is strongly infeasible if there exists x ∈ K suchthat Ax = 0 and ⟨c, x⟩ < 0.
A vector y ∈ Rm satisfying −A∗ y ∈ K∗ and b⊤ y > 0 is called an improving ray of (D) because y makes(D) unbounded, i.e., θd = +∞, if (D) is feasible. We also call x ∈ K an improving ray of (P) if Ax = 0
and ⟨c, x⟩ < 0. If there exists an improving ray of (P) (or (D)), then we can see that the hyperplane{A∗ y}⊥ (or {x}⊥ ) strictly separates the affine space of (P) (or (D)) and K (or K∗ ), which implies theinfeasibility of (P) (or (D)).
To define the remaining feasibility class, we introduce the following proposition.
Proposition 2.4.
1. (P) is not strongly feasible if and only if there exists y ∈ Rm such that −A∗ y ∈∗∗K , A y ̸= 0 and b⊤ y ≥ 0.
6

2. (D) is not strongly feasible if and only if there exists a nonzero x ∈ K such that Ax = 0 and⟨c, x⟩ ≤ 0.
Proof. See Lemma 3.2 in [32] or Theorems 3.1.3 and 3.1.4 in [6].
Here, we define the following feasibility class.
Definition 2.5 (Weak status). We say that (P) is in weak status if there exists y ∈ Rm such that−A∗ y ∈ K∗ , A∗ y ̸= 0 and b⊤ y = 0. Similarly, we say that (D) is in weak status if there exists a nonzerox ∈ K such that Ax = 0 and ⟨c, x⟩ = 0.
We sometimes divide this class into two classes and call them weakly feasible and weakly infeasible,
respectively. It is understood that a problem is weakly feasible if it is feasible and does not have interior
feasible solutions. Similarly, it is understood that a problem is weakly infeasible if it is infeasible and its
dual does not have an improving ray. See [17] for more details.
A vector y ∈ Rm (or a vector −A∗ y ∈ E) satisfying −A∗ y ∈ K∗ , A∗ y ̸= 0 and b⊤ y = 0 is called a
reducing direction for (P). We also call a nonzero x ∈ K a reducing direction for (D) if Ax = 0 and⟨c, x⟩ = 0. As discussed in Section 1.1, reducing directions are used to regularize problems in the FRA.

2.2

Euclidean Jordan algebras and Symmetric cones

Let E be a real-valued vector space equipped with an inner product ⟨·, ·⟩ and a bilinear operation ◦ :E × E → E, and e be the identity element, i.e.,x ◦ e = e ◦ x = x holds for any x ∈ E. (E, ◦) is called a
Euclidean Jordan algebra if it satisfiesx ◦ y = y ◦ x, x ◦ (x2 ◦ y) = x2 ◦ (x ◦ y), ⟨x ◦ y, z⟩ = ⟨y, x ◦ z⟩
for all x, y, z ∈ E and x2 := x ◦ x. We denote y ∈ E as x−1 if y satisfies x ◦ y = e. c ∈ E is called an
idempotent if it satisfies c ◦ c = c, and an idempotent c is called primitive if it can not be written as asum of two or more nonzero idempotents. A set of primitive idempotents c1 , c2 , . . . ck is called a Jordan
frame if c1 , . . . ck satisfy
ci ◦ cj = 0 (i ̸= j), ci ◦ ci = ci (i = 1, . . . , k),kX

ci = e.

i=1

For x ∈ E, the degree of x is the smallest integer d such that the set {e, x, x2 , . . . , xd } is linearly
independent. The rank of E is the maximum integer r of the degree of x over all x ∈ E. The following
properties are known.
Proposition 2.6 (Spectral theorem (cf. Theorem III.1.2 of [7])). Let (E, ◦) be a Euclidean Jordan
algebra having rank r. For any x ∈ E, there exist real numbers λ1 , . . . , λr and a Jordan frame c1 , . . . , cr
for which the following holds:rXx=
λi ci .
i=1

The numbersPλ1 , . . . , λr are uniquely
Qr determined eigenvalues of x (with their multiplicities). Furthermore,r
trace(x) := i=1 λi , det(x) := i=1 λi .
For any p
x, y ∈ E, we define the inner product ⟨·, ·⟩ and the norm ∥ · ∥ as ⟨x, y⟩ := trace(x◦ y) andPr∥x∥ :=⟨x, x⟩, respectively. For any x ∈ E having spectral decomposition x =λi=1 i ci as in
Proposition 2.6, we also define ∥x∥∞ := max{|λ1 |, . . . , |λr |}.
7

It is known that the set of squares K = {x2 : x ∈ E} is the symmetric cone of E (cf. Theorems III.2.1
and III.3.1 of [7]). The following properties can be derived from the results in [7], as in Corollary 2.3 of[35]:
Pr
Proposition 2.7. Let x ∈ E and let j=1 λj cj be a decomposition of x given by Propositoin 2.6. Then(i) x ∈ K if and only if λj ≥ 0 (j = 1, 2, . . . , r),(ii) x ∈ int K if and only if λj > 0 (j = 1, 2, . . . , r).
A Euclidean Jordan algebra (E, ◦) is called simple if it cannot be written as any Cartesian product of
non-zero Euclidean Jordan algebras. If the Euclidean Jordan algebra (E, ◦) associated with a symmetriccone K is simple, then we say that K is simple. In this study, we will consider that K is given by ar
Cartesian product of p simple positive semidefinite cones Sr+ℓ , K := Sr+1 × · · · × S+p , whose rank andidentity element are rℓ and eℓ (ℓ = 1, . . . , p). The rank r and the identity element of K are given byr=pXrℓ , e = (e1 , . . . , ep ).

ℓ=1

Furthermore, for any x ∈ E1 × · · · × Ep , det(x) =

Qp

ℓ=1

Qrℓ

i=1 λi .

In what follows, xℓ stands for the ℓ-th block element of x ∈ E, i.e., x = (x1 , . . . , xp ) ∈ E1 × · · · × Ep .
For each ℓ = 1, · · · , p, we define λmin (xℓ ) := min{λ1 , · · · , λrℓ } and λmax (xℓ ) := max{λ1 , · · · , λrℓ } where
λ1 , · · · , λrℓ are eigenvalues of xℓ . The minimum and maximum eigenvalues of x ∈ K are given by
λmin (x) = min{λmin (x1 ), · · · , λmin (xp )} and λmax (x) = max{λmax (x1 ), · · · , λmax (xp )}, respectively.
Next, we consider the quadratic representation Qv (x) defined by Qv (x) := 2v ◦ (v ◦ x) − v 2 ◦ x. For the
Euclidean Jordan algebra (E, ◦) such as E = E1 × · · · × Ep , the quadratic representation Qv (x) of x ∈ E
is denoted by Qv (x) = Qv1 (x1 ), . . . , Qvp (xp ) . Letting Iℓ be the identity operator of the Euclidean
Jordan algebra (Eℓ , ◦ℓ ) associated with the cone Kℓ , we have Qeℓ = Iℓ for ℓ = 1, . . . , p. The following
properties can also be retrieved from the results in [7] as in Proposition 3 of [15]:Proposition 2.8. For any v ∈ intK, Qv (K) = K.
More detailed descriptions, including concrete examples of symmetric cone optimization, can be foundin, e.g., [7, 8, 25]. Here, we will explain the bilinear operation, the identity element, the inner product,the eigenvalues, the primitive idempotents, and the quadratic representation of the cone when the cone
is a positive semidefinite cone.
Example 2.9 (K is the semidefinite cone Sn+ ). Let Sn be the set of symmetric matrices of n × n.
The semidefinite cone Sn+ is given by Sn+ = {X ∈ Sn : X ⪰ O}. For any symmetric matricesXand ⟨X, Y ⟩ =X, Y ∈ Sn , P
definePthe bilinear operation ◦ and inner product as X ◦ Y = XY +Y
2nnntr(XY ) =X
Y,
respectively.
For
any
X
∈
S
,
performtheeigenvalue
decomposii=1
j=1 ij ij
tion and
let
u
,
.
.
.
,
u
be
the
corresponding
normalized
eigenvectors
fortheeigenvalues
λ1 , . . . , λ n :1nPn
X = i=1 λi ui uTi . The eigenvalues of X in the Jordan algebra are λ1 , . . . , λn and the primitive idempotents are c1 = u1 uT1 , . . . , cn = un uTn , which implies that the rank of the semidefinite cone Sn+ is r = n.
The identity element is the identity matrix I. The quadratic representation of V ∈ Sn is given by
QV (X) = V XV .

2.3

Projection and rescaling algorithm

For two sets C1 and C2 , we denote by FP(C1 , C2 ) the feasibility problem
find x ∈ C1 ∩ C2 .
8The projection and rescaling algorithms [20, 15, 12] solve FP(L, int K), where K ⊆ E is a symmetriccone and L ⊆ E is a linear subspace. The feasibility of FP(L, int K) is closely related to the feasibilityof FP(L⊥ , K \ {0}), where L⊥ is the orthogonal complement of L. The proof of Proposition 2.10 isstraightforward using Theorem 20.2 of [24] and therefore omitted.
Proposition 2.10. FP(L, int K) is infeasible if and only if FP(L⊥ , K \ {0}) is feasible.
For any k > 0 and feasible solution x of FP(L, int K), since kx is a feasible solution of FP(L, int K), it
makes sense to consider the positive scaled version of FP(L, int K). In [12], they consider the following
feasibility problem. We will denote it by FPS∞ (L, int K) in this study.
find x ∈ L ∩ int K

s.t. ∥x∥∞ ≤ 1.

Proposition 2.11. FP(L, int K) is feasible if and only if FPS∞ (L, int K) is feasible.
Proof. If FPS∞ (L, int K) is feasible, it is clear that FP(L, int K) is feasible.
Let x be a feasible solution of FP(L, int K) and let λmax (x) and λmin (x) be a maximum eigenvalue anda minimum eigenvalue of x, respectively. Since x ∈ int K, we can see that λmax (x) ≥ λmin (x) > 0 andhence λmax1 (x) x ∈ int K. In addition, ∥ λmax1 (x) x∥∞ = 1 holds. Thus, λmax1 (x) x is a feasible solution of
FPS∞ (L, int K).
The projection and rescaling algorithms consist of two ingredients: the “main algorithm” and the “basic
procedure.” The structure of the method is as follows: In the outer iteration, the main algorithm calls
the basic procedure with L and K. The basic procedure proposed in [12] generates a sequence in E
using projection to L and terminates in a finite number of iterations returning one of the following:(i). a solution of problem FP(L, int K), (ii). a solution of problem FP(L⊥ , K \ {0}), or (iii). a cut of
FPS∞ (L, int K), i.e., a Jordan frame {c1 , c2 , . . . , cr } such that ⟨ci , x⟩ ≤ ξ holds for any feasible solution
x of problem FPS∞ (L, int K) and for some i ∈ {1, 2, . . . , r}, where r is a rank of K and ξ is a parameter
specified by the user such that 0 < ξ < 1. If the result (i) or (ii) is returned by the basic procedure, thenthe feasibility of problem FP(L, int K) can be determined, and the main procedure stops. If the result(iii) is returned,
main procedure scales the problem FPS∞ (L, int K) as FPS∞ (Qv (L), int K),
P then the P
where v = √1ξ h∈H ch + h∈H/ ch and H = {i : ⟨ci , x⟩ ≤ ξ}. Then, the main procedure calls the basic
procedure with Qv (L) and K. Noting that v ∈ intK and Proposition 2.8, the feasibility of FP(L, int K)
can be checked by solving FPS∞ (Qv (L), int K). Thus, the projection and rescaling algorithm of [12]checks the feasibility of FP(L, int K) by repeating the above procedures.
Their algorithm has a feature that the main algorithm works while keeping information about theminimum eigenvalues of any feasible solution of FPS∞ (L, int K). That is, their method can determine
whether there exists a feasible solution of FPS∞ (L, int K) whose minimum eigenvalue is greater than ε,where ε > 0 is a parameter specified by the user. In [12], a feasible solution of FPS∞ (L, int K) whose
minimum eigenvalue is greater than or equal to ε is called an ε-feasible solution of FPS∞ (L, int K).

9

Algorithm 1 The projection and rescaling algorithm of [12]1: Input: L, K, ε > 0 and a constant ξ such that 0 < ξ < 1.
2: Output: A solution to FP(L, int K) or FP(L⊥ , K \ {0}) or a certificate that there is no ε feasible

solution to problem FPS∞ (L, int K).
3: initialization: k ← 1, Lk ← L
4: Call the basic procedure with Lk , K and ξ.
5: if a solution to FP(Lk , int K) is obtained then
6:
Rescale the obtained solution to the solution of FP(L, int K)
7:
return the solution to FP(L, int K)⊥

8: else if a solution to FP(Lk , K \ {0}) is obtained then9:
Rescale the obtained solution to the solution of FP(L⊥ , K \ {0})10:return the solution to FP(L⊥ , K \ {0})11: else
12:
Compute an upper bound for the minimum eigenvalue of any feasible solution of FPS∞ (L, int K)
13:
if the computed upper bound is less than ε then14:
stop Algorithm 1 (There is no ε feasible solution to FPS∞ (L, int K).)
15:
end if16:
Compute the vector v used to scale the problem
17: end if
18: Scale the linear subspace, i.e., Lk+1 ← Qv (Lk )19: k ← k + 1. Go back to line 4.

3

Proposed algorithms

Since projection and rescaling algorithms can only solve the special case of SCP, i.e., FP(L, int K) fora linear subspace L ⊆ E, we consider how to use projection and rescaling algorithms to obtain an
approximate optimal solution to (P) or (D). In Section 3.1, we introduce two types of formulations towhich projection and rescaling methods can be applied. These formulations require a real value θ ∈ R,
and their feasibilities depend on the value of θ. In Section 3.1.1, we introduce the formulation that gives
the interior feasible solution x of (P) such that ⟨c, x⟩ < θ when (P) is strongly feasible and θ > θp . In
Section 3.1.2, we introduce the formulation that gives the interior feasible solution (y, z) of (D) suchthat b⊤ y > θ when (D) is strongly feasible and θ < θd . Then, we present a basic idea of our algorithm
in Section 3.2. We also discuss some implementation strategies of our algorithm in Section 3.3. We thendevelop a practical version of our algorithm in Section 3.4.

3.1

Theoretical foundations

3.1.1

Primal modelLet θ ∈ R. For θ, let us define the linear operator A(θ) as follows:A −b 0A(θ) = ⊤.
c−θ 1
We define the symmetric cone K̄ = K × R2+ and consider the feasibility problem FP(kerA(θ), int K̄).
Proposition 3.1. Suppose that FP(kerA(θ), int K̄) is feasible and (x, τ, ρ) is a feasible solution of it.
Then, τ1 x is an interior feasible solution to (P), and ⟨c, τ1 x⟩ < θ holds.
10

Proof. Since (x, τ, ρ) is a feasible solution of FP(kerA(θ), int K̄), Ax − τ b = 0 and ⟨c, x⟩ − τ θ + ρ = 0
hold. Noting that τ > 0, we have A τ1 x − b = 0 and ⟨c, τ1 x⟩ − θ + τρ = 0 and hence, τ1 x is an interior
feasible solution of (P) such that ⟨c, τ1 x⟩ < θ because x ∈ int K and ρ > 0.
From Proposition 3.1, if we obtain the feasible solution of FP(kerA(θ), int K̄), then we can construct theinterior feasible solution to (P) whose objective value is smaller than θ. The following proposition gives
us a necessary and sufficient condition for FP(kerA(θ), int K̄) to be feasible.
Proposition 3.2. FP(kerA(θ), int K̄) is feasible if and only if (P) is strongly feasible and θp < θ.
Proof. If FP(kerA(θ), int K̄) is feasible, then there exists a feasible solution (x, τ, ρ) to FP(kerA(θ), int K̄).
For x and τ , τ1 x is an interior feasible solution to (P) satisfying ⟨c, τ1 x⟩ < θ from Proposition 3.1, which
implies that (P) has an interior feasible solution and θp ≤ ⟨c, τ1 x⟩ < θ.
Conversely, if (P) is stronlgy feasible and θp < θ, then there exists an interior feasible solution x
to (P) such that θp < ⟨c, x⟩ < θ. We can easily see that (x, 1, θ − ⟨c, x⟩) is a feasible solution forFP(kerA(θ), int K̄).
Combining Proposition 3.2 with Proposition 2.10, we have a necessary and sufficient condition for alter∗
native problem FP(rangeA(θ) , K̄ \ {0}) of FP(kerA(θ), int K̄) to be feasible.
∗

Corollary 3.3. FP(rangeA(θ) , K̄ \ {0}) is feasible if and only if (P) is not strongly feasible or θp ≥ θ.
While feasible solutions of FP(kerA(θ), int K̄) give us interior feasible solutions to (P) whose objective∗
value is smaller than θ, feasible solutions of FP(rangeA(θ) , K̄ \ {0}) give us information about thefeasibility of (P) or a feasible solution to (D) whose objective value is greater than or equal to θ.
∗

Proposition 3.4. Suppose that FP(rangeA(θ) , K̄ \ {0}) is feasible and (z, ω, κ) is a feasible solution of∗FP(rangeA(θ) , K̄ \ {0}). Then, there exists y ∈ Rm such that z = A∗ y + κc and ω = −b⊤ y − κθ. For(y, κ), one of the following three cases holds:
1. κ > 0 meaning that (− κ1 y, c − A∗ ( −1κ y)) is a feasible solution to (D) and its objective value isgreater than or equal to θ,
2. κ = 0 and ω > 0 meaning that −y is an improving ray of (D), i.e., −A∗ (−y) ∈ K and b⊤ (−y) > 0,or
3. κ = ω = 0 meaning that −y is a reucing direction for (P), i.e., −A∗ (−y) ∈ K\{0} and b⊤ (−y) = 0.
∗

Proof. Since (z, ω, κ) ∈ rangeA(θ) , there exists (y, γ) ∈ Rm+1 such that   ∗Ac  zω  = −b⊤ −θ y .
γ
κ0⊤1
From this equation, we can easily see that κ = γ, and hence z = A∗ y + κc and ω = −b⊤ y − κθ hold for(y, κ).
⊤ −1(1): If κ > 0, then −A∗ ( −1κ y) + c ∈ K and b ( κ y) − θ ≥ 0 hold since (z, ω, κ) ∈ K̄ \ {0}.

(2) & (3): If κ = 0, then z = −A∗ (−y) ∈ K and ω = b⊤ (−y) ≥ 0 hold for y since (z, ω, κ) ∈ K̄ \ {0}.
If ω > 0, y satisfies −A∗ (−y) ∈ K and b⊤ (−y) > 0 and hence, −y is an improving ray of (D).
If ω = 0, we can easily see that b⊤ (−y) = 0. In addition, −A∗ (−y) ∈ K \ {0} holds since (z, ω, κ) ̸=(0, 0, 0). Thus, −y is a reducing direction for (P).
11∗

Proposition 3.4 ensures that feasible solutions of FP(rangeA(θ) , K̄ \ {0}) give feasible solutions to (D)if (P) is strongly feasible and (D) is feasible. By adding one more assumption, we can guarantee that∗the feasible solution of FP(rangeA(θ) , K̄ \ {0}) gives the optimal solution of (D).
∗Corollary 3.5. Suppose that (P) is strongly feasible, (D) is feasible, and θ = θp . Then, FP(rangeA(θ) , K̄\{0}) is feasible, i.e., there exists y ∈ Rm such that z = A∗ y + κc and ω = −b⊤ y − κθ for any feasible∗
solution (z, ω, κ) of FP(rangeA(θ) , K̄ \ {0}). Furthermore, (− κ1 y, κ1 z) is an optimal solution for (D).
∗Proof. Since θ = θp , FP(rangeA(θ) , K̄ \ {0}) is feasible by Corollary 3.3. In addition, for any feasible∗
solution (z, ω, κ) for FP(rangeA(θ) , K̄ \ {0}), there exists y ∈ Rm satisfying z = A∗ y + κc and ω =⊤−b y − κθ by Proposition 3.4.
Noting that (P) is strongly feasible and (D) is feasible, we can see that κ > 0 holds for any feasible∗
solution (z, ω, κ) for FP(rangeA(θ) , K̄\{0}) from Proposition 3.4. Thus, (− κ1 y, c−A∗ ( −1κ y)) is a feasible⊤ −1solution for (D) and b ( κ y) ≥ θp holds.
Since (P) is strongly feasible and (D) is feasible, by Proposition 2.2, (D) has an optimal solution andθp = θd and hence, (− κ1 y, c − A∗ ( −1κ y)) is an optimal solution for (D).
3.1.2

Dual modelLet θ ∈ R. We define the linear operator A(θ) and the symmetric cone K̄ in the same way as defined in
Section 3.1.1. In this section, we consider the feasibility problem FP(rangeA(θ)∗ , int K̄).
Proposition 3.6. Suppose that FP(rangeA(θ)∗ , int K̄) is feasible and (z, ω, κ) is a feasible solution of it.
Then, there exists y ∈ Rm such that z = A∗ y + κc and ω = −b⊤ y − κθ. In addition, (− κ1 y, c − A∗ ( −1κ y))is an interior feasible solution to (D), and b⊤ ( −1y)>θholds.
κ
Proof. Since this proposition can be proved in the same way as the proof of Proposition 3.1, we omit
the proof.
Similar to Proposition 3.1, Proposition 3.6 implies that we can construct the interior feasible solutionof (D) whose objective value is greater than θ using the feasible solutions of FP(rangeA(θ)∗ , int K̄)The following proposition gives us a necessary and sufficient condition for FP(rangeA(θ)∗ , int K̄) to befeasible.
Proposition 3.7. FP(rangeA(θ)∗ , int K̄) is feasible if and only if (D) is strongly feasible and θd > θ.
Proof. Since this proposition can be proved in the same way as the proof of Proposition 3.2, we omit
the proof.
Combining Proposition 3.7 with Proposition 2.10, we have a necessary and sufficient condition for alternative problem FP(kerA(θ), K̄ \ {0}) of FP(rangeA(θ)∗ , int K̄) to be feasible.
Corollary 3.8. FP(kerA(θ), K̄ \ {0}) is feasible if and only if (D) is not strongly feasible or θd ≤ θ.
∗

While feasible solutions for FP(rangeA(θ) , int K̄) give us interior feasible solutions to (D) whose objective value is greater than θ, feasible solutions for FP(kerA(θ), K̄ \ {0}) give us information about thefeasibility of (D) or a feasible solution to (P) whose objective value is smaller than or equal to θ.

12

Proposition 3.9. Suppose that FP(kerA(θ), K̄ \ {0}) is feasible and (x, τ, ρ) is a feasible solution ofFP(kerA(θ), K̄ \ {0}). Then, for (x, τ, ρ), one of the following three cases holds:
1. τ > 0 meaning that τ1 x is a feasible solution to (P) and its objective value is smaller than or equalto θ,
2. τ = 0 and ρ > 0, meaning that x is an improving ray of (P), i.e., x ∈ K, Ax = 0 and ⟨c, x⟩ < 0,or
3. τ = ρ = 0 meaning that x is a reucing direction for (D), i.e., x ∈ K \ {0}, Ax = 0 and ⟨c, x⟩ = 0.
Proof. Since this proposition can be proved in the same way as the proof of Proposition 3.4, we omit
the proof.
Proposition 3.9 ensures that feasible solutions for FP(kerA(θ), K̄ \ {0}) provide feasible solutions for (P)if (D) is strongly feasible and (P) is feasible. Similar to Corollary 3.5, by adding one more assumption,
we can guarantee that the feasible solution of FP(kerA(θ), K̄ \ {0}) gives the optimal solution of (P).
Corollary 3.10. Suppose that (D) is strongly feasible, (P) is feasible, and θ = θd . Then, FP(kerA(θ), K̄\{0}) is feasible. In addition, for any feasible solution (x, τ, ρ) for FP(kerA(θ), K̄ \ {0}), τ1 x is an optimal
solution for (P).
Proof. Since this proposition can be proved in the same way as the proof of Corollary 3.5, we omit theproof.

3.2

Basic concept of the proposed algorithm

To briefly illustrate the concept of the proposed method, suppose that (P) is strongly feasible. Then,the feasibility of FP(kerA(θ), int K̄) only depends on the value of θ by Proposition 3.2. If θ > θp ,FP(kerA(θ), int K̄) is feasible and its solution gives an interior feasible solution x to (P) such that⟨c, x⟩ < θ by Proposition 3.1. If θ ≤ θp , FP(kerA(θ), int K̄) is infeasible and the infeasibility certificates∗for FP(kerA(θ), int K̄), i.e., feasible solutions for FP(rangeA(θ) , K̄ \ {0}), give the dual feasible solution⊤
y such that b y ≥ θ by Proposition 3.4. Therefore, the closer the value of θ is to the optimal value of(P) and (D), the more accurate the approximate optimal solution of (P) and (D) obtained by solving
FP(kerA(θ), int K̄). In addition, we can know whether θ > θp or θ ≤ θp by solving FP(kerA(θ), int K̄).
We present our algorithm for finding an approximate optimal interior feasible solution to (P).
Algorithm 2 works as follows. First, Algorithm 2 chooses the input value θk ∈ (LB, U B) and execute a projection and rescaling algorithm with the corresponding problem FP(kerA(θk ), int K̄). Next,
Algorithm 2 performs the operations according to the returned result, as follows:
1. If a solution to (P) is obtained, the current primal solution xtmp and U B are updated.
2. If a solution to (D) is obtained, the current dual solution ytmp and LB are updated.
3. If a reducing direction for (P) or an improving ray of (D) is obtained, then Algorithm 2 terminates.
4. If a projection and rescaling algorithm determines that the minimum eigenvalue of any feasible
solution of the input problem, i.e., FPS∞ (ker A(θk ), int K̄), is less than ε, then LB is updated.

13

Algorithm 2 Projection and rescaling algorithm with the primal model
1: Input: A, b, c, K, and θacc > 0.
2: Output: A feasible solution to (P) or a vector that determines the feasibility status of (P).
3: initialization: k ← 0, LB ← −∞, U B ← ∞, K̄ ← K × R2+
4: Choose θ k ∈ (LB, U B) and constructkA(θ ) =



A
c⊤

−b
−θk


0
.
1

5: Let ε be a sufficiently small positive value and ξ be a constant such that 0 < ξ < 1.
6: while U B − LB > θacc do
7:
Call the projection and rescaling algorithm of [12] with kerA(θk ), K̄, ε, and ξ.
8:
if a solution (x, τ, ρ) to FP(kerA(θk ), int K̄) is obtained then9:
xtmp ← τ1 x, U B ← θk∗else if a solution (z, ω, κ) to FP(rangeA(θk ) , K̄ \ {0}) is obtained then11:
Compute (y, γ) ∈ Rm+1 such that z = A∗ y + γc, ω = −b⊤ y − γθ and κ = γ.
12:
if −y is an improving ray of (D) or a reducing direction for (P) then13:
stop Algorithm 2 and return (−y, A∗ y)
14:
end if∗k15:
ytmp ← −1
κ y, ztmp ← c − A ytmp , LB ← θ
16:
else
17:
LB ← θk18:
end if19:
Choose θk+1 ∈ (LB, U B), k ← k + 1
20: end while
21: return xtmp
10:

14

Algorithm 2 repeats the above operations until U B − LB > θacc holds. U B and LB play the role ofupper and lower bounds on θp , respectively. Thus, if θacc is sufficiently small, the output xtmp from
Algorithm 2 can be seen as an approximate optimal solution to (P).
Here, we note that Algorithm 2 updates LB on line 17. Suppose that Algorithm 2 reaches line 17 at
the k-th iteration. In this case, it can be inferred that the projection and rescaling algorithm terminateswith the same termination criteria with FPS∞ (ker A(θ), int K̄) for any θ such that θ < θk , unless θk is
not too large compared to the maximum value of the objective function in (P). Noting that Algorithm
2 is used as a post-processing step, it is reasonable to update LB as on line 17. We also note that
Algorithm 2 can find an approximate optimal solution to (D). Suppose that Algorithm 2 reaches line
15 at the k-th iteration and θk is very close to the optimal value of (D). Then, (ytmp , ztmp ) satisfiesb⊤ ytmp ≥ θk and c − A∗ ytmp = ztmp ∈ K by Proposition 3.4. However, even if FP(kerA(θk ), int K̄) is
infeasible, the projection and rescaling algorithm does not necessarily return a solution to its alternative
problem. Thus, Algorithm 2 is just a method to find the approximate optimal interior feasible solutionof (P).
From the contents of Section 3.1.2, the algorithm for finding an approximate optimal interior feasible
solution to (D) can be considered similarly. (See Algorithm 3.)
Algorithm 3 Projection and rescaling algorithm with the dual model
1: Input: A, b, c, K, and θacc > 0.
2: Output: A feasible solution to (D) or a vector that determines the feasibility status of (D).
3: Same as lines 3-5 of Algorithm 2
4: while U B − LB > θacc do∗
5:Call the projection and rescaling algorithm of [12] with rangeA(θk ) , K̄, ε, and ξ.
∗
6:
if a solution (z, ω, κ) to FP(rangeA(θk ) , int K̄) is obtained then7:
Compute (y, γ) ∈ Rm+1 such that z = A∗ y + γc, ω = −b⊤ y − γθ and κ = γ.
∗k8:ytmp ← −1
κ y, ztmp ← c − A ytmp , LB ← θk9:else if a solution (x, τ, ρ) to FP(ker A(θ ), K̄ \ {0}) is obtained thenif x is an improving ray of (P) or a reducing direction for (D) thenstop Algorithm 3 and return x
end ifxtmp ← τ1 x, U B ← θkelse
U B ← θk16:
end if17:
Choose θk+1 ∈ (LB, U B), k ← k + 1
18: end while
19: return ytmp

10:
11:
12:
13:
14:
15:

3.3

Implementation strategies

Algorithms 2 and 3 can operate more efficiently by fully utilizing the information obtained at each
iteration. In this section, we modify Algorithm 2 to make it more practical. These modifications canalso be employed in Algorithm 3.

15

3.3.1

Updating LB using a dual feasible solution

Algorithm 2 keeps LB as the lower bound on the θp . If a dual feasible solution (ytmp , ztmp ) is obtainedat the k-th iteration of Algorithm 2, we update LB with θk . Here, we note that b⊤ ytmp ≥ θk by
Proposition 3.4 and all dual feasible solutions give the lower bound on the θp . Therefore, LB can be
updated with b⊤ ytmp instead of θk , which reduces the number of iterations of Algorithm 2. However,
Algorithm 2 obtains approximate feasible solutions in practice. That is, ztmp ∈/ K or b⊤ ytmp < θk might
hold. Considering that (ytmp , ztmp ) might be an approximate dual feasible solution, we update LB as
follows:(max{θk , b⊤ ytmp } ztmp ∈ K
.
(1)
LB :=
θk
otherwise

3.3.2

Keeping and updating a current dual feasible solution

The modification in this section has the same spirit as Section 3.3.1. That is, we update LB using
dual feasible solutions. In the previous section, we propose to update LB as in (1) only if (ytmp , ztmp )is a feasible solution for (D). However, even if (ytmp , ztmp ) is an approximate feasible solution, it canbe used to update LB as long as we have a dual feasible solution (ȳ, z̄). By considering the linear
combination of ytmp and ȳ, (ynew , znew ) might be obtained such that znew = c − A∗ ynew ∈ K andb⊤ ynew ≥ max{θk , b⊤ ȳ}, which leads to reducing the number of iterations of Algorithm 2. In addition,
this modification allows Algorithm 2 to return the current dual feasible solution (ȳ, z̄).
Therefore, the following operations are added to Algorithm 2.
1. Initialize ȳ as ȳ ← ∅. ( If a dual feasible solution y is known in advance, initialize ȳ and LB asȳ ← y and LB ← b⊤ y, respectively.)
2. Suppose that (ytmp , ztmp ) is obtained at the k-th iteration. Then, we perform the following operations.
• If ztmp ∈ K and ȳ is empty, then ȳ = ytmp .
• If ȳ is not empty, compute ynew such that b⊤ ynew ≥ b⊤ ȳ and c − A∗ ynew ∈ K, and thenupdate LB and ȳ as LB = max{θk , b⊤ ynew } and ȳ = ynew , respectively.
3. Return ȳ on line 21 if ȳ is not empty.
In Algorithm 2, ȳ plays the role of the current dual feasible solution. If we have a dual feasible solution
before running Algorithm 2, it can be used to initialize ȳ. Since Algorithm 2 is used as a post-processing
step for the interior point method, ȳ can be initialized with the output of the interior point method.
The method for computing ynew is described in the Appendix A.

3.3.3

Use of scaling information from previous iterations

Algorithm 2 calls the projection and rescaling algorithm of [12] iteratively. It is natural to consider ways
to reduce the computational time of the projection and rescaling algorithm at the k +1-th iteration using
the information obtained by the k-th iteration. Recall that the projection and rescaling algorithm of [12]solves the feasibility problem FPS∞ (L, int K) by repeating two steps: (i). find a cut for FPS∞ (L, int K),(ii). scale the problem to an isomorphic problem equivalent to FPS∞ (L, int K) such that the region
narrowed by the cut is efficiently explored. Therefore, in Algorithm 2, if the cuts obtained by a projection
and rescaling algorithm at the i(< k)-th iteration hold for any feasible solution of the feasibility problem
16

considered at the k-th iteration, such cuts can be used to reduce the execution time of the projection
and rescaling algorithm at the k-th iteration. Proposition 3.11 provides the sufficient condition for a cut
to FPS∞ (kerA(θ̄), int K̄) to be valid for FPS∞ (kerA(θ), int K̄) for two real values θ̄ ∈ R and θ ∈ R.
Proposition 3.11. Suppose that (P) is strongly feasible and that θ̄ ∈ R satisfies θ̄ > θp and θ̄ − θp ≤ 1.
Then, FPS∞ (kerA(θ), int K̄) is feasible for any θ ∈ R such that θp < θ < θ̄. Furthermore, if ⟨v, x̄⟩ ≤ ξx ,τ̄ ≤ ξτ and ρ̄ ≤ ξρ hold for any feasible solution (x̄, τ̄ , ρ̄) of FPS∞ (kerA(θ̄), int K̄) and for some ξx <1, ξτ < 1, ξρ < 1 and v ∈ K, then, for any θ ∈ R such that θp < θ < θ̄ and for any feasible solution(x, τ, ρ) of FPS∞ (kerA(θ), int K̄), ⟨v, x⟩ ≤ ξx , τ ≤ ξτ and ρ ≤ ξρ hold.
Proof. For any θ ∈ R such that θp < θ < θ̄, FPS∞ (kerA(θ), int K̄) is feasible from Proposition 3.2. Let(x, τ, ρ) be a feasible solution for FPS∞ (kerA(θ), int K̄). Then, we have⟨c, x⟩ − τ θ + ρ = 0.

(2)

Noting that τ > 0, we have ⟨c, τ1 x⟩ + τ1 ρ = θ. Since ρ > 0 and τ1 x is an interior feasible solution for (P),θp < ⟨c, τ1 x⟩ < θ < θ̄. Thus, we find1(3)θ̄ − ⟨c, x⟩ < θ̄ − θp .
τLet α = θ̄ − θ. By substituting θ = θ̄ − α into (2), we have⟨c, x⟩ − τ θ̄ + τ α + ρ = 0.

(4)

Since θ̄ − θp ≤ 1 holds from the assumption, we find
τ α + ρ = τ θ̄ − ⟨c, x⟩ (by (4))< τ (θ̄ − θp )(by (3))≤ τ ≤ 1.
Therefore, τ α + ρ < 1 holds, and hence (x, τ, τ α + ρ) is a feasible solution for FPS∞ (kerA(θ̄), int K̄).
From the assumption, ⟨v, x⟩ ≤ ξx , τ ≤ ξτ and τ α + ρ ≤ ξρ hold, which completes the proof.
Based on Proposition 3.11, we add the following operations to Algorithm 2.
1. Initialize v̄ as v̄ ← (e, 1, 1).

2. Call the projection and rescaling algorithm with Qv̄ kerA(θk ) and K̄ to solve FP(kerA(θk ), int K̄).
• Suppose that the projection and rescaling algorithm returns the solution
 of the input problem by finding the solution of the scaled problem FPS∞ (Qv kerA(θk ) , int K̄), where v =(v1 , v2 , v3 ) ∈ int K̄.
– After updating U B as U B ← θk , if U B − LB ≤ 1 holds, then preserve the scaling
information as v̄ ← v.

3.3.4

Use of approximate optimal solutions

Let us consider the indicator δ∞ (L ∩ int K) := maxx {det(x) | x ∈ L ∩ int K, ∥x∥∞ = 1}, which is equivalent to the indicators used in [20] and Section 6.2 of [12]. If L ∩ int K ̸= ∅, then δ∞ (L ∩ int K) ∈ (0, 1]
holds, and if e ∈ L ∩ int K, then δ∞ (L ∩ int K) = 1 holds. The larger the value of the indicatorδ∞ (L ∩ int K), the sooner projection and rescaling algorithms will find a solution for FP(L, int K).

17

Therefore, scaling with v ∈ int K̄ such that δ∞ (Qv (kerA(θ)) ∩ int K̄) ≥ δ∞ (kerA(θ) ∩ int K̄) holds can
reduce the computational time of Algorithm 2.
Let us introduce Proposition 3.12, which gives us the basic idea of obtaining v ∈ int K̄ such that
δ∞ (Qv (kerA(θ)) ∩ int K̄) ≥ δ∞ (kerA(θ) ∩ int K̄).
Proposition 3.12. Suppose that (P) is strongly feasible and for a given θ ∈ R and an interior feasible
1
solution x ∈ E for (P), max{θp , θ − 1} < ⟨c, x⟩ < θ holds. Define v ∈ E × R2 as v := (x− 2 , 1, 1). Then,the following inequality holds:δ∞ (Qv (kerA(θ)) ∩ int K̄) ≥ θ − ⟨c, x⟩.
Proof. It is obvious that (x, 1, θ − ⟨c, x⟩) ∈ kerA(θ) ∩ int K̄. Noting that Qv ((x, 1, θ − ⟨c, x⟩)) = (e, 1, θ −⟨c, x⟩) ∈ Qv (kerA(θ)) ∩ int K̄ and θ − ⟨c, x⟩ < 1, we find δ∞ (Qv (kerA(θ)) ∩ int K̄) ≥ det(e) × 1 × (θ −⟨c, x⟩) = θ − ⟨c, x⟩.
The next corollary follows similarly to Proposition 3.12.
Corollary 3.13. Suppose that (P) is strongly feasible and for a given θ ∈ R, θp < θ − 1 holds. For any
1
interior feasible solution x ∈ E for (P) such that ⟨c, x⟩ = θ − 1, define v ∈ E × R2 as v := (x− 2 , 1, 1).
Then, δ∞ (Qv (kerA(θ)) ∩ int K̄) = 1 holds.
Proposition 3.12 and Corollary 3.13 raise interest in whether the following assumption holds or not.
Assumption 3.14. Suppose that (P) is strongly feasible. Let x ∈ E and s ∈ E be interior feasible
solutions for (P) such that max{θp , θ − 1} < ⟨c, x⟩ < ⟨c, s⟩ < θ for a given θ ∈ R. Define vx ∈ E × R2
1
1
and vs ∈ E × R2 as vx := (x− 2 , 1, 1) and vs := (s− 2 , 1, 1), respectively. Then, the following relation
holds.
δ∞ (Qvx (kerA(θ)) ∩ int K̄) > δ∞ (Qvs (kerA(θ)) ∩ int K̄).
Unfortunately, the authors could not prove whether Assumption 3.14 holds. What prevents us fromproving this assumption is revealed by the following proposition.
Proposition 3.15. Suppose that (P) is strongly feasible and that for a given θ ∈ R and an interior
1
feasible solution s ∈ E for (P), max{θp , θ − 1} < ⟨c, s⟩ < θ holds. Let vs := (s− 2 , 1, 1) and (s1 , s2 , s3 )be the point giving the maximum value of δ∞ (Qvs (kerA(θ)) ∩ int K̄). If s1 = e, then for any interior
feasible solution x ∈ E for (P) such that max{θp , θ − 1} < ⟨c, x⟩ < ⟨c, s⟩,δ∞ (Qvx (kerA(θ)) ∩ int K̄) > δ∞ (Qvs (kerA(θ)) ∩ int K̄)holds, where vx := (x− 21, 1, 1).


Proof. It is obvious that (e, 1, θ − ⟨c, s⟩) ∈ Qvs (kerA(θ)) ∩ int K̄ and Q 12 (s1 ), s2 , s3 ∈ kerA(θ) ∩ int K̄sholds.
If s1 = e, then Q 21 (s1 ) = s holds. In addition, we can easily see that s2 = 1 and s3 = θ − ⟨c, s⟩ since ss
is a feasible solution for (P) and (s, s2 , s3 ) ∈ kerA(θ) ∩ int K̄. Thus, we haveδ∞ (Qvs (kerA(θ)) ∩ int K̄) = det(e) × 1 × (θ − ⟨c, s⟩) = θ − ⟨c, s⟩.
By Proposition 3.12, for any interior feasible solution x for (P) such that max{θp , θ − 1} < ⟨c, x⟩ <⟨c, s⟩, we find δ∞ (Qvx (kerA(θ)) ∩ int K̄) ≥ θ − ⟨c, x⟩, and hence we have δ∞ (Qvx (kerA(θ)) ∩ int K̄) >δ∞ (Qvs (kerA(θ)) ∩ int K̄).
18

As in the proof of Proposition 3.15, Assumption 3.14 holds in the case s1 = e. However, proving
whether Assumption 3.14 holds when s1 ̸= e is difficult. In this case, the specific value or upper boundof δ∞ (Qvs (kerA(θ)) ∩ int K̄) is challenging to obtain. Even if (s1 , s2 , s3 ) were obtained, it is unclear
how the existence of (s1 , s2 , s3 ) such that s1 ̸= e affects the value of δ∞ (Qvx (kerA(θ)) ∩ int K̄) for any
interior feasible solution x satisfying max{θp , θ − 1} < ⟨c, x⟩ < ⟨c, s⟩. These obstacles prevent us fromproving Assumption 3.14.
So far, we have focused on scaling with an interior feasible solution x ∈ E such that max{θp , θ − 1} <⟨c, x⟩ < θ. The critical concern for our algorithm is whether scaling with such x can reduce the execution
time of Algorithm 2. In other words, our algorithm needs to determine whether the following relation
1
holds for any interior feasible solution x satisfying max{θp , θ − 1} < ⟨c, x⟩ < θ and v = (x− 2 , 1, 1).
δ∞ (Qv (kerA(θ)) ∩ int K̄) ≥ δ∞ (kerA(θ) ∩ int K̄).
Unfortunately, the above relation does not always hold. The easiest counterexample is when e is a feasible
solution for (P) and ⟨c, e⟩ = θ − 1, i.e., δ∞ (kerA(θ) ∩ int K̄) = 1. Even if e is not a feasible solution for(P), for the same reason that it is challenging to prove Assumption 3.14, it is also difficult to ascertain
whether this relation holds. It isn’t easy to see whether this relation holds when x is an approximate
feasible solution. However, the authors believe that Assumption 3.14 holds and scaling with an arbitrary
interior feasible solution x such that max{θp , θ − 1} < ⟨c, x⟩ < θ can reduce the computational time of
Algorithm 2 based on the observation of a simple example discussed in Appendix B.
The observations in Appendix B imply that even if x is an approximate solution for (P), we can expect that the scaling with such x reduces the computational time of Algorithm 2, as long as ⟨c, x⟩ ≃max{θp , θ − 1} and e is not an approximate or feasible solution for (P) such that ⟨c, e⟩ ≃ max{θp , θ − 1}.
Noting that Algorithm 2 will be used as a post-processing step of interior point methods, there is no
problem in supposing that we have an approximate optimal solution x ∈ int K and θ such that θ ≃ θp ,i.e., max{θp , θ − 1} = θp , before running Algorithm 2.
Thus, the following operations are added to Algorithm 2.
1. Initialize v̄ as v̄ ← (e, 1, 1). ( If an approximate primal solution x ∈ int K is known in advance,
1
initialize v̄ as v̄ ← (x− 2 , 1, 1).)
2. Call the projection and rescaling algorithm with Qv̄ kerA(θk ) and K̄ to solve FP(kerA(θk ), int K̄).
• Suppose that the projection and rescaling algorithm returns the solution of the input problem,
and we obtain the solution (x, τ, ρ) for FP(kerA(θk ), int K̄).
– After updating U B as U B ← θk , if U B − LB > 1 holds, then update v̄ as v̄ ←1(( τ1 x)− 2 , 1, 1).
Note that Algorithm 2 with this modification does not update v̄ in the item (2) above if U B − LB ≤ 1.
This is because the technique in Section 3.3.3 updates v̄ when U B − LB ≤ 1. This modification is
not theoretically guaranteed to work. Our numerical experiments in Section 4 confirm whether thesetechniques work well.

3.3.5

Extracting a highly accurate solution

Algorithm 2 will obtain approximate solutions many times before they terminate. Such solutions can beused to make the accuracy of the outputs from Algorithm 2 robust.
The following operations are added to Algorithm 2. Since our algorithm is intended to be used as a
post-processing step, it is assumed that an approximate optimal solution (x0 , y 0 , z 0 ) is known in advance.
19

1. Initialize SolP and SolD as SolP ← x0 and SolD ← y 0 , respectively.
2. If xtmp is obtained at the k-th iteration, then we add xtmp to SolP .
3. If ytmp is obtained at the k-th iteration, then we add ytmp to SolD .
4. Choose y ∗ as in (6) and then compute x∗ as in (5) using y ∗ before line 21
5. Return x∗ instead of xtmp .
Since the set SolP will contain many approximate primal solutions, Algorithm 2 can extract the highly
accurate approximate optimal solution x∗ from this set as inx∗ ← arg min f (x, y ∗ , c − A∗ y ∗ ),(5)x∈SolPwhere∥Ax − b∥2
−λmin (x) |⟨c, x⟩ − b⊤ y||⟨x, z⟩|f (x, y, z) =+ max 0,++.
⊤
 1 + max |bi |  1 + |⟨c, x⟩| + |b y| 1 + |⟨c, x⟩| + |b⊤ y|
1 + max |bi |
i=1,...,mi=1,...,mEach term of the function f (x, y, z) is based on the DIMACS Error [18], which is a measure of accuracy
as an optimal solution for (P) and (D). Note that a dual solution (y, z) is required to extract x∗ as in (5).
If the dual optimal solution were known, f (x, y, z) could be used to accurately evaluate the accuracy ofx as the primal optimal solution, but such cases would be sporadic. Thus, we choose y ∗ from SolD and
use it as the approximate optimal dual solution to extract x∗ . Algorithm 2 chooses y ∗ as iny ∗ ← arg max b⊤ y,

(6)

y∈Sol


where Sol := y ∈ SolD : λmin (c − A∗ y) ≥ min{λmin (c − A∗ y 0 ), 0} . With the modification of Algorithm 2 proposed in Section 3.3.2, we can use a current dual solution (ȳ, c − A∗ ȳ) to extract x∗ as longas ȳ is not empty.

3.4

Practical versions of Algorithms 2 and 3

We now describe Algorithms 2 and 3 employing the modifications proposed in the previous section. Bothalgorithms are designed to use the approximate optimal solutions (x0 , y 0 , z 0 ) of (P) and (D). Algorithms
4 and 5 are practical versions of Algorithms 2 and 3, respectively. These algorithms terminate when
U B − LB ≤ θacc holds or when a vector that determines the feasibility status of (P) or (D) is found. We
consider that a reducing direction for (P) is obtained when Algorithm 4 finds a vector (y, γ) such that|γ| ≤ 1e-12, | − b⊤ y| ≤ 1e-12, λmin (A∗ y) ≥ -1e-12, and ∥A∗ y∥ > 1e-12.
In addition, we consider that an improving ray of (D) is obtained when Algorithm 4 finds a vector (y, γ)such that1λmin (A∗ y) ≥ -1e-12.
|γ| ≤ 1e-12, −b⊤ y > 1e-12, and−b⊤ ySimilarly, when Algorithm 5 finds a vector (x, τ, ρ) satisfying|τ | ≤ 1e-12, |⟨c, x⟩| ≤ 1e-12, λmin (x) ≥ -1e-12, and ∥x∥ > 1e-12,
we consider that a reducing direction for (D) is obtained, and when Algorithm 5 finds a vector satisfying|τ | ≤ 1e-12, ⟨c, x⟩ < -1e-12, and20

1
λmin (x) ≥ -1e-12,−⟨c, x⟩we consider that an improving ray of (P) is obtained.
Algorithm 4 Practical version of Algorithm 2
1: Input: A, b, c, K, (x0 , y 0 , z 0 ) and θacc > 0.
2: Output: A primal solution x (and a dual solution y) or a vector that determines the feasibility

status of (P).
3: initialization: k ← 0, LB ← −∞, U B ← ∞, K̄ ← K×R2+ , ȳ ← ∅, v̄ ← (e, 1, 1), SolP ← x0 , SolD ← y 0
1( If c − A∗ y 0 ∈ K, ȳ ← y 0 , LB ←b⊤ ȳ. If x0 ∈ 
intK, x̄ ← x0 , v̄ ← (x̄− 2 , 1, 1). )A −b 0.
4: Choose θ k ∈ (LB, U B) and construct A(θ k ) =c⊤ −θk 1
5: Let ε be a sufficiently small positive value and ξ be a constant such that 0 < ξ < 1.
6: while U B − LB > θacc do
7:
Call the projection and rescaling algorithm of [12] with Qv̄ (kerA(θk )), K̄, ε, and ξ
to solve FP(kerA(θk ), int K̄) and then obtain the scaling information v = (v1 , v2 , v3 ).
8:
if a solution (x, τ, ρ) to FP(kerA(θk ), int K̄) is obtained then9:
xtmp ← τ1 x, SolP ← SolP ∪ {xtmp }, U B ← θk10:
if U B − LB ≤ 1 then11:v̄ ← (v1 , v2 , v3 )
12:
else
13:
if xtmp ∈ intK then−12v̄ ← (xtmp, 1, 1)
end ifend if∗else if a solution (z, ω, κ) to FP(rangeA(θk ) , K̄ \ {0}) is obtained thenm+1∗
Compute (y, γ) ∈ R
such that z = A y + γc, ω = −b⊤ y − γθ and κ = γ.
19:
if −y is an improving ray of (D) or a reducing direction for (P) then20:
stop Algorithm 4 and return (−y, A∗ y)
21:
else
∗
k
22:
ytmp ← −1
κ y, ztmp ← c − A ytmp , SolD ← SolD ∪ {ytmp }, LB ← θ
23:
if ȳ ̸= ∅ then24:
Compute ynew such that b⊤ ynew ≥ b⊤ ȳ and c − A∗ ynew ∈ K using ȳ and ytmp .
25:ȳ ← ynew , LB ← max{θk , b⊤ ȳ}
26:
else
27:
if ztmp ∈ K then28:ȳ ← ytmp , LB ← max{θk , b⊤ ȳ}
29:
end if30:
end if31:
end if32:
else
33:
LB ← θk34:
end if35:
Choose θk+1 ∈ (LB, U B), k ← k + 1
36: end while// If ȳ = ∅, y ∗ ← ȳ.
37: Choose y ∗ from SolD as in (6)∗38: Choose x from SolP as in (5)39: return x∗ (and y ∗ )

14:
15:
16:
17:
18:

21

Algorithm 5 Practical version of Algorithm 3
1: Input: A, b, c, K, (x0 , y 0 , z 0 ) and θacc > 0.
2: Output: A dual solution y (and a primal solution x) or a vector that determines the feasibility

status of (D).
3: initialization: k ← 0, LB ← −∞, U B ← ∞, K̄ ← K×R2+ , ȳ ← ∅, v̄ ← (e, 1, 1), SolP ← x0 , SolD ← y 0
1( If c − A∗ y 0 ∈ K, ȳ ← y 0 , LB ←b⊤ ȳ. If z 0 ∈ 
intK, z̄ ← z 0 , v̄ ← (z̄ − 2 , 1, 1). )A−b0.
4: Choose θ k ∈ (LB, U B) and construct A(θ k ) =c⊤ −θk 1
5: Let ε be a sufficiently small positive value and ξ be a constant such that 0 < ξ < 1.
6: while U B − LB > θacc do∗
7:
Call the projection and rescaling algorithm of [12] with Qv̄ (rangeA(θk ) ), K̄, ε, and ξk ∗to solve FP(rangeA(θ ) , int K̄) and then obtain the scaling information v = (v1 , v2 , v3 ).
∗8:
if a solution (z, ω, κ) to FP(rangeA(θk ) , int K̄) is obtained thenm+1
9:Compute (y, γ) ∈ R
such that z = A∗ y + γc, ω = −b⊤ y − γθ and κ = γ.
−110:ytmp ← κ y, ztmp ← c − A∗ ytmp , SolD ← SolD ∪ {ytmp }, LB ← θk11:
if ȳ ̸= ∅ then12:
Compute ynew such that b⊤ ynew ≥ b⊤ ȳ and c − A∗ ynew ∈ K using ȳ and ytmp .
13:ȳ ← ynew , LB ← max{θk , b⊤ ȳ}
14:
else
15:
if ztmp ∈ K then16:ȳ ← ytmp , LB ← max{θk , b⊤ ȳ}
17:
end if18:
end if19:
if U B − LB ≤ 1 then20:v̄ ← (v1 , v2 , v3 )
21:
else
22:
if ztmp ∈ intK then−12v̄ ← (ztmp, 1, 1)
end ifend ifelse if a solution (x, τ, ρ) to FP(ker A(θk ), K̄ \ {0}) is obtained thenif x is an improving ray of (P) or a reducing direction for (D) thenstop Algorithm 5 and return x
29:
end if30:
xtmp ← τ1 x, Sol ← Sol ∪ {xtmp }, U B ← θk
31:
else
32:
U B ← θk33:
end if34:
Choose θk+1 ∈ (LB, U B), k ← k + 1
35: end while// If ȳ = ∅, y ∗ ← ȳ.
36: Choose y ∗ from SolD as in (6)∗37: Choose x from SolP as in (5)38: return y ∗ (and x∗ )

23:
24:
25:
26:
27:
28:

4

Numerical results

In this section, we apply our algorithm to some instances to show the numerical performance of the
proposed methods. Figure 1 shows the flow of our numerical experiments. First, we solve the instanceswith SDP solvers to obtain approximate optimal solutions (x0 , y 0 , z 0 ) to (P) and (D). SDPA [34], SDPT3

22

[29], and Mosek [1] were used in our experiment. Next, we call Algorithm 6 with (x0 , y 0 , z 0 ). Algorithm
6 calls Algorithm 5 and Algorithm 4 in that order if λmin (z 0 ) >-1e-12. Algorithm 5 is called first to
take advantage of the modification in Section 3.3.2. Since Algorithm 5 can find an approximate optimal
interior feasible solution to (D), a highly accurate optimal dual solution y will likely be obtained after
running Algorithm 5. Such a vector y can reduce the execution time of Algorithm 4 via the modification
proposed in Section 3.3.2. In our experiment, SDPA and SPDT3 returned z 0 such that λmin (z 0 ) >1e-14 for all instances. However, Mosek returned z 0 such that λmin (z 0 ) <-1e-10 for some instances inthe experiment of Section 4.2. Algorithm 6 processed these problems in the order of Algorithm 4 andAlgorithm 5. This is because we preferred to use the modifications proposed in Section 3.3.4 rather thanfind a highly accurate optimal dual solution before executing Algorithm 4. (The next section will show
the effect of the modifications proposed in Section 3.3.4.) Even if λmin (z 0 ) <-1e-12, we can generate aninterior point of the cone K by adding a slight perturbation to z 0 . However, the interior points obtainedin this way are not likely to be accurate dual feasible solutions. On the other hand, Algorithm 4 can takeadvantage of the modifications proposed in Section 3.3.4 using x0 . If Algorithm 4 can find a dual feasible
solution, then Algorithm 5, called after Algorithm 4, can also use the modifications proposed in Section
3.3.4 from the first iteration. We note that Mosek did not yield (x0 , y 0 , z 0 ) such that λmin (z 0 ) < -1e-12
and λmin (x0 ) < -1e-12 for all instances in our experiment. Thus, Algorithm 6 did not reach step 30 inour experiment. As long as (x0 , y 0 , z 0 ) is an approximate interior feasible solution, step 30 of Algorithm
6 is not reached.
We set the upper limit for the execution time of Algorithms 4 and 5 to 30 minutes and θacc = 1e-12.
In addition, we added practical termination conditions to Algorithms 4 and 5 to account for numericalerrors. (See Appendix C.1.) For detailed settings of our algorithm, see Appendix C.

Figure 1: Experiment flow
We conducted three types of numerical experiments. In Section 4.1, we verified whether the modification
proposed in Section 3.3.4 contributes to reducing the execution time of Algorithm 6. In Section 4.2, wechecked whether Algorithm 6 can obtain approximate optimal solutions with higher accuracy than the
SDP solvers. In Section 4.3, we tested whether Algorithm 6 detects the feasibility status of SDP moreaccurately than the SDP solvers. All executions were performed using MATLAB R2022a on an Intel(R)Core(TM) i9-10980XE CPU @ 3.00GHz machine with 128GB of RAM.
In Section 4.1 and Section 4.2, we measured the accuracy of the output solution (x, y, z) to (P) and (D)using the DIMACS errors [18]. Letting d be the dimension of the Euclidean space E corresponding to23

Algorithm 6 Proposed Algorithm
1: Input: A, b, c, K, (x0 , y 0 , z 0 ) and θacc > 0.
2: Output: Solutions to (P) and (D) or a vector that determines the feasibility status of (P) or (D).
3: if λmin (z 0 ) ≥ −1e-12 then4:(x∗ , y ∗ , z ∗ ) ← (x0 , y 0 , z 0 )if z ∗ ∈/ intK thenz ∗ ← z ∗ + (−λmin (z ∗ )+1e-15)eend ifCall Algorithm 5 with A, b, c, K, (x∗ , y ∗ , z ∗ ) and θacc > 0.
if a solution (x, y) to (P) and (D) is obtained thenx∗ ← x, y ∗ ← y, z ∗ ← c − A∗ y11:else if x, a reducing direction for (D) or an improving ray of (P), is obtained then12:
stop Algorithm 6 and return x
13:
end if14:
Call Algorithm 4 with A, b, c, K, (x∗ , y ∗ , z ∗ ) and θacc > 0.
15:
if a solution (x, y) to (P) and (D) is obtained then16:x∗ ← x, y∗ ← y, z ∗ ← c − A∗ y17:else if (y, z), a reducing direction for (P) or an improving ray of (D), is obtained then18:
stop Algorithm 6 and return (y, z)
19:
end if
20: else if λmin (x0 ) ≥ −1e-12 then21:(x∗ , y ∗ , z ∗ ) ← (x0 , y 0 , z 0 )22:
if x∗ ∈
/ intK then23:x∗ ← x∗ + (−λmin (x∗ )+1e-15)e24:
end if25:
Call Algorithm 4 with A, b, c, K, (x∗ , y ∗ , z ∗ ) and θacc > 0.
26:
Same as lines 15 - 19
27:
Call Algorithm 5 with A, b, c, K, (x∗ , y ∗ , z ∗ ) and θacc > 0.
28:
Same as lines 9 - 13
29: else30:(x∗ , y ∗ , z ∗ ) ← (x0 , y 0 , z 0 )31:Same as lines 8 - 19
32: end if
33: return (x∗ , y ∗ , z ∗ )
5:
6:
7:
8:
9:
10:

24

Table 2: Experimental results testing the effectiveness of the modification proposed in Section 3.3.4

Method

err1

err2

err3

err4

err5

err6

time(s)

Naive
Algorithm 4

7.15e-14
1.50e-14

04.81e-170000

3.89e-10
1.81e-13

3.89e-10
1.81e-13

13.36
2.66

K, the DIMACS errors consists of six measures as follows:∥Ax − b∥2,
err1 (x, y, z) =1 + max |bi |
i=1,...,merr3 (x, y, z) =∥c − A∗ y − z∥J,
1 + max |ci |
i=1,...,d− λmin (x) err2 (x, y, z) = max 0,, 1 + max |bi |
i=1,...,m− λmin (z) err4 (x, y, z) = max 0,, 1 + max |ci |
i=1,...,d⟨c, x⟩ − b⊤ y⟨x, z⟩
err5 (x, y, z) =, err6 (x, y, z) =.
⊤1 + |⟨c, x⟩| + |b y|
1 + |⟨c, x⟩| + |b⊤ y|Primal feasibility is measured by err1 (x, y, z) and err2 (x, y, z) and dual feasibility is measured by err3 (x, y, z)
and err4 (x, y, z). Optimality is measured by err5 (x, y, z) and err6 (x, y, z). We note that the valuesof err5 (x, y, z) and err6 (x, y, z) might be negative as long as (x, y, z) is an approximate solution. If
err5 (x, y, z) = −δ and δ > 0, then err5 (x, y, z) corresponds to a “worse” solution than if err5 (x, y, z) = δ.

4.1

The effectiveness of the modification in Section 3.3.4

The instances used in this experiment are picked from SDPLIB [2]. The feasibility status of SDPLIB
instances can be inferred based on Freund et al.’s study [9]. Since this experiment was only to evaluate themodification in Section 3.3.4, we chose only small size instances where both the primal and dual problems
are strongly feasible, i.e., control1, control2, control3, truss1, truss3, and truss4. We first solved these
instances with Mosek to obtain an approximate optimal interior feasible solution (x0 , y 0 , z 0 ). However,Mosek returned dual solutions (y 0 , z 0 ) such that c − A∗ y 0 ∈/ K and z 0 ∈/ K to truss1, truss3, and truss4.
Thus, we only checked for six instances how the computation time of Algorithm 4 changed with andwithout the modification proposed in Section 3.3.4. In this section, we referred to Algorithm 4 without
the modification proposed in Section 3.3.4 as the “Naive” method.
Table 2 summarizes the results of our experiments. The “times(s)” column shows the average CPU timeof the corresponding method, and the other columns show the average value of the DIMACS errors.
Table 2 shows that the computational time of Algorithm 4 is significantly smaller than that of the“Naive” method. Algorithm 4 scales the problem with an approximate optimal interior feasible solution
before executing the projection and rescaling algorithm. Such scaling reduced the number of iterationsof the projection and rescaling algorithm in this experiment. Thus, the computational time of Algorithm
4 is much smaller than that of the “Naive” method.

4.2

The effectiveness of our post-processing algorithm

The outline of our numerical experiment in this section is as follows:
1. Solve the instances with the SDP solvers using the default settings to obtain approximate optimal
solutions (xdef , ydef , zdef ).
25

Table 3: Solver setting in our numerical experiments

Solverdefault tolerances
ϵprimal ϵdual ϵgap

tight tolerances
ϵprimal ϵdual ϵgap

Mosek
SDPT3
SDPA

1.0e-08
1.0e-08
1.0e-071.0e-12

2. Solve the instances using (xdef , ydef , zdef ) and Algorithm 6 to obtain approximate optimal solutions(xpro , ypro , zpro ).
3. Solve the instances with the SDP solvers using the tight settings to obtain approximate optimal
solutions (xtight , ytight , ztight ).
4. Compare the above three results regarding accuracy and computational time.
In this experiment, we used SDPA, SDPT3, and Mosek. These solvers have parameters that allow us
to tune the feasibility and the optimality tolerances. For example, SDPA terminates if an approximate
optimal solution (x, y, z) is obtained for parameters ϵprimal , ϵdual and ϵgap such thatmax |(Ax − b)i | ≤ ϵprimal ,i=1,...,mmax |(c − A∗ y − z)i | ≤ ϵdual , andi=1,...,d|⟨c, x⟩ − b⊤ y|≤ ϵgapmax {(|⟨c, x⟩| + |b⊤ y|) /2, 1}

are satisfied. That is, the parameters ϵprimal , ϵdual and ϵgap are the tolerances for primal feasibility, dual
feasibility, and optimality measures, respectively. The definitions of feasibility and optimality measures
are slightly different for each solver, but the other solvers have parameters that play the same role. Table
3 summarizes the values of the parameters used in our experiment. The “default tolerances” column
shows the default values of the parameters for each solver. The “tight tolerances” column shows thevalues of the parameters used as the tight setting in our experiment.
The instances of SDPLIB were used in this experiment. Note that the instances for which the SDP solverusing the default setting returned infeasibility criteria were excluded. In addition, we excluded someinstances due to memory limitations and then conducted numerical experiments with 57 instances intotal. To appropriately observe the results, we classified these instances into two groups, the well-posed
and the ill-posed groups, based on Freund et al.’s study [9]. The well-posed group includes 34 instanceswhere both the primal and dual problems are expected to be strongly feasible. On the other hand,
the ill-posed group includes 23 instances where either the primal or dual problem is not expected to
be strongly feasible. According to [9], SDPLIB does not include the instances whose primal problem isstrongly feasible, but the dual is not. Thus, the ill-posed group includes only instances where the dual
problem is expected to be strongly feasible, but the primal problem is not.
The numerical results for the well-posed group and ill-posed group are summarized in Figures 24 and 5-7, respectively. Figures 2-7 summarize the values of DIMACS errors for (xdef , ydef , zdef ),(xtight , ytight , ztight ) and (xpro , ypro , zpro ). In this experiment, no output (xpro , ypro , zpro ) was obtainedsuch that err2 (xpro , ypro , zpro ) >1e-11 or err4 (xpro , ypro , zpro ) > 0. Therefore, we omitted figures summarizing the values of err2 and err4 . In Figures 2-7, the black solid line, the blue circle and the invertedorange triangle show the values of the DIMACS errors logarithmized by the base 10 for (xdef , ydef , zdef ),(xtight , ytight , ztight ) and (xpro , ypro , zpro ), respectively. It is not plotted if the corresponding DIMACS
error value is 0. We note that the values of log10 |err5 (x, y, z)| and log10 |err6 (x, y, z)| are plotted because the values of err5 (x, y, z) and err6 (x, y, z) can be negative. In addition, we plot the points where
the corresponding DIMACS error values are negative by filling them in. In each graph of Figures 2-7,26

the horizontal axis indicates the instances, sorted so that the corresponding DIMACS error values for(xdef , ydef , zdef ) are in ascending order.
First, let us compare the results for the well-posed group. From Figures 2-4, we can observe that Algorithm 6 returned an approximate optimal solution (xpro , ypro , zpro ) that was superior to the (xdef , ydef , zdef )and (xtight , ytight , ztight ) in terms of feasibility and optimality for almost all instances. Algorithm 6 returns (xpro , ypro , zpro ) such that zpro = c − A∗ ypro , thus the value of err3 (xpro , ypro , zpro ) should be 0 for
all instances. However, in (b) of Figures 2-4, four inverted triangles representing the results for four instances, theta1, theta2, theta3, and theta4, were plotted. This is probably due to slight numerical errors
in computing c − A∗ ypro for these instances. Note that (xpro , ypro , zpro ) satisfies ⟨c, xpro ⟩–b⊤ ypro > 0 for
almost all instances.
We can also see that the solvers with the tight setting tend to return more accurate approximate optimal
solutions (xtight , ytight , ztight ) than (xdef , ydef , zdef ). However, Mosek and SDPA, with the tight setting,returned strange outputs for some instances. Mosek, with the default setting, determined the primal anddual problems are expected to be feasible and returned an approximate optimal solution for all instances.
The error message “rescode = 100006” was returned for only one instance. This error message meansthat “the optimizer is terminated due to slow progress”. On the other hand, when using Mosek withthe tight settings, it returned the error message “rescode = 100006” for 21 instances. Among these
instances, 4 instances were determined that their primal problems were expected to be infeasible, and
13 instances were not determined their feasibility. For the aforementioned 4 instances and 13 instances,
Mosek, with the tight setting, provided incorrect infeasibility certificates and inaccurate dual feasible
solutions, respectively. SDPA, with the default setting, determined the primal and/or dual problems
are feasible and returned an approximate optimal solution for all instances. However, when using SDPAwith tight settings, it was determined that at least one of the primal or dual problems was expected
to be infeasible for 13 instances, and incorrect primal solutions were returned for 11 instances of them.
A possible reason for these strange outputs is that tightening the tolerances might cause numericalinstability. Figure 4 shows that SDPT3 with the tight setting worked stably and obtained more accurate
approximate optimal solutions (xtight , ytight , ztight ) than (xdef , ydef , zdef ) for almost all instances. We also
solved all instances using SDPT3 with the tolerances ϵprimal , ϵdual and ϵgap set to 1e-13 and obtained
the same results as Figure 4.
Next, let us compare the results for the ill-posed group. Since Mosek, using the default setting, returned
the reducing direction for hinf12, Figure 5 excludes the plot representing the result for this instance.
On the other hand, Algorithm 6 did not find a reducing direction for (P) in this experiment. Thus,
Algorithm 6 terminated by returning an approximate optimal solution for all instances. From Figures
5-7, we can observe that Algorithm 6 returned an approximate optimal solution (xpro , ypro , zpro ) that wassuperior to the (xdef , ydef , zdef ) and (xtight , ytight , ztight ) in terms of feasibility for almost all instances.
In addition, we can see that the value of |err5 (xpro , ypro , zpro )| or |err6 (xpro , ypro , zpro )| was larger thanthe value of |err5 (xdef , ydef , zdef )| or |err6 (xdef , ydef , zdef )| for some instances. However, this observation
does not imply that (xpro , ypro , zpro ) was inferior to (xdef , ydef , zdef ) and (xtight , ytight , ztight ) in terms of
optimality.
Tables 4-6 compare the dual objective value of (xpro , ypro , zpro ) with the primal or dual objective valuesof (xdef , ydef , zdef ) and (xtight , ytight , ztight ). From Tables 4-6, we can see thatb⊤ ypro > max{b⊤ ydef , b⊤ ytight }holds for almost all instances of the ill-posed group. Noting that c − A∗ ypro = zpro ∈ K holds for all
instances, (ypro , zpro ) can be regarded as a more accurate optimal dual solution than (ydef , zdef ) and(ytight , ztight ). Therefore, the reason why the value of |err5 (xpro , ypro , zpro )| or |err6 (xpro , ypro , zpro )| wassometimes greater than the corresponding DIMACS error values for (xdef , ydef , zdef ) and (xtight , ytight , ztight )is that Algorithm 6 did not obtain a sufficient accurate primal solution xpro such that ⟨c, xpro ⟩ ≃ b⊤ ypro
for some instances. Here, we note that the primal problem of all instances in the ill-posed group is not
27

Table 4: Comparison of the objective values of (xpro , ypro , zpro ), (xdef , ydef , zdef ) and (xtight , ytight , ztight )for the ill-posed group : Mosek

instanceb⊤ ypro − ⟨c, xdef ⟩b⊤ ypro − b⊤ ydefb⊤ ypro − ⟨c, xtight ⟩b⊤ ypro − b⊤ ytightgpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

7.38e-06
4.88e-06
5.75e-05
4.76e-05
5.10e-05
6.65e-07
3.79e-05
6.85e-05
8.33e+00
1.86e-03
7.17e+00
4.63e-03
7.17e-05
2.23e-04
3.40e-04
5.49e-04
8.12e-04
1.29e-06
4.38e-04
4.81e-05
5.26e-03
1.14e-03
1.56e-02

7.37e-06
4.86e-06
5.81e-05
4.94e-05
5.09e-05
6.01e-07
3.59e-05
6.61e-05
8.33e+00
1.75e-03
7.17e+00
4.46e-03
4.00e-05
1.93e-04
2.59e-04
5.25e-04
6.42e-04
1.22e-06
4.36e-04
4.43e-05
5.25e-03
1.13e-03
1.55e-02

7.38e-06
1.24e-06
5.75e-05
4.76e-05
5.10e-05
1.30e-06
3.85e-05
1.62e-05
8.33e+00
7.51e-03
7.17e+00
4.63e-03
3.09e-04
1.60e-03
3.40e-04
5.58e-04
2.24e-03
1.90e-09
2.68e-03
8.71e-04
4.50e-03
4.89e-03
1.56e-02

7.37e-06
1.23e-06
5.81e-05
4.94e-05
5.09e-05
1.18e-06
3.64e-05
1.53e-05
8.33e+00
7.21e-03
7.17e+00
4.46e-03
2.43e-04
1.48e-03
2.59e-04
5.34e-04
2.08e-03
1.79e-09
2.61e-03
8.53e-04
4.49e-03
4.84e-03
1.55e-02

expected to be strongly feasible, which might prevent the projection and rescaling methods in Algorithm
6 from working stably and obtaining accurate optimal primal solutions.
From the results of the solvers for the ill-posed group, we can observe the same thing as for the well-posedgroup. When using SDPA and Mosek with the tight setting, they sometimes returned inaccurate primal
solutions and inaccurate dual solutions, respectively. In addition, SDPT3 with the tight setting returnedmore accurate optimal solutions (xtight , ytight , ztight ) than (xdef , ydef , zdef ) for almost all instances. We
note that SDPT3 obtained the same results when ϵprimal = ϵdual = ϵgap = 1e-13 as when ϵprimal = ϵdual =ϵgap = 1e-12.
Let us compare the results for the well-posed and ill-posed groups. Comparing Figures 2-4 and 5-7, we
can observe the following:• Algorithm 6 did not consistently obtain an accurate optimal solution for the ill-posed group compared to the results for the well-posed group.
• Algorithm 6 returned (xpro , ypro , zpro ) such that |err5 (xpro , ypro , zpro )| ≃ |err6 (xpro , ypro , zpro )| foralmost all instances of the well-posed group, but such a relation did not hold for the ill-posedgroup.
The first observation is evident in Figures 2-7, (c). To clarify the second observation, see Table
7. Table 7 summarizes the average value of ||err5 (xpro , ypro , zpro )| − |err6 (xpro , ypro , zpro )|| for eachgroup. Table 7 shows that for all combinations of Algorithm 6 and the solvers, the average value of||err5 (xpro , ypro , zpro )| − |err6 (xpro , ypro , zpro )|| for the ill-posed group is greater than for the well-posedgroup. From this table, we can see that the relation |err5 (xpro , ypro , zpro )| ≃ |err6 (xpro , ypro , zpro )| holds
for the well-posed group but not for the ill-posed group.

28

Table 5: Comparison of the objective values of (xpro , ypro , zpro ), (xdef , ydef , zdef ) and (xtight , ytight , ztight )for the ill-posed group : SDPA

instanceb⊤ ypro − ⟨c, xdef ⟩b⊤ ypro − b⊤ ydefb⊤ ypro − ⟨c, xtight ⟩b⊤ ypro − b⊤ ytightgpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

-1.88e-07-1.29e-07-4.51e-06
5.07e-05-3.14e-05
1.18e-05-5.02e-03
3.46e-04
2.05e+01
4.65e-02-3.08e+00
1.69e-01
1.07e-01
1.25e-01
2.63e+01
4.39e+00-2.90e-03
3.63e+00-2.24e-02-5.04e-02-1.01e-01-1.53e-01-3.95e-01-7.21e-01

2.07e-07
5.94e-08
1.03e-07
6.27e-05
1.88e-06
1.27e-05
9.78e-03
3.46e-04
2.00e+01
2.41e-02
4.77e+00
1.69e-01
5.37e-02
6.30e-02
3.21e+00
2.88e+00
3.14e-03
2.64e+00
3.36e-04
1.21e-02
2.34e-02
2.11e-02
8.01e-02
8.16e-02-1.55e-03-1.04e-03-1.21e-03-2.05e-03-4.54e-03-2.06e-04
4.19e-03
5.96e-04
2.06e+01
2.86e-01-3.08e+00
1.68e-01
9.72e+00
3.11e+00
4.93e+01
4.39e+00-2.03e-02
3.63e+00-1.60e-03-1.93e-02-4.57e-02-4.95e-01-3.01e-01-6.57e-01

3.00e-05
1.28e-05
9.34e-06
1.04e-04
1.03e-04
1.09e-04
5.67e-03
4.22e-04
2.01e+01
2.40e-01
4.77e+00
1.68e-01
6.91e+00
2.58e+00
4.17e+01
2.88e+00
1.84e-02
2.64e+00
1.08e-04
5.86e-03
1.58e-02
1.62e-01
5.72e-02
7.75e-02

Table 6: Comparison of the objective values of (xpro , ypro , zpro ), (xdef , ydef , zdef ) and (xtight , ytight , ztight )for the ill-posed group : SDPT3

instanceb⊤ ypro − ⟨c, xdef ⟩b⊤ ypro − b⊤ ydefb⊤ ypro − ⟨c, xtight ⟩b⊤ ypro − b⊤ ytightgpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

2.88e-06
9.15e-07
1.71e-06
4.48e-06
2.72e-05
1.03e-04
2.71e-02
1.92e-03
4.81e+00
1.60e-02
1.42e-02
4.06e-02
6.14e-02
7.37e-02
2.97e-05
1.03e-02
6.37e-05
1.80e-02-3.08e-07
4.52e-02
3.15e-02
1.13e-01
2.19e-02
5.11e-02

1.88e-06
3.71e-07
1.11e-06
2.94e-06
1.20e-05
5.19e-05
1.36e-02
9.68e-04
4.47e+00
1.73e-02
7.48e-03
2.03e-02
5.28e-02
3.68e-02
1.45e-05
4.33e-03
8.15e-05
2.76e-02
8.53e-08
2.22e-02
1.55e-02
5.54e-02
1.06e-02
1.69e-02

3.70e-06
9.20e-07
2.25e-06
5.65e-06
2.78e-05
1.03e-04
2.71e-02
1.92e-03
4.81e+00
2.89e-02
1.42e-02
4.06e-02
1.35e-01
7.37e-02-8.09e-06
6.81e-03
5.90e-05
1.80e-02-4.55e-09
4.52e-02
3.15e-02
1.13e-01
2.19e-02
5.11e-02

1.84e-06
3.71e-07
1.09e-06
2.88e-06
1.20e-05
5.19e-05
1.36e-02
9.68e-04
4.47e+00
1.46e-02
7.48e-03
2.03e-02
6.73e-02
3.68e-02-1.29e-05
2.03e-03
3.54e-05
2.76e-02
1.58e-09
2.22e-02
1.55e-02
5.54e-02
1.06e-02
1.69e-02

29

Table 7: Comparison of the average values of ||err5 (xpro , ypro , zpro )| − |err6 (xpro , ypro , zpro )||MethodWell-posed groupIll-posed group

Mosek + Algorithm 6
SDPA + Algorithm 6
SDPT3 + Algorithm 6

5.34e-11
1.93e-11
2.51e-123.45e-03
3.75e-03
3.51e-04

There are two reasons for this. The first one is Algorithm 6 did not obtain accurate optimal primal
solutions for some instances of the ill-posed group. As mentioned above, the projection and rescaling
methods might not work stably due to the feasibility status of the primal problem for the ill-posed group,
which results in the instability of Algorithm 6 in obtaining accurate optimal primal solutions. Therefore,
the relation |err5 (xpro , ypro , zpro )| ≃ |err6 (xpro , ypro , zpro )| did not hold for the ill-posed group comparedto the results for the well-posed group. The second one is the existence of a reducing direction for (P).
Recall that (f, −A∗ f ) ∈ Rm × E is called a reducing direction for (P) if (f, −A∗ f ) satisfies b⊤ f = 0 and−A∗ f ∈ K \ {0}. Thus, if (D) has an optimal solution and a reducing direction for (P) exists, then the
optimal solution set of (D) is unbounded. Suppose that optimal dual solutions and reducing directionsfor (P) exist for all instances of the ill-posed group. Then, for any optimal dual solution (y, z) and any
positive value k > 0, there exists a dual optima solution (yopt , zopt ) and a reducing direction (f, −A∗ f )such that y = yopt + f and zopt + kA∗ f ∈/ K, and we have⟨c, x⟩ − b⊤ (yopt + f )1 + |⟨c, x⟩| + |b⊤ y|⟨c, x⟩ − b⊤ yopt
, (since b⊤ f = 0)=
1 + |⟨c, x⟩| + |b⊤ y|err5 (x, y, z) =and⟨x, c − A∗ yopt − A∗ f ⟩1 + |⟨c, x⟩| + |b⊤ y|⟨x, c⟩ − (Ax)⊤ yopt + ⟨x, −A∗ f ⟩=.
1 + |⟨c, x⟩| + |b⊤ y|err6 (x, y, z) =Therefore, even if ∥Axpro − b∥2 is sufficiently small, the value of ⟨xpro , −A∗ f ⟩ might not be negligibly
small as long as ypro ≃ yopt + f holds for some reducing direction (f, −A∗ f ) such that the value of∥ − A∗ f ∥ is very large.
∥z∥
for zdef and zpro by the well1+ max |ci | + max |Aij |
i
i,j
m×d

Table 8 summarizes the average values of f (z) =posed and the ill-posed groups, where A ∈ R
is a matrix representation of the linear operator
A. Since Mosek and SDPA with the tight settings did not work stably in this experiment, the averagevalues of f (ztight ) for each solver are omitted. In Table 8, the first, third, and fifth rows show the averagevalues of f (z) for zdef obtained from Mosek, SDPA, and SDPT3, respectively. The second, fourth, andsixth rows show the average values of f (z) for zpro obtained from Algorithm 6 using (xdef , ydef , zdef )returned from Mosek, SDPA, and SDPT3, respectively. We note that Algorithm 6 returned zpro suchthat ∥zpro ∥ >> ∥zdef ∥ for hinf2. Since hinf2 is included in the well-posed group, in Table 8, the values
in rows 2, 4, and 6 of the “Well-posed group” column are significantly different from the values in rows
1, 3 and 5 of the same column, respectively. The average values of f (zdef ) and f (zpro ) for the well-posedgroup, excluding hinf2, are summarized in the second column. From Table 8, we can see that the averagevalues of f (zdef ) and f (zpro ) in the third column are greater than in the second column. Thus, the dual
solutions zdef and zpro obtained by the solvers and Algorithm 6 for the ill-posed group are likely toinclude a reducing direction (f, −A∗ f ) such that the value of ∥ − A∗ f ∥ is very large. Furthermore, we30

Table 8: Comparison of the average values of f (z) =∥z∥
for zdef and zpro
1+ max |ci | + max |Aij |ii,jMethodWell-posed group

Well-posed group excluding hinf2

Ill-posed group

Mosek
Mosek + Algorithm 6
SDPA
SDPA + Algorithm 6
SDPT3
SDPT3 + Algorithm 6

1.04e+03
3.32e+03
1.04e+03
3.32e+03
6.70e+02
3.33e+03

6.85e+02
6.85e+02
6.85e+02
6.85e+02
6.85e+02
6.85e+02

6.75e+05
2.63e+10
8.81e+04
2.74e+11
4.66e+08
7.87e+09

can expect that the dual optimal solution set of hinf2 includes solutions (ymin , zmin ) and (ymax , zmax )such that ∥zmin ∥ << ∥zmax ∥.
Finally, let us compare the execution time of Algorithm 6 for each instance. Figures 8, 9 and 10 show
the execution time of Algorithm 6 using (xdef , ydef , zdef ) returned from Mosek, SDPA and SDPT3,
respectively. In these figures, the horizontal axis shows instances sorted in ascending order of problem
size. In this study, we defined the problem size as m × d, where m is the number of constraints andd is the dimension of the Euclidean space E corresponding to K. The line graph shows the execution
time of Algorithm 6, and the bar graph shows the problem size. From Figures 8-10, we can observe thefollowing:• As the problem size increases, the execution time of Algorithm 6 tends to increase.
• There was a variation in the execution time of Algorithm 6, even for instances of similar problem
size.
The above results were observed due to the structure of the projective rescaling method. The computational cost of the projection and rescaling algorithm proposed in [12] is

 


r
1
1
2
O −
log
m3 + m2 d + 2 p2 rmax
max C sd , md
(7)
log ξ
ε
ξ
where C sd is the computational cost of the spectral decomposition. In (7), the maximum number of
iterations of the main algorithm, the computational cost of the projection matrix, the maximum numberof iterations of the basic procedureand the computational cost per iteration of the basic procedure2corresponds to − logr ξ log 1ε , m3 + m2 d, ξ12 p2 rmax
and max C sd , md , respectively. Since the increasein problem size will increase the time required to compute the projection matrix, the execution time of
Algorithm 6 in Figures 8-10 tends to increase monotonically. Here, we note that the main algorithm
and the basic procedure can be terminated in less than their maximum number of iterations. The mainalgorithm (and the basic procedure) might terminate in a significantly different number of iterations forproblems with similar problem sizes. Therefore, there is expected to be some variation in the execution
time of Algorithm 6 for problems with similar problem sizes.

31

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 2: Numreical results for the well-posed group with Mosek

32

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 3: Numreical results for the well-posed group with SDPA

33

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 4: Numreical results for the well-posed group with SDPT3

34

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 5: Numreical results for the ill-posed group with Mosek

35

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 6: Numreical results for the ill-posed group with SDPA

36

(a) The values of log10 err1 (x, y, z)(b) The values of log10 err3 (x, y, z)(c) The values of log10 |err5 (x, y, z)|(d) The values of log10 |err6 (x, y, z)|Figure 7: Numreical results for the ill-posed group with SDPT3

37

Figure 8: Execution time of Algorithm 6 using (xdef , ydef , zdef ) returned from Mosek

Figure 9: Execution time of Algorithm 6 using (xdef , ydef , zdef ) returned from SDPA

38

Figure 10: Execution time of Algorithm 6 using (xdef , ydef , zdef ) returned from SDPT3

4.3

Experiments to determine feasibility status

The numerical results in the previous section showed that Algorithm 6 obtained more accurate approximate optimal solutions for the well-posed group than the solvers. On the other hand, the numericalresults for the ill-posed group showed that Algorithm 6 failed to detect that the primal problem is in
weak status. Algorithm 6, theoretically, can obtain a reducing direction for (P) (or (D)) if (P) (or (D))
is in weak status, but Algorithm 6 returned not a reducing direction for (P) but an approximate interior
feasible solution to (P) for the instances of the ill-posed group. Detecting the feasibility status of (P)and (D) and finding the reducing directions for (P) and (D) can be replaced by solving a certain SDP
whose primal and dual problems are strongly feasible, [16]. Thus, using the results of [16], we tested
whether Algorithm 6 can detect the feasibility status of SDP more accurately than the solvers. We
conducted this experiment with the ill-posed instances of SDPLIB and the weakly infeasible cases [14].
These instances have the primal problems in weak status.

4.3.1

Preparation to explain the flow of the experimentD
Before going to the outline of our experiments, we derive the (PKD ) and (DK), which is closely related
to the feasibility status of (P), by using the following lemma.

Lemma 4.1 (Lemma 3.4 in [16]). For (P) and (D), consider the following pair of primal and dual
problems.
(PKD ) inf x,t,w t
sub.to −⟨c, x − te⟩ + t − w = 0⟨ex⟩ + w = 1
Ax − tAe = 0(x, t, w) ∈ K × R+ × R+

39

D
(DK
)

supy1 ,y2 ,y3sub.toy2cy1 − ey2 − A∗ y3 ∈ K
1 − y1 (1 + ⟨c, e⟩) + ⟨e, A∗ y3 ⟩ ≥ 0
y1 − y2 ≥ 0

The following properties hold.
D
1. (PKD ) and (DK) are strongly feasible.
D
Let (x∗ , t∗ , w∗ ) be an optimal solution to (PKD ) and (y1∗ , y2∗ , y3∗ ) be an optimal solution to (DK).

2. The optimal value is zero if and only if (D) is not strongly feasible. In this case, one of the twoalternatives below must hold:(a) x∗ is an improving ray of (P), or(b) x∗ is a reducing direction for (D).
3. The optimal value is positive if and only if (D) is strongly feasible.
Proof. See Lemma 3.4 in [16].
Note that [16] showed that Lemma 4.1 holds not only for the identity element e of K but also for any
interior point of K. Similar to Lemma 4.1, Proposition 4.2, which is not in [16], can be easily proved.
Proposition 4.2. For (P) and (D), consider the following pair of primal and dual problems.
(PKP )

inf y,z,t,w
sub.totb⊤ y + t − w = 0⟨e, z⟩ + w = 1−A∗ y − z + te = 0(y, s, t, w) ∈ Rm × K × R+ × R+

P
)
(DK

supx1 ,x2 ,x3
sub.tox2
Ax3 − x1 b = 0
1 − x1 − ⟨e, x3 ⟩ ≥ 0
x1 − x2 ≥ 0
x3 − x2 e ∈ K

The following properties hold.
P
1. Both (PKP ) and (DK) are strongly feasible.

2. Let (y ∗ , z ∗ , t∗ , w∗ ) be a primal optimal solution. The optimal value is zero if and only if (P) is notstrongly feasible. Moreover, if the optimal value is zero, (y ∗ , z ∗ ) is an improving ray of (D) or areducing direction for (P).
3. Let (x∗1 , x∗2 , x∗3 ) be a dual optimal solution. If the optimal value is positive, x1∗ x∗3 is an interior
1
feasible solution to (P).


1
1
1
Proof. (1): Let (y 0 , z 0 , t0 , w0 ) = 0, ⟨e,e⟩+1e, ⟨e,e⟩+1, ⟨e,e⟩+1and (x01 , x02 , x03 ) = (0, −1, 0). Then (y 0 , z 0 , t0 , w0 )P
and (x01 , x02 , x03 ) are interior feasible solutions to (PKP ) and (DK), respectively.

40

(2): If t∗ = 0, then b⊤ y ∗ = w∗ ≥ 0 and −A∗ y ∗ = z ∗ ∈ K hold, which implies that (P) is not strongly
feasible by Proposition 2.4. Conversely, if (P) is not strongly feasible, there exists (y, z) ∈ Rm × K suchthat −A∗ y = z, A∗ y ̸= 0 and b⊤ y ≥ 0 by Proposition 2.4. Let k = ⟨e, z⟩ + b⊤ y. Since b⊤ y ≥ 0, z ∈ Kand z ̸= 0 hold, k is positive. Letting (ȳ, z̄, t̄, w̄) = ( k1 y, k1 z, 0, k1 b⊤ y), we can easily see that (ȳ, z̄, t̄, w̄) is
an optimal solution for (PKP ), which implies that the optimal value is zero.
Suppose that t∗ = 0. If b⊤ y ∗ = 0, then z ∗ ̸= 0 holds since w∗ = 0 and hence, (y ∗ , z ∗ ) is a reducing
direction for (P). If b⊤ y ∗ > 0, we can easily see that (y ∗ , z ∗ ) is an improving ray of (D).
(3): If x∗2 > 0, then x∗1 > 0 and x∗3 ∈ intK hold. Since x∗1 and x∗3 satisfy Ax∗3 − x∗1 b = 0, x1∗ x∗3 is an1
interior feasible solution to (P).
P
With some modifications to (PKP ) and (DK), we have optimization problems that Algorithm 6 can handle
well.

Proposition 4.3. For (P) and (D), consider the following pair of primal and dual problems.
P(P K )P(DK )inf α,β,γ,ssub.toα−α + β + γ + ⟨e, s⟩ = 0α11+⟨e,e⟩ (b − Ae) − γb + As = 1+⟨e,e⟩ (b − Ae)(α, β, γ, s) ∈ R+ × R+ × R+ × K

supκ,fsub.to1⊤1+⟨e,e⟩ (b − Ae) f
1
1 + κ − 1+⟨e,e⟩ (b − Ae)⊤ f ≥ 0−κ ≥ 0−κ + b⊤ f ≥ 0−κe − A∗ f ∈ K
The following properties hold.
P) are strongly feasible.
1. Both (P̄KP ) and (D̄K

2. The optimal value is smaller than or equal to 1.
3. Let (κ∗ , f ∗ ) be a dual optimal solution. If the optimal value is equal to 1, (f ∗ , −A∗ f ∗ ) is an
improving ray of (D) or a reducing direction for (P).
4. Let (α∗ , β ∗ , γ ∗ , s∗ ) be a primal optimal solution. If the optimal value is smaller than 1, then
1 + ⟨e, e⟩
1 − α∗∗s +eγ ∗ (1 + ⟨e, e⟩) + 1 − α∗
1 + ⟨e, e⟩
is an interior feasible solution to (P).
P
Proof. (1): For any feasible solution (x1 , x2 , x3 ) to (DK), let(α, β, γ, s) = (1 − (1 + ⟨e, e⟩)x2 , 1 − x1 − ⟨e, x3 ⟩, x1 − x2 , x3 − x2 e) .
P

P
Then, (α, β, γ, s) is a feasible solution to (P K ). If (x1 , x2 , x3 ) is an interior feasible solution to (DK), wePcan easily see that (α, β, γ, s) is an interior feasible solution to (P K ). Similarly, for any feasible solutionP(y, z, t, w) to (PKP ), let (κ, f ) = (−t, y). Then, (κ, f ) is a feasible solution to (DK ) because −κ + b⊤ f = w

41

and
1+κ−


1
⟨e, e⟩
1
1 + κ(1 + ⟨e, e⟩) − (b − Ae)⊤ f(b − Ae)⊤ f =+1 + ⟨e, e⟩
1 + ⟨e, e⟩ 1 + ⟨e, e⟩⟨e, e⟩
1=+
1 + ⟨e, κe + A∗ f ⟩ + κ − b⊤ f
1 + ⟨e, e⟩ 1 + ⟨e, e⟩⟨e, e⟩⟨e, e⟩=+ 1 − ⟨e, z⟩ − w =1 + ⟨e, e⟩
1 + ⟨e, e⟩hold. Moreover if (y, z, t, w) is an interior feasible solution to (PKP ), we cab easily see that (κ, f ) is an
PPPinterior feasible solution to (DK ). Therefore (P K ) and (DK ) are strongly feasible.
P(2): (DK) has an optimal solution (x∗1 , x∗2 , x∗3 ) such that x∗2 ≥ 0. Noting that(α, β, γ, s) = (1 − (1 + ⟨e, e⟩)x∗2 , 1 − x∗1 − ⟨e, x∗3 ⟩, x∗1 − x∗2 , x∗3 − x∗2 e)PP

is a feasible solution to (P K ), we can find that the optimal value of (P K ) is smaller than or equal toPP
1 − (1 + ⟨e, e⟩)x∗2 . Since (P K ) and (DK ) are strongly feasible and 1 + ⟨e, e⟩ > 0, the optimal values ofP
P(P K ) and (DK ) are smaller than or equal to 1.
(3): If the optimal value is 1, we have
1 + κ∗ −1(b − Ae)⊤ f ∗ = κ∗ ≥ 0.
1 + ⟨e, e⟩

Since −κ∗ ≥ 0 holds, we find κ∗ = 0. Thus, f ∗ satisfies b⊤ f ∗ ≥ 0, −A∗ f ∗ ∈ K and b⊤ f ∗ + ⟨e, −A∗ f ∗ ⟩ =1 + ⟨e, e⟩. If b⊤ f ∗ = 0, then ⟨e, −A∗ f ∗ ⟩ = 1 + ⟨e, e⟩ holds, which implies that −A∗ f ∗ ̸= 0. Therefore,(f ∗ , −A∗ f ∗ ) is a reducing direction for (P). If b⊤ f ∗ > 0, then we can easily see that (f ∗ , −A∗ f ∗ ) is an
improving ray of (D).
P(4): Since (α∗ , β ∗ , γ ∗ , s∗ ) is a feasible solution to (P K ), we find that 
1 − α∗
1 − α∗∗∗A s +e = γ +b
1 + ⟨e, e⟩
1 + ⟨e, e⟩holds. Let α∗ < 1. Noting that γ ∗ ≥ 0 and s∗ ∈ K, we can easily see that

1 + ⟨e, e⟩
1 − α∗∗es+γ ∗ (1 + ⟨e, e⟩) + 1 − α∗
1 + ⟨e, e⟩
is an interior feasible solution to (P).

4.3.2

Experimental flow and results

Now, let us explain the outline of our experiments to determine the feasibility status of SDPLIB
instances and the weakly infeasible instances from [14]. The flow of this experiment is almost thesame as that of Section 4.2. In other words, we obtained approximate optimal primal-dual solutionsPP(α∗ , β ∗ , γ ∗ , s∗ , κ∗ , f ∗ ) to (P K ) and (DK ) using the solvers with the default setting, the solvers with thetight setting or Algorithm 6. Then, we compared these solutions in terms of accuracy and optimality.
While the accuracy and optimality of outputs were measured using DIMACS errors in Section 4.2, we
1evaluated the outputs (α∗ , β ∗ , γ ∗ , s∗ , κ∗ , f ∗ ) by checking the values of 1 − α∗ , 1 − 1+⟨e,e⟩(b − Ae)⊤ f ∗ ,b⊤ f ∗ and λmin (−A∗ f ∗ ) in this experiment. In what follows, θ̄P and θ̄D denote the primal and dualPP
objective values of (P K ) and (DK ) for (α∗ , β ∗ , γ ∗ , s∗ , κ∗ , f ∗ ), respectively.
42

Table 9: Results of feasibility determination experiments for the ill-posed group instances from SDPLIB:
Mosek with the tight settings

Instance

1 − θ̄P

1 − θ̄Db⊤ f ∗

λmin (−A∗ f ∗ )time(s)gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

8.22e-15
2.95e-14
2.95e-14
2.95e-14
2.95e-14
4.22e-13
2.22e-15
4.04e-14
1.39e-13
3.47e-13
1.84e-13
5.98e-14
1.62e-13
5.38e-14
4.44e-16
4.64e-14
8.50e-14
1.96e-13
1.00e-13
3.17e-13
2.16e-13
1.55e-15
8.88e-16
1.55e-15

8.33e-15
3.00e-14
3.00e-14
3.00e-14
3.00e-14
4.17e-13
2.44e-15
4.07e-14
1.39e-13
3.30e-13
1.84e-13
5.91e-14
1.63e-13
5.33e-14
3.33e-16
4.65e-14
8.48e-14
1.96e-13
1.03e-13
3.07e-13
2.19e-13
1.78e-15
6.66e-16
1.55e-15

4.58e-16
7.31e-17
7.31e-17
7.31e-17
7.31e-17-2.83e-13-1.39e-15-2.61e-14-9.24e-14-2.12e-13-1.25e-13-4.43e-14-5.36e-14-3.91e-14
1.30e-21-1.99e-14-4.53e-14-1.53e-14-7.82e-14-3.55e-14-1.71e-13
5.68e-14-5.68e-14-5.68e-14-1.29e-14-2.76e-14-2.76e-14-2.76e-14-2.76e-14-3.69e-13-3.08e-15-2.82e-14-1.34e-13-1.97e-13-1.17e-13-4.40e-14-5.15e-14-3.76e-14-1.30e-21-3.16e-14-6.84e-14-1.19e-13-9.85e-14-1.03e-13-2.01e-13-2.50e-15-6.36e-18-9.00e-15

4.26e-02
6.61e-02
6.40e-02
6.55e-02
6.52e-02
8.78e-03
8.45e-03
8.88e-03
1.02e-02
8.48e-03
9.54e-03
9.56e-03
1.13e-02
1.22e-02
1.02e-02
1.95e-02
2.25e-02
2.48e-02
1.03e-02
2.52e-02
3.40e-02
8.68e-02
1.17e-01
2.86e-01

The first test cases are the ill-posed instances of SDPLIB defined in Section 4.2. When using the tighttolerances, Mosek obtained approximate optimal solutions for these instances with such high accuracy
that there was no need to use Algorithm 6. Thus, we did not apply Algorithm 6 and just summarized
the results of Mosek for the ill-posed group in Table 9. From Table 9, we can see that Mosek, using
the tight setting, determined that the primal problem for the ill-posed instances was in weak status andobtained highly accurate reduction directions.
The following test cases are the weakly infeasible instances of [14]. These instances are classified into four
sets, “clean-10-10”, “clean-20-10”, “messy-10-10” and “messy-20-10”. For example, the set “clean-10-10”
contains instances where m = 10 and r = 10, and the set “clean-20-10” contains instances where m = 20
and r = 10. The instance set labeled “messy” includes instances with a less obvious structure leading to
weak infeasibility than the set labeled “clean.” The results for the four instance sets are summarized in
Figures 11-13 and Table 10. Since each set contains 100 instances, we use box plots to report the valuesof |1 − θ̄P |, |1 − θ̄D |, |b⊤ f ∗ | and | min{λmin (−A∗ f ∗ ), 0}| logarithmized by the base 10. In these graphs,“Val1”, “Val2”, “Val3”, and “Val4” represent |1 − θ̄P |, |1 − θ̄D |, |b⊤ f ∗ | and | min{λmin (−A∗ f ∗ ), 0}|,respectively. Blue objects represent the results obtained with the solver using the default setting; red
objects represent the results obtained with Algorithm 6, and yellow objects denote results obtained withthe solver using the tight settings. Table 10 summarizes the average execution time for each method.
Because the problem size was small, there was no significant difference in the execution time of eachmethod.

43

Table 10: Average execution time for each method in the feasibility determination experiment

Methodclean-10-10

clean-20-10

messy-10-10

messy-20-10

Mosek (default)
Algorithm 6 using Mosek
Mosek (tight)
SDPA (default)
Algorithm 6 using SDPA
SDPA (tight)
SDPT3 (default)
Algorithm 6 using SDPT3
SDPT3 (tight)

8.31e-03
3.31e-01
1.07e-02
1.99e+00
1.62e-01
2.17e+00
7.86e-02
1.99e-01
1.09e-01

9.88e-03
1.27e+00
1.51e-02
2.05e+00
1.81e-01
2.90e+00
8.52e-02
2.25e-01
1.21e-01

8.11e-03
8.83e-01
1.31e-02
2.02e+00
2.52e-01
4.20e+00
8.31e-02
3.05e-01
1.05e-01

9.05e-03
1.13e+00
1.95e-02
2.14e+00
2.87e-01
3.51e+00
9.77e-02
3.02e-01
1.15e-01

First, let us compare the results on the instances labeled “clean”. From Figures 11 and 13, we seethat Mosek and SDPT3, using the tight settings, obtained the approximate optimal values with suchhigh accuracy that there is no need to use Algorithm 6. For the SDPA using the tight tolerances,
the optimal values were obtained with roughly the same accuracy as when using the default settings.
Figures 11-13 also show that Algorithm 6 consistently obtained highly accurate optimal values regardlessof the solver used together. Next, let us compare the results on the instances labeled “messy”. Here,
we note that Mosek returned incorrect outputs for some instances when using the tight tolerances.
While Mosek with the default setting obtained approximate optimal solutions (α∗ , β ∗ , γ ∗ , s∗ , κ∗ , f ∗ ) forP
all instances, Mosek with the tight setting returned incorrect infeasibility certificates to (P K ) for 23
instances of “messy-10-10” and 35 instances of “messy-20-10”. Figures 11-13 show that the accuracyof the optimal values obtained by Mosek and SDPT3 was worse than the results for the instance setslabeled “clean”. On the other hand, the accuracy of the dual optimal values θ̄D obtained by SDPA usingtight settings was better than the accuracy of the dual optimal values obtained for “clean” instances.
Algorithm 6 obtained optimal values for the instance sets labeled “messy” with the same accuracy as
for the instance sets labeled “clean.” In addition, Figures 11-13 show that the solvers and Algorithm 6
obtained approximate reducing directions for the weakly infeasible instances of [14], but their accuracy
was inferior to the results for the ill-posed instances of SDPLIB in Table 9.

44

(a) The results on clean-10-10(b) The results on clean-20-10(c) The results on messy-10-10(d) The results on messy-20-10

Figure 11: Numreical results for the weakly infeasible instances of [14] with Mosek

45

(a) The results on clean-10-10(b) The results on clean-20-10(c) The results on messy-10-10(d) The results on messy-20-10

Figure 12: Numreical results for the weakly infeasible instances of [14] with SDPA46

(a) The results on clean-10-10(b) The results on clean-20-10(c) The results on messy-10-10(d) The results on messy-20-10

Figure 13: Numreical results for the weakly infeasible instances of [14] with SDPT3

47

5

Concluding remarks

In this study, we proposed the algorithm for solving SCPs using projection and rescaling methods.
Although our algorithm can solve SCPs by itself, we proposed it intending to use it as a post-processing
step for the interior point method. In addition, we proposed some techniques to make our algorithm
more practical. We also conducted numerical experiments with SDPLIB instances and compared theaccuracy of the approximate optimal solution obtained from our method with that obtained from Mosek,
SDPA, and SDPT3. Our numerical results showed that
• For the well-posed group, i.e., the primal and dual problems are expected to be strongly feasible, ouralgorithm consistently obtained a more accurate approximate optimal solution than that returned
from the solvers.
• For the ill-posed group, i.e., at least one of the primal or dual problems is expected not to be strongly
feasible, our algorithm obtained a more accurate feasible solution than the solvers. However, ouralgorithm did not stably return a solution with good optimality for the ill-posed group comparedto the results for the well-posed group.
In addition, using the formulation in Proposition 4.3, we performed feasibility status determination
experiments on the ill-posed instances of SDPLIB and the weakly infeasible instances of [14]. For
the ill-posed instances of SDPLIB, the solver obtained approximate optimal solutions with such highaccuracy that there was no need to use our algorithm. However, for the instances of [14], our algorithm
obtained more accurate optimal values than the solvers, which implies that our algorithm can contributeto detecting the feasibility status of SDP. The numerical results also indicated the difficulties related tothe execution time of our algorithm.
To overcome this problem, we have two future directions. The first one is to consider an efficientcomputation of a projection matrix. If the problem size is large, the computation of the projection
matrix is expected to take much more time. Thus, efficient methods of computing projection matrices
will reduce the execution time of our algorithm. For example, using an approximate projection matrix
instead of an exact one might make our algorithm more practical, although the output solution may
be less accurate. The second is to process the operations of Algorithms 4 and 5 more efficiently using
parallel computation. Algorithms 4 and 5 choose the input value θ ∈ (LB, U B), call the projection andrescaling algorithm with the corresponding feasibility problem, and update U B or LB with θ according
to the output from the projection and rescaling algorithm until U B − LB ≤ θacc , where θacc is an
accuracy parameter specified by the user. Therefore, if Algorithms 4 and 5 execute the projection andrescaling algorithms in parallel for multiple input values, the execution time of these algorithms can be
reduced, which will reduce the execution time of Algorithm 6. In addition, we should consider why the
projection and rescaling methods could obtain feasible solutions with higher accuracy than the solvers.
To examine the differences between the projection and rescaling methods and interior point methods, it
might be a good idea first to explore the problem structure that the projection and rescaling methods
can solve more accurately than the solvers.

Acknowledgement
This work was supported by JSPS KAKENHI Grant Numbers JP21J20875, 22K18866, 23H01633.

48

References[1] MOSEK ApS. MOSEK Optimization Toolbox for MATLAB manual. Version 9.3, 2022 [Accessed:
2023-10-15].
[2] Brian Borchers. Sdplib 1.2, a library of semidefinite programming test problems. Optimization
Methods and Software, 11(1-4):683–690, 1999.
[3] Jon Borwein and Henry Wolkowicz. Regularizing the abstract convex program. Journal of Mathematical Analysis and Applications, 83(2):495–530, 1981.
[4] Jon M Borwein and Henry Wolkowicz. Facial reduction for a cone-convex programming problem.
Journal of the Australian Mathematical Society, 30(3):369–380, 1981.
[5] Sergei Chubanov. A polynomial projection algorithm for linear feasibility problems. Mathematical
Programming, 153:687–713, 2015.
[6] Dmitriy Drusvyatskiy, Henry Wolkowicz, et al. The many faces of degeneracy in conic optimization.
Foundations and Trends® in Optimization, 3(2):77–170, 2017.
[7] J. Faraut and A. Korányi. Analysis on Symmetric Cones. Oxford mathematical monographs.
Clarendon Press, 1994.
[8] Leonid Faybusovich. Euclidean jordan algebras and interior-point algorithms. Positivity, 1:331–357,
1997.
[9] Robert M Freund, Fernando Ordóñez, and Kim-Chuan Toh. Behavioral measures and their correlation with ipm iteration counts on semi-definite programming problems. Mathematical programming,
109:445–475, 2007.
[10] K Fujisawa, M Fukuda, K Kobayashi, M Kojima, K Nakata, M Nakata, and M Yamashita. Sdpa
(semidefinite programming algorithm) and sdpa-gmp user’s manual—version 7.1. 1. Department ofMathematical and Computing Sciences, Tokyo Institute of Technology. Research Reports on Mathematical and Computing Sciences Series B-448, 1(4):12, 2008.
[11] Didier Henrion, Simone Naldi, and Mohab Safey El Din. Exact algorithms for linear matrix inequalities. SIAM Journal on Optimization, 26(4):2512–2539, 2016.
[12] Shin-ichi Kanoh and Akiko Yoshise. A new extension of chubanov’s method to symmetric cones.
Mathematical Programming, pages 1–40, 2023.
[13] Nathan Krislock and Henry Wolkowicz. Explicit sensor network localization using semidefinite
representations and facial reductions. SIAM Journal on Optimization, 20(5):2679–2708, 2010.
[14] Minghui Liu and Gábor Pataki. Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming. Mathematical Programming, 167:435–480, 2018.
[15] Bruno F Lourenço, Tomonari Kitahara, Masakazu Muramatsu, and Takashi Tsuchiya. An extensionof chubanov’s algorithm to symmetric cones. Mathematical Programming, 173(1-2):117–149, 2019.
[16] Bruno F Lourenço, Masakazu Muramatsu, and Takashi Tsuchiya. Solving sdp completely with aninterior point oracle. Optimization Methods and Software, 36(2-3):425–471, 2021.
[17] Z-Q. Luo, J.F. Sturm, and Shuzhong Zhang. Duality results for conic convex programming. Econometric Institute Research Papers EI 9719/A, Erasmus University Rotterdam, Erasmus School of
Economics (ESE), Econometric Institute, 1997.
[18] Hans D Mittelmann. An independent benchmarking of sdp and socp solvers. Mathematical Programming, 95(2):407–430, 2003.
49

[19] Gábor Pataki. Strong duality in conic linear programming: facial reduction and extended duals. In
Computational and Analytical Mathematics: In Honor of Jonathan Borwein’s 60th Birthday, pages
613–634. Springer, 2013.
[20] Javier Pena and Negar Soheili. Solving conic systems via projection and rescaling. Mathematical
Programming, 166:87–111, 2017.
[21] Frank Permenter, Henrik A Friberg, and Erling D Andersen. Solving conic optimization problems
via self-dual embedding and facial reduction: a unified approach. SIAM Journal on Optimization,27(3):1257–1282, 2017.
[22] Frank Permenter and Pablo Parrilo. Partial facial reduction: simplified, equivalent sdps via approximations of the psd cone. Mathematical Programming, 171:1–54, 2018.
[23] James Renegar. A mathematical view of interior-point methods in convex optimization. SIAM,
2001.
[24] R Tyrrell Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
[25] Stefan H Schmieta and Farid Alizadeh. Extension of primal-dual interior point algorithms to symmetric cones. Mathematical Programming, 96(3):409–438, 2003.
[26] Negar Soheili and Javier Pena. A smooth perceptron algorithm. SIAM Journal on Optimization,
22(2):728–737, 2012.
[27] Negar Soheili and Javier Pena. A primal–dual smooth perceptron–von neumann algorithm. Discrete
Geometry and Optimization, pages 303–320, 2013.
[28] Michael J Todd. Semidefinite optimization. Acta Numerica, 10:515–560, 2001.
[29] Kim-Chuan Toh, Michael J Todd, and Reha H Tütüncü. On the implementation and usage of sdpt3–
a matlab software package for semidefinite-quadratic-linear programming, version 4.0. Handbook on
semidefinite, conic and polynomial optimization, pages 715–754, 2012.
[30] Levent Tunçel and Henry Wolkowicz. Strong duality and minimal representations for cone optimization. Computational optimization and applications, 53:619–648, 2012.
[31] Hayato Waki and Masakazu Muramatsu. A facial reduction algorithm for finding sparse sos representations. Operations Research Letters, 38(5):361–365, 2010.
[32] Hayato Waki and Masakazu Muramatsu. Facial reduction algorithms for conic optimization problems. Journal of Optimization Theory and Applications, 158:188–215, 2013.
[33] Henry Wolkowicz and Qing Zhao. Semidefinite programming relaxations for the graph partitioning
problem. Discrete Applied Mathematics, 96:461–479, 1999.
[34] Makoto Yamashita, Katsuki Fujisawa, and Masakazu Kojima. Implementation and evaluation of
sdpa 6.0 (semidefinite programming algorithm 6.0). Optimization Methods and Software, 18(4):491–
505, 2003.
[35] Akiko Yoshise. Interior point trajectories and a homogeneous model for nonlinear complementarity
problems over symmetric cones. SIAM Journal on Optimization, 17(4):1129–1153, 2007.
[36] Qing Zhao, Stefan E Karisch, Franz Rendl, and Henry Wolkowicz. Semidefinite programming
relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2:71–
109, 1998.
[37] Yuzixuan Zhu, Gábor Pataki, and Quoc Tran-Dinh. Sieve-sdp: a simple facial reduction algorithm
to preprocess semidefinite programs. Mathematical Programming Computation, 11:503–586, 2019.
50

A

Details of the modification in Section 3.3.2

Algorithm 7 computes the direction d such that b⊤ d > 0 using ytmp and ȳ, and then sets the value ofu as the upper bound on the step size α. After that, Algorithm 7 adjust the step size α and computey := ȳ + αd until c − A∗ y ∈ K or b⊤ (αd) ≤ 1e-16 holds. There is room for improvement in setting thevalue of u and choosing the step size α. However, recall that Algorithms 2 and 3 are used in a postprocessing step. Since the approximate optimal value is known in advance, the projection and rescaling
algorithms in Algorithm 2 and 3 will return an approximate optimal solution from the first iteration.
Thus, we can expect α satisfying c − A∗ (ȳ + αd) ∈ K to be small, which implies that further study on
how to choose u and α is not essential.
Algorithm 7 Update procedure for dual feasible solutions
1: Input: A, b, c, K, ytmp and ȳ such that c − A∗ ȳ ∈ K.
2: Output: A feasible solution (y, z) to (D).
3: if b⊤ ȳ = b⊤ ytmp then4:u←0
5: elseif b⊤ ȳ > b⊤ ytmp thend ← ȳ − ytmp , u ← 5elsed ← ytmp − ȳ
if c − A∗ ytmp ∈ K thenȳ ← ytmp , u ← 5
12:
else
13:
u←1
14:
end if15:
end if
16: end if
17: if u > 0 then
18:
α←u
19:
while b⊤ (αd) >1e-16 do
20:y ← ȳ + αd21:
if c − A∗ y ∈ K then22:
stop Algorithm 7 and return (y, c − A∗ y)
23:
else
24:
u ← α, α ∈ (0, u)
25:
end if26:
end while
27:
return (ȳ, c − A∗ ȳ)
28: else
29:
return (ȳ, c − A∗ ȳ)
30: end if
6:
7:
8:
9:
10:
11:

B

Further discussion of the modification in Section 3.3.4

Let us consider the following simple minimization problem (Ex.B). The feasible region of (Ex.B) is
illustrated in Figure 14. The optimal solution x∗ is (1, 0)⊤ ∈ R2 and the optimal value θ∗ is 1.
 
x1
1(Ex.B) min x1 s.t. 4 x1 + x2 = 1, x =∈ R2++ .
x2
x51

Figure 14: Feasible region of (Ex.B)
Using the formulation in Section 3.1.1, the feasibility problem FPS∞ (kerA(θ), R4++ ) is obtained, whereθ ∈ R and1
1 −1 04.
A(θ) =
1 0 −θ 1
Here, let us define v ∈ R4++ as v := ( √1α , √1β, 1, 1)⊤ for any (α, β)⊤ ∈ R2++ and consider the scaled
feasibility problem FPS∞ (kerĀ(θ), R4++ ) such that kerĀ(θ) = Qv (kerA(θ)).
 
 
x1
α
 x1
x2 

β −1 0 
44x2  = 0,
FPS∞ (kerĀ(θ), R4++ ) : find  τ  ∈ R s.t.

α 0 −θ 1τρρ
0 < x1 ≤ 1, 0 < x2 ≤ 1,
0 < τ ≤ 1, 0 < ρ ≤ 1.
To know the value of δ∞ (kerĀ(θ) ∩ R4++ ), let us represent the feasible region of FPS∞ (kerĀ(θ), R4++ ) on1
the τ -ρ plane. Noting that x1 = αθ τ − α1 ρ and x2 = 4−θ
4β τ + 4β ρ hold for any feasible solution (x1 , x2 , τ, ρ)
to FPS∞ (kerĀ(θ), R4++ ), the feasible region of FPS∞ (kerĀ(θ), R4++ ) is given by



1 4−θ
1
θ
τ − ρ,
τ+ρ, τ, ρ : 0 < θτ − ρ ≤ α, 0 < (4 − θ)τ + ρ ≤ 4β, 0 < τ, ρ ≤ 1 .
α
α
4β
4β
4β
For example, if 0 < θ < 4, α+4β
< 4−θ
, θβ ≤ 1, and α+4β
≤ 1 hold, the feasible region of
4
4
4
FPS∞ (kerĀ(θ), R++ ) is as shown in Figure 15a. In this case, we can easily see that the point giving the maximum value of δ∞ (kerĀ(θ) ∩ R4++ ) lies in the red line segment in Figure 15a. Thus, the valueof δ∞ (kerĀ(θ) ∩ R4++ ) is represented as the optimal value of a maximization problem maxτ ∈domT f (τ ),where f (τ ) = α4 τ (τ − β)(4β − (4 − θ)τ ) and dom T = (β, α+4β
4 ]. This maximization problem canbe solved with derivatives and simple calculations. The function f (τ ) is obtained by substituting
x1 = αθ τ − α1 ρ, x2 = 1, and ρ = 4β − (4 − θ)τ into x1 x2 τ ρ. Next, let us consider a more complex case.
4β
If 0 < θ < 4, α+4β
< 4−θ
, θβ ≤ 1, and β ≤ 1 < α+4βhold, the feasible region of FPS∞ (kerĀ(θ), R4++ )4
4is as shown in Figure 15b. The point giving the maximum value of δ∞ (kerĀ(θ) ∩ R4++ ) lies in thered or blue line segment in Figure 15b. Thus, the value of δ∞ (kerĀ(θ) ∩ R4++ ) is represented as4
the optimal valueof max{max τ ∈domT f (τ ), maxρ∈domR g(ρ)}, where f (τ ) = α τ (τ − β)(4β − (4 − θ)τ ),
1g(ρ) = αθ − α1 ρ 4−θ
4β + 4β ρ ρ, dom T = (β, 1], and dom R = [max{0, θ − α}, −(4 − θ) + 4β]. The
1function g(ρ) is obtained by substituting x1 = αθ τ − α1 ρ, x2 = 4−θ
4β τ + 4β ρ, and τ = 1 into x1 x2 τ ρ.

Considering the other cases in the same way, the values of δ∞ (kerĀ(θ) ∩ R4++ ) are summarized in Tables
11-14. The columns in these tables show the relations that hold for α, β, and θ. For example, the4βsecond column of Table 11 shows the case where 0 < θ < 4, α+4β
< 4−θ
, θβ < 1 and 1 ≤ β hold.
4
The “dom T ” and “dom R” rows show the domain of τ and ρ, respectively. The “δ∞ ” row shows the
52

4β
< 4−θ
, θβ ≤ 1, and α+4β≤1(a) 0 < θ < 4, α+4β444β(b) 0 < θ < 4, α+4β
< 4−θ
, θβ ≤ 1, and β ≤ 1 < α+4β
44Figure 15: Feasible region of FPS∞ (kerĀ(θ), R4++ )53

value of δ∞ (kerĀ(θ) ∩ R4++ ). Based on Tables 11-14, we computed the value of δ∞ (kerĀ(θ) ∩ R4++ ) by
substituting specific values into α, β, and θ, and then checked whether Assumption 3.14 holds and thepoint (α, β)⊤ ∈ R2++ such that δ∞ (kerĀ(θ) ∩ R4++ ) ≥ δ∞ (kerA(θ) ∩ R4++ ) can likely hold.
First, let us see whether Assumption 3.14 holds using Figure 16. Figure 16 shows a heatmap of thevalue of δ∞ (kerĀ(θ) ∩ R4++ ) when β = 1 − α4 , i.e., (α, β)⊤ satisfies the linear constraint of (Ex.B). In
Figure 16, the horizontal axis represents the value of θ, the vertical axis represents the value of α, andthe cells show the values of δ∞ (kerĀ(θ) ∩ R4++ ) corresponding to θ and α. This figure provides us withan intuitive understanding that Assumption 3.14 holds. We confirmed Assumption 3.14 holds for thisexample by checking the values of all cells.
Next, let us see what α and β are most likely to satisfy δ∞ (kerĀ(θ) ∩ R4++ ) ≥ δ∞ (kerA(θ) ∩ int K̄).
We computed the value of δ∞ (kerĀ(θ) ∩ R4++ ) for each θ ∈ {0.1, 0.2, . . . , 4.0}, α ∈ {0.1, 0.2, . . . , 4.2},
and β ∈ {0.1, 0.2, . . . , 1.3}, and then made Figure 17. In each graph in Figure 17, the horizontal axis
represents the value of α, the vertical axis represents the value of β, and the cells show the values ofδ∞ (kerĀ(θ) ∩ R4++ ) corresponding to θ, α, and β. We note that α = β = 1 implies kerĀ(θ) = kerA(θ).
From these figures, we can observe the following:• When max{θp , θ − 1} = θ − 1, i.e., θ > 1, the closer the point (α, β)⊤ is to the interior feasible⊤
solution (x1 , x2 ) such that x1 = θ − 1, i.e., (θ − 1, 5−θ4 ) the more likely it seems that δ∞ (kerĀ(θ) ∩44
R++ ) ≥ δ∞ (kerA(θ) ∩ R++ ) holds unless e is an approximate feasible solution for (P) such that⟨c, e⟩ ≃ θ − 1.
• When max{θp , θ − 1} = θp , i.e., 0 < θ < 1 the closer the point (α, β)⊤ is to the optimal solution(0, 1)⊤ , the more likely it seems that δ∞ (kerĀ(θ) ∩ R4++ ) ≥ δ∞ (kerA(θ) ∩ R4++ ) holds.

Figure 16: Heatmap of the value of δ∞ (kerĀ(θ) ∩ R4++ ) when (α, β) = (α, 1 − α4 )54

(a) θ = 0.1(b) θ = 0.5(c) θ = 1(d) θ = 2(e) θ = 3(f) θ = 4

Figure 17: The values of δ∞ (kerĀ(θ) ∩ R4++ )

55

56

[L, θ)
G

domT
domR
δ∞

ρ∈domR(0, θ)
max g(ρ)

1≤β

α+4β
<1
4

[L, 1]
G

θ−α<1
1
V

[L, 1]
G1 ≤ 4β−14−θτ ∈domT

1+α
θ

θ−α≥1

1
<1
θ

1
V

1+α
θ

θ−α<1
[ 4β−1, 1]
4−θ
[L, 4β − (4 − θ)]
FG

θ−α≥1

4β−1
<1
4−θ

β < 1 ≤ α+4β
4ρ∈domRθβ ≤ 1ρ∈domR(β, 1](0, 4β − (4 − θ)]max{ max f (τ ), max g(ρ)}

4β
β < 1 ≤ 4−θτ ∈domTF[ 4β−1, α+4β
]
4−θ
4

α+4β
<1
4

ρ∈domR

1+α
max g(ρ), F G := max{ max f (τ ), max g(ρ)}, V := 4βθ
2 ((4 − θ)(1 + α) + θ).

[L, θ)
G1 ≤ θ11≤βθ−4α + θβ ≤ 1 < θβ4τ ∈domTmax f (τ )

4β
<1
4−θ
4β
(β, 4−θ]ρ∈domR(0, θ)
max g(ρ)

1 ≤ θ1

α+4β
4β
≥ 4−θ
4

ρ∈domR(0, 1]
max g(ρ)

1< 1 ≤ 4β−1θ
4−θ[L, θ)
G

1 < θ1τ ∈domTρ∈domR(0, 4β − (4 − θ)]max{ max f (τ ), max g(ρ)}

4β−14β< 1 ≤ 4−θ4−θ[ 4β−1, 1]
4−θθβ > 14β≥ 4−θ
.
Table 12: The values of δ∞ (kerĀ(θ) ∩ R4++ ) when 0 < θ < 4 and α+4β
4max f (τ ), G :=F(β, α+4β]4τ ∈domT(β, 1][L, 4β − (4 − θ)]FG

β < 1 < α+4β
4

L := max{0, θ − α}, F :=

domT
domR
δ∞

1≤β

θβ < 1

α+4β
4β
< 4−θ
4

4β
Table 11: The values of δ∞ (kerĀ(θ) ∩ R4++ ) when 0 < θ < 4 and α+4β
< 4−θ
.
4

max f (τ )τ ∈domT

4β
<1
4−θ
4β
[ 4β−1,]4−θ 4−θ[L, 1)
G1≤ 1 < 1+αθθ

1 < θ−4α + θβ
4

1
V

1+α
θ

1+α
≤1
θ

57
domT
domR
δ∞

domT
domR
δ∞

(0, 1]
max g(ρ)ρ∈domRρ∈domR(0, 4β]max g(ρ)

4β < 1ρ∈domR(0, 1]
max g(ρ)

1 ≤ 4β1
β < 1 ≤ 4αρ∈domR[4 − α, 4β]
max g(ρ)

4β < 1ρ∈domR[4 − α, 1]
max g(ρ)

4−α<1

1+α
16β

1

1+α
4

1≤4−α

1 ≤ 4β1< 1 ≤ α+4β
4α4ρ∈domR[4 − α, 1]
max g(ρ)

4−α<1

1+α
16β

1

1+α
4

1≤4−α

α
<1≤β
4

ρ∈domR[4 − α, 4β]
max g(ρ)

4β < 1α<β
4ρ∈domR[4 − α, 1]
max g(ρ)

4 − α < 1 ≤ 4β

β < 1 ≤ α+4β
4

1+α
16β

1

1+α
4

1≤4−α

1

1+α
16β

1+α
4

1+α
16β

1

1+α
4

α+4β
4

4β
αβ + 4β 2

1 ≤ 4β4β < 1

α+4β
<1
4

4β
αβ + 4β 2

α+4β4

1 ≤ 4βα+4β<1
44β < 1

Table 14: The values of δ∞ (kerĀ(θ) ∩ R4++ ) when θ = 4 and α4 < β.

1≤ α4ρ∈domR(0, 1]
max g(ρ)

1≤β

α
≥β
4

Table 13: The values of δ∞ (kerĀ(θ) ∩ R4++ ) when θ = 4 and α4 ≥ β.

C

Detailed settings of the proposed algorithm

C.1

Practical termination conditions

C.1.1

Termination condition to deal with cases suffering from numerically unstable outputs

The projection and rescaling algorithms can return incorrect outputs due to numerical errors caused byscaling operations. Such outputs prevent Algorithms 4 and 5 from working correctly. Thus, we added
the practical termination conditions to our algorithms. In our numerical experiments, Algorithms 4 and
5 were set to terminate when 30 consecutive incorrect outputs were returned from the projection andrescaling method. We defined Algorithms 4 and 5 as obtaining incorrect outputs from the projection
and rescaling method if they obtain any output except the following:• a reducing direction for (P) or (D),• an improving ray of (P) or (D),• vectors (y, γ) that satisfies γ > 0 and λmin (c + A∗ γ1 y) ≥ -1e-4,• vectors (x, τ, ρ) that satisfies τ > 0, ∥A τ1 x − b∥ ≤ 1e-4 and λmin ( τ1 x) ≥ -1e-4, or• a certificate that there is no ε-feasible solution to the corresponding feasibility problem, i.e.,∗
FP(kerA(θk ), intK̄) or FP(rangeA(θk ) , intK̄).

C.1.2

Termination condition to deal with cases suffering from non-useful outputs

The projection and rescaling algorithms can return non-useful outputs for Algorithms 4 and 5. For
example, if the projection and rescaling method called in Algorithm 4 returns a certificate that there
is no ε-feasible solution to the input feasibility problem FP(kerA(θk ), intK̄), all Algorithm 4 can do is
update the value of LB. Since such output is likely to be obtained when (P) is not strongly feasible,
we considered it prudent to terminate Algorithm 4 when the projection and rescaling method begin to
return such outputs in succession. Thus, in the numerical experiments, Algorithms 4 and 5 were set toterminate when the projection and rescaling algorithms proved 30 consecutive times that there was no
ε-feasible solution to the corresponding feasibility problem. Note that in our experiments, Algorithms 4
and 5 did not terminate with this termination condition.

C.2

Implementation details of the projection and rescaling algorithm

Algorithm 6 used the projection and rescaling algorithm proposed in [12], which employs the smooth
perceptron scheme [26, 27] in the basic procedure. The reason for using this projection and rescaling
method is that the numerical experiments in [12] show that their method obtained accurate approximate
solutions in a shorter time than the other methods. We set the termination parameter as ξ = 1/4 in thebasic procedure for the same reasons stated in [12]. In addition, we set the accuracy parameter as ε =1e-16 in the main algorithm, which allows the projection and rescaling algorithm to obtain approximate
optimal solutions for (P) and (D) near the boundaries of the cone K.
In Algorithm 6, the projections PkerA(θ) and PrangeA(θ)∗ were computed in the same way as described in[12]. That is, we computed the projections PkerA(θ) and PrangeA(θ)∗ using the singular value decomposition. Let A ∈ Rm+1×d+2 be a matrix representing the linear operator A(θ) and I be the identity matrix.
58
Suppose that the singular value decomposition of a matrix A is given by A = U ΣV ⊤ = U Σm+1 O V ⊤where U ∈ Rm+1×m+1 and V ∈ Rd+2×d+2 are orthogonal matrices, and Σm+1 ∈ Rm+1×m+1 is a diagonal
matrix with m + 1 singular values on the diagonal. Since the projections PkerA(θ) and PrangeA(θ)∗ aregiven by PkerA(θ) = I − A⊤ (AA⊤ )−1 A and PrangeA(θ)∗ = A⊤ (AA⊤ )−1 A, respectively, we can compute
these projections as follows:
PrangeA(θ)∗ = A⊤ (AA⊤ )−1 A= A⊤ (U ΣΣ⊤ U ⊤ )−1 A= A⊤ U −⊤ (Σ2m+1 )−1 U −1 A
Im+1⊤
= V Σ⊤ Σ−2
ΣV
=
V
m+1
O


O
⊤
V ⊤ = V:,1:m+1 V:,1:m+1,
O⊤
and PkerA(θ) = I − PrangeA(θ)∗ = I − V:,1:m+1 V:,1:m+1, where V:,1:m+1 represents the submatrix fromcolumn 1 to column m + 1 of V .

C.3

How to compute (y, γ) from (z, ω, κ) ∈ rangeA(θ)∗ ∩ K̄If a nonzero point (z, ω, κ) ∈ rangeA(θ)∗ ∩ K̄ is obtained from the projection and rescaling methods in
Algorithms 4 and 5, we compute (y, γ) ∈ Rm+1 such that z = A∗ y + γc, ω = −b⊤ y − γθ and κ = γ. The
matrices U , Σ, and V described in the previous section are also used to compute such a (y, γ). Supposethat A ∈ Rm+1×d+2 is a matrix representation of the linear operator A(θ) and A is decomposed into
A = U ΣV ⊤ by the singular value decomposition. Then, we find
 
 
 
z

ω  = A⊤ y = V Σm+1 O ⊤ U ⊤ y .
γγ
κSince U and V are orthogonal matrices, we have
 
 
z

y
⊤ 
ω
= U Σ−1
V
.
O
m+1
γ
κ

C.4

Modification of the basic procedure

The basic procedure of [12] requires a constant ξ ∈ R such that 0 < ξ < 1 as an input. This procedure
finds a Jordan frame {c1 , c2 , . . . , cr } such that ⟨ci , x⟩ ≤ ξ holds for any feasible solution x of the input2
p2 rmax
iterations, where K is aproblem FPS∞ (L, int K) and for some i ∈ {1, 2, . . . , r} in at most2
ξ
Pp
Cartesian product of p simple symmetric cones K1 , . . . , Kp , r = i=1 ri is a rank of K and rmax =max{r1 , . . . , rp }. Whether ⟨ci , x⟩ ≤ ξ is valid is determined by calculating the upper bound ui of ⟨ci , x⟩.
If such a Jordan frame {c1 , c2 , . . . , cr } is obtained, the basic procedure terminates and returns the sets
C := {c1 , c2 , . . . , cr } and H := {i : ui ≤ ξ} to the main algorithm.PThen, thePmain algorithm scales
the problem FPS∞ (L, int K) as FPS∞ (Qv (L), int K), where v = √1ξ h∈H ch + h∈H/ ch . In this case,PP
however, the main algorithm can scale the problem more efficiently using v = h∈H √1uh ch + h∈H/ ch ,
which will reduce the computational time of Algorithms 4 and 5. Furthermore, if the same constantξ is used for all feasibility problems, Algorithms 4 and 5 might encounter problems where the basic
p2 r 2
procedure requires many iterations, close to the maximum number of iterations ξmax
. Therefore, we
2
modified the projection and rescaling algorithm of [12] called in Algorithms 4 and 5 as follows:59• Modification of the basic procedure– Let k be the number of iterations of the basic procedure. The termination condition varies
depending on the value of k.
1. If k ≤ 100, the basic procedure terminates when a Jordan frame {c1 , c2 , . . . , cr } such that⟨ci , x⟩ ≤ ui ≤ ξ holds for any feasible solution x of the input problem FPS∞ (L, int K) andfor some i ∈ {1, 2, . . . , r} is obtained. Then, return C := {c1 , c2 , . . . , cr }, H := {i : ui ≤ ξ}
and U := {ui : ui ≤ ξ} to the main algorithm.
2. If k > 100, the basic procedure terminates when a Jordan frame {c1 , c2 , . . . , cr } such that⟨ci , x⟩ ≤ ui < 1 holds for any feasible solution x of the input problem FPS∞ (L, int K) andfor some i ∈ {1, 2, . . . , r} is obtained. Then, return C := {c1 , c2 , . . . , cr }, H := {i : ui < 1}
and U := {ui : ui < 1} to the main algorithm.
• Modification of the main algorithm
1. Suppose that the basic procedure returns the sets C, H and U at the k-th iteration of
the main algorithm.
Then, scale the linear subspace Lk as Lk+1 ← Qv (Lk ), where v =
P
P
1
√
h∈H
/ ch .
h∈H uh ch +D

Computational results on SDPLIB

The detailed results of the experiments conducted in Section 4.2 are summarized in Tables 15-32. Pleaserefer to the respective solver’s documentation for the meaning of the messages returned by each solverin Tables 15-26. Tables 27-32 summarize the results of Algorithm 6. The columns “Algorithm 5” and“Algorithm 4” in Tables 27-32 summarize the execution time of each algorithm and what termination
conditions they met to finish. “Complete” means that the algorithm terminated because U B −LB ≤ θacc
was satisfied, “Time Over” means that the algorithm terminated because its execution time exceeded 30
minutes, and “Numerical Error” means that the algorithm terminated because the termination condition
defined in Appendix C.1 was met.

60

61

err1

1.55e-05
8.99e-06
6.34e-06
2.65e-06
2.12e-08
1.19e-07
7.90e-08
1.22e-07
1.77e-07
1.74e-06
1.91e-07
3.06e-07
2.51e-07
1.50e-06
5.91e-07
7.73e-09
3.65e-07
6.19e-125.65e-12
4.94e-12
1.57e-12
1.47e-11
1.01e-09
9.80e-09
5.18e-09
1.08e-09
9.59e-09
3.89e-09
8.77e-10
7.07e-09
9.28e-09
7.28e-08
2.47e-08
4.30e-08

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss81.15e-06
7.04e-07
5.36e-07
2.37e-07
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
3.07e-14
0.00e+00
0.00e+00
0.00e+00
8.00e-170.00e+00
2.51e-15
0.00e+00
0.00e+00
5.99e-16
8.09e-10
5.10e-11
5.65e-11
5.17e-10
1.15e-10
2.47e-10
4.40e-11
4.15e-10

err4-5.08e-09-4.05e-09-3.29e-09-1.60e-09-1.36e-09-3.89e-09-2.30e-09-6.64e-10-4.50e-09-6.06e-10-3.73e-09-4.59e-09-4.06e-09-5.23e-10-4.22e-09-1.23e-09-4.48e-09-1.72e-09-5.65e-10-6.00e-10-4.61e-09-7.56e-10-7.14e-11-5.93e-10-2.24e-10-2.49e-11-9.76e-10-1.53e-11-2.46e-11-4.65e-10-1.54e-11-1.52e-10-9.11e-11-2.78e-11

err5
4.80e-07
3.31e-07
3.31e-07
2.32e-07
2.06e-08
1.65e-07
1.37e-07
1.93e-07
4.07e-07
1.30e-07
4.98e-07
5.90e-07
6.36e-07
1.10e-07
8.76e-07
2.10e-08
7.11e-08
2.43e-09
1.44e-09
8.80e-10
3.99e-09
4.17e-109.30e-10
9.16e-09
4.90e-09
1.04e-09
1.22e-08
2.08e-09
1.00e-09
6.51e-09
4.70e-09
7.49e-08
1.39e-08
1.67e-08

err6
3.03e-01
2.84e-01
2.84e-01
3.38e-01
1.26e-02
3.00e-02
7.52e-02
1.84e-01
3.79e-01
7.06e-01
1.55e+00
2.47e+00
3.72e+00
8.12e+00
1.03e+01
1.70e-02
9.28e-03
5.24e-02
7.47e-02
8.57e-02
7.58e-02
7.78e-02
2.40e-02
1.25e-01
4.12e-01
1.40e+00
2.62e-03
2.52e-02
8.61e-03
5.75e-03
7.87e-02
7.94e-02
1.43e-02
3.98e-01time(s)MSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES TRM STALLMSK RES OKMSK RES OK

Message

PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE

Problem status

Table 15: Results of Mosek using the default setting on well-posed group instances

5.77e-13
4.11e-13
2.69e-08
5.13e-122.62e-10
4.57e-10
1.64e-09
3.20e-09
3.04e-09
1.10e-08
1.01e-08
1.32e-08
1.19e-08
3.36e-08
2.79e-08
1.16e-11
1.03e-11
3.69e-08
1.89e-08
2.34e-08
2.45e-08
5.50e-08
4.38e-10
2.00e-07
9.20e-10
1.51e-10
6.69e-09
1.09e-10
1.43e-08
1.38e-09
2.69e-10
4.23e-07
1.34e-10
1.35e-09

Results of Mosek

Problem

D.1

OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL

Solution status

62

err1

2.16e-08
1.40e-08
5.31e-06
1.62e-06
2.23e-07
2.12e-08
9.39e-11
2.02e-09
2.46e-05
5.31e-08
4.48e-06
4.76e-07
3.78e-09
2.59e-09
5.00e-01
1.13e-08
1.15e-07
2.42e-08
2.94e-09
6.05e-08
3.10e-10
1.69e-07
7.76e-10
1.67e-07

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
2.75e-04
7.13e-12
4.63e-07
1.12e-05
1.82e-04
4.13e-10
2.09e-10
2.04e-11
4.46e-06
6.37e-11
1.14e-09
1.51e-12
1.67e-08
5.18e-09
1.79e+00
8.84e-09
1.14e-10
4.26e-09
9.91e-09
3.06e-11
1.07e-10
1.59e-11
5.49e-11
5.42e-06

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
2.14e-160.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4-9.09e-11-8.63e-10
6.95e-09
6.00e-09-1.60e-10-1.25e-08-1.73e-08-4.37e-09-1.51e-06-1.25e-07-2.96e-07-7.15e-07-1.45e-07-2.26e-07-1.12e-18-9.03e-07-8.94e-07-3.48e-06-8.25e-11-2.20e-09-4.48e-09-4.30e-09-4.88e-09-3.01e-08

err5
7.95e-08
2.70e-07
8.42e-08
5.15e-08
3.30e-08
1.35e-07
3.18e-07
7.70e-08
2.36e-05
2.00e-06
5.10e-06
9.92e-06
2.01e-06
4.86e-06
1.20e-29
2.61e-05
3.10e-05
1.36e-04
2.74e-09
1.04e-07
2.20e-07
5.81e-07
4.09e-07
3.48e-06

err6
2.75e-01
3.01e-01
3.28e-01
3.34e-01
4.92e-01
3.32e-02
2.81e-02
1.47e-02
1.61e-02
3.22e-02
1.10e-02
1.60e-02
3.07e-02
3.38e-02
4.34e-02
5.12e-02
5.11e-02
6.69e-02
1.30e-02
7.96e-02
1.62e-01
3.02e-01
4.96e-01
7.66e-01time(s)MSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES OKMSK RES OKMSK RES OKMSK RES TRM STALLMSK RES OKMSK RES TRM STALL

Message
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
ILL POSEDPRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE

Problem status

Table 16: Results of Mosek using the default setting on ill-posed group instances

OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
PRIMAL ILLPOSED CER
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL

Solution status

63

err1

arch0
4.05e-08
arch2
7.79e-09arch4
1.10e-08
arch8
2.14e-07
control1 2.56e-11
control2 1.98e-08
control3 2.14e-07
control4 9.46e-08
control5 9.29e-08
control6 7.40e-07
control7 1.17e-07
control8 7.14e-07
control9 1.45e-07
control10 3.34e-07
control11 7.97e-07
hinf2
1.73e-09
hinf9
3.26e-10
mcp1007.18e-14
mcp124-1 3.21e-14
mcp124-2 5.80e-13
mcp124-3 7.23e-15
mcp124-4 4.55e-13
theta12.61e-13
theta2
1.57e-12
theta3
1.16e-12
theta45.48e-13
truss11.68e-11
truss2
1.36e-12
truss35.31e-01
truss42.07e-12
truss52.42e-12
truss6
7.46e-01
truss77.44e-01
truss81.12e+00

Problem

2.25e-09
3.70e-12
2.52e-10
1.70e-100.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
4.75e-15
0.00e+00
0.00e+00
5.00e-15
0.00e+00
0.00e+00
4.14e-16err2
5.75e-13
4.03e-13
6.95e-13
5.04e-12
2.85e-10
1.41e-03
2.74e-03
2.16e-02
2.37e-02
4.19e-02
1.16e-01
7.13e-02
1.62e-02
1.85e-01
1.76e-02
2.27e-04
6.74e-14
4.48e-13
7.83e-13
6.37e-13
7.08e-13
4.25e-13
2.05e-13
4.30e-13
6.90e-13
1.07e-12
1.91e-09
1.96e-13
3.52e-01
4.47e-13
2.84e-13
4.98e-01
4.99e-01
4.55e-01

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
2.73e-110.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
4.30e-17
1.25e-16
3.86e-17
1.45e-16
1.35e-160.00e+00
6.82e-160.00e+00
0.00e+00
1.44e-12
2.38e-15
9.46e-15
1.58e-13
2.50e-14
8.12e-13
1.60e-14
9.26e-16err4-9.65e-12-2.11e-14-1.55e-12-1.14e-12-1.12e-13-5.33e-10-3.63e-09-1.29e-09-1.59e-09-9.65e-09-2.39e-09-2.90e-09-2.80e-09-4.78e-09-1.76e-08-2.41e-08-1.28e-13-7.61e-14-1.28e-13-9.49e-14-1.29e-13-7.77e-14-1.90e-14-8.93e-14-3.47e-14-3.36e-15-1.82e-12-8.03e-16-1.12e-14-1.39e-13-3.31e-15-1.30e-10-2.66e-11-4.25e-16

err5
9.30e-10
1.73e-12
1.56e-10
1.66e-10
1.68e-122.12e-08
2.05e-07
1.59e-07
1.80e-07
1.60e-06
3.91e-07
4.18e-07
5.08e-07
8.24e-07
2.99e-06
4.15e-07
2.79e-12
1.03e-13
2.99e-13
1.34e-13
1.12e-13
4.14e-14
2.43e-13
1.41e-128.28e-13
9.17e-14
2.20e-11
1.06e-13
9.38e-14
1.99e-12
1.02e-12
2.08e-10
5.59e-12
3.55e-14err6
6.24e-01
3.19e-01
5.38e-01
5.61e-01
3.28e-02
5.25e-02
1.24e-01
3.07e-01
4.68e-01
1.06e+00
2.04e+00
3.30e+00
4.38e+00
9.82e+00
1.37e+01
2.14e-02
1.20e-02
1.10e-01
1.37e-01
1.84e-01
1.46e-01
1.53e-01
3.18e-02
1.60e-01
5.07e-01
1.61e+00
3.44e-03
3.83e-02
2.53e-02
5.31e-03
1.09e-01
7.64e-02
2.19e-02
6.79e-01time(s)MSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES OKMSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES OKMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALL

Message
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
UNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNPRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
UNKNOWNPRIMAL AND DUAL FEASIBLE
PRIMAL INFEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL AND DUAL FEASIBLE
PRIMAL INFEASIBLE
PRIMAL INFEASIBLE
PRIMAL INFEASIBLE

Problem status

Table 17: Results of Mosek using the tight setting on well-posed group instances

OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMALUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNOPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMAL
OPTIMALUNKNOWNOPTIMAL
PRIMAL INFEASIBLE CER
OPTIMAL
OPTIMAL
PRIMAL INFEASIBLE CERPRIMAL INFEASIBLE CERPRIMAL INFEASIBLE CER

Solution status

64

err1

2.16e-08
8.96e-10
5.31e-06
1.62e-06
2.23e-07
1.17e-11
1.01e-10
1.25e-09
2.46e-05
5.89e-08
4.48e-06
4.76e-07
7.61e-11
9.81e-10
1.30e-09
4.01e-08
4.11e-09
5.68e-12
6.44e-09
8.05e-10
1.20e-07
7.22e-09
1.67e-07

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
2.75e-04
3.98e-11
4.63e-07
1.12e-05
1.82e-04
2.39e-01
6.49e+00
5.31e-02
4.46e-06
1.49e-04
2.45e-05
6.65e-05
6.46e+00
3.91e-01
2.06e+02
2.79e-04
4.92e+00
1.32e-14
1.05e-05
2.60e-04
1.39e-04
3.62e-05
5.42e-06

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4-9.09e-11-3.45e-10
6.95e-09
6.00e-09-1.60e-10-2.48e-08-1.81e-08-1.58e-09-1.51e-06-3.40e-07-2.96e-07-7.15e-07-2.99e-07-8.93e-07-9.04e-07-8.93e-07-3.42e-06-1.27e-13-9.96e-08-2.11e-08-5.69e-09-1.85e-08-3.01e-08

err5
7.95e-08
5.92e-08
8.42e-08
5.15e-08
3.30e-08
2.57e-07
3.39e-07
2.52e-08
2.36e-05
5.22e-06
5.45e-06
9.99e-06
4.66e-06
1.91e-05
2.62e-05
3.06e-05
1.31e-04
5.04e-12
3.08e-06
1.03e-06
6.61e-07
1.65e-06
3.48e-06

err6
2.71e-01
5.69e-01
3.25e-01
3.27e-01
4.92e-01
2.41e-02
2.55e-02
2.75e-02
1.15e-02
1.50e-02
1.04e-02
1.43e-02
2.92e-02
2.74e-02
4.26e-02
3.72e-02
6.40e-02
1.47e-02
8.17e-02
1.84e-01
2.89e-01
5.84e-01
7.65e-01time(s)MSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES OKMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALLMSK RES TRM STALL

Message
UNKNOWNPRIMAL AND DUAL FEASIBLE
UNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNPRIMAL AND DUAL FEASIBLE
UNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWN

Problem status

Table 18: Results of Mosek using the tight setting on ill-posed group instances

UNKNOWNOPTIMALUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWNOPTIMALUNKNOWNUNKNOWNUNKNOWNUNKNOWNUNKNOWN

Solution status

65

D.2

err1
5.01e-08
1.10e-08
4.28e-09
1.01e-07
1.67e-09
9.98e-09
1.31e-07
1.74e-07
4.34e-07
6.50e-07
8.36e-08
6.24e-08
1.74e-08
8.34e-08
2.25e-07
1.71e-10
1.53e-05
1.55e-14
2.55e-14
5.67e-15
1.50e-14
1.52e-14
5.67e-17
1.79e-14
3.03e-15
1.97e-14
1.12e-13
4.92e-12
1.59e-13
5.08e-14
4.13e-11
2.39e-07
1.26e-06
1.16e-10

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss80.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
4.22e-120.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
6.41e-13
4.82e-13
4.50e-13
1.30e-12
7.38e-11
8.19e-11
2.52e-10
4.46e-10
5.88e-10
1.98e-09
1.73e-09
1.79e-09
2.04e-09
5.23e-09
5.13e-09
2.70e-12
1.01e-13
2.34e-15
1.64e-14
1.19e-14
8.00e-15
2.87e-15
6.09e-15
3.88e-14
4.65e-14
3.43e-14
8.38e-16
1.36e-14
2.63e-15
7.08e-16
8.36e-14
4.78e-13
1.13e-07
1.14e-07

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.78e-160.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4
1.18e-07
1.96e-07
5.96e-08
6.64e-09
2.62e-08
2.72e-09
1.66e-07-8.75e-17
1.01e-06
2.00e-06
1.13e-06
1.39e-06
9.58e-07
6.64e-06
3.32e-06
0.00e+00
4.79e-07
8.52e-09
5.60e-09
1.55e-08
1.38e-08
1.09e-08
2.59e-08
7.13e-09
7.76e-09
1.12e-08
1.32e-08
1.85e-08
1.96e-08
2.60e-08
1.66e-08-1.70e-08
2.90e-08
6.74e-09

err5
1.18e-07
1.96e-07
5.96e-08
5.59e-09
2.59e-08
8.35e-08
1.81e-07
1.19e-07
1.06e-06
1.86e-06
1.12e-06
1.38e-06
9.60e-07
6.61e-06
3.35e-06
3.32e-07
1.54e-13
8.52e-09
5.60e-09
1.55e-08
1.38e-08
1.09e-08
2.59e-08
7.13e-09
7.76e-09
1.12e-08
1.32e-08
1.85e-08
1.96e-08
2.60e-08
1.66e-08
6.75e-12
1.42e-09
9.30e-08

err6
5.31e+00
4.82e+00
4.81e+00
5.33e+00
6.63e+00
7.39e+00
9.76e+00
1.08e+01
1.25e+01
1.76e+01
1.95e+01
1.90e+01
1.97e+01
2.40e+01
2.95e+01
5.21e+00
1.57e+01
2.50e+00
2.77e+00
2.68e+00
2.70e+00
2.50e+00
2.43e+00
3.55e+00
4.30e+00
4.50e+00
9.74e+00
5.71e+01
1.19e+01
9.74e+00
7.41e+01
5.74e+02
3.82e+02
8.01e+01

time(s)pdFEAS
pdFEAS
pdFEAS
pFEAS
pdOPT
pdOPT
pFEAS
pFEAS
pFEAS
pFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pFEAS
pdOPT
pFEAS
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pdOPT
pFEAS
pFEAS
pdOPT

Message

Table 19: Results of SDPA using the default setting on well-posed group instances

ProblemResults of SDPA

66

err1
1.19e-07
3.06e-07
3.48e-08
1.72e-08
1.28e-11
2.32e-09
1.22e-06
4.09e-09
8.46e-04
4.11e-05
1.58e-03
4.82e-05
4.86e-07
8.13e-07
2.66e-04
1.25e-03
1.03e-05
6.09e-04
5.36e-08
4.86e-08
9.08e-08
4.39e-08
4.61e-08
7.58e-08

Problem
gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
2.19e-12
6.81e-12
7.06e-12
2.33e-128.30e-12
3.63e-12
4.87e-13
8.61e-12
2.85e-13
1.15e-12
1.68e-13
4.94e-13
1.98e-10
1.72e-10
2.18e-10
1.81e-06
5.39e-12
1.35e-06
1.60e-12
2.63e-12
2.52e-11
3.60e-12
1.11e-11
3.31e-11

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4
4.35e-09
1.20e-08
4.87e-08
3.91e-08
3.97e-08
1.72e-07
1.29e-04
0.00e+00-6.17e-04-2.49e-05
1.00e-02
1.72e-06-2.46e-04-4.67e-04-7.56e-01-1.56e-02
2.24e-04-1.80e-02
2.60e-05
8.18e-05
1.46e-04
1.15e-04
1.68e-04
3.67e-04

err5
8.81e-09
1.52e-08
5.01e-08
4.05e-08
4.10e-08
3.19e-06
1.84e-04
6.08e-07
3.77e-05
1.24e-06
1.15e-02
8.35e-05
2.27e-07
1.25e-04
1.00e+01
1.15e-01
1.34e-03
1.65e-01
3.11e-05
1.07e-04
1.85e-04
1.35e-04
1.90e-04
4.53e-04

err6
3.24e+00
4.27e+00
3.37e+00
3.27e+00
3.61e+00
5.88e+00
4.19e+00
5.24e+00
5.23e+00
8.01e+00
3.84e+00
4.89e+00
1.26e+01
1.20e+01
7.78e+00
4.30e+00
5.82e+00
4.77e+00
2.08e+00
2.18e+00
2.82e+00
2.57e+00
2.97e+00
4.66e+00

time(s)
pdOPT
pFEAS
pdOPT
pdOPT
pdOPT
pdFEAS
pFEAS
pdOPT
pFEAS
pFEAS
pFEAS
pFEAS
pFEAS
pFEAS
pFEAS
pdINF
pFEAS
pdINF
pFEAS
pFEAS
pFEAS
pFEAS
pFEAS
pFEAS

Message

Table 20: Results of SDPA using the default setting on ill-posed group instances

67

err1
2.13e-08
1.39e-09
3.05e-09
1.01e-07
6.78e+01
1.16e+02
2.80e+02
1.57e+02
3.24e+02
1.49e+02
2.43e+02
3.34e+02
2.93e+02
3.54e+02
1.80e+02
2.47e-10
9.23e-07
3.55e-14
3.42e-14
7.72e-15
1.54e-14
3.17e-14
1.12e-16
1.79e-14
3.03e-15
3.35e-14
1.12e-13
1.90e-13
1.59e-13
5.08e-14
3.61e-11
1.43e-06
6.77e-07
3.38e-10

Problem
arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss80.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.24e-15
0.00e+00
0.00e+00
4.97e-15

err2
6.39e-13
4.88e-13
4.42e-13
1.30e-12
1.17e-12
1.51e-12
2.79e-12
4.36e-12
4.14e-12
9.07e-12
9.39e-12
1.13e-11
1.47e-11
1.70e-11
3.22e-11
1.52e-12
3.28e-14
2.33e-15
1.63e-14
1.18e-14
8.11e-15
3.06e-15
5.87e-15
3.88e-14
4.65e-14
3.53e-14
8.38e-16
1.35e-14
2.63e-15
7.08e-16
2.02e-14
5.21e-13
3.24e-13
1.91e-14

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.53e-14
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
6.45e-170.00e+00
0.00e+00
1.82e-16err4
9.40e-10
2.39e-10
2.41e-10
6.64e-09-1.18e-01-5.49e-02-8.78e-02-5.41e-02-7.10e-02-2.28e-02-3.71e-02-7.43e-02-5.85e-02-2.75e-02-3.69e-02-2.22e-07
3.41e-09
8.52e-10
5.61e-10
1.56e-09
1.40e-10
1.09e-10
2.61e-09
7.13e-09
7.76e-09
1.13e-09
1.32e-08
1.02e-09
1.96e-08
2.60e-08
3.10e-13
2.61e-08-4.21e-08
1.84e-12err5
9.76e-102.32e-10
2.13e-10
5.59e-09
1.36e-01
2.30e-01
3.45e-01
2.29e-01
4.32e-01
2.67e-01
3.46e-01
4.21e-01
4.23e-01
4.04e-01
3.54e-01
5.74e-08
4.12e-11
8.52e-10
5.61e-10
1.56e-09
1.40e-10
1.09e-10
2.61e-09
7.13e-09
7.76e-09
1.13e-09
1.32e-08
1.02e-09
1.96e-08
2.60e-08
7.79e-14
1.61e-11
1.11e-10
1.13e-13err6
5.75e+00
5.93e+00
5.95e+00
5.37e+00
1.91e+00
2.24e+00
2.69e+00
3.09e+00
3.35e+00
4.94e+00
5.16e+00
5.24e+00
6.35e+00
6.55e+00
8.59e+00
5.93e+00
7.68e+00
2.89e+00
3.17e+00
3.07e+00
3.17e+00
3.03e+00
2.79e+00
3.87e+00
4.55e+00
6.14e+00
1.04e+01
6.89e+01
1.26e+01
1.05e+01
1.13e+02
6.09e+02
4.17e+02
1.25e+02

time(s)
pFEAS
pFEAS
pFEAS
pFEAS
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pdFEAS
pFEAS
pFEAS
pFEAS
pFEAS

Message

Table 21: Results of SDPA using the tight setting on well-posed group instances

68

err1
1.29e-06
4.18e-06
1.25e-05
9.50e-07
1.39e-06
8.31e-09
7.82e-07
1.34e-08
1.84e-04
5.09e-05
1.58e-03
6.65e-06
1.63e-02
2.85e-03
2.19e-02
1.25e-03
3.83e-06
6.09e-04
2.61e-07
3.37e-08
1.63e-08
2.65e-07
1.13e-07
5.07e-08

Problem
gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
2.60e-12
6.10e-12
8.94e-12
1.58e-12
1.00e-12
1.46e-12
4.57e-13
9.86e-12
1.45e-13
2.19e-13
1.68e-13
5.11e-13
2.42e-13
2.04e-13
1.84e-13
1.81e-06
6.52e-12
1.35e-06
3.49e-13
1.64e-12
1.71e-12
2.08e-12
1.32e-119.72e-12

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4
1.74e-05
6.72e-05
1.28e-05
7.03e-06
5.53e-06
6.23e-05
1.29e-05-3.16e-07-6.70e-04-5.09e-05
1.00e-02-2.20e-06-1.20e-02-3.80e-03-8.30e-02-1.56e-02
1.43e-03-1.80e-02
1.96e-06
3.29e-05
7.23e-05
4.34e-04
1.27e-04
3.36e-04

err5
1.74e-05
6.74e-05
1.28e-05
7.06e-06
5.54e-06
8.69e-05
4.98e-05
3.88e-07
1.12e-04
4.53e-04
1.15e-02
6.88e-05
4.76e-02
3.52e-02
3.70e-01
1.15e-01
4.21e-03
1.65e-01
2.71e-06
4.25e-05
8.48e-05
4.78e-04
1.40e-04
3.80e-04

err6
2.37e+00
2.90e+00
2.83e+00
2.63e+00
2.71e+00
4.20e+00
4.55e+00
5.93e+00
4.55e+00
4.88e+00
3.85e+00
4.55e+00
3.53e+00
3.90e+00
3.21e+00
4.31e+00
5.08e+00
4.78e+00
2.07e+00
2.31e+00
3.17e+00
2.54e+00
2.93e+00
3.46e+00

time(s)
pdINF
pdINF
pdINF
pdINF
pdINF
pdINF
noINFO
pdINF
pdINF
pdINF
noINFO
pdINF
pdINF
pdINF
pdINF
pdINF
noINFO
pdINF
pdINF
pdINF
noINFOnoINFO
pdINF
noINFO

Message

Table 22: Results of SDPA using the tight setting on ill-posed group instances

69

D.3

err1
3.37e-08
3.57e-09
4.97e-09
6.30e-08
4.56e-09
5.26e-09
8.15e-08
3.04e-07
6.11e-08
2.00e-07
6.15e-08
2.08e-07
5.43e-08
4.99e-07
2.29e-07
3.40e-06
4.13e-07
6.46e-11
7.74e-12
7.88e-12
1.28e-13
7.54e-12
1.10e-11
1.18e-129.55e-12
5.16e-13
2.22e-09
1.43e-09
4.83e-14
4.28e-09
2.38e-10
7.79e-08
1.20e-08
3.19e-10

Problem

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss80.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
3.50e-11
8.81e-11
5.38e-119.55e-11
3.52e-11
6.48e-11
2.14e-10
3.72e-10
6.74e-10
1.74e-09
1.65e-09
1.82e-09
1.85e-09
5.74e-09
5.34e-09
1.90e-11
2.74e-12
4.16e-12
3.67e-12
4.73e-12
5.36e-12
1.07e-11
1.17e-10
5.65e-11
7.55e-11
1.00e-10
9.03e-11
5.70e-10
1.00e-12
1.38e-11
2.04e-12
4.08e-11
2.06e-11
7.41e-12

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4
1.56e-09
3.66e-09
3.57e-09
2.23e-09-3.42e-10
2.40e-08
8.82e-08
9.56e-08
1.68e-06
7.23e-07
4.63e-07
4.38e-07
6.29e-07
2.32e-06
1.13e-06-4.83e-05
5.62e-08
1.99e-09
7.46e-09
4.12e-10
4.94e-09
4.01e-10
8.20e-09
1.41e-09
2.60e-09
7.11e-09
1.11e-08
3.65e-09
7.14e-09
8.45e-09
5.44e-10
6.10e-08
9.89e-08
2.51e-10err5
1.59e-09
4.02e-09
3.84e-09
1.83e-09
1.72e-09
3.39e-08
1.26e-07
2.15e-08
1.67e-06
7.67e-07
4.65e-07
3.69e-07
6.37e-07
2.46e-06
1.10e-06
1.83e-09
4.18e-08
1.99e-09
7.46e-09
4.12e-10
4.94e-09
4.02e-10
8.19e-09
1.41e-09
2.61e-09
7.11e-09
6.86e-09
2.16e-09
7.14e-09
1.03e-10
5.76e-10
6.11e-08
1.02e-07
2.78e-10err6
9.76e-01
7.57e-01
6.99e-01
8.28e-01
2.71e-01
2.20e-01
5.61e-01
1.19e+00
2.46e+00
2.60e+00
4.05e+00
6.99e+00
9.50e+00
1.72e+01
2.28e+01
8.25e-02
1.10e-01
1.31e-01
1.80e-01
1.44e-01
1.32e-01
1.48e-01
2.37e-01
2.31e-01
7.41e-01
1.79e+00
9.05e-02
1.56e-01
8.08e-02
6.11e-02
2.26e-01
3.76e-01
2.78e-01
8.04e-01time(s)stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: steps too short consecutively
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: primal infeas has deteriorated too muchlack of progress in infeas
stop: relative gap < infeasibility
stop: primal infeas has deteriorated too muchstop: progress is badstop: steps too short consecutively
stop: progress is too slow
stop: steps too short consecutively
stop: progress is badstop: progress is too slow
stop: steps too short consecutively
stop: relative gap < infeasibility
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: relative gap < infeasibility
stop: primal infeas has deteriorated too muchstop: max(relative gap, infeasibilities) < 1.00e-08

Message

Table 23: Results of SDPT3 using the default setting on well-posed group instances

Results of SDPT3

70

err1
1.51e-09
2.09e-10
6.68e-10
2.53e-09
3.40e-09
5.35e-08
9.02e-06
8.36e-08
1.18e-04
8.57e-06
2.98e-06
1.49e-05
1.70e-06
3.63e-07
2.27e-11
2.86e-05
1.08e-06
1.57e-05
8.93e-12
7.57e-07
5.35e-07
1.40e-06
8.22e-08
5.13e-07

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
2.87e-10
2.59e-11
1.05e-10
4.51e-10
7.32e-10
4.83e-09
8.16e-12
2.57e-09
4.29e-09
1.89e-07
3.33e-10
2.59e-11
1.09e-06
1.31e-08
8.13e-06
9.42e-07
5.51e-08
2.88e-06
2.45e-09
1.95e-09
3.38e-09
4.47e-08
4.92e-08
2.31e-08

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4-1.09e-08-3.47e-08-6.28e-09-5.01e-09-1.80e-08-1.02e-05-1.18e-04-1.72e-06-4.72e-04
1.47e-06-8.52e-06-8.69e-05-3.95e-05-2.78e-04-1.52e-05-6.71e-05
6.62e-07
1.96e-04
4.50e-10-3.02e-05-1.88e-05-3.81e-05-3.99e-06-1.56e-05

err5
9.81e-09
8.64e-10
6.17e-09
4.15e-09
9.08e-10
1.45e-08
2.00e-09
2.32e-08
7.38e-07
2.00e-05
1.11e-06
9.44e-09
8.07e-04
1.30e-07
4.10e-05
2.17e-04
1.11e-05
3.89e-03
7.45e-10
2.66e-09
4.06e-09
2.97e-08
1.52e-08
1.04e-08

err6
2.83e-01
2.51e-01
1.91e-01
1.78e-01
1.88e-01
2.96e-01
1.15e-01
9.85e-02
1.30e-01
1.04e-01
7.10e-02
1.19e-01
1.74e-01
3.24e-01
4.45e-01
3.48e-01
4.20e-01
5.04e-01
1.46e-01
3.85e-01
6.65e-01
3.98e-01
4.97e-01
1.55e+00

time(s)stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: relative gap < infeasibility
stop: relative gap < infeasibility
stop: relative gap < infeasibility
stop: relative gap < infeasibility
stop: relative gap < infeasibility
lack of progress in infeas
stop: progress is badstop: steps too short consecutively
stop: progress is badstop: dual infeas has deteriorated too muchstop: progress is badstop: progress is bad*stop: steps too short consecutively
stop: max(relative gap, infeasibilities) < 1.00e-08
stop: steps too short consecutively
lack of progress in infeas
lack of progress in infeas
stop: primal infeas has deteriorated too muchlack of progress in infeas

Message

Table 24: Results of SDPT3 using the default setting on ill-posed group instances

71

err1
2.85e-08
2.60e-09
1.81e-09
6.30e-08
4.56e-09
5.26e-09
8.15e-08
3.04e-07
2.20e-07
2.00e-07
6.15e-08
2.08e-07
5.43e-08
4.99e-07
2.29e-07
3.40e-06
4.13e-07
5.06e-14
1.43e-13
3.32e-14
1.38e-13
6.22e-14
3.71e-13
7.87e-14
1.08e-13
6.31e-14
7.12e-13
8.81e-12
9.23e-12
5.87e-11
1.86e-10
7.79e-08
1.20e-08
3.19e-10

Problem
arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss80.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
6.87e-15
0.00e+00
0.00e+00
0.00e+00

err2
1.76e-11
4.71e-12
3.96e-129.55e-11
3.52e-11
6.48e-11
2.14e-10
3.72e-10
6.07e-10
1.74e-09
1.65e-09
1.82e-09
1.85e-09
5.74e-09
5.34e-09
1.90e-11
2.74e-12
3.35e-14
3.78e-14
3.43e-14
2.86e-14
3.18e-14
6.16e-13
2.34e-12
1.39e-11
5.78e-12
2.18e-14
7.15e-13
1.00e-12
1.95e-13
4.47e-13
4.08e-11
2.06e-11
7.41e-12

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4
6.76e-10
1.96e-10
1.49e-10
2.23e-09-3.42e-10
2.40e-08
8.82e-08
9.56e-08
4.30e-07
7.23e-07
4.63e-07
4.38e-07
6.29e-07
2.32e-06
1.13e-06-4.83e-05
5.62e-08
2.78e-14
4.76e-14
2.65e-14
3.22e-14
1.68e-14-2.14e-13
9.81e-14
2.37e-13
1.07e-13-1.17e-13
3.07e-12
2.52e-10
9.85e-11
6.65e-12
6.10e-08
9.89e-08
2.51e-10err5
8.01e-10
2.15e-10
1.58e-10
1.83e-09
1.72e-09
3.39e-08
1.26e-07
2.15e-08
4.10e-07
7.67e-07
4.65e-07
3.69e-07
6.37e-07
2.46e-06
1.10e-06
1.83e-09
4.18e-08
3.25e-14
4.49e-14
2.92e-14
2.24e-14
1.91e-14
3.78e-14
7.69e-14
2.92e-13
8.87e-14
1.29e-13
2.69e-12
2.53e-10
1.45e-122.64e-12
6.11e-08
1.02e-07
2.78e-10err6
8.76e-01
8.51e-01
9.22e-01
8.35e-01
9.74e-02
2.02e-01
5.02e-01
1.26e+00
3.22e+00
2.44e+00
4.32e+00
7.27e+00
1.03e+01
1.81e+01
2.42e+01
6.69e-02
8.46e-02
1.97e-01
2.32e-01
2.34e-01
2.58e-01
2.57e-01
3.33e-01
4.46e-01
1.19e+00
3.19e+00
1.22e-01
1.64e-01
1.01e-01
1.10e-01
4.54e-01
5.16e-01
4.15e-01
9.51e-01time(s)lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas

Message

Table 25: Results of SDPT3 using the tight setting on well-posed group instances

72

err1
1.50e-09
2.09e-10
6.49e-10
2.51e-09
3.41e-09
5.35e-08
9.02e-06
8.36e-08
1.60e-04
2.33e-06
2.98e-06
1.49e-05
4.71e-07
3.63e-07
1.72e-10
1.13e-05
2.82e-07
1.57e-05
3.46e-13
7.57e-07
5.35e-07
1.40e-06
8.22e-08
5.13e-07

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

0.00e+00
8.67e-170.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err2
6.39e-12
2.99e-11
2.21e-11
1.22e-11
8.18e-12
4.83e-09
8.16e-12
2.57e-09
3.97e-11
2.19e-10
3.33e-10
2.59e-11
1.35e-07
1.31e-08
9.50e-06
2.22e-07
1.38e-07
2.88e-06
3.52e-11
1.95e-09
3.38e-09
4.47e-08
4.92e-08
2.31e-08

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4-2.05e-08-3.50e-08-1.23e-08-9.01e-09-1.89e-08-1.02e-05-1.18e-04-1.72e-06-4.74e-04-1.59e-05-8.52e-06-8.69e-05-3.10e-04-2.78e-04-4.86e-06-5.34e-05-8.75e-07
1.96e-04
7.02e-12-3.02e-05-1.88e-05-3.81e-05-3.99e-06-1.56e-05

err5
2.24e-11
5.49e-10
1.06e-10
2.88e-11
1.02e-11
1.45e-08
2.00e-09
2.32e-08
4.97e-09
6.56e-08
1.11e-06
9.44e-09
1.16e-05
1.30e-07
1.56e-05
8.46e-05
5.95e-06
3.89e-03
1.34e-11
2.66e-09
4.06e-09
2.97e-08
1.52e-08
1.04e-08

err6
1.87e-01
2.79e-01
2.42e-01
2.32e-01
2.65e-012.12e-01
9.94e-02
9.39e-02
4.59e-01
1.12e-01
8.09e-02
1.47e-01
2.35e-01
3.05e-01
3.69e-01
3.71e-01
3.63e-01
1.67e+00
1.61e-01
4.61e-01
7.50e-01
3.60e-01
7.01e-01
1.51e+00

time(s)lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
sqlp stop: maximum number of iterations reachedlack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
sqlp stop: maximum number of iterations reachedstop: difficulty in computing predictor directions
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas
lack of progress in infeas

Message

Table 26: Results of SDPT3 using the tight setting on ill-posed group instances

73

D.4

err1

4.82e-13
4.20e-13
1.80e-13
6.91e-13
6.66e-15
1.26e-14
3.80e-14
3.67e-14
8.17e-14
2.11e-13
8.61e-14
4.69e-14
1.11e-13
9.25e-13
1.19e-13
5.34e-13
5.05e-11
1.70e-14
6.04e-14
8.82e-14
2.95e-14
1.84e-14
1.00e-15
9.85e-16
4.73e-16
2.26e-15
1.23e-15
2.55e-13
1.56e-14
3.06e-15
4.96e-13
1.04e-11
2.34e-12
1.98e-12

Problem

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss8err2
5.89e-17
1.83e-17
2.01e-17
3.88e-160.00e+00
2.85e-17
2.15e-16
8.62e-16
1.01e-15
2.82e-15
4.28e-16
5.47e-16
3.12e-16
4.09e-16
7.21e-160.00e+00
0.00e+00
6.66e-160.00e+00
0.00e+00
0.00e+00
1.48e-15
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
4.74e-15
0.00e+00
0.00e+00
6.22e-15
0.00e+00
0.00e+00
1.17e-15

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.80e-16
4.69e-16
6.82e-16
9.41e-160.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6
err5
4.14e-13
1.71e-13
2.90e-13
4.63e-14
4.39e-14
3.72e-13
7.55e-13
1.22e-12
7.36e-13
3.04e-13
3.07e-12
7.02e-12
4.20e-12
2.86e-11
4.28e-12-4.73e-11
3.61e-10
3.07e-15
1.03e-122.31e-13
2.89e-12
4.21e-15
3.64e-14
6.14e-14
9.47e-12
1.78e-11
1.85e-14
1.18e-14
1.41e-14
1.13e-14
2.71e-13
9.38e-12
2.51e-12
4.73e-13err6
4.29e-13
1.58e-13
2.98e-13
9.17e-14
4.66e-14
3.84e-13
7.53e-13
1.25e-12
7.57e-13
3.66e-13
3.11e-12
7.02e-12
4.20e-12
2.85e-11
4.26e-12
1.38e-09
8.40e-10
2.72e-15
1.04e-12
2.23e-13
2.89e-125.43e-15
3.76e-14
6.68e-14
9.46e-12
1.78e-11
1.80e-14
1.06e-14
1.58e-14
1.17e-14
2.73e-13
1.47e-11
2.50e-12
4.79e-13time(s)1.23e+03
1.60e+03
4.66e+02
6.69e+02
1.70e-01
2.64e+00
6.11e+00
1.53e+01
4.88e+01
6.59e+02
6.47e+02
8.62e+02
2.20e+03
3.83e+03
3.36e+03
2.66e-01
2.67e-01
1.77e+03
3.19e+03
3.39e+03
3.84e+03
3.54e+03
1.91e+03
8.74e+02
4.57e+03
4.03e+03
8.13e-01
4.27e+00
1.86e+00
3.17e-01
1.57e+02
4.95e+02
5.80e+02
2.35e+03

Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Time Over
Numerical Error
Time OverTime Over
Complete
Numerical Error
Complete
Complete
Complete
Complete
Complete
Time Over

Message
1.19e+03
1.57e+03
4.41e+02
5.85e+02
1.23e-01
2.50e+00
5.51e+00
1.28e+01
4.18e+01
6.32e+02
5.39e+02
7.53e+02
1.72e+03
1.78e+03
1.87e+03
7.50e-02
2.19e-01
5.06e+02
1.37e+03
1.52e+03
1.94e+03
1.52e+03
1.88e+03
5.40e+02
2.76e+03
2.07e+03
7.57e-01
1.18e+00
1.10e+00
2.38e-01
1.17e+02
1.07e+02
5.49e+02
1.85e+03

time(s)Algorithm 5Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Time OverTime OverTime OverTime Over
Complete
Complete
Time OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete

Message

4.30e+01
2.42e+01
2.45e+01
8.40e+01
4.76e-02
1.45e-01
6.09e-01
2.52e+00
7.04e+00
2.69e+01
1.07e+02
1.10e+02
4.86e+02
2.05e+03
1.50e+03
1.92e-01
4.78e-02
1.27e+03
1.82e+03
1.87e+03
1.90e+03
2.02e+03
2.83e+01
3.34e+02
1.80e+03
1.96e+03
5.61e-02
3.09e+00
7.62e-01
8.00e-02
3.95e+01
3.87e+02
3.04e+01
5.00e+02

time(s)Algorithm 4

Table 27: Results of Algorithm 6 using the solutions from Mosek on well-posed group instances

Results of the proposed method

74

err1

2.75e-13
2.29e-13
3.30e-13
7.27e-13
1.31e-13
5.37e-16
4.62e-12
4.51e-14
8.74e-12
1.89e-12
2.87e-11
1.40e-11
5.21e-13
2.59e-09
3.50e-09
8.76e-14
5.21e-09
2.76e-15
6.32e-15
2.85e-11
9.54e-13
5.24e-14
2.48e-12

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

err2
0.00e+00
0.00e+00
0.00e+00
2.16e-16
4.01e-18
0.00e+00
2.75e-15
0.00e+00
3.78e-14
0.00e+00
0.00e+00
5.01e-14
0.00e+00
0.00e+00
0.00e+00
2.71e-15
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6
err5
1.32e-10
1.61e-11
1.28e-12-4.62e-13
9.77e-11
4.81e-08-3.14e-09
4.95e-12-1.02e-02
1.08e-07-9.24e-03
1.59e-06-9.60e-08-1.68e-06-1.45e-06
9.75e-07
5.43e-06
1.70e-13
9.73e-07
2.87e-09
3.62e-08
2.55e-08
6.89e-05

err6
2.20e-10
1.72e-09
1.42e-09
3.83e-11
2.56e-10
4.94e-08
6.07e-08
2.73e-09
4.47e-02
1.20e-07
5.42e-02
2.68e-06
1.06e-06
4.67e-06
1.82e-05
9.93e-07
2.78e-05
2.63e-13
9.94e-07
2.25e-07
2.16e-07
8.87e-08
6.90e-05

time(s)1.61e+03
3.01e+03
3.19e+03
4.01e+03
3.72e+03
1.07e+00
1.63e-01
2.94e-01
2.04e-01
3.49e-01
5.19e-01
9.74e-01
3.86e-01
2.42e+00
1.80e+03
1.80e+03
1.52e+01
1.30e+01
1.99e+02
4.64e+02
8.12e+02
1.25e+03
9.19e+03

Complete
Time OverTime OverTime OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Numerical Error
Complete
Complete
Time OverTime Over
Complete
Complete
Complete
Complete
Numerical Error
Numerical Error
Time Over

Message
9.02e+02
1.85e+03
1.85e+03
2.73e+03
1.97e+03
7.93e-01
5.70e-02
2.36e-01
1.87e-01
2.13e-01
4.36e-01
8.05e-01
1.38e-01
2.00e+00
1.80e+03
1.80e+03
1.40e+01
1.24e+01
1.84e+02
4.41e+02
7.45e+02
1.16e+03
6.37e+03

time(s)Algorithm 5Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over

7.10e+02
1.16e+03
1.34e+03
1.27e+03
1.75e+03
2.78e-01
1.06e-01
5.78e-02
1.72e-02
1.36e-01
8.24e-02
1.69e-01
2.48e-01
4.18e-01
6.20e-01
1.15e+00
1.20e+00
6.85e-01
1.41e+01
2.25e+01
6.73e+01
9.50e+01
2.82e+03

time(s)Algorithm 4
Message

Table 28: Results of Algorithm 6 using the solutions from Mosek on ill-posed group instances

75

err1
5.24e-13
2.68e-13
2.19e-13
8.93e-13
2.32e-14
1.56e-14
4.33e-14
4.60e-14
1.60e-13
1.51e-13
1.51e-13
7.81e-14
1.97e-13
4.82e-13
1.31e-12
5.52e-14
6.73e-11
2.87e-14
1.19e-14
6.01e-15
4.77e-14
4.35e-14
5.32e-15
2.06e-15
3.46e-15
6.90e-16
1.17e-15
3.47e-14
3.25e-15
6.23e-15
7.40e-14
3.61e-10
5.20e-12
1.53e-12

Problem

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss8err2
8.24e-18
2.07e-18
1.12e-17
8.27e-17
7.09e-16
5.47e-17
7.12e-16
3.00e-15
4.60e-16
8.33e-16
2.61e-16
8.20e-16
1.56e-16
2.68e-16
8.22e-17
7.62e-15
0.00e+00
8.57e-16
1.45e-15
3.75e-15
1.01e-14
0.00e+00
0.00e+00
0.00e+00
4.90e-18
0.00e+00
0.00e+00
2.38e-15
0.00e+00
0.00e+00
4.42e-15
0.00e+00
0.00e+00
5.33e-15

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.60e-16
4.26e-16
6.04e-16
1.13e-15
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6err5
6.73e-13
3.77e-13
5.47e-14
1.08e-13
6.12e-15
5.94e-14
8.75e-13
2.21e-128.02e-13
8.26e-13
3.23e-12
4.57e-12
5.67e-128.15e-12
4.06e-12
8.09e-10
4.66e-12
4.51e-15
5.09e-15
1.59e-14
1.12e-14
8.68e-15
9.90e-15
3.85e-14
3.08e-14
3.14e-13
2.04e-14
1.31e-14
4.86e-14
1.74e-14
3.72e-13
2.91e-11
3.15e-12
1.29e-12err6
6.90e-13
3.76e-13
5.20e-14
1.22e-13
6.99e-15
5.43e-14
8.66e-13
2.24e-128.42e-13
7.94e-13
3.25e-12
4.54e-12
5.83e-128.13e-12
4.72e-129.75e-10
4.12e-10
7.19e-15
4.87e-15
1.61e-14
1.21e-14
1.16e-14
2.80e-14
3.61e-14
2.59e-14
3.18e-13
2.10e-14
1.54e-14
4.81e-14
1.67e-14
3.72e-13
1.12e-10
3.17e-12
1.29e-12time(s)8.34e+02
7.17e+02
3.43e+02
6.47e+02
5.30e-02
1.06e+00
5.55e+00
1.45e+01
6.30e+01
2.05e+02
6.83e+02
1.04e+03
1.74e+03
2.84e+03
2.99e+03
2.07e-01
6.40e-02
3.65e+02
1.71e+03
1.25e+03
1.26e+03
2.08e+03
1.48e+01
1.84e+02
8.93e+02
3.70e+03
7.30e-02
2.91e+00
2.65e-01
4.45e-02
6.51e+01
1.33e+03
1.21e+02
1.15e+02

Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete

Message
1.98e+02
4.07e+02
2.73e+02
3.70e+02
4.34e-02
9.65e-01
4.93e+00
1.10e+01
5.89e+01
1.90e+02
6.27e+02
8.94e+02
1.59e+03
2.18e+03
2.01e+03
1.93e-01
4.40e-02
3.23e+02
9.57e+02
8.64e+02
9.56e+02
1.81e+03
1.22e+01
9.99e+01
7.66e+02
1.82e+03
4.90e-02
1.62e+00
2.49e-01
4.07e-02
6.09e+01
7.96e+02
9.68e-01
9.86e+00

time(s)Algorithm 5Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete

Message
6.35e+02
3.09e+02
7.01e+01
2.77e+02
9.65e-03
9.38e-02
6.16e-01
3.54e+00
4.06e+00
1.48e+01
5.63e+01
1.43e+02
1.44e+02
6.67e+02
9.81e+02
1.39e-02
2.00e-02
4.21e+01
7.55e+02
3.90e+02
3.02e+02
2.71e+02
2.58e+00
8.37e+01
1.27e+02
1.88e+03
2.40e-02
1.28e+00
1.61e-02
3.80e-03
4.28e+00
5.34e+02
1.20e+02
1.05e+02

time(s)Algorithm 4

Table 29: Results of Algorithm 6 using the solutions from SDPA on well-posed group instances

76

err1

1.91e-13
2.34e-13
1.08e-13
1.20e-13
3.41e-13
6.07e-15
1.07e-11
2.28e-14
1.31e-12
4.34e-12
2.90e-11
4.55e-12
1.73e-14
1.04e-14
1.46e-16
5.77e-11
1.00e-129.42e-10
3.33e-15
2.19e-13
3.21e-15
1.70e-13
1.80e-12
1.03e-11

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

err2
0.00e+00
3.58e-16
8.52e-17
6.70e-17
3.26e-16
8.27e-17
3.46e-14
0.00e+00
0.00e+00
0.00e+00
1.19e-12
4.27e-14
0.00e+00
4.43e-160.00e+00
3.04e-13
3.28e-16
1.51e-13
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6
err5-2.91e-13-1.48e-11
3.63e-10-1.85e-07-5.18e-12
3.82e-08
2.17e-08
1.16e-11-2.03e-03-2.51e-10-1.18e-03-9.06e-05-6.79e-10
1.41e-06
3.57e-03
7.18e-04
1.97e-05
2.38e-04
5.05e-09
2.11e-09
3.72e-08
1.06e-07
3.06e-08
9.02e-08

err6
3.54e-10-6.68e-11
2.56e-10
1.14e-06
2.89e-11
6.90e-08
4.64e-08
3.81e-09
7.85e-02
2.78e-08
8.33e-03
2.15e-03
3.85e-07
2.25e-06
7.92e-03
7.54e-04
2.69e-05
2.62e-04
1.55e-08
7.39e-08
5.39e-08
3.14e-07
5.47e-08
2.72e-07time(s)2.40e+03
3.00e+03
3.35e+03
2.14e+03
3.03e+03
3.45e-01
5.48e-01
2.06e-01
2.43e-01
9.07e-01
2.08e-01
1.86e+00
1.84e+00
1.80e+03
1.44e+00
1.80e+03
1.80e+03
1.62e+01
2.42e+00
3.50e+01
1.87e+02
6.98e+02
1.90e+03
3.32e+03

Time OverTime OverTime Over
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Numerical Error
Numerical Error
Complete
Time Over
Complete
Time OverTime Over
Complete
Numerical Error
Numerical Error
Complete
Numerical Error
Numerical Error
Time Over

Message
1.92e+03
1.83e+03
1.90e+03
1.49e+03
1.82e+03
2.44e-01
4.86e-01
1.96e-01
1.94e-01
8.14e-01
1.47e-01
6.45e-01
1.81e+00
1.80e+03
1.11e+00
1.80e+03
1.80e+03
1.05e+01
8.92e-01
3.05e+01
1.79e+02
6.40e+02
1.77e+03
2.13e+03

time(s)Algorithm 5Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete

4.77e+02
1.16e+03
1.44e+03
6.56e+02
1.21e+03
1.01e-01
6.15e-02
1.05e-02
4.90e-02
9.28e-02
6.07e-02
1.22e+00
3.11e-02
4.66e-01
3.31e-01
1.73e+00
1.28e+00
5.72e+00
1.53e+00
4.56e+00
8.26e+00
5.80e+01
1.35e+02
1.19e+03

time(s)Algorithm 4
Message

Table 30: Results of Algorithm 6 using the solutions from SDPA on ill-posed group instances

77

err1
3.25e-13
4.11e-13
2.90e-13
7.71e-13
3.87e-15
2.16e-14
1.48e-14
3.26e-14
5.20e-14
1.61e-13
1.06e-13
1.53e-13
9.76e-14
2.07e-13
7.62e-14
4.11e-14
4.64e-11
4.86e-14
1.63e-14
1.15e-14
8.63e-15
7.20e-14
1.15e-16
3.51e-16
8.07e-16
4.72e-15
1.31e-15
2.84e-13
3.53e-15
4.63e-16
9.54e-14
2.22e-12
9.39e-13
1.61e-12

Problem

arch0
arch2
arch4
arch8
control1
control2
control3
control4
control5
control6
control7
control8
control9
control10
control11
hinf2
hinf9
mcp100mcp124-1
mcp124-2
mcp124-3
mcp124-4
theta1
theta2
theta3
theta4
truss1truss2truss3truss4
truss5truss6
truss7
truss8err2
1.51e-17
6.14e-17
2.09e-17
2.73e-16
1.11e-15
0.00e+00
4.10e-16
9.65e-16
2.25e-15
4.84e-15
2.06e-16
1.72e-16
2.28e-16
5.66e-16
1.43e-15
6.92e-15
1.31e-127.31e-16
7.32e-16
1.54e-15
5.45e-15
0.00e+00
0.00e+00
0.00e+00
1.84e-160.00e+00
0.00e+00
2.37e-15
0.00e+00
0.00e+00
3.55e-15
0.00e+00
0.00e+00
5.79e-16

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.67e-16
3.23e-16
7.21e-16
9.72e-160.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6
err5
1.33e-13
8.27e-13
4.78e-13
1.15e-13
1.25e-12
7.85e-14
4.78e-13
7.50e-13
1.10e-13
1.48e-12
1.54e-12
2.84e-12
5.84e-12
9.81e-13
9.78e-122.25e-11
1.85e-10
4.01e-15
2.39e-15
3.15e-15
2.49e-15
1.39e-14
2.46e-12
1.74e-13
2.90e-14
2.60e-13
3.32e-14
1.62e-13
4.97e-14
2.69e-14
5.16e-13
3.59e-11-7.10e-14
4.72e-12err6
1.29e-13
8.18e-13
4.93e-13
1.15e-13
1.25e-12
7.65e-14
4.79e-13
7.41e-13
9.65e-14
1.36e-12
1.54e-122.73e-12
5.88e-12
9.86e-13
9.75e-128.12e-11
2.10e-10
9.16e-15
3.35e-15
3.46e-15
2.51e-15
1.56e-14
2.46e-12
1.76e-13
2.68e-14
2.76e-13
3.33e-14
1.64e-13
5.04e-14
2.70e-14
5.16e-13
3.59e-11
1.38e-12
4.73e-12time(s)3.29e+02
1.83e+03
2.56e+02
4.70e+02
1.80e-01
1.88e+00
5.40e+00
1.43e+01
7.30e+01
1.88e+02
5.19e+02
7.77e+02
1.83e+03
2.73e+03
3.12e+03
4.06e-01
6.79e-02
5.75e+02
1.99e+03
2.29e+03
1.93e+03
1.58e+03
5.28e+01
1.79e+02
1.18e+03
5.37e+03
3.44e-02
2.07e+00
2.58e-01
3.97e-02
6.67e+01
6.09e+03
6.07e+02
3.42e+02

Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete

Message
2.75e+02
1.68e+03
2.05e+02
2.73e+02
1.25e-01
1.55e+00
4.89e+00
1.18e+01
6.02e+01
1.72e+02
4.36e+02
6.36e+02
1.58e+03
2.00e+03
1.90e+03
3.96e-01
5.07e-02
4.90e+02
1.02e+03
1.41e+03
1.01e+03
1.37e+03
2.44e+01
9.97e+01
1.01e+03
3.11e+03
3.10e-02
1.07e+00
2.43e-01
3.58e-02
6.31e+01
5.99e+03
6.03e+02
2.51e+02

time(s)Algorithm 5Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete

Message
5.42e+01
1.57e+02
5.12e+01
1.97e+02
5.42e-02
3.32e-01
5.08e-01
2.51e+00
1.28e+01
1.64e+01
8.32e+01
1.41e+02
2.50e+02
7.26e+02
1.22e+03
1.03e-02
1.72e-02
8.43e+01
9.72e+02
8.78e+02
9.11e+02
2.11e+02
2.84e+01
7.98e+01
1.69e+02
2.26e+03
3.41e-03
1.00e+00
1.51e-02
3.95e-03
3.59e+00
1.01e+02
3.42e+00
9.13e+01

time(s)Algorithm 4

Table 31: Results of Algorithm 6 using the solutions from SDPT3 on well-posed group instances

78

err1

2.68e-13
8.66e-14
4.06e-13
2.26e-13
2.97e-13
1.13e-13
1.40e-11
1.96e-14
1.23e-11
1.39e-11
8.99e-11
1.21e-11
2.53e-14
2.39e-14
2.56e-16
2.69e-12
8.81e-14
5.68e-12
2.11e-15
7.69e-10
5.16e-15
9.14e-13
2.25e-12
5.13e-07

Problem

gpp100gpp124-1
gpp124-2
gpp124-3
gpp124-4
hinf1
hinf3
hinf4
hinf5
hinf6
hinf7
hinf8
hinf10
hinf11
hinf12
hinf13
hinf14
hinf15
qap5
qap6
qap7
qap8
qap9
qap10

err2
1.82e-15
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
3.51e-15
0.00e+00
0.00e+00
0.00e+00
0.00e+00
1.42e-15
0.00e+00
3.21e-160.00e+00
4.25e-14
2.14e-16
1.39e-14
0.00e+00
0.00e+00
0.00e+00
1.96e-19
0.00e+00
0.00e+00

err3
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00
0.00e+00

err4

Algorithm 6
err5
9.24e-11
1.23e-08
8.98e-10-4.64e-12
5.27e-08
2.71e-08
2.35e-10-1.53e-11-6.57e-04
3.71e-09
4.93e-09
5.51e-08
2.25e-08
4.75e-08-6.74e-06
5.12e-05
9.51e-07
2.15e-04-8.43e-14-3.84e-09
6.32e-08
3.10e-07
8.86e-08-2.34e-05

err6-9.73e-11
1.42e-08
1.13e-09
1.50e-09
5.72e-08
7.39e-08
3.66e-08
2.79e-09
8.88e-03
1.08e-07
4.26e-08
7.05e-08
2.69e-07
5.44e-07
2.04e-04
5.14e-05
9.72e-07
2.15e-04
3.46e-11
1.08e-05
8.59e-08
5.66e-07
6.60e-07
3.19e-05

time(s)2.37e+03
3.72e+03
3.81e+03
4.03e+03
4.42e+03
1.10e+00
5.47e-01
2.78e-01
2.10e-01
6.81e-01
2.36e-01
9.21e-01
1.49e+00
4.51e+00
3.17e+00
1.80e+03
7.34e+00
1.80e+03
5.68e+00
1.11e+02
5.28e+02
1.96e+03
2.75e+03
4.63e+03

Time OverTime OverTime OverTime OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over
Complete
Time Over
Numerical Error
Numerical Error
Numerical Error
Time OverTime OverTime Over

Message
1.92e+03
1.82e+03
1.83e+03
2.22e+03
2.28e+03
5.25e-01
4.09e-01
2.67e-01
1.94e-01
5.54e-01
1.63e-01
7.37e-01
1.40e+00
4.37e+00
3.17e+00
1.80e+03
6.59e+00
1.80e+03
4.61e+00
8.32e+01
5.14e+02
1.82e+03
1.95e+03
1.84e+03

time(s)Algorithm 5Complete
Time OverTime OverTime OverTime Over
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Complete
Time Over

4.58e+02
1.89e+03
1.98e+03
1.82e+03
2.14e+03
5.77e-01
1.38e-01
1.19e-02
1.63e-02
1.27e-01
7.35e-02
1.85e-01
9.64e-02
1.40e-01
3.67e-03
4.48e-01
7.46e-01
1.35e+00
1.07e+00
2.78e+01
1.39e+01
1.36e+02
8.00e+02
2.79e+03

time(s)Algorithm 4
Message

Table 32: Results of Algorithm 6 using the solutions from SDPT3 on ill-posed group instances