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 Free Access

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 is bounded away from 0 uniformly over all points in the intersection of these convex sets.

**1.**A. G. Bakan,*Normal pairs of cones in finite-dimensional spaces*, Some problems in the theory of the approximation of functions, and their applications (Russian), Akad. Nauk Ukrain. SSR, Inst. Mat., Kiev, 1988, pp. 3–11, i (Russian). MR**986499****2.**A. G. Bakan,*The Moreau-Rockafellar equality for sublinear functionals*, Ukrain. Mat. Zh.**41**(1989), no. 8, 1011–1022, 1149 (Russian); English transl., Ukrainian Math. J.**41**(1989), no. 8, 861–871 (1990). MR**1019523**, 10.1007/BF01058299**3.**A. G. Bakan,*Nonemptiness of classes of normal pairs of cones of transfinite order*, Ukrain. Mat. Zh.**41**(1989), no. 4, 531–536, 576 (Russian); English transl., Ukrainian Math. J.**41**(1989), no. 4, 462–466. MR**1004860**, 10.1007/BF01060626**4.**H. H. Bauschke,*Projection Algorithms and Monotone Operators,*Ph.D. thesis, Simon Fraser University, 1996.**5.**H. H. Bauschke and J. M. Borwein,*On the convergence of von Neumann’s alternating projection algorithm for two sets*, Set-Valued Anal.**1**(1993), no. 2, 185–212. MR**1239403**, 10.1007/BF01027691**6.**Heinz H. Bauschke and Jonathan M. Borwein,*On projection algorithms for solving convex feasibility problems*, SIAM Rev.**38**(1996), no. 3, 367–426. MR**1409591**, 10.1137/S0036144593251710**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.**Heinz H. Bauschke, Jonathan M. Borwein, and Adrian S. Lewis,*The method of cyclic projections for closed convex sets in Hilbert space*, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995) Contemp. Math., vol. 204, Amer. Math. Soc., Providence, RI, 1997, pp. 1–38. MR**1442992**, 10.1090/conm/204/02620**9.**Heinz H. Bauschke, Jonathan M. Borwein, and Wu Li,*Strong conical hull intersection property, bounded linear regularity, Jameson’s property (𝐺), and error bounds in convex optimization*, Math. Program.**86**(1999), no. 1, Ser. A, 135–160. MR**1712477**, 10.1007/s101070050083**10.**Heinz H. Bauschke, Jonathan M. Borwein, and Paul Tseng,*Bounded linear regularity, strong CHIP, and CHIP are distinct properties*, J. Convex Anal.**7**(2000), no. 2, 395–412. MR**1811687****11.**Charles K. Chui, Frank Deutsch, and Joseph D. Ward,*Constrained best approximation in Hilbert space*, Constr. Approx.**6**(1990), no. 1, 35–64. MR**1027508**, 10.1007/BF01891408**12.**Charles K. Chui, Frank Deutsch, and Joseph D. Ward,*Constrained best approximation in Hilbert space. II*, J. Approx. Theory**71**(1992), no. 2, 213–238. MR**1186970**, 10.1016/0021-9045(92)90117-7**13.**Sien Deng,*Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems*, Math. Programming**83**(1998), no. 2, Ser. A, 263–276. MR**1647861****14.**Sien Deng,*Global error bounds for convex inequality systems in Banach spaces*, SIAM J. Control Optim.**36**(1998), no. 4, 1240–1249 (electronic). MR**1618049**, 10.1137/S0363012995293645**15.**Frank Deutsch,*The role of the strong conical hull intersection property in convex optimization and approximation*, Approximation theory IX, Vol. I. (Nashville, TN, 1998) Innov. Appl. Math., Vanderbilt Univ. Press, Nashville, TN, 1998, pp. 105–112. MR**1742997****16.**Frank Deutsch,*Best approximation in inner product spaces*, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 7, Springer-Verlag, New York, 2001. MR**1823556****17.**F. Deutsch, W. Li, and J. Swetits,*Fenchel duality and the strong conical hull intersection property*, J. Optim. Theory Appl.**102**(1999), no. 3, 681–695. MR**1710727**, 10.1023/A:1022658308898**18.**Frank Deutsch, Wu Li, and Joseph D. Ward,*A dual approach to constrained interpolation from a convex subset of Hilbert space*, J. Approx. Theory**90**(1997), no. 3, 385–414. MR**1469335**, 10.1006/jath.1996.3082**19.**Frank Deutsch, Wu Li, and Joseph 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**(1999), no. 1, 252–268 (electronic). MR**1742319**, 10.1137/S1052623498337273**20.**Joseph Diestel,*Geometry of Banach spaces—selected topics*, Lecture Notes in Mathematics, Vol. 485, Springer-Verlag, Berlin-New York, 1975. MR**0461094****21.**C. Franchetti and W. Light,*The alternating algorithm in uniformly convex spaces*, J. London Math. Soc. (2)**29**(1984), no. 3, 545–555. MR**754940**, 10.1112/jlms/s2-29.3.545**22.**J.-B. Hiriart-Urruty and C. Lemarechal, Convex analysis and minimization algorithms I,*Springer-Verlag*, N.Y., 1993.**23.**Alan J. Hoffman,*On approximate solutions of systems of linear inequalities*, J. Research Nat. Bur. Standards**49**(1952), 263–265. MR**0051275****24.**A. Ioffe and V. Tikhomirov, Theory of Extremal Problems,*Nauka,*Moscow, 1974 (in Russian) [English translation by North Holland, Amsterdam, 1979].**25.**Diethard Klatte and Wu Li,*Asymptotic constraint qualifications and global error bounds for convex inequalities*, Math. Program.**84**(1999), no. 1, Ser. A, 137–160. MR**1687264****26.**G. J. O. Jameson,*The duality of pairs of wedges*, Proc. London Math. Soc. (3)**24**(1972), 531–547. MR**0298388****27.**A. G. Kusraev,*Vektornaya dvoistvennost i ee prilozheniya*, “Nauka” Sibirsk. Otdel., Novosibirsk, 1985 (Russian). MR**836135****28.**A. G. Kusraev and S. S. Kutateladze,*Subdifferentials: theory and applications*, Mathematics and its Applications, vol. 323, Kluwer Academic Publishers Group, Dordrecht, 1995. Translated from the Russian. MR**1471481****29.**Pierre-Jean Laurent,*Approximation et optimisation*, Hermann, Paris, 1972 (French). Collection Enseignement des Sciences, No. 13. MR**0467080****30.**Adrian S. Lewis and Jong-Shi Pang,*Error bounds for convex inequality systems*, Generalized convexity, generalized monotonicity: recent results (Luminy, 1996) Nonconvex Optim. Appl., vol. 27, Kluwer Acad. Publ., Dordrecht, 1998, pp. 75–110. MR**1646951**, 10.1007/978-1-4613-3341-8_3**31.**Wu Li,*Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities*, SIAM J. Optim.**7**(1997), no. 4, 966–978. MR**1479609**, 10.1137/S1052623495287927**32.**Wu Li, Chandal Nahak, and Ivan Singer,*Constraint qualifications for semi-infinite systems of convex inequalities*, SIAM J. Optim.**11**(2000), no. 1, 31–52 (electronic). MR**1785387**, 10.1137/S1052623499355247**33.**Wu Li and Ivan Singer,*Global error bounds for convex multifunctions and applications*, Math. Oper. Res.**23**(1998), no. 2, 443–462. MR**1626694**, 10.1287/moor.23.2.443**34.**R. Tyrrell Rockafellar,*Convex analysis*, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR**0274683****35.**Helmut H. Schaefer,*Topological vector spaces*, The Macmillan Co., New York; Collier-Macmillan Ltd., London, 1966. MR**0193469**

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

Email:
andrew@bakan.kiev.ua

**Frank Deutsch**

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

Email:
deutsch@math.psu.edu

**Wu Li**

Affiliation:
NASA Langley Research Center, Hampton, Virginia 23681

Email:
w.li@nasa.gov

DOI:
http://dx.doi.org/10.1090/S0002-9947-05-03945-0

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