Interior Point Method for Non-Linear Non-Convex Optimization

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F04%3A00103267" target="_blank" >RIV/67985807:_____/04:00103267 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Interior Point Method for Non-Linear Non-Convex Optimization

Original language description

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.

Czech name

Metoda vnitřních bodů pro nelineární nekonvexní optimalizaci

Czech description

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ů.

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/IAA1030103" target="_blank" >IAA1030103: Scalable Sparse Linear Algebraic Solvers: Analysis, Development, Implementation and Application</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

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

Name of the periodical

Numerical Linear Algebra with Applications

ISSN

1070-5325

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

-

Country of publishing house

SE - SWEDEN

Number of pages

23

Pages from-to

431-453

UT code for WoS article

—

EID of the result in the Scopus database

—