{'fraction_non_alphanumeric': 0.057925934620576325, 'fraction_numerical': 0.01346910029931334, 'mean_word_length': 3.9268468989446292, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimality Conditions for Nonlinear Semidefinite Programming via Squared Slack Variables

In this work, we derive second-order optimality conditions for nonlinear semidefinite programming (NSDP) problems, by reformulating it as an ordinary nonlinear programming problem using squared slack variables. We first consider the correspondence between Karush-Kuhn-Tucker points and regularity conditions for the general NSDP and its reformulation via slack variables. Then, we obtain a pair of"no-gap"second-order optimality conditions that are essentially equivalent to the ones already considered in the literature. We conclude with the analysis of some computational prospects of the squared slack variables approach for NSDP.


Introduction
We consider the following nonlinear semidefinite programming (NSDP) problem: where f : R n → R and G : R n → S m are twice continuously differentiable functions, S m is the linear space of all real symmetric matrices of dimension m × m, and S m + is the cone of all positive semidefinite matrices in S m . Second-order optimality conditions for such problems were originally derived by Shapiro in [20]. It might be fair to say that the second-order analysis of NSDP problems is more intricated than its counterpart for classical nonlinear programming problems. That is one of the reasons why it is interesting to have alternative ways for obtaining optimality conditions for (P1); see the works by Forsgren [9] and Jarre [12]. In this work, we propose to use the squared slack variables approach for deriving these optimality conditions.
It is well-known that the squared slack variables can be used to transform a nonlinear programming (NLP) problem with inequality constraints into a problem with only equality constraints. For NLP problems, this technique was hardly considered in the literature because it increases the dimension of the problem and may lead to numerical instabilities [18]. However, recently, Fukuda and Fukushima [10] showed that the situation may change in the nonlinear second-order cone programming context. Here, we observe that the slack variables approach can be used also for NSDP problems, because, like the nonnegative orthant and the second-order cone, the cone of positive semidefinite matrices is also a cone of squares. More precisely, S m + can be represented as where • is the Jordan product associated with the space S m , which is defined as for any W, Z ∈ S m . Note that actually Z • Z = ZZ = Z 2 for any Z ∈ S m . The fact above allows us to develop the squared slack variables approach. In fact, by introducing a slack variable Y ∈ S m in (P1), we obtain the following problem: which is an NLP problem with only equality constraints. Note that if (x, Y ) ∈ R n × S m is a global (local) minimizer of (P2), then x is a global (local) minimizer of (P1). Moreover, if x ∈ R n is a global (local) minimizer of (P1), then there exists Y ∈ S m such that (x, Y ) is a global (local) minimizer of (P2). However, the relation between stationary points, or Karush-Kuhn-Tucker (KKT) points, of (P1) and (P2) is not so trivial. As in [10], we will take a closer look at this issue, and investigate also the relation between constraint qualifications for (P1) and (P2), using second-order conditions. We remark that second-order conditions for these two problems are vastly different. While (P2) is a run-of-the-mill nonlinear programming problem, (P1) has nonlinear conic constraints, which are more difficult to deal with. Moreover, it is known that second-order conditions for NSDPs include an extra term, which takes into account the curvature of the cone. For more details, we refer to the papers of Kawasaki [13], Cominetti [7] and Shapiro [20]. The main objective of this work is to show that, under appropriate regularity conditions, second-order conditions for (P1) and (P2) are essentially the same. This suggests that the addition of the slack term already encapsulates most of the nonlinear structure of the cone. In the analysis, we also propose and use a sharp characterization of positive semidefiniteness that takes into account the rank information. We believe that such a characterization can be useful in other contexts as well.
Finally, we present results of some numerical experiments where NSDPs are reformulated as NLPs using slack variables. Note that we are not necessarily advocating the use of slack variables and we are, in fact, driven by curiosity about its computational prospects. Nevertheless, there are a couple of reasons why this could be interesting. First of all, conventional wisdom would say that using squared slack variables is not a good idea, but, in reality, even for linear SDPs there are good reasons to use such variables. In [5,6], Burer and Monteiro transform a linear SDP inf{tr(CX) | AX = b, X ∈ S m + } into inf{tr(CV V ) | AV V = b}, where V is a square matrix and tr denotes the trace map. The idea is to use a theorem, proven independently by Barvinok [1] and Pataki [16], which bounds the rank of possible optimal solutions. By doing so, it is possible to restrict V to be a rectangular matrix instead of a square one, thereby reducing the number of variables. Another reason to use squared slack variables is that the reformulated NLP problem can be solved by efficient NLP solvers that are widely available. In fact, while there are a number of solvers for linear SDPs, as we move to the general nonlinear case, the situation changes drastically [22].
Throughout the paper, the following notations will be used. For x ∈ R s and Y ∈ R ×s , x i ∈ R and Y ij ∈ R denote the ith entry of x and the (i, j) entry (ith row and jth column) of Y , respectively. The identity matrix of dimension is denoted by I . The transpose, the Moore-Penrose pseudo-inverse, and the rank of Y ∈ R ×s are denoted by Y ∈ R s× , Y † ∈ R s× , and rank Y , respectively. If Y is a square matrix, its trace is denoted by tr(Y ) := i Y ii . For square matrices W and Y of the same dimension, their inner product 1 is denoted by W, Y := tr(W Y ). We will use the notation Z 0 for Z ∈ S m + . In that case, we will denote by √ Z the positive semidefinite square root of Z, that is, For any function P : R s+ → R, the gradient and the Hessian at (x, y) ∈ R s+ with respect to x are denoted by ∇ x P(x, y) and ∇ 2 x P(x, y), respectively. Moreover, for any linear operator G : . . , s, and v ∈ R s , the adjoint operator G * : S → R s is defined by Given a mapping H : R s → S , its derivative at a point x ∈ R s is denoted by ∇H(x) : R s → S and defined by where ∂H(x)/∂x i ∈ S are the partial derivative matrices. Finally, for a closed convex cone K, we will denote by lin K the largest subspace contained in K. Note that lin K = K ∩ −K. The paper is organized as follows. In Section 2, we recall a few basic definitions concerning KKT points and second-order conditions for (P1) and (P2). We also give a sharp characterization of positive semidefiniteness. In Section 3, we prove that the original and the reformulated problems are equivalent in terms of KKT points, under some conditions. In Section 4, we establish the relation between constraint qualifications of those two problems. The analyses of second-order sufficient conditions and second-order necessary conditions are presented in Sections 5 and 6, respectively. In Section 7, we show some computational results. We conclude in Section 8, with final remarks and future works.

A sharp characterization of positive semidefiniteness
It is a well-known fact that a matrix Λ ∈ S m is positive semidefinite if and only if Λ, W 2 ≥ 0 for all W ∈ S m . This statement is equivalent to the self-duality of the cone S m + . However, we get no information about the rank of Λ. In the next lemma, we give a new characterization of positive semidefinite matrices, which takes into account the rank information.
Lemma 2.1. Let Λ ∈ S m . The following statements are equivalent: For any Y satisfying the conditions in (ii), we have rank Λ = m − rank Y . Moreover, if σ and σ are nonzero eigenvalues of Y , then σ + σ = 0.
Proof. Let us prove first that (ii) implies (i). Since the inner product is invariant under orthogonal transformations, we may assume without loss of generality that Y is diagonal, i.e., where D is a k × k nonsingular diagonal matrix, and rank Y = k. We partition Λ in blocks in a similar way: where A ∈ S k , B ∈ R k×(m−k) , and C ∈ S m−k . We will proceed by proving that A = 0, B = 0 and C is positive definite. First, observe that, by assumption, holds. Since D is nonsingular, this implies B = 0. Now, let us prove that A = 0. From (2.2) and the fact that D is diagonal, we obtain Again, because D is nonsingular, it must be the case that all diagonal elements of A should be zero. Now, suppose that A ij is nonzero for some i and j, with i = j. In face of (2.3), this can only happen if D ii + D jj = 0. Let us now consider the following matrix: where W ∈ S k is a submatrix containing only two nonzero elements, W ij = 1 and W ji = 1. Then, easy calculations show that W • D = 0, which also implies W • Y = 0. Moreover, W • W, Λ = 0 because W 2 = W • W is the diagonal matrix having 1 in the (i, i) entry and 1 in the (j, j) entry, and since A ii and A jj are zero. We conclude that Y / ∈ Φ(Λ), contradicting the assumptions. So, it follows that A must be zero. Similarly, we have that D ii + D jj is never zero, which corresponds to the statement about eigenvalues σ and σ in the lemma. In fact, if D ii + D jj is zero, then, by taking W exactly as before, we have W • Y = 0 and W • W, Λ = 0. Once again, this shows that Y / ∈ Φ(Λ), which is a contradiction. It remains to show that C is positive definite. Taking an arbitrary nonzeroH ∈ S m−k , and defining we easily obtain H • Y = 0. Since Y ∈ Φ(Λ), we have H 2 , Λ > 0. But this shows that H 2 , C > 0, which implies that C is positive definite. In particular, the rank of Λ is equal to the rank of C, which is m − rank Y . Now, let us prove that (i) implies (ii). Similarly, we may assume Λ = 0 0 0 C , with C positive definite. Then, we can take Y = E 0 0 0 , where E is any positive definite matrix. It follows that any matrix W ∈ S m satisfying Y • W = 0 must have the shape 0 0 0 F , for some matrix F . Since C is positive definite, it is clear that W • W , Λ > 0, whenever W is nonzero.
The statement about the sum of nonzero eigenvalues might seem innocuous at first, but it will be very useful in Section 5. In fact, the idea for this new characterization of positive semidefiniteness comes from the second-order conditions of (P2). For now, let us present another result that will be necessary. Given A ∈ S m , denote by L A : S m → S m the linear operator defined by for all E ∈ S m . There are many examples of invertible matrices A for which the operator L A is not invertible 2 . This is essentially due to the failure of the condition on the eigenvalues. The following proposition is well-known in the context of Euclidean Jordan algebra (see [21,Proposition 1]), but we include here a short-proof for completeness. Proof. The statements in the proposition are all invariant under orthogonal transformations. Thus, we may assume without loss of generality that A is already diagonalized, and so A kk is an eigenvalue of A for every k = 1, . . . , m.
Let us show that the invertibility of L A implies the statement about the eigenvalues of A. We will do so by proving the contrapositive. Take i and j such that A ii + A jj = 0. Let W be such that all the entries are zero except for W ij = W ji = 1. Then, we have A • W = 0. This shows that the kernel of L A is non-trivial and consequently, L A is not invertible.
Reciprocally, since we assume that A is diagonal, for every W ∈ S m , we have 2(L A (W )) ij = W ij (A ii + A jj ) for all i and j. Due to the fact that A ii + A jj is never zero, the kernel of L A must only contain the zero matrix. Hence L A is invertible, and the result follows.
In view of Proposition 2.2, the matrix D which appears in the proof of Lemma 2.1 is such that L D is invertible. This will play an important role when we discuss the relation between the second-order sufficient conditions of problems (P1) and (P2).

KKT conditions and constraint qualifications
Now, let us consider the following lemma, which will allow us to present appropriately the KKT conditions of problems (P1) and (P2). Lemma 2.3. The following statements hold.
(c) For any matrix A ∈ R m×m and function θ : where the last equality follows from the definition of adjoint operator. We can now recall the KKT conditions of problems (P1) and (P2). First, define the Lagrangian function L : R n × S m → R associated with problem (P1) as We say that (x, Λ) ∈ R n × S m is a KKT pair of problem (P1) if the following conditions are satisfied: . Applying the trace map on both sides of (P1.4), we see that condition (P1.4) is equivalent to Λ, G(x) = 0. This result, together with the fact that Λ 0 and G(x) 0, shows that (P1.4) is also equivalent to ΛG(x) = 0, by Lemma 2.3(e). Moreover, the equality (P1.4) implies that Λ and G(x) commute, which means, by Lemma 2.3(d), that they are simultaneously diagonalizable by an orthogonal matrix. The following definition is also well-known.
then (x, Λ) is said to satisfy the strict complementarity condition.
As for the equality constrained NLP problem (P2), we observe that (x, Y, Λ) ∈ R n × S m × S m is a KKT triple if the conditions below are satisfied: where L : R n × S m × S m → R is the Lagrangian function associated with (P2), which is given by From Lemma 2.3(b),(c), these conditions can be written as follows: For problem (P1), we say that the Mangasarian-Fromovitz constraint qualification (MFCQ) holds at a point x if there exists some d ∈ R n such that where int S m + denotes the interior of S m + , that is, the set of symmetric positive definite matrices. If x is a local minimum for (P1), MFCQ ensures the existence of a Lagrange multiplier Λ and that the set of multipliers is bounded. A more restrictive assumption is the nondegeneracy condition discussed in [20], where it is presented in terms of a transversality condition on the map G. However, at the end, it boils down to the following condition.
) (see, for instance, the observations on page 310 in [20]). Then, (x, Λ) is said to satisfy the nondegeneracy condition.
A good thing about the nondegeneracy condition is that it ensures that Λ is unique. For problem (P2), a common constraint qualification is the linear independence constraint qualification (LICQ), which simply requires that the gradients of the constraints be linearly independent. In Section 4, we will show that LICQ and the nondegeneracy are essentially equivalent.

Second-order conditions
Since (P2) is just an ordinary equality constrained nonlinear program, second-order sufficient conditions are well-known and can be written as follows.
3 We refer to this condition as SOSC-NLP in order to distinguish it from SOSC for SDP.
Proof. The second-order sufficient condition for (P2) holds if we have the desired result.
Similarly, we have the following second-order necessary condition. Note that we require the LICQ to hold.
Second-order conditions for (P1) are a more delicate matter. Let (x, Λ) be a KKT pair of (P1). It is true that a sufficient condition for optimality is that the Hessian of the Lagrangian be positive definite over the set of critical directions. However, replacing "positive definite" by "positive semidefinite" does not yield a necessary condition. Therefore, it seems that there is a gap between necessary and sufficient conditions. In order to close the gap, it is essential to add an additional term to the Hessian of the Lagrangian. For the theory behind this see, for instance, the papers by Kawasaki [13], Cominetti [7], and Bonnans, Cominetti and Shapiro [4]. The condition below was obtained by Shapiro in [20] and it is sufficient for (x, Λ) to be a local minimum, see Theorem 9 therein.
Proposition 2.8. Let (x, Λ) ∈ R n ×S m be a KKT pair of problem (P1) satisfying strict complementarity and the nondegeneracy condition. The second-order sufficient condition (SOSC-SDP) holds if is the critical cone at x, and H(x, Λ) ∈ S m is a matrix with elements for i, j = 1, . . . , n. In this case, (x, Λ) is a local minimum for (P1). Conversely, if x is a local minimum for (P1) and (x, Λ) is a KKT pair satisfying strict complementarity and nondegeneracy, then the following second-order necessary condition (SONC-SDP) holds: for all d ∈ C(x).

Equivalence between KKT points
Let us now establish the relation between KKT points of the original problem (P1) and its reformulation (P2). We start with the following simple implication.
The converse is not always true. That is, even if (x, Y, Λ) is a KKT triple of (P2), (x, Λ) may fail to be a KKT pair of (P1), since Λ need not be positive semidefinite. This, however, is the only obstacle for establishing equivalence.
Proof. The only condition that remains to be verified is (P1.4). Due to (P2.2), we have Since G(x) and Λ are both positive semidefinite, we must have G(x) • Λ = 0.
The previous proposition leads us to consider conditions which ensure that Λ is positive semidefinite. It turns out that if the second-order sufficient condition for (P2) is satisfied at (x, Y, Λ), then Λ is positive semidefinite. In fact, a weaker condition is enough to ensure positive semidefiniteness.
for every nonzero W ∈ S m such that Y • W = 0. Then (x, Λ) is a KKT pair of (P1) satisfying strict complementarity.
Proof. Due to Lemma 2.1, Λ is positive semidefinite and rank Y = m−rank Λ. Now, since G(x) = Y 2 , we have rank G(x) = rank Y . Therefore (x, Λ) must satisfy the strict complementarity condition.
Then (x, Λ) is a KKT pair for (P1) which satisfies the strict complementarity condition.
Proof. If we take v = 0 in the definition of SOSC-NLP, we obtain Y ∈ Φ(Λ). So, the result follows from Proposition 3.3.
The next result is a refinement of Proposition 3.1.
Proposition 3.5. Suppose that (x, Λ) ∈ R n × S m is a KKT pair of (P1) which satisfies the strict complementarity condition. Then there exists some Y ∈ Φ(Λ) such that (x, Y, Λ) is a KKT triple of (P2).
Proof. Without loss of generality, we may assume that G(x) has the shape A 0 0 0 , where A ∈ S k + and k = rank G(x). Since G(x) and Λ are both positive semidefinite, the condition G(x) • Λ = 0 is equivalent to G(x)Λ = 0. It follows that Λ has the shape 0 0 0 C for some matrix C ∈ S m−k + . However, strict complementarity holds only if C is positive definite. Therefore, it is enough to pick Y to be the positive semidefinite matrix satisfying Y 2 = G(x).

Relations between constraint qualifications
In this section, we shall show that the nondegeneracy in Definition 2.5 is essentially equivalent to LICQ for (P2). In [20], Shapiro mentions that the nondegeneracy condition for (P1) is an analogue of LICQ, but he also states that the analogy is imperfect. For instance, when G(x) is diagonal, (P1) naturally becomes an NLP, since the semidefiniteness constraint is reduced to the nonnegativity of the diagonal elements. However, even in that case, LICQ and the nondegeneracy in Definition 2.5 might not be equivalent (see page 309 of [20]). In this sense, it is interesting to see whether a correspondence between the conditions can be established when (P1) is reformulated as (P2). Before that, we recall some facts about the geometry of the cone of positive semidefinite matrices.
Let A ∈ S m + and let U be an m × k matrix whose columns form a basis for the kernel of A. Then, the tangent cone of S m + at A is written as (see [17] or [20,Equation 26]). For example, if A can be written as D 0 0 0 , where D is positive definite, then the matrices in T S m + (A) have the shape C F F H , where the only restriction is that H should be positive semidefinite.
Our first step is to notice that nondegeneracy implies that the only matrix which is orthogonal to both lin T S m + (G(x)) and Im ∇G(x) is the trivial one, i.e., W ∈ (lin T S m + (G(x))) ⊥ and ∇G(x) * W = 0 ⇒ W = 0, where ⊥ denotes the orthogonal complement. On the other hand, the LICQ constraint qualification for (P2) holds at a feasible point (x, Y ) if the linear function which maps (v, W ) to ∇G(x)v − 2W • Y is surjective. This happens if and only if the adjoint map has trivial kernel. The adjoint map takes W ∈ S m and maps it to (∇G(x) * W, −2W • Y ). So the surjectivity assumption amounts to requiring that every W which satisfies both ∇G(x) * W = 0 and W • Y = 0 must actually be 0, that is, The subspaces ker L Y = {W | Y • W = 0} and (lin T S m + (G(x))) ⊥ are closely related. The next proposition clarifies this connection.
Proof. Note that if Q is an orthogonal matrix, then T S m + (Q V Q) = Q T S m + (V )Q. The same is true for ker L Y , i.e., ker L Q Y Q = Q ker L Y Q. So, without loss of generality, we may assume that Y is diagonal and that where D is an r × r nonsingular diagonal matrix. Then, we have This shows that every matrix Z ∈ (lin T S m + (V )) ⊥ satisfies Y Z = 0 and therefore lies in ker L Y . Now, the kernel of L Y can be described as follows: If Y is positive semidefinite, then D is positive definite and the operator L D is nonsingular. Hence Proof. It follows easily from Proposition 4.1.
Proof. In Corollary 3.4, we have already shown that (x, Λ) is a KKT pair of (P1) and strict complementarity is satisfied. In addition, if (x, Y, Λ) satisfies LICQ for (P2), then Corollary 4.2 ensures that (x, Λ) satisfies nondegeneracy for (P1). It only remains to show that (2.6) is also satisfied. To this end, consider an arbitrary nonzero d ∈ R n such that ∇G(x)d ∈ T S m + (G(x)) and ∇f (x), d = 0. We are thus required to show that The strategy here is to first identify the shape and properties of several matrices involved, before showing that (5.1) holds. Without loss of generality, we may assume that G(x) is diagonal, i.e., We partition ∇G(x)d in blocks in the following fashion: where A ∈ S k , B ∈ R k×(m−k) and C ∈ S m−k . Inasmuch as ∇G(x)d lies in the tangent cone T S m + (G(x)), C must be positive semidefinite. However, as observed earlier, we have ∇G(x)d, Λ = 0, which yields C, Γ = 0. Since Γ is positive definite, this implies C = 0, and hence We are now ready to show that (5.1) holds. We shall do that by considering v = d in (2.4) and exhibiting some W such that ∇G(x)d − 2Y • W = 0 and 2 W • W , Λ = H(x, Λ)d, d . Then SOSC-NLP will ensure that (5.1) holds. Note that, for any Z ∈ S m−k ,  Proposition 5.2. Suppose that (x, Λ) ∈ R n × S m is a KKT pair for (P1) satisfying (2.6) and the strict complementarity condition. Then, there exists Y ∈ S m such that (x, Y, Λ) is a KKT triple for (P2) satisfying SOSC-NLP.
Proof. Again, we assume without loss of generality that G(x) is diagonal, so that where E 2 = D and E is positive definite; in particular L E is invertible. Then (x, Y, Λ) is a KKT triple for (P2). Due to strict complementarity, we have where Γ ∈ S m−k + is positive definite. We are required to show that Recall that L E as well as E is invertible. So, Y • W = 0 implies W 1 = 0 and W 2 = 0. If W = 0, then W 3 must be nonzero, which in turn implies that W 3 • W 3 must also be nonzero. We then have W • W , Λ = W 3 • W 3 , Γ . But W 3 • W 3 , Γ must be greater than zero, since Γ is positive definite. Thus, in this case, (5.4) is satisfied. Now, we suppose that v is nonzero. First, we will show that ∇G(x)v lies in the tangent cone T S m + (G(x)) and that ∇G(x)v is orthogonal to Λ, which implies 0 = ∇G(x)v, Λ = v ∇G(x) * Λ = v ∇f (x). This shows that v lies in the critical cone C(x).
Note that the image of the operator L Y only contains matrices having the lower right (m − k) × (m − k) block equal to zero. Therefore, ∇G(x)v = 2Y • W implies that ∇G(x)v has the shape Hence, ∇G(x)v ∈ T S m + (G(x)) and ∇G(x)v is orthogonal to Λ. Due to SOSC-SDP, we must have Here, we remark one interesting consequence of the previous analysis. The second-order sufficient condition for NSDPs in [20] is stated under the assumption that the pair (x, Λ) satisfies both strict complementarity and nondegeneracy. However, since (P1) and (P2) share the same local minima, Proposition 5.2 implies that we may remove the nondegeneracy assumption from SOSC-SDP. We now state a sufficient condition for (P1) based on the analysis above.

Proposition 5.3 (A Sufficient Condition via Slack Variables).
Let (x, Λ) ∈ R n × S m be a KKT pair for (P1) satisfying strict complementarity. Assume also that the following condition holds: Then, x is a local minimum for (P1).
Apart from the detail of requiring nondegeneracy, the condition above is equivalent to SOSC-SDP, due to Propositions 5.1 and 5.2.

Analysis of second-order necessary conditions
We now take a look at the difference between second-order necessary conditions that can be derived from (P1) and (P2). Since the inequalities (2.5) and (2.8) are not strict, we need a slightly stronger assumption to prove the next proposition. Proposition 6.1. Suppose that (x, Y, Λ) ∈ R n × S m × S m is a KKT triple of (P2) satisfying LICQ and SONC-NLP. Moreover, assume that Y and Λ are positive semidefinite. If (x, Λ) is a KKT pair for (P1) satisfying strict complementarity, then it also satisfies SONC-SDP.
Proof. Since (x, Y, Λ) satisfies LICQ for (P2) and Y is positive semidefinite, Corollary 4.2 implies that (x, Λ) satisfies nondegeneracy. Under the assumption that (x, Λ) is strictly complementary, the only thing missing is to show that (2.8) holds. To do so, we proceed as in Proposition 5.1. We partition G(x), Y, Λ, G(x) † and ∇G(x)d in blocks in exactly the same way. The only difference is that, since (2.5) does not hold strictly, we cannot make use of Lemma 2.1 in order to conclude that L E is invertible. Nevertheless, since we assume that Y is positive semidefinite, all the eigenvalues of E are strictly positive anyway. So, as before, we can conclude that L E is an invertible operator, by Proposition 2.2. Due to strict complementarity, we can also conclude that Γ ∈ S m−k + is positive definite and that C = 0.
All our ingredients are now in place and we can proceed exactly as in the proof of Proposition 5.1. Namely, we have to prove that, given d ∈ C(x), the inequality (∇ 2 x L(x, Λ) + H(x, Λ))d, d ≥ 0 holds. As before, the way to go is to craft a matrix W satisfying both ∇G(x)d − 2Y • W = 0 and H(x, Λ)d, d = 2 W • W , Z . Then SONC-NLP will ensure that (2.8) holds. Actually, it can be done by taking and following the same line of arguments that leads to (5.3). Assume that (x, Λ) is a KKT pair of (P1) satisfying nondegeneracy and strict complementarity. Then, Proposition 6.1 gives an elementary route to prove that SONC-SDP holds. This is because if we select Y to be the positive semidefinite square root of G(x), all the conditions of Proposition 6.1 are satisfied, which means that (2.8) must hold. Moreover, if we were to derive second-order necessary conditions for (P1) from scratch, we could consider the following.

Proposition 6.3 (A Necessary Condition via Slack Variables)
. Let x ∈ R n be a local minimum of (P1). Assume that (x, Λ) ∈ R n × S m is a KKT pair for (P1) satisfying strict complementarity and nondegeneracy. Then the following condition holds: Propositions 6.1 and 6.2 ensure that the condition above is equivalent to SONC-SDP. Comparing Propositions 5.3 and 6.3, we see that the second-order conditions derived through the aid of slack variables have "no-gap" in the sense that, apart from regularity conditions, the only difference between them is the change from ">" to "≥".

Computational experiments
Let us now examine the validity of the squared slack variables method for NSDP problems. We tested the slack variables approach on a few simple problems. Our solver of choice was PENLAB [8], which is based on PENNON [14] and uses an algorithm based on the augmented Lagrangian technique. As far as we know, PENLAB is the only open-source general nonlinear programming solver capable of handling nonlinear SDP constraints. Because of that, we have the chance of comparing the "native" approach against the slack variables approach using the same code. We ran PENLAB with the default parameters. All the tests were done on a notebook with the following specs: Ubuntu 14.04, CPU Intel i7-4510U with 4 cores operating at 2.0Ghz and 4GB of RAM.
In order to use an NLP solver to tackle (P1), we have to select a vectorization strategy. We decided to vectorize an n × n symmetric matrix by transforming it into an n(n+1) 2 vector, such that the columns of the lower triangular part are stacked one on top of the other. For instance, the matrix

Modified Hock-Schittkowski problem 71
There is a known suite of problems for testing nonlinear optimization problems collected by Hock and Schittkowski [11,19]. The problem below is a modification of problem 71 of [19] and it comes together with PENLAB. Both the constraints and the objective function are nonconvex. The problem has the following formulation: 1 ≤ x i ≤ 5, i = 1, 2, 3, 4 x i ≥ 0, i = 5, 6. (HS) We reformulate the problem (HS) by removing the positive semidefiniteness constraints and adding a squared slack variable Y . We then test both formulations using PENLAB. The initial point is set to be x = (5, 5, 5, 5, 0, 0) and the slack variable to be the identity matrix Y = I 4 . This produces infeasible points for both formulations. Nevertheless, PENLAB was able to solve the problem via both approaches. The results can be seen in Table 1. The first three columns count the numbers of evaluations of the augmented Lagrangian function, its gradients and its Hessians, respectively. The fourth column is the number of outer iterations. The "time" column indicates the time in seconds as measured by PENLAB. The last column indicates the optimal value obtained. It seems that there were no significant differences in performance between both approaches.

The closest correlation matrix problem -simple version
Given an m × m symmetric matrix H with diagonal entries equal to one, we want to find the element in S m + which is closest to H and has all diagonal entries also equal to one. The problem can be formulated as follows: This problem is convex and, due to its structure, we can use slack variables without increasing the number of variables. We have the following formulation: (Cor-Slack) In our experiments, we generated 100 symmetric matrices H such that the diagonal elements are all 1 and other elements are uniform random numbers between −1 and 1. For both Cor and Cor-Slack, we used X = I m as an initial solution in all instances. We solved problems with m = 5, 10, 15, 20 and the results can be found in Table 2. The columns "mean", "min" and "max" indicate, respectively, the mean, minimum and maximum of the running times in seconds of all instances. For this problem, both formulations were able to solve all instances. We included the "mean time" column just to give an idea about the magnitude of the running time. In reality, for fixed m, the running time oscillated highly among different instances, as can be seen by the difference between the maximum and the minimum running times. We noted no significant difference between the optimal values obtained from both formulations.
We tried, as much as possible, to implement gradients and Hessians of both problems in a similar way. As Cor is an example that comes with PENLAB, we also performed some minor tweaks to conform to that goal. Performance-wise, the formulation Cor-Slack seems to be competitive for this example. In most instances, Cor-Slack had a faster running time. In Figure 1, we show the comparison between running times, instance-by-instance, for the case m = 20.  where κ is some positive number greater than 1 and the notation X κI m means X − κI m ∈ S m + . This is a nonconvex problem, and using slack variables, we obtain the following formulation: (Cor-Ext-Slack) In our experiments, we set κ = 10. As before, we generated 100 symmetric matrices H whose diagonal elements are all 1 and other elements are uniform random numbers between −1 and 1. For Cor-Ext, we used z = 1 and X = I m as initial points. For Cor-Ext-Slack, we used an infeasible starting point z = 1, X = Y 2 = I m and Y 1 = 3I m . We solved problems with m = 5, 10, 15, 20 and the results can be found in Table 3. The columns have the same meaning as in Section7.2. This time, we saw a higher failure rate for the formulation Cor-Ext-Slack. We tried a few different initial points, but the results stayed mostly the same. The best results were obtained for the case m = 5 and m = 10, where Cor-Ext-Slack had a performance comparable to Cor-Ext, although the latter seldom failed. For m = 15 and m = 20, Cor-Ext-Slack was slower than Cor-Ext, which is expected, because the number of variables increased significantly. However, it was still able to solve the majority of instances. In Figure 2, we show the comparison of running times, instance-by-instance, for the cases m = 10 and m = 20.

Final remarks
In this article, we have shown that the optimality conditions for (P1) and (P2) are essentially the same. One intriguing part of this connection is the fact that the addition of squared slack variables seems to be enough to capture a great deal of the structure of S m + . The natural progression from here is to expand the results to symmetric cones. In this article, we already saw some results that have a distinct Jordan-algebraic flavor, such as Lemma 2.1. It would be interesting to see how these results can be further extended and, whether clean proofs can be obtained without recoursing to the classification of simple Euclidean Jordan algebras.
As for the computational results, we found it mildly surprising that the slack variables approach was able to outperform the "native" approach in many instances. This warrants a deeper investigation of whether this could be a reliable tool for attacking NSDPs that are not linear. These are precisely the ones that are not covered by the earlier work by Burer and Monteiro [5,6].