Interior Point Methods for Large-Scale Nonlinear Programming

0405206 - UIVT-O 330373 RIV US eng J - Článek v odborném periodiku
Lukšan, Ladislav - Matonoha, Ctirad - Vlček, Jan
Interior Point Methods for Large-Scale Nonlinear Programming.
[Metody vnitřních bodů pro velké řídké úlohy nelineárního programování.]
Optimization Methods & Software. Roč. 20, č. 4-5 (2005), s. 569-582. ISSN 1055-6788. E-ISSN 1029-4937
Grant CEP: GA AV ČR IAA1030405
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: nonlinear programming * interior point methods * KKT systems * indefinite preconditioners * filter methods * algorithms
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.477, rok: 2005

In this paper we describe an algorithm for solving nonlinear nonconvex programming problems, which is based on the interior point approach. The main theoretical results concern direction determination and step-length selection. We split inequality constraints into active and inactive parts to overcome problems with instability. Inactive constraints are eliminated directly, whereas active constraints are used for defining a symmetric indefinite linear system. Inexact solution of this system is obtained iteratively using indefinitely preconditioned conjugate gradient method. Theorems confirming efficiency of the indefinite preconditioner are introduced. Furthermore, a new merit function is defined and a filter principle is used for step-length selection. The algorithm was implemented in the interactive system for universal functional optimization UFO. Results of numerical experiments are reported.

V tomto článku popisujeme algoritmus pro řešení problémů nelineárního nekonvexního programování, který je založen na principu vnitřních bodů. Hlavní teoretické výsledky se týkají určení směrového vektoru a volby délky kroku. Omezení s nerovnostmi rozdělíme na aktivní a neaktivní, abychom předešli problémům s nestabilitou. Neaktivní omezení vyeliminujeme a aktivní omezení použijeme pro vytvoření symetrického indefinitního lineárního systému. Nepřesné řešení tohoto systému dostaneme iteračně použitím indefinitně předpodmíněné metody sdružených gradientů. Dále uvádíme věty týkající se efektivity indefinitního předpodmiňovače, definujeme novou pokutovou funkci a pro volbu délky kroku používáme princip filtru. Algoritmus byl implementován do systému UFO a jsou uvedeny numerické výsledky.
Trvalý link: http://hdl.handle.net/11104/0125399