Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Strong CHIP, normality, and linear regularity of convex sets

Authors: Andrew Bakan, Frank Deutsch and Wu Li
Journal: Trans. Amer. Math. Soc. 357 (2005), 3831-3863
MSC (2000): Primary 90C25, 41A65; Secondary 52A15, 52A20, 41A29
Published electronically: May 10, 2005
MathSciNet review: 2159690
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We extend the property (N) introduced by Jameson for closed convex cones to the normal property for a finite collection of convex sets in a Hilbert space. Variations of the normal property, such as the weak normal property and the uniform normal property, are also introduced. A dual form of the normal property is derived. When applied to closed convex cones, the dual normal property is the property (G) introduced by Jameson. Normality of convex sets provides a new perspective on the relationship between the strong conical hull intersection property (strong CHIP) and various regularity properties. In particular, we prove that the weak normal property is a dual characterization of the strong CHIP, and the uniform normal property is a characterization of the linear regularity. Moreover, the linear regularity is equivalent to the fact that the normality constant for feasible direction cones of the convex sets at $x$ is bounded away from 0 uniformly over all points in the intersection of these convex sets.

References [Enhancements On Off] (What's this?)

  • 1. A. Bakan, Normal pairs of cones in finite-dimensional spaces, in ``Questions of the Theory of Approximation of Functions and Their Applications,'' Inst. Mat., Akad. Nauk Ukr. SSR, Kiev, 1988 (in Russian). MR 90h:52001
  • 2. A. Bakan, The Moreau-Rockafellar equality for sublinear functionals, Transl. Ukr. Math. J., 41(1990), 861-871. MR 1019523 (91a:58025)
  • 3. A. Bakan, Nonemptiness of classes of normal pairs of cones of transfinite order, Transl. Ukr. Math. J., 41(1989), 462-466. MR 1004860 (90g:52001)
  • 4. H. H. Bauschke, Projection Algorithms and Monotone Operators, Ph.D. thesis, Simon Fraser University, 1996.
  • 5. H. Bauschke and J. Borwein, On the convergence of von Neumann's alternating projection algorithm for two sets, Set-Valued Analysis, 1(2)(1993), 185-212. MR 1239403 (95d:65048)
  • 6. H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38(1996), 367-426. MR 1409591 (98f:90045)
  • 7. H. Bauschke and J. Borwein, Conical open mapping theorems and regularity, Proceedings of the Centre for Mathematics and its Applications, 36 (Australian National University, 1998), 1999, 1-10.
  • 8. H. Bauschke, J. Borwein, and A. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, in Optimization and Nonlinear Analysis (edited by Y. Censor and S. Reich), Contemporary Mathematics, Amer. Math. Soc., 1997. MR 1442992 (98c:49069)
  • 9. H. Bauschke, J. Borwein, and W. Li, Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization, Mathematical Programming (Series A), 86(1)(1999), 135-160. MR 1712477 (2000f:90095)
  • 10. H. Bauschke, J. Borwein, and P. Tseng, Bounded linear regularity, strong CHIP, and CHIP are distinct properties, J. Convex Anal., 7(2000), 395-412. MR 1811687 (2002d:90113)
  • 11. C. Chui, F. Deutsch, and J. Ward, Constrained best approximation in Hilbert space, Constructive Approx., 6(1990), 35-64. MR 1027508 (91b:41014)
  • 12. C.K. Chui, F. Deutsch, and J.D. Ward, Constrained best approximation in Hilbert space II, J. Approx. Theory, 71(1992), 231-238. MR 1186970 (93k:41019)
  • 13. S. Deng, Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems, Math. Programming, 83(1998), 263-276. MR 1647861 (99j:90094)
  • 14. S. Deng, Global error bounds for convex inequalities in Banach spaces, SIAM J. Control Optimiz., 36(4)(1998), 1240-1249. MR 1618049 (99f:90142)
  • 15. F. Deutsch, The role of the strong conical hull intersection property in convex optimization and approximation, in Approximation Theory IX, Vol. I: Theoretical Aspects (edited by C.K. Chui and L.L. Schumaker), Vanderbilt University Press, Nashville, TN, 1998, pp. 105-112. MR 1742997 (2001c:90098)
  • 16. F. Deutsch, Best Approximation in Inner Product Spaces, Springer, New York, 2001. MR 1823556 (2002c:41001)
  • 17. F. Deutsch, W. Li, and J. Swetits, Fenchel duality and the strong conical hull intersection property, J.Optimiz. Theory Appl., 102(1999), 681-695. MR 1710727 (2000k:49047)
  • 18. F. Deutsch, W. Li, and J. Ward, A dual approach to constrained interpolation from a convex subset of Hilbert space, J. Approx. Theory, 90(1997), 385-414. MR 1469335 (98m:41050)
  • 19. F. Deutsch, W. Li, and J.D. Ward, Best approximation from the intersection of a closed convex set and a polyhedron in Hilbert space, weak Slater conditions, and the strong conical hull intersection property, SIAM J. Optimiz., 10(2000), 252-268. MR 1742319 (2001a:41047)
  • 20. J. Diestel, Geometry of Banach spaces, Selected Topics, Lect. Not. in Math., Springer-Verlag, 1980. MR 0461094 (57:1079)
  • 21. C. Franchetti and W. Light, The alternating algorithm in uniformly convex spaces, J. London Math. Soc., 29(1984), 545-555. MR 0754940 (85h:41064)
  • 22. J.-B. Hiriart-Urruty and C. Lemarechal, Convex analysis and minimization algorithms I, Springer-Verlag, N.Y., 1993.
  • 23. A. Hoffman, On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Standards, 49(1952), 263-265. MR 0051275 (14:455b)
  • 24. A. Ioffe and V. Tikhomirov, Theory of Extremal Problems, Nauka, Moscow, 1974 (in Russian) [English translation by North Holland, Amsterdam, 1979].
  • 25. D. Klatte and W. Li, Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Programming, 84(1999), 137-160. MR 1687264 (2000f:90073)
  • 26. G. Jameson, The duality of pairs of wedges, Proc. London Math. Soc., 24(1972), 531-547. MR 0298388 (45:7440)
  • 27. A. Kusraev, Vector Duality and Its Application (in Russian), Nauka, Novosybirsk, 1985. MR 0836135 (87f:46014)
  • 28. A. Kusraev and S. Kutateladze, Subdifferential Calculus, Nauka, Novosybirsk, 1987 (in Russian) [English translation as: Subdifferentials: Theory and Applications, Mathematics and its Applications, Vol. 323, Kluwer Academic Publ., 1995]. MR 1471481 (99c:46001)
  • 29. P.-J.Laurent, Approximation et Optimization, Univ. Sci. Med. Grenoble, Hermann, Paris, 1972. MR 0467080 (57:6947)
  • 30. A. S. Lewis and J.-S. Pang, Error bounds for convex inequality systems, in Generalized Convexity, Generalized Monotonicity (edited by J.-P. Crouzeix, J.-E. Martizez-Legaz, and M. Volle), 1998, pp. 75-110. MR 1646951 (2000d:90082)
  • 31. W. Li, Abadie's constraint qualification, metric regularity, and error bounds for differentiable convex inequalities, SIAM J. Optim., 7(1997), 966-978. MR 1479609 (99b:90131)
  • 32. W. Li, C. Nahak, and I. Singer, Constraint qualifications for semi-infinite systems of convex inequalities, SIAM J. Optimiz., 11(2000), 31-52. MR 1785387 (2001i:90096)
  • 33. W. Li and I. Singer, Global error bounds for convex multifunctions and applications, Math. Oper. Res., 23(1998), 443-462. MR 1626694 (99i:90097)
  • 34. R. Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, N.J., 1970. MR 0274683 (43:445)
  • 35. H. Schaefer, Topological Vector Spaces, Macmillan, N.Y., 1966. MR 0193469 (33:1689)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 90C25, 41A65, 52A15, 52A20, 41A29

Retrieve articles in all journals with MSC (2000): 90C25, 41A65, 52A15, 52A20, 41A29

Additional Information

Andrew Bakan
Affiliation: Institute of Mathematics, National Academy of Sciences of Ukraine, Kyiv 01601, Ukraine

Frank Deutsch
Affiliation: Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

Wu Li
Affiliation: NASA Langley Research Center, Hampton, Virginia 23681

Keywords: Moreau-Rockafellar equality, Jameson's property (N), Jameson's property (G), the conical hull intersection property (the CHIP), the strong conical hull intersection property (the strong CHIP), basic constraint qualification, linear regularity, bounded linear regularity, normal property, weak normal property, uniform normal property, dual normal property.
Received by editor(s): May 30, 2002
Published electronically: May 10, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society