{'fraction_non_alphanumeric': 0.05433224088488325, 'fraction_numerical': 0.014696845555100368, 'mean_word_length': 3.9328113159888862, 'pattern_counts': {'":': 1, '<': 4, '<?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': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A simple canonical form for nonlinear programming problems and its use

We argue that reducing nonlinear programming problems to a simple canonical form is an effective way to analyze them, specially when the problem is degenerate and the usual linear independence hypothesis does not hold. To illustrate this fact we solve an open problem about constraint qualifications using this simple canonical form.


Introduction
In this article we look at the classical nonlinear programming problem minimize f (x) subject to h(x) = 0 ∈ R m , g(x) ≤ 0 ∈ R r+p (1) in situations in which the derivatives Dh(0) and Dg(0) of the constraints are defective, in the sense that the rank of combined matrix is m + r ≤ m + r + p (by "derivative" Dh(x) here we mean the linear transformation represented by the Jacobian matrix of the function h.) To simplify the notation, we look at problem (1) for x in an open set A containing 0 ∈ R n and assume that all constraints are active at 0, that is h(0) = 0 and g(0) = 0. The analysis of problem (1) is usually based on a constraint qualification. For instance, the well known Mangasarian-Fromovitz constraint qualification assumes that Dh(0) has rank m and require the existence of a "strictly decreasing direction d" for the inequality constraints, which is also compatible with the equality constraints: Definition 1 (The Mangasarian-Fromovitz Constraint Qualification) For functions h and g such that h(0) = 0 and g(0) = 0, we say that 0 ∈ R n satisfies the Mangasarian-Fromovitz constraint qualification for problem (1) if rank(Dh(0)) = m and there exists d ∈ R n such that Dh(0) d = 0 and Dg(0) d < 0.
Unfortunately, even under conditions like Mangasarian-Fromovitz, the analysis of problem (1) can be tricky, and it is not uncommon to find articles in which incorrect results or proofs are presented, as pointed out in [2]. In fact, we are all human and our capability to deal with the details involved in the analysis of problem (1) is limited, and we need tools to handle them. In the present article we argue that by reducing problem (1) to a simple canonical form we have a better chance of understanding degenerated cases, and we illustrate this point by proving the following conjecture by Andreani, Martinez and Schuverdt [1] regarding second order constraint qualifications.
Theorem 1 (Andreani's Conjecture) Suppose the functions f , h and g in problem (1) are of class C 2 in a neighborhood A of 0 ∈ R n and h(0) = 0 and g(0) = 0. If the Mangasarian-Fromovitz constraint qualification is satisfied and rank(Dhg(x)) ≤ rank(Dhg(0)) + 1 for x ∈ A then there exist λ ∈ R m and µ ∈ R p , with µ ≥ 0, such that The reduction of complicated problems to simpler ones is a standard procedure in mathematics. Frequently, the Inverse Function Theorem and its variations, like the Implicit Function Theorem, are used to obtain changes of variables which reduce a nonlinear problem to a linear one. The results can be striking, as in Malgrange's Preparation Theorem, and Mather's Division Theorem [4], which generalize the Implicit Function Theorem and have their roots in Weierstrass' work. The Hartman-Grobman Theorem [11,13] is another remarkable result along these lines, and allows us to understand the behavior of a nonlinear dynamical system in terms of its linearization, under mild technical conditions.
The Stable Manifold Theorem [11] is yet another example. In our research about nonlinear programming we have used it to analyze the convergence of significant algorithms, like the Affine Scaling Method [6], Newton's Method [9], the BFGS Method [7], and even to general families of methods [8,10]. In these articles, by looking at low dimensional problems from the right perspective, we were able to provide satisfactory answers to relevant open problems.
Here we present yet another instance in which the proper simplification leads to a better understanding of nonlinear programming problems. In Section 2 we emphasize that usual optimality conditions in nonlinear programming are invariant under changes of variables. In particular the Lagrange multipliers are the same in different coordinate systems for the independent variables, and the Mangasiran-Fromovitz constraint qualification is invariant under changes of these variables. Section 2 is obvious but relevant. In fact, we believe that changes of variables do not receive the attention they deserve in the mathematical programming literature. For instance, most textbooks do not mention the invariance above explicitly. Authors usually have these changes of variables on the back of their mind, and build good examples to illustrate their points based upon them. However, readers may not notice that, with the proper changes of variables, more general situations can be reduced to these good examples, and in many cases such examples are more enlightening than proofs.
In Section 3 we present a convenient change of the independent variables for nonlinear programming problems in which the rank of the derivative of the inequality constraints drops at the point in which we are interested. Of course, we cannot rely on the usual linear independence hypothesis in this case, but we show that we can still simplify problem considerably by using the proper choice of variables. Finally, in Section 4 we prove Andreani's conjecture, using the results from the previous sections and two linear algebraic lemmas proved in the appendix.

Changes of variables
This section calls the reader's attention to the fundamental fact that the usual optimality conditions in mathematical programming are invariant under changes of variables. In other words, in theory we can pick any coordinate system we please, as long as the coordinates are "consistent" and reflect correctly the problem we want to understand.
We emphasize that, for theoretical purposes, changes of coordinates do not need to be explicit: it suffices to know that they exist and have the nice properties required to deal with the problem at hand. Of course, things are different in practice, because we usually cannot afford, or know how, to compute such changes of coordinates.
The simplest changes of variables are the linear ones: we replace the coordinates x by Ay, where A is a nonsingular square matrix. As a result, we can replace a function f by a more appropriate, or simpler, functionf , as in The chain rule yields and applying the formula above to the functionf k (y) := ∂ k f (Ay) and taking one more derivative and doing the algebra we obtain that Equations (5) and (6) are quite useful, but they are not enough to explore the full power of changes of variables. For that we we need to replace x by a nonlinear function q(y) of a more convenient variable y, as in the nonlinear version of Equation (4): In Equation (7), the function q is a local diffeomorphism, that is a differentiable function defined in a neighborhood of the point with which we are concerned, and such that its inverse q −1 (in the sense that q −1 (q(x)) = x) exists and is also differentiable. In this nonlinear setting we have the following version of Equation (5) ∇f (y) = Dq(y) T ∇f (q(y)) .
Equation (8) is almost the same as (5): we only need to replace A by Dq(y) and Ay by q(y), and keep in mind that the matrix Dq(y) is square and non singular. Things are a bit more complicated for the Hessian. In this case we need to introduce an extra sum due to the curvature in q, and the resulting formula is: With Equations (8) and (9) we can find how the optimality conditions behave under nonlinear changes of coordinates x = q(y). To see why this is true, we consider the classical nonlinear programming problem (1). By making the change of variables x = q(y) we do not affect the satisfiability of the equalities and inequalities in (1), that iŝ will be equal to zero as long as h j (x) is equal to zero. This is obvious, but the analogous obvious property would not hold if we were to take combinations of the dependent instead of the independent variables in problem (1), as when replace the equations by Due to this obvious fact we must think carefully before using techniques like the SVD to analyze the nonlinear programming problem (1). In particular, when we say "change of variables" in this article we refer to changes in the dependent variables x, but not to combinations of the equality constraints or changes in the order of the inequality constraints.
Let us now analyze the first order optimality conditions for problem (1). These conditions are written in terms of the Lagrange multiplies λ j ∈ R and µ ℓ ≥ 0: Given a local diffeomorphism q with q(y) = x, by defininĝ f (y) := f (q(y)) ,ĥ(y) := h(q(y)) , andĝ(y) := g(q(y)) , Equation (8) yields and ∇ĥ j (y) = Dq(y) T ∇h j (q(y)) and ∇ĝ ℓ (y) = Dq(y) T ∇g ℓ (q(y)) . (14) Since our Dq(y) is always non singular, it is easy to see that the first order condition (11) holds if and only if In other words, the first order conditions are invariant with respect to changes of coordinates, and we may study them by using Equation (11), or Equation (15), or both. In particular, the Lagrange multipliers do not change as we change coordinates as above.
For the second order conditions, we consider directions d such that Equation (14) shows that Equation (16) is equivalent to and the orthogonality condition (16) is invariant under changes of coordinates, that is, Equations (16) for d and Equation (17) ford are equivalent. Using the equations above, we can write the second order term Equation (9) yields When the first order conditions (11) hold we have that µ ℓ ∇g ℓ (q(y)) = 0 and ∆ = 0. Therefore, when the first order conditions hold, the second order term S(d) in Equation (18) is invariant with respect to changes of variables, and it can be evaluated using the expression An analogous argument starting from the conditions instead of Equation (16) shows that the Mangazarian-Fromovitz constraint qualification is invariant under changes of coordinates, and similar arguments apply to many other constraint qualifications.
In summary, when trying to answer many theoretical questions regarding the first and second order optimality conditions, Lagrange multipliers and constraint qualifications for the nonlinear programming problem (1), we can analyze them in other coordinate systems, and reach correct conclusions by considering only simplified problems. As we show in the next sections, this obvious observation has far reaching consequences, and can be used to give simpler proofs for some results one finds in the nonlinear optimization literature.

The canonical form
In this section we present a simple canonical form for the classical nonlinear programming problem (1), which can be used when the derivative of the equality constraints has full rank but the inequality constraints are degenerated. In this canonical form the variables are y = (y 1 , . . . , y m ) T , z = (z 1 , . . . , z r ) T and w = (w 1 , . . . , z n−m−r ) T , where r := rank(Dhg(0)) − m.
The equality constraints are given bŷ h(y, z, w) = y = 0, and there are two groups of inequality constraints. The first one is given bŷ The second group of inequalities is is given by a potentially complicated function c: In this problem, the derivative of the constraints has the simple form with D w c(0, 0, 0) = 0, where I m×m is the m × m identity matrix. The next theorem shows that nonlinear programming problems can be reduced to the canonical form (21) under mild assumptions, and the discussion in the previous section shows that the form of the first and second order conditions and the Lagrange multipliers do not change in this reduction. In many relevant situations we can then use Theorem 2 below and say rigorously "without loss of generality, we can assume that our linear programming problem is of the form (21)" The purpose of the present article is to call the readers attention to this simple intuitive idea, which is formalized by Theorem 2 and its proof, which we now present. Theorem 2 is a direct consequence of the Projection Lemma below, which is a corollary of the Inverse Function Theorem (see Thm 2-13 in page 43 of [12].) Besides Lemma 1, we only need to note that the equality D w (0, 0, 0) = 0 follows from Equation (22) and the assumption that Dhg(0) has rank m + r.

Lemma 1 (The Projection Lemma) Let
A be a neighborhood of 0 ∈ R n+k and let f : A → R n a function of class C s . If D f (0) has rank n then there exists a neighborhood Y of 0 ∈ R n , a neighborhood Z of 0 ∈ R k and a diffeomorphism q : Y × Z → q(Y × Z) ⊂ A of class C s such that f (q(y, z)) = y.

A proof of Andreani's Conjecture
In this section we use the canonical form (21) to prove the conjecture by Andreani, Martinez and Schuverdt mentioned in the introduction. This is an interesting application of the canonical form because there were several failed attempts to find a proof of this conjecture by other means.
For instance, the authors of [2] attempted to obtain an appropriate coordinate system, by using a version of the Singular Value Decomposition, and succeeded in proving new particular cases of Andreani's conjecture with this approach. However, they did not prove the conjecture because their decomposition is not as effective as the canonical form: it has "high order terms" in places in which the canonical decomposition has exact zeros, and the technicalities required to handle these terms precluded them from obtaining a proof for which they had found all the other ingredients. This shows that good choices of variables go beyond controlling "high order terms": we actually want to eliminate them, and Andreani's conjecture is one of the fortunate cases in which this is possible.
We now prove Andreani's Conjecture using the arguments presented in the previous sections. Along the proof we resort to two linear algebraic lemmas, which are proved in the appendix. These lemmas are variations of results already presented in other references [2,5], and we provide their proofs to make the article self contained. The first step to prove Theorem 1 is to use Theorem 2 to reduce problem (1) to the canonical form (21). In order to that we note that the Mangasarian-Fromovitz constraint qualification requires that Dh(0) has rank m and recall that we use m + r to denote the rank of the matrix Dhg(0) in Equation (2). Therefore, by changing the order of the inequality constraints if necessary, we can assume that the matrix in Equation (23) in the statement of Theorem 2 has rank m + r. We can then use this theorem to analyze Andreani's conjecture and assume without loss of generality that our linear programming problem has the form (21), because in Section 2 we have shown that Equation (3) and the Mangasarian-Fromovitz constraint qualification are invariant under changes of coordinates.
Lemma 2 (Hessians with rank at most one) Let A be a neighborhood of 0 ∈ R n , and let c 1 , . . . , c m be functions from A to R of class C 2 . If Dc(0) = 0 and rank(Dc(x)) ≤ 1 for all x ∈ A then there exist α 1 , . . . , α m ∈ R and a symmetric matrix H ∈ R n×n such that ∇ 2 c ℓ (0) = α ℓ H for ℓ = 1, . . . , m.

It follows that Equation (24) is equivalent tõ
The Mangasarian-Fromovitz constraint qualification implies that for every d there exists λ and µ > 0 such that S(d) ≥ 0 in Equation (3) (see [2].) Since this equation is equivalent to Equation (25), for everyd there exists γ such thatS d ≥ 0 in Equation (25), and in order to complete the proof we use the following lemma: Lemma 3 (Semidefinite separation) Let I ⊂ R be a compact interval. If the symmetric matrices A, B ∈ R n×n are such that for all x ∈ R n there exists γ x ∈ I such that x T (A + γ x B) x ≥ 0 then there exists γ * ∈ I such that for all x ∈ R n .

A Linear Algebra
In this appendix we prove the results involving Linear Algebra used in Section 4. The proof of Lemma 2 is based on the next two lemmas: Lemma 4 (Rank one columns) If the symmetric matrices H 1 , . . . , H m ∈ R n×n are such that the n × m matrix has rank at most one for all v ∈ R n then there exist α 1 , . . . α m ∈ R and a symmetric matrix H ∈ R n×n \ {0} such that H j = α j H for j = 1 . . . m.
Lemma 5 (Directional derivatives of rank one) Let A be a neighborhood of 0 ∈ R n and let h : A → R n×m be a function of class C 1 , and for 1 ≤ ℓ ≤ m let h ℓ (x) be the ℓth column of h(x). If h(0) = 0 and rank(h(x)) ≤ 1 for all x ∈ A then for every v ∈ R n the n × m matrix has rank at most one.
The proof of Lemma 3 uses the following auxiliary results: Theorem 3 (Dines' Theorem) If the symmetric matrices A, B ∈ R n×n are such that for all x ∈ R n \ {0} either x T Ax = 0 or x T Bx = 0 then the set is either R 2 itself or a closed angular sector of angle less than π.
Lemma 6 (Definite separation) Let I ⊂ R be a compact interval. If the symmetric matrices A, B ∈ R n×n are such that for all x ∈ R n \ {0} there exists γ x ∈ I such that x T (A + γ x B) x > 0 then there exists γ * ∈ I such that for all x ∈ R n \ {0}.
Dines' Theorem is proved in [3], and in the rest of this appendix we prove our lemmas in the order in which they were stated.
Proof of Lemma 2.
Applying Lemma 5 to the function h(x) := Dc(x) we conclude that for every v ∈ R n the n × m matrix has rank at most one, and Lemma 4 yields the coefficients α j and the matrix H. ✷ Proof of Lemma 3. For every k ∈ N, Lemma 6 yields γ k ∈ I such that for all x ∈ R n . Since the sequence γ k is bounded, it has a subsequence which converges to some γ * ∈ I. This γ * is as required by Corollary 3. ✷ Proof of Lemma 4.
Lemma 4 holds when n = 1 or m = 1. Let us then assume that it holds when for n − 1 ≥ 1 or m − 1 ≥ 1 and show that it also holds for m and n. If some H j is zero then we can take α j = 0 and use induction for Therefore, we can assume that H j = 0 for all j. It follows that H 1 has an eigenvalue decomposition H 1 = QDQ T with d 11 = 0. By replacing H j by Q T H j Q for all j, we can assume that Q = I n×n . Taking v = 1/d 11 e 1 we obtain that H 1 v = e 1 and the hypothesis that the matrix A v has rank one implies that H j v = α j e 1 for all j. Since the matrices H j are symmetric, all of them have the form for symmetric matrices H ′ j ∈ R (n−1)×(n−1) \{0} which satisfy the hypothesis of Lemma 4 with n = n − 1. Since H 1 e 1 = d 11 e 1 = 0, we have that α 1 = 0. Let then v ′ ∈ R n−1 be such that H ′ v ′ = 0, and write v = 1 v ′ We have that and the H 1 v and H j v are aligned by hypothesis. Moreover, either α j = 0 or α ′ j = 0, because H j = 0. It follows that α ′ j = α ′ 1 α j /α 1 for all j. For every v ∈ R n and 1 ≤ ℓ ≤ m, the facts that h ∈ C 1 and h(0) = 0 imply that lim δ →0 Let ρ > 0 be such that if B − A v ≤ ρ then rank(B) ≥ rank(A v ). Taking δ such that Therefore, rank(A v ) ≤ 1, and we are done. ✷ Proof of Lemma 6. Let us write I = [a, b]. If a = b then we could simply take γ * = a and we would be done. Therefore, we can assume that a < b. If (u, v) ∈ R(A, B) then u + γv ≥ 0 for some γ ∈ [a, b]. This implies that u ≥ − |γ| |v| ≥ − (1 + |a| + |b|) |v| Therefore, (−2 (1 + |a| + |b|) , 1) ∈ R(A, B) and by Dines' Theorem R(A, B) is a closed pointed cone. For each γ ∈ I the set is a closed convex cone, and is also a closed cone. Moreover, C is pointed because a < b. The hypothesis tells us that for every (u, v) ∈ R(A, B) \ {(0, 0)} there exists γ ∈ I such that (u, v) ∈ C γ , and this implies that C ∩ R(A, B) = {(0, 0)}. Therefore, there exists (c, d) ∈ R 2 such that cu + dv > 0 for (u, v) ∈ R(A, B) \ {(0, 0)} (28) and cu + dv < 0 for (u, v) ∈ C \ {(0, 0)}.