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

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1ET400300415" target="_blank" >1ET400300415: Modelování a simulace náročných technických problémů: efektivní numerické algoritmy a paralelní implementace s pomocí nových informačních technologií</a><br>

Návaznosti

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

Rok uplatnění

2007

Kód důvěrnosti údajů

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

Název periodika

Computational Optimization and Applications

ISSN

0926-6003

e-ISSN

—

Svazek periodika

38

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

13

Strana od-do

47-59

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—