Počet záznamů: 1  

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

  1. 1. 0103267 - UIVT-O 20040008 RIV SE eng J - Článek v odborném periodiku
    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
    Grant CEP: GA AV ČR IAA1030103
    Výzkumný záměr: CEZ:AV0Z1030915
    Klíčová slova: non-linear programming * interior point methods * indefinite systems * indefinite preconditioners * preconditioned conjugate gradient method * merit functions * algorithms * computational experiments
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.727, rok: 2004

    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ů.
    Trvalý link: http://hdl.handle.net/11104/0010579