×
de Pierro, A. R.; Iusem, A. N.

A relaxed version of Bregman’s method for convex programming. (English) Zbl 0581.90069

J. Optimization Theory Appl. 51, 421-440 (1986).
A new type of relaxation for Bregman’s method, an iterative primal-dual algorithm for linearly constrained convex programming, is presented. It is shown that the new relaxation procedure generalizes the usual concept of relaxation and preserves the convergence properties of Bregman’s algorithm for a suitable choice of the relaxation parameters. For convergence, Bregman’s method requires that the objective function satisfy certain conditions. A sufficient and easily checkable condition for these requirements to hold is also given.

Cited in 41 Documents

MSC:

90C25 Convex programming
90C55 Methods of successive quadratic programming type
65K05 Numerical mathematical programming methods

Keywords:

relaxation; Bregman’s method; iterative primal-dual algorithm; linearly constrained convex programming; entropy optimization; large and sparse matrices; nonorthogonal projections
Cite Review PDF
Full Text: DOI

References:

[1] Lamond, B., andStewart, N. F.,Bregman’s Balancing Method, Transportation Research, Vol. 15B, pp. 239-248, 1981.
[2] Herman, G. T., andLent, A.,A Family of Iterative Quadratic Optimization Algorithms for Pairs of Inequalities, with Application in Diagnostic Radiology, Mathematical Programming Study, Vol. 9, pp. 15-29, 1978. · Zbl 0389.90078
[3] Herman, G. T., andLent, A.,Iterative Reconstruction Algorithms, Computers in Biology and Medicine, Vol. 6, pp. 273-294, 1976. · doi:10.1016/0010-4825(76)90066-4
[4] Censor, Y.,Row-Action Methods for Huge and Sparse Systems and Their Applications, SIAM Review, Vol. 23, pp. 444-464, 1981. · Zbl 0469.65037 · doi:10.1137/1023097
[5] Bregman, L. M.,The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming, USSR Computational Mathematics and Mathematical Physics, Vol. 7, pp. 200-217, 1967. · Zbl 0186.23807 · doi:10.1016/0041-5553(67)90040-7
[6] Censor, Y., andLent, A.,An Iterative Row-Action Method for Interval Convex Programming, Journal of Optimization Theory and Applications, Vol. 34, pp. 321-353, 1981. · Zbl 0431.49042 · doi:10.1007/BF00934676
[7] Herman, G. T., Lent, A., andLutz, P. H.,Relaxation Methods for Image Reconstruction, Communications of the Association for Computing Machinery, Vol. 21, pp. 152-158, 1978. · Zbl 0367.68065
[8] Lent, A., andCensor, Y.,Extensions of Hildreth’s Row-Action Method for Quadratic Programming, SIAM Journal on Control and Optimization, Vol. 18, pp. 444-454, 1980. · Zbl 0444.49025 · doi:10.1137/0318033
[9] Ortega, J. M., andRheinboldt, W. S.,Iterative Solutions of Nonlinear equations in Several Variables, Academic Press, New York, New York, 1970. · Zbl 0241.65046
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.