Abstract
In this paper, two PVD-type algorithms are proposed for solving inseparable linear constraint optimization. Instead of computing the residual gradient function, the new algorithm uses the reduced gradients to construct the PVD directions in parallel computation, which can greatly reduce the computation amount each iteration and is closer to practical applications for solve large-scale nonlinear programming. Moreover, based on an active set computed by the coordinate rotation at each iteration, a feasible descent direction can be easily obtained by the extended reduced gradient method. The direction is then used as the PVD direction and a new PVD algorithm is proposed for the general linearly constrained optimization. And the global convergence is also proved.
Similar content being viewed by others
References
Fischer, A. A special newton-type optimization method. Optimization, 24: 269–284 (1992)
Friendlander, A., Martínez, J.M., Santos, S.A. On the resolution of linearly constrained convex minimization problems. SIAM J. Optimization, 4(2): 331–339 (1994)
Liu, C.S., Tseng, C.H. Parallel synchronous and asynchronous space-decomposition algorithms for largescale minimization. Comput. Optim. Appl., 17: 85–107 (2000)
Sagastizábal C.A., Solodov, M.A. Parallel variable distribution for constrained optimization. Comput. Optim. Appli., 22: 111–131 (2002)
Han, C.Y., Wang, L., He, G.P. On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem. Applied Mathematics and Computation, 211: 434–441 (2009)
Bertsekas, D.P., Tsitsiklis, J.N. Parallel and Distributed Computation: Numerical Methods. Prentize-Hall: Englewood Cliffs, New Jersey, 1989
Yamakawa, E., Fukushima, M. Testing parallel variable transformation. Comput. Optim. Appl., 13: 1–22 (1999)
Ortega, J.M. Numerical Analysis. Second ed., Academic Press, 1972
Jian, J.B. An extension of reduced gradient method for linearly constrained programmings. Mathematics in Economics, 1: 70–78 (1993)
Pang, L.P., Xia, Z.Q. A PVT-type algorithm for minimization a nonsmooth convex function. Serdica Math. J., 29: 11–32 (2003)
Ferris, M.C., Mangasarian, O.L. Parallel variable distribution. SIAM J. Optimization, 4(4): 815–832 (1994)
Solodov, M.V. New inexact parallel variable distribution algorithms. Comput. Optim. Appl., 7: 165–182 (1997)
Solodov, M.V. On the convergence of constrained parallel variable distribution algorithms. SIAM J. Optimization, 8: 187–196 (1998)
Fukushima, M. Parallel variable transformation in unconstrained optimization. SIAM J. Optimization, 8(4): 658–672 (1998)
Gill, Ph. E., Murray, W., Wright, M.H. Practical Optimization. Academic Press, New York, ???nian
Flecher, R. Practical Methods of Optimization, 2nd ed., John Wiley and Sons. Chichester, New York, Brisbane, Toronto, and Singapore, 1987
Han, S.P. Optimization By Updated Conjugate Subspaces, Numerical Analysis: Pitman Research Notes Mathematics Series 140, (Eds D.F. Griffiths, G.A. Watson) Longman Scientific and Technical, Burnt Mill, England, 5, 82–97, 1985
Han, S.P., Lou, G. A parallel algorithm for a class of convex programs. SIAM J. Control Optim., 26: 346–355 (1988)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China (No. 11101420,11331012,71271204).
Rights and permissions
About this article
Cite this article
Han, Cy., Zheng, Fy., Guo, Td. et al. Parallel algorithms for large-scale linearly constrained minimization problem. Acta Math. Appl. Sin. Engl. Ser. 30, 707–720 (2014). https://doi.org/10.1007/s10255-013-0300-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-013-0300-9