×

On preconditioned and relaxed AVMM methods for quadratic programming problems with equality constraints. (English) Zbl 1352.65096

Summary: To iteratively compute a solution of the equality-constraint quadratic programming problem, by successively introducing relaxation parameters and skillfully adopting a preconditioning matrix, we establish a preconditioned and relaxed alternating variable minimization with multiplier (PRAVMM) method, which is a further generalization of the preconditioned alternating variable minimization with multiplier (PAVMM) method proposed by the authors [BIT 56, No. 2, 399–422 (2016; Zbl 1357.65071)]. Based on rigorous matrix analysis we demonstrate the asymptotic convergence property of the PRAVMM method. Numerical results show that the PRAVMM method is feasible and effective for solving the equality-constraint quadratic programming problems.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C25 Convex programming

Citations:

Zbl 1357.65071
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow, K.; Hurwicz, L.; Uzawa, H., Studies in Nonlinear Programming (1958), Stanford University Press: Stanford University Press Stanford
[2] Bai, Z.-Z.; Parlett, B. N.; Wang, Z.-Q., On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102, 1-38 (2005) · Zbl 1083.65034
[3] Bai, Z.-Z.; Tao, M., Rigorous convergence analysis of alternating variable minimization with multiplier methods for quadratic programming problems with equality constraints, BIT Numer. Math., 56, 399-422 (2016) · Zbl 1357.65071
[4] Bai, Z.-Z.; Wang, Z.-Q., On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428, 2900-2932 (2008) · Zbl 1144.65020
[5] Bergen, A. R., Power Systems Analysis (1986), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[6] Betts, J. T., Practical Methods for Optimal Control Using Nonlinear Programming (2001), SIAM: SIAM Philadelphia · Zbl 0995.49017
[7] Bossavit, A., “Mixed” systems of algebraic equations in computational electromagnetics, COMPEL, 17, 59-63 (1998)
[8] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Faund. Trends Mach. Learn., 3, 1-122 (2010) · Zbl 1229.90122
[9] Cao, Y.; Jiang, M.-Q.; Yao, L.-Q., New choices of preconditioning matrices for generalized inexact parameterized iterative methods, J. Comput. Appl. Math., 235, 263-269 (2010) · Zbl 1202.65039
[10] Chan, R. H.; Ng, M. K., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[11] Chen, F.; Jiang, Y.-L., A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput., 206, 765-771 (2008) · Zbl 1159.65034
[12] Chua, L. O.; Desoer, C. A.; Kuh, E. S., Linear and Nonlinear Circuits (1987), McGraw-Hill: McGraw-Hill New York · Zbl 0631.94017
[13] Elman, H. C.; Golub, G. H., Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31, 1645-1661 (1994) · Zbl 0815.65041
[14] Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073
[15] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034
[16] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, London · Zbl 0865.65009
[17] Hadjidimos, A.; Lapidakis, M., Optimal alternating direction implicit preconditioners for conjugate gradient methods, Appl. Math. Comput., 183, 559-574 (2006) · Zbl 1109.65088
[18] Hall, E. L., Computer Image Processing and Recognition (1979), Academic Press: Academic Press New York · Zbl 0489.68084
[19] Han, D.-R.; Yuan, X.-M., Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal., 51, 3446-3457 (2013) · Zbl 1285.90033
[20] Haber, E.; Modersitzki, J., Numerical methods for volume-preserving image registration, Inverse Probl., 20, 1621-1638 (2004) · Zbl 1065.65084
[21] He, B.-S.; Yuan, X.-M., On the \(O(1 / n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50, 700-709 (2012) · Zbl 1245.90084
[22] Hearn, T. A.; Reichel, L., Application of denoising methods to regularization of ill-posed problems, Numer. Algorithms, 66, 761-777 (2014) · Zbl 1297.65043
[23] Hearn, T. A.; Reichel, L., Image denoising via residual kurtosis minimization, Numer. Math. Theory Methods Appl., 8, 406-424 (2015) · Zbl 1349.94018
[24] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[25] Hochstenbach, M. E.; Noschese, S.; Reichel, L., Fractional regularization matrices for linear discrete ill-posed problems, J. Engrg. Math., 93, 113-129 (2015) · Zbl 1360.65113
[26] Jiang, E.-X.; Gao, K.-M.; Wu, J.-K., Linear Algebra (1978), People’s Education Press: People’s Education Press Beijing
[27] Lions, P. L.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979 (1979) · Zbl 0426.65050
[28] Markowitz, H. M., Portfolio Selection: Efficient Diversification of Investments (1959), Wiley: Wiley New York
[29] Meijerink, J. A.; van der Vorst, H. A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric \(M\)-matrix, Math. Comp., 31, 148-162 (1977) · Zbl 0349.65020
[30] Miller, J. J.H., On the location of zeros of certain classes of polynomials with applications to numerical analysis, J. Inst. Math. Appl., 8, 397-406 (1971) · Zbl 0232.65070
[31] Modersitzki, J., Numerical Methods for Image Registration (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1131.92316
[32] Morini, B.; Porcelli, M.; Chan, R. H., A reduced Newton method for constrained linear least-squares problems, J. Comput. Appl. Math., 233, 2200-2212 (2010) · Zbl 1186.65049
[33] Rockafellar, R. T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116 (1976) · Zbl 0402.90076
[34] Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898 (1976) · Zbl 0358.90053
[35] Rockafellar, R. T.; Wets, R. J.-B., Variational Analysis (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0888.49001
[36] Shefi, R.; Teboulle, M., Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24, 269-297 (2014) · Zbl 1291.90176
[37] Tao, M.; Yuan, X.-M., On the \(O(1 / t)\) convergence rate of alternating direction method with logarithmic-quadratic proximal regularization, SIAM J. Optim., 22, 1431-1448 (2012) · Zbl 1263.90103
[38] Varga, R. S., Matrix Iterative Analysis (1962), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0133.08602
[39] Yang, A.-L.; Wu, Y.-J., The Uzawa-HSS method for saddle-point problems, Appl. Math. Lett., 38, 38-42 (2014) · Zbl 1314.65055
[40] Zhang, G.-F.; Yang, J.-L.; Wang, S.-S., On generalized parameterized inexact Uzawa method for a block two-by-two linear system, J. Comput. Appl. Math., 255, 193-207 (2014) · Zbl 1291.65115
[41] Zhou, Y.-Y.; Zhang, G.-F., A generalization of parameterized inexact Uzawa method for generalized saddle point problems, Appl. Math. Comput., 215, 599-607 (2009) · Zbl 1173.65318
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.