An optimal algorithm for a class of equality constrained quadratic programming problems with bounded spectrum

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F07%3A00014975" target="_blank" >RIV/61989100:27240/07:00014975 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

An optimal algorithm for a class of equality constrained quadratic programming problems with bounded spectrum

Original language description

The implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for the solution of large convex equality constrained quadratic programming problems is considered. It is proved that if the auxiliary problems are approximately solved by the conjugate gradient method, then the algorithm finds an approximate solution of the class of problems with uniformly bounded spectrum of the Hessian matrix at $O(1)$ matrix-vector multiplications. If applied to the class of problems with the Hessian matrices that are in addition either sufficiently sparse or can be be expressed as a product of such sparse matrices, then the cost of the solution is proportional to the dimension of the problems. Theoretical results are illustrated by numericalexperiments.

Czech name

Optimální algoritmu pro řešení konvexních úloh kvadratického programování s asymptoticky optimální složitostí

Czech description

V článku je popsán algoritmus pro řešení konvexníh úloh kvadratického programování s asymptoticky optimální (lineární) složitostí.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/1ET400300415" target="_blank" >1ET400300415: Modelling and simulation of complex technical problems:effective numerical algorithms and parallel implementation using new information technologie</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Computational Optimization and Applications

ISSN

0926-6003

e-ISSN

—

Volume of the periodical

38

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

13

Pages from-to

47-59

UT code for WoS article

—

EID of the result in the Scopus database

—