×

Qualification conditions in semialgebraic programming. (English) Zbl 1396.49007

Summary: For an arbitrary finite family of semialgebraic/definable functions, we consider the corresponding inequality constraint set and we study qualification conditions for perturbations of this set. In particular we prove that all positive diagonal perturbations, save perhaps a finite number of them, ensure that any point within the feasible set satisfies the Mangasarian-Fromovitz constraint qualification. Using the Milnor-Thom theorem, we provide a bound for the number of singular perturbations when the constraints are polynomial functions. Examples show that the order of magnitude of our exponential bound is relevant. Our perturbation approach provides a simple protocol to build sequences of “regular” problems approximating an arbitrary semialgebraic/definable problem. Applications to sequential quadratic programming methods and sum of squares relaxation are provided.

MSC:

49J40 Variational inequalities
93C70 Time-scale analysis and singular perturbations in control/observation systems
90C20 Quadratic programming
49K21 Optimality conditions for problems involving relations other than differential equations
49J52 Nonsmooth analysis
37B35 Gradient-like behavior; isolated (locally maximal) invariant sets; attractors, repellers for topological dynamical systems
14P15 Real-analytic and semi-analytic sets

Software:

PLCP; SQPlab
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Abril Bucero and B. Mourrain, Exact Relaxation for Polynomial Optimization on Semi-Algebraic Sets, preprint, arXiv.1307.6426, 2014.
[2] E. L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction, Springer Ser. Comput. Math. 13, Springer, Berlin, 1990, . · Zbl 0717.65030
[3] A. Auslender, An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming, J. Optim. Theory Appl., 156 (2013), pp. 183–212, . · Zbl 1290.90060
[4] R. Benedetti, F. Loeser, and J.-J. Risler, Bounding the number of connected components of a real algebraic set, Discrete Comput. Geom., 6 (1991), pp. 191–209, . · Zbl 0743.14040
[5] R. Benedetti and J.-J. Risler, Real Algebraic and Semi-Algebraic Sets, Actualités Math., Hermann, Paris, 1990. · Zbl 0694.14006
[6] D. P. Bertsekas, Nonlinear Programming, Athena Sci. Optim. Comput. Ser., 3rd ed., Athena Scientific, Belmont, MA, 2016.
[7] L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.), 21 (1989), pp. 1–46, . · Zbl 0681.03020
[8] J. Bolte, A. Daniilidis, and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17 (2007), pp. 1205–1223, . · Zbl 1129.26012
[9] J. Bolte, A. Daniilidis, and A. Lewis, Tame functions are semismooth, Math. Program., 117 (2009), pp. 5–19, . · Zbl 1158.49030
[10] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, Clarke subgradients of stratifiable functions, SIAM J. Optim., 18 (2007), pp. 556–572, . · Zbl 1142.49006
[11] J. Bolte, A. Daniilidis, and A. S. Lewis, Generic optimality conditions for semialgebraic convex programs, Math. Oper. Res., 36 (2011), pp. 55–70, . · Zbl 1218.90189
[12] J. Bolte and E. Pauwels, Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs, Math. Oper. Res., 41 (2016), pp. 442–465, . · Zbl 1338.65156
[13] J.-F. Bonnans, J. C. Gilbert, C. Lemaréchal, and C. A. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects, Universitext, 2nd ed., Springer, Berlin, 2006.
[14] J.-F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Ser. Oper. Res., Springer, New York, 2000. · Zbl 0966.49001
[15] J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, CMS Books Math./Ouvrages de Math. SMC 3, 2nd ed., Springer, New York, 2006, . · Zbl 1116.90001
[16] M. Coste, An Introduction to O-Minimal Geometry, RAAG notes, Institut de Recherche Mathématique de Rennes, 1999; available at .
[17] D. A. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergrad. Texts Math., 4th ed., Springer, New York, 2015, . · Zbl 1335.13001
[18] A. Daniilidis and J. C. H. Pang, Continuity and differentiability of set-valued maps revisited in the light of tame geometry, J. Lond. Math. Soc., 83 (2011), pp. 637–658. · Zbl 1214.49016
[19] J. Demmel, J. Nie, and V. Powers, Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals, J. Pure Appl. Algebra, 209 (2007), pp. 189–200, . · Zbl 1106.13028
[20] J. Demmel, J. Nie, and B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Math. Program., 106 (2006), pp. 587–606, . · Zbl 1134.90032
[21] A. L. Dontchev, M. Quincampoix, and N. Zlateva, Aubin criterion for metric regularity, J. Convex Anal., 13 (2006), pp. 281–297. · Zbl 1098.49018
[22] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, Springer Ser. Oper. Res. Financ. Eng., 2nd ed., Springer, New York, 2014, . · Zbl 1337.26003
[23] L. van den Dries, Tame Topology and O-Minimal Structures, London Math. Soc. Lecture Note Ser. 248, Cambridge University Press, Cambridge, 1998, . · Zbl 0953.03045
[24] L. van den Dries and C. Miller, Geometric categories and o-minimal structures, Duke Math. J., 84 (1996), pp. 497–540, . · Zbl 0889.03025
[25] D. Drusvyatskiy, A. D. Ioffe, and A. S. Lewis, Generic minimizing behavior in semialgebraic optimization, SIAM J. Optim., 26 (2016), pp. 513–534, . · Zbl 1334.49057
[26] R. Fletcher, An \(ℓ_1\) penalty method for nonlinear constraints, in Numerical Optimization 1984, SIAM, Philadelphia, PA, 1985, pp. 26–40.
[27] H. Frankowska, Some inverse mapping theorems, Ann. Inst. H. Poincaré Anal. Non Linéaire, 7 (1990), pp. 183–234. · Zbl 0727.26014
[28] H. Frankowska and M. Quincampoix, Hölder metric regularity of set-valued maps, Math. Program., 132 (2012), pp. 333–354, . · Zbl 1262.90173
[29] O. Fujiwara, Morse programs: A topological approach to smooth constrained optimization. ŭshape I, Math. Oper. Res., 7 (1982), pp. 602–616. · Zbl 0496.90068
[30] P. E. Gill and E. Wong, Sequential Quadratic Programming Methods, Springer, New York, 2012, pp. 147–224, . · Zbl 1242.90297
[31] H. V. Hà and T. S. Pham, Genericity in Polynomial Optimization, Ser. Optim. Appl. 3, World Scientific, Hackensack, NJ, 2017. · Zbl 1370.14049
[32] A. Ioffe, A Sard theorem for tame set-valued mappings, J. Math. Anal. Appl., 335 (2007), pp. 882–901, . · Zbl 1121.49016
[33] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817, . · Zbl 1010.90061
[34] J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imp. Coll. Press Optim. Ser. 1, Imperial College Press, London, 2010.
[35] G. M. Lee and T.-S. Pham, Generic properties for semialgebraic programs, Optim. Online, 2015; available at . · Zbl 1396.90065
[36] G. M. Lee and T.-S. Pham, Stability and genericity for semi-algebraic compact programs, J. Optim. Theory Appl., 169 (2016), pp. 473–495, https://doi.org/10.1007/s10957-016-0910-5. · Zbl 1338.90320
[37] P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika, 17 (1970), pp. 179–184, . · Zbl 0217.46703
[38] J. W. Milnor, Topology from the Differentiable Viewpoint, University Press of Virginia, Charlottesville, VA, 1965. · Zbl 0136.20402
[39] B. S. Mordukhovich, Maximum principle in the problem of time optimal response with nonsmooth constraints, Prikl. Mat. Meh., 40 (1976), pp. 1014–1023.
[40] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I, Grundlehren Math. Wiss. 330, Springer, Berlin, 2006.
[41] J. Nie, Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program., 146 (2014), pp. 97–121, . · Zbl 1300.65041
[42] J. Nocedal and S. J. Wright, Numerical Optimization, Springer Ser. Oper. Res. Financ. Eng., 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[43] R. T. Rockafellar and R. J.-B. Wets, Variational analysis, Grundlehren Math. Wiss. 317, Springer, Berlin, 1998, . · Zbl 0888.49001
[44] K. Schmüdgen, The \(K\)-moment problem for compact semi-algebraic sets, Math. Ann., 289 (1991), pp. 203–206, .
[45] S. Scholtes and M. Stöhr, How stringent is the linear independence assumption for mathematical programs with complementarity constraints?, Math. Oper. Res., 26 (2001), pp. 851–863, . · Zbl 1082.90580
[46] R. Seidel, The upper bound theorem for polytopes: An easy proof of its asymptotic version, Comput. Geom., 5 (1995), pp. 115–116, . · Zbl 0831.68114
[47] J. E. Spingarn and R. T. Rockafellar, The generic nature of optimality conditions in nonlinear programming, Math. Oper. Res., 4 (1979), pp. 425–430, . · Zbl 0423.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.