×

Hölder-type global error bounds for non-degenerate polynomial systems. (English) Zbl 1375.32017

Summary: Let \(F:= (f_1, \dots, f_p): \mathbb{R}^n \to \mathbb{R}^p\) be a polynomial map, and suppose that \(S:=\{x \in \mathbb{R}^n: f_i(x) \leq 0,i=1, \dots,p\} \neq \emptyset\). Let \(d:= \max_{i=1, \dots, p} \deg f_i\) and \(\mathcal {H}(d, n, p) := d(6d - 3)^{n + p - 1}\). Under the assumptions that the map \(F: \mathbb{R}^n \to\mathbb{R}^p\) is convenient and non-degenerate at infinity, we show that there exists a constant \(c>0\) such that the following so-called Hölder-type global error bound result holds \[ cd(x,S) \leq [f(x)]_{+}^{\frac {2}{\mathcal {H}(2d, n, p)}} + [f(x)]_{+} \quad\text{for all} \quad x \in \mathbb {R}^{n}, \] where \(d(x,S)\) denotes the Euclidean distance between \(x\) and \(S\), \(f(x) := \max_{i=1, \dots, p}f_i(x)\), and \([f(x)]_+ :=\max\{ f(x),0\}\). The class of polynomial maps (with fixed Newton polyhedra), which are non-degenerate at infinity, is generic in the sense that it is an open and dense semi-algebraic set. Therefore, Hölder-type global error bounds hold for a large class of polynomial maps, which can be recognized relatively easily from their combinatoric data. This follows up the result on a Frank-Wolfe type theorem for non-degenerate polynomial programs in [S. T. Dinh, H. V. Hà and T. S. Pham, “A Frank-Wolfe type theorem for nondegenerate polynomial programs”, Mathematical Programming Series A, 147 (16), 519–538 (2014)].

MSC:

32B20 Semi-analytic sets, subanalytic sets, and generalizations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arnold, V.I., Gusein-Zade, S., Varchenko, A.N.: Singularities of Differentiable Maps. Monogr. Math., vol. I And II, Birkhäuser, Basel (1985) · Zbl 1297.32001
[2] Auslender, A.A., Crouzeix, J.-P.: Global regularity theorem. Math. Oper. Res. 13, 243-253 (1988) · Zbl 0655.90059 · doi:10.1287/moor.13.2.243
[3] Auslender, A.A., Crouzeix, J.-P.: Well behaved asymptotical convex functions. Ann. Inst. H. Poincaré, Anal. Non Linéaire 6, 10-121 (1989) · Zbl 0675.90070 · doi:10.1016/S0294-1449(17)30017-3
[4] Auslender, A.A., Cominetti, R., Crouzeix, J.-P.: Convex functions with unbounded level sets. SIAM J. Optim. 3, 669-687 (1993) · Zbl 0808.90102 · doi:10.1137/0803034
[5] Benedetti, R., Risler, J.: Real Algebraic and Semi-algebraic Sets Hermann (1991) · Zbl 0694.14006
[6] Bierstone, E., Milman, P.: Semianalytic and subanalytic sets. Inst. Hautes Études Sci. Publ. Math. 67, 5-42 (1988) · Zbl 0674.32002 · doi:10.1007/BF02699126
[7] Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Vol. 36 springer (1998) · Zbl 0912.14023
[8] Bolte, J., Daniilidis, A., Lewis, A.S.: The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205-1223 (2007) · Zbl 1129.26012 · doi:10.1137/050644641
[9] Borwein, J.M., Li, G., Yao, L.: Analysis of the convergence rate for the cyclic projection algorithm applied to basic semi-algebraic convex sets. SIAM J. Optim. 24, 498-527 (2014) · Zbl 1296.41011 · doi:10.1137/130919052
[10] Borwein, J.M., Preiss, D.: A smooth variational principle with applications to subdifferentiability and to differentiability of convex functions. Trans. Am. Math. Soc. 303, 517-527 (1987) · Zbl 0632.49008 · doi:10.1090/S0002-9947-1987-0902782-7
[11] Broughton, S.: Milnor number and topology of polynomial hypersurfaces. Invent. Math. 92, 217-241 (1988) · Zbl 0658.32005 · doi:10.1007/BF01404452
[12] Clarke, F.H.: Optimization and Nonsmooth Analysis. New York et al., John Wiley & Sons (1983) · Zbl 0582.49001
[13] Clarke, F.H., Ledyaev, Y.S., Sterm, R.J., Wolenski, P.R.: Nonsmooth analysis and control theory. Springer-Verlag Inc., New York (1998) · Zbl 0836.90125
[14] Corvellec, J.-N., Motreanu, V.V.: Nonlinear error bounds for lower semicontinuous functions on metric spaces. Math. Program. Ser. A 114(2), 291-319 (2008) · Zbl 1190.90206 · doi:10.1007/s10107-007-0102-z
[15] Dinh, S.T., Hà, H.V., Thao, N.T.: Łojasiewicz inequality for polynomial functions on non compact domains. Int. J. Math. 23(4), 1250033 (2012). doi:10.1142/S0129167X12500334. (28 pages) · Zbl 1246.26013 · doi:10.1142/S0129167X12500334
[16] Dinh, S.T., Hà, H.V., Phạm, T. S.: A Frank-Wolfe type theorem for nondegenerate polynomial programs. Mathematical Programming Series A 147, 519-538 (2014) · Zbl 1297.90126 · doi:10.1007/s10107-013-0732-2
[17] Dinh, S.T., Hà, H.V., Phạm, T.S., Thao, N.T.: Global Łojasiewicz-type inequality for non-degenerate polynomial maps. J. Math. Anal. Appl. 410(2), 541-560 (2014) · Zbl 1311.14055 · doi:10.1016/j.jmaa.2013.08.044
[18] van den Dries, L., Miller, C.: Geometric categories and o-minimal structures. Duke Math. J 84, 497-540 (1996) · Zbl 0889.03025 · doi:10.1215/S0012-7094-96-08416-1
[19] Ekeland, I.: Nonconvex minimization problems. Bull. A.M.S 1, 443-474 (1979) · Zbl 0441.49011 · doi:10.1090/S0273-0979-1979-14595-6
[20] Forti, M., Tesi, A.: The Łojasiewicz exponent at an equilibrium point of a standard CNN is 1/2. Internat. J. Bifur. Chaos Appl. Sci. Engrg. 16(8), 2191-2205 (2006) · Zbl 1192.37116 · doi:10.1142/S0218127406016008
[21] Gaffney, T.: Integral closure of modules and Whitney equisingularity. Invent. Math. 107, 301-322 (1992) · Zbl 0807.32024 · doi:10.1007/BF01231892
[22] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Company, Publishers, San Francisco (1979) · Zbl 0411.68039
[23] Hà, H.V., Duc, N.H.: Łojasiewicz inequality at infinity for polynomials in two real variables. Math. Z 266, 243-264 (2010) · Zbl 1201.14039 · doi:10.1007/s00209-009-0567-y
[24] Hà, H.V.: Global Hölderian error bound for non-degenerate polynomials. SIAM J. Optim. 23(2), 917-933 (2013) · Zbl 1273.32014 · doi:10.1137/110859889
[25] Hoffman, A.J.: On approximate solutions of linear inequalities. J. Res. Natl. Bur. Stand. 49, 263-265 (1952) · doi:10.6028/jres.049.027
[26] Hörmander, L.: On the division of distributions by polynomials. Ark. Mat. 3 (53), 555-568 (1958) · Zbl 0131.11903 · doi:10.1007/BF02589517
[27] Ioffe, A.D.: Metric regularity and subdifferential calculus. Russ. Math. Surv. 55 (3), 501-558 (2000) · Zbl 0979.49017 · doi:10.1070/RM2000v055n03ABEH000292
[28] Ji, S., Kollár, J., Shiffman, B.: A global Łojasiewicz inequality for algebraic varieties. Trans. Am. Math. Soc. 329(2), 813-818 (1992) · Zbl 0762.14001
[29] Khovanskii, A.G.: Newton polyhedra and toroidal varieties. Funct. Anal. Appl. 11, 289-296 (1978) · Zbl 0445.14019 · doi:10.1007/BF01077143
[30] Khovanskii, A.G.: Fewnomials. Translated from the Russian by Smilka Zdravkovska Translations of Mathematical Monographs, 88. American Mathematical Society, Providence, RI (1991) · Zbl 1296.41011
[31] Klatte, D.: Hoffman’s error bound for systems of convex inequalities. Mathematical Programming with Data Perturbations, 185-199, Lecture Notes in Pure and Appl. Math., 195 Dekker New York (1998) · Zbl 0911.90315
[32] Klatte, D., Li, W.: Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Program. 84, 137-140 (1999) · Zbl 1050.90557 · doi:10.1007/s10107980002a
[33] Kollár, J.: An effective Lojasiewicz inequality for real polynomials. Period. Math. Hungar. 38(3), 213-221 (1999) · Zbl 0973.26012 · doi:10.1023/A:1004806609074
[34] Kouchnirenko, A.G.: Polyhedres de Newton et nombre de Milnor. Invent. Math. 32, 1-31 (1976) · Zbl 0328.32007 · doi:10.1007/BF01389769
[35] Lemaire, B.: Bonne position, conditionnement, et bon comportement asymptotique. sém. Anal. Convexe 22, Exp. No. 5 12 pp (1992) · Zbl 1267.49006
[36] Lewis, A.S., Pang, J.S.: Error Bounds for Convex Inequality Systems. Generalized Convexity, Generalized Monotonicity: Recent Results (Luminy, 1996), 75-110, Nonconvex Optim. Appl., 27, Kluwer Acad. Publ., Dordrecht (1998) · Zbl 0953.90048
[37] Li, G.: On the asymptotic well behaved functions and global error bound for convex polynomials. SIAM J. Optim. 20(4), 1923-1943 (2010) · Zbl 1208.90135 · doi:10.1137/080733668
[38] Li, G., Mordukhovich, B.S.: Hölder metric subregularity with applications to proximal point method. SIAM J. Optim. 22, 1655-1684 (2012) · Zbl 1260.49069 · doi:10.1137/120864660
[39] Li, G.: Global error bounds for piecewise convex polynomials. Math. Program. Ser. A 137(1-2), 37-64 (2013) · Zbl 1270.90080 · doi:10.1007/s10107-011-0481-z
[40] Li, G., Mordukhovich, B.S., Phạm, T.S.: New fractional error bounds for polynomial systems with applications to hölderian stability in optimization and spectral theory of tensors. Math. Program. 153, 333-362 (2015) · Zbl 1327.90237 · doi:10.1007/s10107-014-0806-9
[41] Li, W.: Error bounds for piecewise convex quadratic programs and applications. SIAM J. Control Optim. 33, 1510-1529 (1995) · Zbl 0836.90125 · doi:10.1137/S0363012993243022
[42] Łojasiewicz, S.: Division d’une distribution par une fonction analytique de variables réelles. C. R. Acad. S.i. Paris 246, 683-686 (1958) · Zbl 0115.10202
[43] Luo, Z.-Q., Pang, J.S.: Error bounds for analytic systems and their applications. Math. Program. 67, 1-28 (1994) · Zbl 0813.90116 · doi:10.1007/BF01582210
[44] Luo, Z.-Q., Sturm, J.F. In: Frenk, H., Roos, K., Terlaky, T., Zhang (eds.) : Error bound for quadratic systems, in high performance optimization, pp 383-404. Kluwer, Dordrecht, The Netherlands (2000) · Zbl 1043.90552
[45] Mangasarian, O.L.: A condition number for differentiable convex inequalities. Math. Oper. Res. 10, 175-179 (1985) · Zbl 0565.90059 · doi:10.1287/moor.10.2.175
[46] Miller, C.: Exponentiation is hard to avoid. Proc. Am. Math. Soc. 122, 257-259 (1994) · Zbl 0808.03022 · doi:10.1090/S0002-9939-1994-1195484-5
[47] Milnor, J.: Singular points of complex hypersurfaces. Annals of mathematics studies 61 princeton university press (1968) · Zbl 0184.48405
[48] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I: Basic Theory, II. Applications. Springer, Berlin (2006)
[49] Némethi, A., Zaharia, A.: Milnor fibration at infinity. Indag. Math. 3, 323-335 (1992) · Zbl 0806.57021 · doi:10.1016/0019-3577(92)90039-N
[50] Ngai, H.V., Thera, M.: Error bounds for differentiable convex inequality systems in Banach spaces. Math. Program., Ser. B 104(2-3), 465-482 (2005) · Zbl 1089.49028 · doi:10.1007/s10107-005-0624-1
[51] Oka, M.: Non-Degenerate Complete Intersection Singularity. Actualités Mathématiques. Hermann, Paris (1997) · Zbl 0930.14034
[52] Pang, J.S.: Error bounds in mathematical programming. Math. Program., Ser. B 79, 299-332 (1997) · Zbl 0887.90165
[53] Penot, J.P.: Well-behavior, well-posedness and nonsmooth analysis. In: Proceedings of the 4th International Conference on Mathematical Methods in Operations Research and 6th Workshop on Well-posedness and Stability of Optimization Problems (Sozopol, 1997). Pliska Stud. Math. Bulgar, vol. 12, pp 141-190 (1998) · Zbl 0946.49019
[54] Robinson, S.M.: An application of error bounds for convex programming in a linear space. SIAM J. Control. 13, 271-273 (1975) · Zbl 0297.90072 · doi:10.1137/0313015
[55] Rockafellar, R.T., Wets, R.: Variational Analysis. Grundlehren Math Wiss, vol. 317. Springer, New York (1998) · Zbl 0888.49001
[56] Wu, Z., Ye, J.J.: Sufficient conditions for error bounds. SIAM J. Optim. 12, 421-435 (2001) · Zbl 1042.49023 · doi:10.1137/S1052623400371557
[57] Yang, W.H.: Error bounds for convex polynomials. SIAM J. Optim. 19(4), 1633-1647 (2008) · Zbl 1191.47068 · doi:10.1137/070689838
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.