✦ LIBER ✦

The conjugate gradient technique for certain quadratic network problems

✍ Scribed by Larry J. Leblanc

Publisher: John Wiley and Sons
Year: 1976
Tongue: English
Weight: 326 KB
Volume: 23
Category: Article
ISSN: 0894-069X
DOI: 10.1002/nav.3800230403

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large‐scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum‐cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.

📜 SIMILAR VOLUMES

Indefinitely preconditioned conjugate gr

Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems

✍ C. Durazzi; V. Ruggiero 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

## Abstract This paper is concerned with the numerical solution of a symmetric indefinite system which is a generalization of the Karush–Kuhn–Tucker system. Following the recent approach of Lukšan and Vlček, we propose to solve this system by a preconditioned conjugate gradient (PCG) algorithm and

CONJUGATE GRADIENT METHODS FOR SOLVING T

CONJUGATE GRADIENT METHODS FOR SOLVING THE SMALLEST EIGENPAIR OF LARGE SYMMETRIC EIGENVALUE PROBLEMS

✍ Y. T. FENG; D. R. J. OWEN 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1000 KB

In this paper, a detailed description of CG for evaluating eigenvalue problems by minimizing the Rayleigh quotient is presented from both theoretical and computational viewpoints. Three variants of CG together with their asymptotic behaviours and restarted schemes are discussed. In addition, it is s

Lower bounding techniques for the degree

Lower bounding techniques for the degree-constrained network design problem

✍ Güvenç Şahin; Ravindra K. Ahuja 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 1 views

Conjugate gradient method for the Robin

Conjugate gradient method for the Robin inverse problem associated with the Laplace equation

✍ Bangti Jin 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

Application of the preconditioned conjug

Application of the preconditioned conjugate-gradient algorithm to the edge FEM for electromagnetic boundary-value problems

✍ R. S. Chen; Edward K. N. Yung; C. H. Chan; D. G. Fang 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB 👁 1 views

A note on the efficiency of the conjugat

A note on the efficiency of the conjugate gradient method for a class of time-dependent problems

✍ Xing Cai; Bjørn Fredrik Nielsen; Aslak Tveito 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 1 views

## Abstract We discuss the efficiency of the conjugate gradient (CG) method for solving a sequence of linear systems; __Au__^__n__+1^ = __u__^__n__^, where __A__ is assumed to be sparse, symmetric, and positive definite. We show that under certain conditions the Krylov subspace, which is generated