Interior-Point Method for Non-Linear Non-Convex Optimization

0103267 - UIVT-O 20040008 RIV SE eng J - Journal Article
Lukšan, Ladislav - Matonoha, Ctirad - Vlček, Jan
Interior-Point Method for Non-Linear Non-Convex Optimization.
[Metoda vnitřních bodů pro nelineární nekonvexní optimalizaci.]
Numerical Linear Algebra with Applications. Roč. 11, č. 5-6 (2004), s. 431-453. ISSN 1070-5325. E-ISSN 1099-1506
R&D Projects: GA AV ČR IAA1030103
Institutional research plan: CEZ:AV0Z1030915
Keywords : non-linear programming * interior point methods * indefinite systems * indefinite preconditioners * preconditioned conjugate gradient method * merit functions * algorithms * computational experiments
Subject RIV: BA - General Mathematics
Impact factor: 0.727, year: 2004
https://www.math.ru.nl/pmocco/Announcement_2.html

In this paper, we propose an algorithm for solving non-linear non-convex programming problems, which is based on the interior point approach. Main theoretical results concern direction determination and step-length selection. We split inequality constraints into active and inactive to overcome problems with stability. Inactive constraints are eliminated directly while active constraints are used to define symmetric indefinite linear system. Inexact solution of this system is obtained iteratively using indefinitely preconditioned conjugate gradient method. Theorems confirming efficiency of several indefinite preconditioners are proved. Furthermore, new merit function is defined, which includes effect of possible regularization. This regularization can be used to overcome problems with near linear dependence of active constraints. The algorithm was implemented in the interactive system for universal functional optimization UFO. Results of extensive numerical experiments are reported.

V tomto článku předkládáme algoritmus pro řešení nelineárních nekonvexních problémů založený na metodě vnitřních bodů. Hlavní teoretické výsledky se týkají určení směrového vektoru a volby délky kroku. Omezení, ve kterých se vyskytují nerovnosti, rozdělíme na aktivní a neaktivní, abychom předešli problémům se stabilitou. Neaktivní omezení vyeliminujeme a aktivní omezení použijeme k vytvoření symetrického indefinitního lineárního systému. Ten řešíme iteračně použitím metody sdružených gradientů s indefinitním předpodmiňovačem. Jsou dokázány věty potvrzující efektivitu některých předpodmiňovačů. Kromě toho je definována nová pokutová funkce, která zahrnuje vliv regularizace, kterou je možné použít k překonání problémů, kdy jsou aktivní omezení téměř lineárně závislé. Algoritmus byl implementován do interaktivního systému pro univerzální funkcionální optimalizaci UFO a jsou uvedeny výsledky rozsáhlých numerických experimentů.
Permanent Link: http://hdl.handle.net/11104/0010579