×

Sparsity-preserving SOR algorithms for separable quadratic and linear programming. (English) Zbl 0606.90102

The main purpose of this work is to give explicit sparsity-preserving SOR (successive overrelaxation) algorithms for the solution of separable quadratic and linear programming problems. The principal and computationally-distinguishing feature of the present SOR algorithms is that they preserve the sparsity structure of the problem and do not require the computation of the product of the constraint matrix by its transpose as is the case in earlier SOR algorithms for linear and quadratic programming.

MSC:

90C20 Quadratic programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] B.-H- Ahn, Solution of non-symmetric linear complementarity problems by iterative methods. J. Opt. Theory Appl.; B.-H- Ahn, Solution of non-symmetric linear complementarity problems by iterative methods. J. Opt. Theory Appl. · Zbl 0422.90079
[2] Cottle, R. W.; Dantzig, G. B., Complementary pivot theory of mathematical programming, Linear Algebra Applic., 1, 103-125 (1968) · Zbl 0155.28403
[3] Cottle, R. W.; Golub, G. H.; Sacher, R. S., On the solution of large structured linear complementarity problems—III, Appl. Math. Opt., 4, 347-363 (1978) · Zbl 0391.90087
[4] Cryer, C. W., The solution of a quadratic programming problem using systematic overrelaxation, SIAM J. Control, 9, 385-392 (1971) · Zbl 0201.22202
[5] Dorn, W. S., Duality in quadratic programming, Quart. Appl. Math., 18, 155-162 (1960) · Zbl 0101.37003
[6] Eckhardt, U., Quadratic programming by successive overrelaxation, Kernforschungsanlage Ju¨lich, Technical Report No. Ju¨l-1064-MA (1974)
[7] Fiacco, A. V.; McCormick, G. P., Nonlinear Programming: Sequential Unconstrained Minimization Techniques (1968), Wiley: Wiley New York · Zbl 0193.18805
[8] Han, S.-P.; Mangasarian, O. L., A dual differentiable exact penalty function, Math. Prog., 25, 293-306 (1983) · Zbl 0495.90070
[9] J. L. Kreuser, Computational experiemce with iterative SOR methods; J. L. Kreuser, Computational experiemce with iterative SOR methods
[10] Mangasarian, O. L., Nonlinear Programming (1969), McGraw-Hill: McGraw-Hill New York · Zbl 0194.20201
[11] Mangasarian, O. L., Solution of symmetric linear complementarity problems by iterative methods, J. Opt. Theory and Appl., 22, 465-485 (1977) · Zbl 0341.65049
[12] Mangasarian, O. L., Iterative solution of linear programs, SIAM J. Numer. Anal., 18, 4 (1981), August. · Zbl 0471.65033
[13] Mangasarian, O. L., Least-norm linear programming solution as an unconstrained minimization problem, J. Math. Anal. Appl., 29, 240-251 (1983) · Zbl 0525.90064
[14] Mangasarian, O. L.; Meyer, R. R., Nonlinear perturbation of linear programs, SIAM J. Control Opt., 17, 745-752 (1979) · Zbl 0432.90047
[15] Pang, J.-S., The implicit complementarity problem, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear programming, 4 (1981), Academic Press: Academic Press New York), 487-518
[16] Pang, J.-S., On the convergence of a basic iterative method for the implicit complementarity problem, J. Opt. Theory Appl., 37, 149-162 (1982) · Zbl 0482.90084
[17] Wolfe, P., A duality theorem for nonlinear programming, Quart. Appl. Math., 19, 239-244 (1961) · Zbl 0109.38406
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.