Abstract

Bounded linear regularity, the strong conical hull intersection property (strong CHIP), and the conical hull intersection property (CHIP) are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. It was shown recently that these properties are fundamental in several branches of convex optimization, including convex feasibility problems, error bounds, Fenchel duality, and constrained approximation. It was known that regularity implies strong CHIP, which in turn implies CHIP; moreover, the three properties always hold for subspaces. The question whether or not converse implications are true for general convex sets was open. We show that – even for convex cones – the converse implications need not hold by constructing counter-examples in R4\mathbb{R}^4.

Author information

Contact details are reproduced from the original publication and may be historical.

Heinz H. Bauschke

Dept. of Mathematics and Statistics, Okanagan University College, Kelowna BC, V1V 1V7, Canada

Jonathan M. Borwein

Centre for Experimental and Constructive Mathematics, Dept. of Mathematics, Simon Fraser University, Burnaby BC, V5A 1S6, Canada

Paul Tseng

Dept. of Mathematics, University of Washington, Seattle, WA 98195-4350, U.S.A.

Keywords

  • Bounded linear regularity
  • linear regularity
  • normal cone
  • property CHIP
  • property strong CHIP
  • tangent cone

Mathematics Subject Classification

90C25; 46C05, 52A15, 52A20

References

  1. A. G. Bakan: Normal pairs of cones in finite-dimensional spaces (Russian), In: Some problems in the theory of the approximation of functions, and their applications (Russian), Akad. Nauk Ukrain. SSR, Inst. Mat., Kiev (1988) 3–11.Google Scholar
  2. A. G. Bakan: Nonemptiness of classes of normal pairs of cones of transfinite order (Russian), Ukrain. Mat. Zh. 41(4) (1989) 531–536, 576; translation in: Ukrainian Mathematical Journal 41(4) (1989) 462-466.https://doi.org/10.1007/BF01060626Google Scholar
  3. A. G. Bakan: The Moreau-Rockafellar equality for sublinear functionals (Russian), Ukrain. Mat. Zh. 41(8) (1989) 1011–1022, 1149; translation in Ukrainian Mathematical Journal 41(8) (1990) 861–871.https://doi.org/10.1007/BF01058299Google Scholar
  4. A. G. Bakan, F. Deutsch, W. Li: CHIP, strong CHIP, and linear regularity of convex sets and their conifications, forthcoming.Google Scholar
  5. H. H. Bauschke, J. M. Borwein: On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Analysis 1(2) (1993) 185–212.https://doi.org/10.1007/BF01027691Google Scholar
  6. H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38(3) (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  7. H. H. Bauschke, J. M. Borwein: Conical open mapping theorems and regularity; in: J. Giles, B. Ninness (eds.) Functional Analysis, Optimization and Applications, Proceedings of the Centre for Mathematics and its Applications 36, Australian National University (1999) 1–10; Proceedings of the National Symposium on Functional Analysis, Optimization and Applications, March 1998.Google Scholar
  8. H. H. Bauschke, J. M. Borwein, A. S. Lewis: The method of cyclic projections for closed convex sets in Hilbert space; in: Y. Censor, S. Reich (eds.), Optimization and Nonlinear Analysis, American Mathematical Society, Contemporary Mathematics 204 (1997) 1–38; Proceedings on the Special Session on Optimization and Nonlinear Analysis, Jerusalem, May 1995.https://doi.org/10.1090/conm/204/02620Google Scholar
  9. H. H. Bauschke, J. M. Borwein, W. Li: Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization, Mathematical Programming 86(1) (1999) 135–160.https://doi.org/10.1007/s101070050083Google Scholar
  10. C. K. Chui, F. Deutsch, J. D. Ward: Constrained best approximation in Hilbert space II, Journal of Approximation Theory 71(2) (1992) 213–238.https://doi.org/10.1016/0021-9045(92)90117-7Google Scholar
  11. F. Deutsch: The angle between subspaces of a Hilbert space; in: S. P. Singh (ed.), Approximation Theory, Wavelets and Applications, Kluwer Academic Publishers (1995) 107–130.https://doi.org/10.1007/978-94-015-8577-4_7Google Scholar
  12. F. Deutsch: The role of the strong conical hull intersection property in convex optimization and approximation; in: C. K. Chui, L. L. Schumaker (eds.), Approximation Theory IX, 1998.Google Scholar
  13. F. Deutsch, W. Li, J. Swetits: Fenchel duality and the strong conical hull intersection property, Journal of Optimization Theory and Applications 102(3) (1999) 681–695.https://doi.org/10.1023/A:1022658308898Google Scholar
  14. F. Deutsch, W. Li, 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. Optim. 10(1) (1999) 252–268.https://doi.org/10.1137/S1052623498337273Google Scholar
  15. F. Deutsch, W. Li, J. D. Ward: A dual approach to constrained interpolation from a convex subset of Hilbert space, Journal of Approximation Theory 90 (1997) 385–414.https://doi.org/10.1006/jath.1996.3082Google Scholar
  16. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, Grundlehren der mathematischen Wissenschaften 305, Springer-Verlag, 1993.https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  17. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms II, Grundlehren der mathematischen Wissenschaften 306, Springer-Verlag, 1993.https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  18. A. D. Ioffe: Codirectional compactness, metric regularity and subdifferential calculus, preprint.Google Scholar
  19. G. J. O. Jameson: The duality of pairs of wedges, Proceedings of the London Mathematical Society 24(3) (1972) 531–547.https://doi.org/10.1112/plms/s3-24.3.531Google Scholar
  20. K. C. Kiwiel, B. Łopuch: Surrogate projection methods for finding fixed points of firmly nonexpansive mappings, SIAM Journal on Optimization 7(4) (1997) 1084–1102.https://doi.org/10.1137/S1052623495279569Google Scholar
  21. A. S. Lewis: Convex analysis on the Hermitian matrices, SIAM Journal on Optimization 6(1) (1996) 164–177.https://doi.org/10.1137/0806009Google Scholar
  22. A. S. Lewis, J.-S. Pang: Error bounds for convex inequality systems; in: J.-P. Crouzeix (ed.), Generalized Convexity Proceedings of the Fifth Symposium on Generalized Convexity, Luminy-Marseille (1997) 75–110.https://doi.org/10.1007/978-1-4613-3341-8_3Google Scholar
  23. J.-S. Pang: Error bounds in mathematical programming, Mathematical Programming 79 (1997) 299–332.https://doi.org/10.1016/S0025-5610(97)00042-7Google Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, NJ, 1970.Google Scholar

Suggested citation

H. H. Bauschke, J. M. Borwein, P. Tseng. “Bounded Linear Regularity, Strong CHIP, and CHIP are Distinct Properties.” Journal of Convex Analysis 7 (2000), No. 2, 395–412. https://doi.org/10.68381/jca07020

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2000. Rights now held by Banach Press.