×
Han, Congying; Wang, Yongli; He, Guoping

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem. (English) Zbl 1162.90559

Appl. Math. Comput. 211, No. 2, 434-441 (2009).
Summary: As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.

Cited in 5 Documents

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation

Keywords:

parallel algorithm; constrained convex optimization; nonlinear programming; large-scale minimization
Cite Review PDF
Full Text: DOI

References:

[1] Flecher, R., Practical Methods of Optimization (1987), John Wiley and Sons: John Wiley and Sons Chichester/New York/Brisbane/Toronto/Singapore · Zbl 0905.65002
[2] Gill, Ph. E.; Murray, W.; Wright, M. H., Practical Optimization (1982), Academic Press: Academic Press New York
[3] Friendlander, A.; Martínez, J. M.; Santos, S. A., On the resolution of linearly constrained convex minimization problems, SIAM J. Optim., 4, 2, 331-339 (1994) · Zbl 0820.90084
[4] Kanzow, C., An unconstrained optimization technique for large-scale linearly constrained minimization problems, Computing, 53, 101-117 (1994) · Zbl 0820.90099
[5] Ferris, M. C.; Mangasarian, O. L., Parallel variable distribution, SIAM J. Optim., 4, 4, 815-832 (1994) · Zbl 0820.90098
[6] Solodov, M. V., New inexact parallel variable distribution algorithms, Comput. Optim. Appl., 7, 165-182 (1997) · Zbl 0884.90138
[7] Solodov, M. V., On the convergence of constrained parallel variable distribution algorithms, SIAM J. Optim., 8, 187-196 (1998) · Zbl 0914.90242
[8] Sagastizábal, C. A.; Solodov, M. V., Parallel variable distribution for constrained optimization, Comput. Optim. Appl., 22, 111-131 (2002) · Zbl 1007.90063
[9] Fukushima, M., Parallel variable transformation in unconstrained optimization, SIAM J. Optim., 8, 4, 658-672 (1998) · Zbl 0913.90243
[10] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284 (1992) · Zbl 0814.65063
[11] Ortega, J. M., Numerical Analysis (1972), Academic Press · Zbl 0248.65001
[12] Yamakawa, E.; Fukushima, M., Testing parallel variable transformation, Comput. Optim. Appl., 13, 1-22 (1999)
[13] Pang, L. P.; Xia, Z. Q., A PVT-TYPE algorithm for minimization a nonsmooth convex function, Serdica Math. J., 29, 11-32 (2003) · Zbl 1036.65054
[14] S.P. Han, Optimization by updated conjugate subspaces, in: D.F. Griffiths, G.A. Watson (Eds.), Numerical Analysis: Pitman Research Notes Mathematics Series, vol. 140, Longman Scientific and Technical, Burnt Mill, England, 1986, pp. 82-97.; S.P. Han, Optimization by updated conjugate subspaces, in: D.F. Griffiths, G.A. Watson (Eds.), Numerical Analysis: Pitman Research Notes Mathematics Series, vol. 140, Longman Scientific and Technical, Burnt Mill, England, 1986, pp. 82-97. · Zbl 0642.65049
[15] Han, S. P.; Lou, G., A parallel algorithm for a class of convex programs, SIAM J. Control Optim., 26, 346-355 (1988) · Zbl 0644.90068
[16] Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey · Zbl 0743.65107
[17] Liu, C. S.; Tseng, C. H., Parallel synchronous and asynchronous space-decomposition algorithms for large-scale minimization, Comput. Optim. Appl., 17, 85-107 (2000) · Zbl 0997.90047
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.