Strong CHIP, normality, and linear regularity of convex sets

Bakan, Andrew; Deutsch, Frank; Li, Wu

doi:10.1090/S0002-9947-05-03945-0

Strong CHIP, normality, and linear regularity of convex sets
HTML articles powered by AMS MathViewer

by Andrew Bakan, Frank Deutsch and Wu Li PDF

Trans. Amer. Math. Soc. 357 (2005), 3831-3863 Request permission

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

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
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, DOI 10.1007/BF01058299
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, DOI 10.1007/BF01060626
H. H. Bauschke, Projection Algorithms and Monotone Operators, Ph.D. thesis, Simon Fraser University, 1996.
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, DOI 10.1007/BF01027691
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, DOI 10.1137/S0036144593251710
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.
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, DOI 10.1090/conm/204/02620
Heinz H. Bauschke, Jonathan M. Borwein, and Wu Li, Strong conical hull intersection property, bounded linear regularity, Jameson’s property $(G)$, and error bounds in convex optimization, Math. Program. 86 (1999), no. 1, Ser. A, 135–160. MR 1712477, DOI 10.1007/s101070050083
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
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, DOI 10.1007/BF01891408
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, DOI 10.1016/0021-9045(92)90117-7
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
Sien Deng, Global error bounds for convex inequality systems in Banach spaces, SIAM J. Control Optim. 36 (1998), no. 4, 1240–1249. MR 1618049, DOI 10.1137/S0363012995293645
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
Frank Deutsch, Best approximation in inner product spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 7, Springer-Verlag, New York, 2001. MR 1823556, DOI 10.1007/978-1-4684-9298-9
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, DOI 10.1023/A:1022658308898
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, DOI 10.1006/jath.1996.3082
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. MR 1742319, DOI 10.1137/S1052623498337273
Joseph Diestel, Geometry of Banach spaces—selected topics, Lecture Notes in Mathematics, Vol. 485, Springer-Verlag, Berlin-New York, 1975. MR 0461094
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, DOI 10.1112/jlms/s2-29.3.545
J.-B. Hiriart-Urruty and C. Lemarechal, Convex analysis and minimization algorithms I, Springer-Verlag, N.Y., 1993.
Alan J. Hoffman, On approximate solutions of systems of linear inequalities, J. Research Nat. Bur. Standards 49 (1952), 263–265. MR 0051275
A. Ioffe and V. Tikhomirov, Theory of Extremal Problems, Nauka, Moscow, 1974 (in Russian) [English translation by North Holland, Amsterdam, 1979].
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, DOI 10.1007/s10107980002a
G. J. O. Jameson, The duality of pairs of wedges, Proc. London Math. Soc. (3) 24 (1972), 531–547. MR 298388, DOI 10.1112/plms/s3-24.3.531
A. G. Kusraev, Vektornaya dvoĭstvennost′i ee prilozheniya, “Nauka” Sibirsk. Otdel., Novosibirsk, 1985 (Russian). MR 836135
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, DOI 10.1007/978-94-011-0265-0
Pierre-Jean Laurent, Approximation et optimisation, Collection Enseignement des Sciences, No. 13, Hermann, Paris, 1972 (French). MR 0467080
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, DOI 10.1007/978-1-4613-3341-8_{3}
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, DOI 10.1137/S1052623495287927
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. MR 1785387, DOI 10.1137/S1052623499355247
Wu Li and Ivan Singer, Global error bounds for convex multifunctions and applications, Math. Oper. Res. 23 (1998), no. 2, 443–462. MR 1626694, DOI 10.1287/moor.23.2.443
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
Helmut H. Schaefer, Topological vector spaces, The Macmillan Company, New York; Collier Macmillan Ltd., London, 1966. MR 0193469