×

Block-iterative surrogate projection methods for convex feasibility problems. (English) Zbl 0821.65037

The author gives projection methods for solving the set intersection problem (SIP): find, if possible, any point in \(\bigcap^ m_{i=1} C_ i\), and the convex feasibility problem (CFP): find, if possible, any point \(x\), such that \(f_ i(x) \leq 0\), \(i = 1, \dots, m\), where each \(C_ i\) is a closed convex subset of \(\mathbb{R}^ n\) and each function \(f_ i \in \mathbb{R}^ n \to \mathbb{R}\) is convex.
In this paper it is shown that many algorithms for SIP or CFP fit a geometric framework. In this geometric framework, algorithms for CFP are treated as methods for SIP that approximate the sets \(C_ i\) via half spaces. In section 2 of the paper an abstract method is described that employs approximating half spaces under general conditions which simplify its convergence analysis. In the further section examples of surrogate cuts, a surrogate projection method and block-iterative methods are discussed.

MSC:

65K05 Numerical mathematical programming methods
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharoni, R.; Berman, A.; Censor, Y., An interior points algorithm for the convex feasibility problem, Adv. in Appl. Math., 4, 479-489 (1983) · Zbl 0489.52005
[2] Agmon, S., The relaxation method for linear inequalities, Canad, J. Math., 6, 382-392 (1954) · Zbl 0055.35001
[3] Ahroni, R.; Censor, Y., Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, Linear Algebra Appl., 120, 165-175 (1989) · Zbl 0679.65046
[4] Ansorge, R., Connections between the Cimmino method and the Kaczmarz method for the solution of singular and regular systems of equations, Computing, 33, 367-375 (1984) · Zbl 0537.65027
[5] Auslender, A., Optimisation, Methodes Numériques (1976), Masson: Masson Paris · Zbl 0326.90057
[6] Bland, R. B.; Goldfarb, D.; Todd, M. J., The ellipsoid method: A survey, Oper. Res., 29, 1039-1091 (1981) · Zbl 0474.90056
[7] Butnariu, D.; Censor, Y., On the behaviour of a block-iterative projection method for solving convex feasibility problems, Internat. J. Comput. Math., 34, 79-94 (1990) · Zbl 0708.90064
[8] Bulavskii, V. A., On one type of projection methods in mathematical programming, Optimizatsiya, 5, 11-22 (1972), (in Russian) · Zbl 0256.90044
[9] Bulavskii, V. A., On finite-dimensional approximation in some convex problems, Optimizatsiya, 9, 181-187 (1973), (in Russian) · Zbl 0306.90060
[10] Censor, Y.; Elfving, T., New methods for linear inequalities, Linear Algebra Appl., 42, 199-211 (1982) · Zbl 0479.65039
[11] Censor, Y.; Lent, A., Cyclic subgradient projections, Math. Programming, 24, 233-235 (1982) · Zbl 0491.90077
[12] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 4, 444-466 (1981) · Zbl 0469.65037
[13] Censor, Y., An automatic relaxation method for solving interval linear inequalities, J. Math. Anal. Appl., 106, 19-25 (1985) · Zbl 0568.65022
[14] Censor, Y., Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Programming, 42, 307-325 (1988) · Zbl 0658.90099
[15] Cimmino, G., Calcolo approsimato per le soluzioni dei sistemi di equazioni lineari, Ric. Sci. XVI, 1, 326-333 (1938) · JFM 64.1244.02
[16] De Pierro, A. R.; Iusem, A. N., A parallel projection method for finding common points of a family of convex sets, Pesquisa Oper., 5, 1, 1-20 (1985)
[17] De Pierro, A. R.; Iusem, A. N., A simultaneous projections method for linear inequalities, Linear Algebra Appl., 64, 243-253 (1985) · Zbl 0552.65051
[18] Drezner, Z., The nested ball principle for the relaxation method, Oper. Res., 31, 587-590 (1983) · Zbl 0516.90047
[19] dos Santos, L. T., A parallel subgradient projections method for the convex feasibility problem, J. Comput. Appl. Math., 18, 307-320 (1987) · Zbl 0623.90076
[20] Eaves, B. C.; Zangwill, W. I., Generalized cutting plane algorithms, SIAM J. Control, 9, 529-542 (1971)
[21] Eremin, I. I., A generalization of the Motzkin-Agmon relaxation method, Uspekhi Mat. Nauk, 20, 2, 183-187 (1965), (in Russian) · Zbl 0254.65049
[22] Soviet Math. Dokl., 6, 219-222 (1965) · Zbl 0144.30601
[23] Eremin, I. I.; Mazurov, V. D., Nonstationary Processess of Mathematical Programming (1979), Nauka: Nauka Moscow, (in Russian) · Zbl 0447.90051
[24] Fletcher, R., Practical Methods of Optimization (1987), Wiley: Wiley Chichester · Zbl 0905.65002
[25] Flȧm, S. D.; Zowe, J., Relaxed outer projections, weighted averages and convex feasibility, BIT, 30, 289-300 (1990) · Zbl 0715.65038
[26] Goffin, J.-L., Nondifferentiable optimization and the relaxation method, (Lemaréchal, C.; Mifflin, R., Nonsmooth Optimization (1978), Pergamon: Pergamon Oxford), 31-49 · Zbl 0404.90072
[27] Goffin, J.-L., The relaxation method for solving systems of linear inequalities, Math. Oper. Res., 5, 3, 388-414 (1980) · Zbl 0442.90051
[28] Goffin, J.-L., Convergence results in a class of variable metric subgradient methods, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear Programming 4 (1981), Academic: Academic New York), 283-326 · Zbl 0545.65045
[29] Goldfarb, D.; Idnani, A., A numerically stable dual method for solving strictly convex quadratic programs, Math. Programming, 27, 1-33 (1983) · Zbl 0537.90081
[30] Goldfarb, D.; Todd, M. J., Modifications and implementation of the ellipsoid algorithm for linear programming, Math. Programming, 23, 1-19 (1982) · Zbl 0477.90038
[31] García-Palomares, U., A class of methods for solving large convex systems, Oper. Res. Lett., 9, 181-187 (1990) · Zbl 0784.65058
[32] García-Palomares, U., Parallel projected aggregation methods for solving convex (and linear) systems, (Reporte Tecnico 199110611 (1991), Departmento de Procesos y Sistemas, Univ. Simón Bolivar: Departmento de Procesos y Sistemas, Univ. Simón Bolivar Caracas) · Zbl 0791.90042
[33] U.S.S.R. Comput. Math. and Math. Phys., 7, 1-24 (1967) · Zbl 0199.51002
[34] Iusem, A. N.; De Pierro, A. R., Convergence results for an accelerated nonlinear Cimmino algorithm, Numer. Math., 49, 367-378 (1986) · Zbl 0571.65051
[35] Iusem, A. N., On the convergence of Han’s method for convex programming with quadratic objective, Math. Programming, 52, 265-284 (1991) · Zbl 0744.90066
[36] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Polon. Sci. Lett. A, 35, 355-357 (1937) · Zbl 0017.31703
[37] Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization, (Lecture Notes in Math. 1133 (1985), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0602.90122
[38] Lobyrev, A. I., The method of successive projection along an auxiliary variety, Optimizatsiya, 5, 121-127 (1972), (in Russian)
[39] Mandel, J., Convergence of the cyclical relaxation method for linear inequalities, Math. Programming, 30, 218-228 (1984) · Zbl 0545.90068
[40] Marti, J. T., On the convergence of the discrete ART algorithm for the reconstruction of digital pictures from their projections, Computing, 21, 105-111 (1979) · Zbl 0394.68031
[41] U.S.S.R. Comput Math. and Math. Phys., 2, 504-510 (1962) · Zbl 0123.11204
[42] Motzkin, T.; Schoenberg, I. J., The relaxation method for linear inequalities, Canad. J. Math., 6, 393-404 (1954) · Zbl 0055.35002
[43] Oettli, W., Symmetric duality, and a convergent subgradient method for discrete, linear, constrained approximation problems with arbitrary norms appearing in the objective function and in the constraints, Approx. Theory Appl., 14, 43-50 (1975) · Zbl 0297.41015
[44] Oko, S. O., Surrogate methods for linear inequalities, J. Optim. Theory Appl., 72, 247-268 (1992) · Zbl 0794.90035
[45] Ottavy, N., Strong convergence of projection-like methods in Hilbert spaces, J. Optim Theory Appl., 56, 433-461 (1988) · Zbl 0621.49019
[46] Pierra, G., Decomposition through formalization in a product space, Math. Programming, 28, 96-115 (1984) · Zbl 0523.49022
[47] Plotnikov, S. V., Cyclic projection on a system of convex sets with empty intersection, (Improper Optimization Problems (1982), Acad. Nauk SSSR, Ural. Nauchn: Acad. Nauk SSSR, Ural. Nauchn Tstentr, Sverdlovsk), 60-66, Abstract, MR 85g:90094
[48] U.S.S.R. Comput. Math. and Math. Phys., 9, 14-29 (1969) · Zbl 0229.65056
[49] Paik, E. V., Methods of Fejér type in Hilbert space, Izv. Akad. Nauk EstSSR Ser. Mat.-Fiz., 6, 3, 286-293 (1967), (in Russian)
[50] Rockafellar, R. T., Convex Analysis (1970), Princeton U.P: Princeton U.P Princeton, N.J · Zbl 0229.90020
[51] Spingarn, J. E., A projection method for least-squares solutions to overdetermined systems of linear inequalities, Linear Algebra Appl., 86, 211-236 (1987) · Zbl 0616.65064
[52] Sukharev, A. G.; Timokhov, A. V.; Fedorov, V. V., A Course on Optimization Methods (1986), Nauka: Nauka Moscow, (in Russian) · Zbl 0602.90091
[53] Telgen, J., On relaxation methods for systems of linear inequalities, European J. Oper. Res., 9, 184-189 (1982) · Zbl 0476.65041
[54] Todd, M. J., Some remarks on the relaxation method for Linear Inequalities, (Tech. Report 419 (1979), Cornell Univ: Cornell Univ Ithaca, N.Y)
[55] Trumer, M. R., Reconstructing pictures from projections: On the convergence of the ART algorithm with relaxation, Computing, 26, 189-195 (1981) · Zbl 0444.68079
[56] Yang, K.; Murty, K. G., New iterative methods for linear inequalities, J. Optim. Theory Appl., 72, 163-185 (1992) · Zbl 0793.90035
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.