On the stratification of a class of specially structured matrices

Abstract

We consider specially structured matrices representing optimization problems with quadratic objective functions and (finitely many) affine linear equality constraints in an n-dimensional Euclidean space. The class of all such matrices will be subdivided into subsets [‘strata’], reflecting the features of the underlying optimization problems. From a differential-topological point of view, this subdivision turns out to be very satisfactory: Our strata are smooth manifolds, constituting a so-called Whitney Regular Stratification, and their dimensions can be explicitly determined. We indicate how, due to Thom's Transversality Theory, this setting leads to some fundamental results on smooth one-parameter families of linear-quadratic optimization problems with (finitely many) equality and inequality constraints.

Keywords:

• parametric quadratic optimization problems
• generalized critical points
• Whitney regular stratification

AMS Subject Classifications::

• 90C30
• 58A35
• 90C31

Acknowledgements

The authors thank the two referees. Their comments were very helpfull to improve this paper considerably. We also thank Dini Heres for preparing the layout of the manuscript.

Notes

Notes

1. if k = n (≤ m), then S is not defined, but we formally put (ξ⁺, ξ⁻, ξ⁰) = (0, 0, 0) in this case. In order to focus on the general line of reasoning, here and in the sequel we shall not dwell on these types of ‘degeneracies’; see, however, the forthcoming Tables 1, 2, 4, 5 and related comments.

2. Note that ‘rank(B) = m’(thus 0 ≤ m ≤ n) means: the linear independency constraint qualification (LICQ) holds at all (possible) feasible points for Q. Moreover, if – under LICQ – we have 𝒦 _Q  ≠ ∅, then ξ⁰ = 0 yields a well-known second-order non-degeneracy condition on the ‘restricted Hessian of the Lagrange function’ at a critical point for Q. The condition ξ⁰ = 0, together with LICQ, will be referred to as to ND. Note that if rank(B) = m and ξ⁰ = 0, we have: rank M = n + m and thus, 𝒦 _Q consists of the singleton . See, e.g. the forthcoming Corollary 2 (Inertia Theorem).

3. One could expect that sign[M⋮c] not only plays a role in Clusters 3 and 6 but also in Clusters 5 and 7. This is not the case, because under the features in this clusters, we always have: sign[M⋮c] = 0.

4. Two points, say x and y, in a connected component of a stratum are said to ‘have the same topological type with respect to the stratification’ whenever there exist two neighbourhoods of x respectively y, and a homeomorphism between these neighbourhoods that preserves the local stratification around these points.

5. for a definition of semi-algebraic (partition), see Section 6.

6. That is, given any two points in the same stratum, there exists a diffeomorphism of an ℝ ^N -neighbourhood of one point onto an ℝ ^N -neighbourhood of the other point which preserves strata.

7. That is, locally around such a regular point the semi algebraic set is a smooth submanifold.

8. That is, restricted to the C ¹-open and-dense set of mappings Q(·), which are transversal to each stratum .

9. Thus, the gradients at x of the object function for Q, together with the gradients of the (active) constraint functions form a linear dependent set. See e.g., 7,11.

10. In fact, up till now, only an informal, hand written manuscript with these proofs is available.

11. Note that such P exists since ξ⁰ ≥ 1 and ξ⁺ + ξ⁻ = r implies: (r + 1) ≤ (n − k).

12. So, ξ^k = ξ⁻ = 0 does not occur (cf. list of empty strata in Table 1).

13. As a consequence of this expression for τ we have: combinations ‘ξ⁻ = 0, with either τ = 0 or τ = 1’ and ‘ξ⁺ = 0, with either τ = 0 or τ = −1’ do not occur; compare also the list of empty strata in Table 1.

14. Such ϕ₀ exists and is uniquely determined, in fact: ϕ₀ = tanh⁻¹(−α₋/α₊); note that |−α₋/α₊| < 1.

15. Open with respect to the relative topology on ℳ, induced by the standard topology on ℝ ^N .

16. In contradistinction to Section 4, here a pair of sub indices of a block does not indicate its dimension.

17. Use alo the continuous dependency of the eigenvalues of a symmetric matrix on its entries.

18. In fact, due to Lemmas 1–3, this proves that the set {M∣rank(B) = k, In (A _{∣ker B} ) = ξ} is a smooth manifold in ℝ ^N−n−m of codimension .

19. This assumption does not imply a restriction to our final results.

20. Note that in the proof of Theorem 2 (cases ℓ = 3,6) we characterized these conditions – essentially – by means of polynomials. However these characterizations are of a ‘local nature’, whereas for our present aim global characterizations are needed.

21. Note that violation of the condition k + ξ⁺ + ξ⁻ > 0 yields in the cases ℓ = 3,6 empty strata, cf Table 1.

22. Here it is not necessary to restrict ourselves to sets ω which are linearly independent since in case of linear dependency of ω we have G _ω = 0.

23. It is not difficult to show that this also holds for all other sets ∑_ξ,k with the exception of ∑₀, _{k = m = n} , which admits precisely two connected components.

24. With respect to relative topology on W _{(k, r)}.