Abstract
In this paper, by examining the recession properties of convex polynomials, we provide a necessary and sufficient condition for a piecewise convex polynomial to have a Hölder-type global error bound with an explicit Hölder exponent. Our result extends the corresponding results of Li (SIAM J Control Optim 33(5):1510–1529, 1995) from piecewise convex quadratic functions to piecewise convex polynomials.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andronov V.G., Belousov E.G.: Types of upper discontinuities of convex polynomial mappings. Comput. Math. Math. Phys. 41, 943–959 (2001)
Andronov V.G., Belousov E.G.: On a type of Hausdorff discontinuity of convex polynomial mappings. Comput. Math. Math. Phys. 42, 1086–1094 (2002)
Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer Monographs in Mathematics. Springer, New York (2003)
Bauschke H.H., Borwein J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3), 367–426 (1996)
Belousov E.G.: On types of Hausdorff discontinuity from above for convex closed mappings. Optimization 49, 303–325 (2001)
Belousov E.G., Andronov V.G.: Solvability and stability of problems of polynomial programming (in Russian). Moscow University Publisher, Moscow (1993)
Belousov E.G., Klatte D.: A Frank–Wolfe type theorem for convex polynomial programs. Comput. Optim. Appl. 22, 37–48 (2002)
Burke J.V., Deng S.: Weak sharp minima revisited part I: basic theory. Control Cybern. 31, 439–469 (2002)
Burke J.V., Deng S.: Weak sharp minima revisited, II: application to linear regularity and error bounds. Math. Program. Ser. B 104(2–3), 235–261 (2005)
Burke J.V., Deng S.: Weak sharp minima revisited, III: error bounds for differentiable convex inclusions. Math. Program. Ser. B 116(1–2), 37–56 (2009)
Deng S.: Computable error bounds for convex inequality systems in reflexive Banach spaces. SIAM. J. Optim. 7, 274–279 (1997)
Deng S.: Pertubation analysis of a condition number for convex inequality systems and global error bounds for analytic systems. Math. Program. 83, 263–276 (1998)
Deng S.: Lausanne 1997. Well-posed problems and error bounds in optimization. Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods. Appl. Optim. 22, 117–126 (1999)
He Y.R., Sun J.: Second-order sufficient conditions for error bounds in Banach spaces. SIAM J. Optim. 17(3), 795–805 (2006)
Hiriart-Urruty, J.B., Lémarachal, C.: Convex analysis and minimization algorithms. II. Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften Fundamental Principles of Mathematical Sciences, 306, pp. xviii+346. Springer, Berlin (1993)
Jeyakumar V., Lee G.M., Li G.Y.: Alternative theorems for quadratic inequality systems and global quadratic optimization. SIAM J. Optim. 20(2), 983–1001 (2009)
Jeyakumar V., Li G.Y.: Necessary global optimality conditions for nonlinear programming problems with polynomial constraints. Math. Program. Ser. A 126(2), 393–399 (2011)
Klatte, D.: Hoffman’s error bound for systems of convex inequalities. Mathematical programming with data perturbations. Lecture Notes in Pure and Appl. Math., vol. 195, pp. 185–199. Dekker, New York (1998)
Klatte D., Li W.: Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Program. 84, 137–160 (1999)
Lewis, A.S., Pang, J.S.: Error bounds for convex inequality systems generalized convexity, generalized monotonicity. In: Crouzeix, J.P., Martinez-Legaz, J.E., Volle, M. (eds.) pp. 75–110 (1998)
Li G.Y., Jeyakumar V.: Qualification-free optimality conditions for convex programs with separable inequality constraints. J. Convex Anal. 16(3–4), 845–856 (2009)
Li G.: On the asymptotic well behaved functions and global error bound for convex polynomials. SIAM J. Optim. 20(4), 1923–1943 (2010)
Li G., Ng K.F.: On extension of Fenchel duality and its application. SIAM J. Optim. 19, 1489–1509 (2008)
Li G., Ng K.F.: Error bounds of generalized D-gap functions for nonsmooth and nonmonotone variational inequality problems. SIAM J. Optim. 20(2), 667–690 (2009)
Li G., Tang C.M., Wei Z.X.: Error bound results for generalized D-gap functions of nonsmooth variational inequality problems. J. Comput. Appl. Math. 233, 2795–2806 (2010)
Li W.: Error bounds for piecewise convex quadratic programs and applications. SIAM J. Control Optim. 33(5), 1510–1529 (1995)
Luo X.D., Luo Z.Q.: Extension of Hoffman’s error bound to polynomial systems. SIAM J. Optim. 4(2), 383–392 (1994)
Luo Z.Q., Pang J.S.: Error bounds for analytic systems and their applications. Math. Programm. 67, 1–28 (1994)
Mangasarian O.L.: A condition number for differentiable convex inequalities. Math. Oper. Res. 10(2), 175–179 (1985)
Ng K.F., Zheng X.Y.: Error bounds for lower semicontinuous functions in normed spaces. SIAM J. Optim. 12(1), 117 (2001)
Ng K.F., Zheng X.Y.: Global error bounds with fractional exponents. Error bounds in mathematical programming. Math. Program. Ser. B 88(2), 357–370 (2000)
Ngai H.V., Théra M.: Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. Ser. B 104(2–3), 465–482 (2005)
Obuchowska W.T.: On generalizations of the Frank–Wolfe theorem to convex and quasi-convex programmes. Comput. Optim. Appl. 33, 349–364 (2006)
Pang J.S.: Error bounds in mathematical programming. Math. Program. 79(2), 299–332 (1997)
Robinson S.M.: An application of error bounds for convex programming in a linear space. SIAM J. Control 13, 271–273 (1975)
Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton, N.J (1970)
Rockafellar R.T., Wets R.: Variational analysis, Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), vol. 317. Springer, Berlin (1998)
Shironin, V.M.: On Hausdorff continuity of convex and convex polynomial mappings (in Russian). In: Belousov, E.G., Bank, B. (eds.) Mathematical Optimization: Questions of Solvability and Stability, Chapter V. Moscow Univeristy Publ., Moscow (1986)
Tikhomirov, V.M.: Analysis. II. Convex analysis and approximation theory. In: Gamkrelidze, R.V. (ed.) A translation of Sovremennye problemy matematiki. Fundamentalnye napravleniya, Tom 14, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1987, Translation by D. Newton. Encyclopaedia of Mathematical Sciences, 14. Springer, Berlin (1990)
Wang T., Pang J.S.: Global error bounds for convex quadratic inequality systems. Optimization 31(1), 1–12 (1994)
Wu Z.L., Ye J.J.: On error bounds for lower semicontinuous functions. Math. Program Ser. A. 92(2), 301–314 (2002)
Yang W.H.: Error bounds for convex polynomials. SIAM J. Optim. 19(4), 1633–1647 (2008)
Zalinescu C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by a grant from the Australian Research Council.
Rights and permissions
About this article
Cite this article
Li, G. Global error bounds for piecewise convex polynomials. Math. Program. 137, 37–64 (2013). https://doi.org/10.1007/s10107-011-0481-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0481-z