×

Reflection-projection method for convex feasibility problems with an obtuse cone. (English) Zbl 1136.90432

Summary: The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in the mathematical and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections.
In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive-semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies the method of cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection.
This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative [resp. positive semidefinite] solution to linear constraints in \(\mathbb R^n\) [resp. in \(\mathbb S^n\), the space of symmetric \(n\times n\) matrices] and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well.

MSC:

90C25 Convex programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauschke, H. H., Projection Algorithms and Monotone Operators, PhD Thesis, Simon Fraser University, 1996. Available at www.cecm.sfu.ca/preprints/1996pp.html as 96:080.
[2] Bauschke, H. H., and Borwein, J. M., On Projection Algorithms for Solving Convex Feasibility Problems, SIAM Review, 38, 367-426, 1996. · Zbl 0865.47039 · doi:10.1137/S0036144593251710
[3] Censor, Y., and Zenios, S. A., Parallel Optimization, Oxford University Press, Oxford, UK, 1997. · Zbl 0945.90064
[4] Combettes, P. L., Hilbertian Convex Feasibility Problem: Convergence of Projection Methods, Applied Mathematics and Optimization, 35, 311-330, 1997. · Zbl 0872.90069 · doi:10.1007/BF02683333
[5] Crombez, G., Parallel Algorithms for Finding Common Fixed Points of Paracontractions, Numerical Functional Analysis and Optimization, 23, 47-59, 2002. · Zbl 1004.65068 · doi:10.1081/NFA-120003670
[6] Kiwiel, K. C., and Łopuch, B., Surrogate Projection Methods for Finding Fixed Points of Firmly Nonexpansive Mappings, SIAM Journal of Optimization, 7, 1084-1102, 1997. · Zbl 0905.47044 · doi:10.1137/S1052623495279569
[7] Motzkin, T. S., and Schoenberg, I. J., The Relaxation Method for Linear Inequalities, Canadian Journal of Mathematics, 6, 393-404, 1954. · Zbl 0055.35002 · doi:10.4153/CJM-1954-038-x
[8] Cimmino, G., Calcolo Approssimato per le Soluzioni dei Sistemi di Equazioni Lineari, La Ricerca Scientifica ed il Progresso Tecnico nella Economia Nazionale (Roma), 1, 326-333, 1938.
[9] Goebel, K., and Kirk, W. A., Topics in Metric Fixed-Point Theory, Cambridge University Press, Cambridge, UK, 1990. · Zbl 0708.47031
[10] Zarantonello, E. H., Projections on Convex Sets in Hilbert Space and Spectral Theory, Contributions to Nonlinear Functional Analysis, E. H. Zarantonello, Academic Press, New York, NY, 237-424, 1971.
[11] Moreau, J. J., Décomposition Orthogonale d’un Espace Hilbertien selon Deux Cônes Mutuellement Polaires, Comptes Rendus des Séances de l’Académie des Sciences, Paris, Séries A-B, 255, 238-240, 1962. · Zbl 0109.08105
[12] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[13] Goffin, J. L., The Relaxation Method for Solving Systems of Linear Inequalities, Mathematics of Operations Research, 5, 388-414, 1980. · Zbl 0442.90051 · doi:10.1287/moor.5.3.388
[14] Todd, M. J., Some Remarks on the Relaxation Method for Linear Inequalities, Technical Report 419, School of Operations Research and Industrial Engineering, Cornell University, 1979.
[15] Cegielski, A., Projection onto an Acute Cone and Convex Feasibility Problem, System Modelling and Optimization (Compiègne, 1993); Lecture Notes in Control and Information Sciences, J. Henry and J. P. Yvon, Springer Verlag, London, UK, 197, 187-194, 1994. · Zbl 0816.90108
[16] Cegielski, A., A Method of Projection onto an Acute Cone with Level Control in Convex Minimization, Mathematical Programming, 85, 469-490, 1999. · Zbl 0973.90057 · doi:10.1007/s101070050068
[17] Cegielski, A., Obtuse Cones and Gram Matrices with Nonnegative Inverse, Linear Algebra and Its Applications, 335, 167-181, 2001. · Zbl 0982.15028 · doi:10.1016/S0024-3795(01)00284-1
[18] Cegielski, A., and Dylewski, R., Residual Selection in a Projection Method for Convex Minimization Problems, Optimization, 52, 211-220, 2003. · Zbl 1057.49021 · doi:10.1080/0233193031000079883
[19] Kiwiel, K. C., The Efficiency of Subgradient Projection Methods for Convex Optimization, Part 2: Implementations and Extensions, SIAM Journal on Control and Optimization, 34, 677-697, 1996. · Zbl 0846.90085 · doi:10.1137/S0363012994261483
[20] Kiwiel, K. C., Monotone Gram Matrices and Deepest Surrogate Inequalities in Accelerated Relaxation Methods for Convex Feasibility Problems, Linear Algebra and Its Applications, 252, 27-33, 1997. · Zbl 0870.65046 · doi:10.1016/0024-3795(95)00608-7
[21] Güler, O., Barrier Functions in Interior-Point Methods, Mathematics of Operations Research, 21, 860-885, 1996. · Zbl 0867.90090 · doi:10.1287/moor.21.4.860
[22] Nesterov, Y. E., and Todd, M. J., Self-Scaled Barriers and Interior-Point Methods for Convex Programming, Mathematics of Operations Research, 22, 1-42, 1997. · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[23] Lobo, M. S., Vandenberghe, L., Boyd, S., and Lebret, H., Applications of Second-Order Cone Programming, Linear Algebra and Its Applications, 284, 193-228, 1998. · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[24] Bruck, R. E., and Reich, S. Nonexpansive Projections and Resolvents of Accretive Operators in Banach Spaces, Houston Journal of Mathematics, 3, 459-470, 1977. · Zbl 0383.47035
[25] De Pierro, A. R., and Iusem, A. N., On the Asymptotic Behavior of Some Alternate Smoothing Series Expansion Iterative Methods, Linear Algebra and Its Applications, 130, 3-24, 1990. · Zbl 0718.65093 · doi:10.1016/0024-3795(90)90203-O
[26] Bauschke, H. H., Projection Algorithms: Results and Open Problems, Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications (Haifa, 2000); D. Butnariu, Y. Censor, and S. Reich, Elsevier, Amsterdam, Holland, 11-22, 2001.
[27] Combettes, P. L., Quasi-Fejérian Analysis of Some Optimization Algorithms, Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications (Haifa, 2000); D. Butnariu, Y. Censor, and S. Reich, Elsevier, Amsterdam, Holland, 115-152, 2001.
[28] Groetsch, C. W., Generalized Inverses of Linear Operators: Representation and Approximation, Dekker, New York, NY, 1977. · Zbl 0358.47001
[29] Deutsch, F., Best Approximation in Inner Product Spaces, Springer, New York, NY, 2001. · Zbl 0980.41025
[30] Golub, G. H., and Van Loan, C. F., Matrix Computations, Johns Hopkins University Press, Baltimore, Maryland, 1996. · Zbl 0865.65009
[31] Kruk, S., Implementation of the Algorithms Discussed in This Manuscript, www.oakland.edu/\(\sim\)kruk/research/ProjRefl.
[32] Horn, R. A., and Johnson, C. R., Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985. · Zbl 0576.15001
[33] Borwein, J. M., and Lewis, A. S., Convex Analysis and Nonlinear Optimization, Springer, New York, NY, 2000. · Zbl 0953.90001
[34] Wolkowicz, H., Saigal, R., and Vandenberghe, L., Editors, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, International Series in Operations Research and Management Science, Kluwer, Norwell, Massachusetts, 27, 2000. · Zbl 0951.90001
[35] Vandenberghe, L., and Boyd, S., Semidefinite Programming, SIAM Review, 38, 49-95, 1996. · Zbl 0845.65023 · doi:10.1137/1038003
[36] Parlett, B. N., The Symmetric Eigenvalue Problem, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1998 (Corrected Reprint of the 1980 Original). · Zbl 0885.65039
[37] Stewart, G. W., Matrix Algorithms, 2: Eigensystems, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 2001. · Zbl 0984.65031
[38] Bauschke, H. H., Borwein, J. M., and Lewis, A. S., The Method of Cyclic Projections for Closed Convex Sets in Hilbert Space, Recent Developments in Optimization Theory and Nonlinear Analysis (Jerusalem, 1995); Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 204, 1-38, 1997.
[39] Cheney, W., and Goldstein, A. A., Proximity Maps for Convex Sets, Proceedings of the American Mathematical Society, 10, 448-450, 1959. · Zbl 0092.11403 · doi:10.1090/S0002-9939-1959-0105008-8
[40] Bauschke, H. H., and Borwein, J. M., Dykstra’s Alternating Projection Algorithm for Two Sets, Journal of Approximation Theory, 79, 418-443, 1994. · Zbl 0833.46011 · doi:10.1006/jath.1994.1136
[41] de Klerk, E., Roos, C., and Terlaky, T., Infeasible-Start Semidefinite Programming Algorithms via Self-Dual Embeddings, Topics in Semidefinite and Interior-Point Methods (Toronto, 1996); P. M. Pardalos and H. Wolkowicz, American Mathematical Society, Providence, Rhode Island, 215-236, 1998. · Zbl 0905.90155
[42] Luo, Z. Q., Sturm, J. F., and Zhang, S., Conic Convex Programming and Self-Dual Embedding, Optimization Methods and Software, 14, 169-218, 2000. · Zbl 1072.90559 · doi:10.1080/10556780008805800
[43] Strang, G., Linear Algebra and Its Applications, Academic Press, New York, NY, 1976. · Zbl 0338.15001
[44] Kruk, S., High-Accuracy Algorithms for the Solutions of Linear Programs, University of Waterloo, PhD Thesis, 2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.