Методи оптимiзацiї: Повний навчальний посiбник

Мiнiмiзацiя функцiй однiєї змiнної

У задачах одновимiрної мiнiмiзацiї розглядається скалярна функцiя $\phi(x)$, задана на числовiй прямiй $E^1$. Точка $x^<em>$ називається точкою глобального (абсолютного) мiнiмуму, якщо умова $\phi(x^</em>) \le \phi(x)$ виконується для всiх $x \in E^1$. Якщо дана нерiвнiсть виконується лише для достатньо малого \epsilon > 0 у межах $|x - x^<em>| \le \epsilon$, то $x^</em>$ називається точкою локального (вiдносного) мiнiмуму. Мiнiмум називається строгим, якщо вiдповiднi нерiвностi виконуються строго при $x \neq x^<em>$. Необхiдною умовою екстремуму першого порядку для диференцiйовної функцiї є рiвнiсть першої похiдної нулю: $\frac{d\phi(x^</em>)}{dx} = 0$. Точки, що задовольняють цiй умовi, називаються стацiонарними.

Необхiдна умова другого порядку стверджує, що у точцi локального мiнiмуму друга похiдна функцiї має бути невiд’ємною: $\frac{d^2\phi(x^<em>)}{dx^2} \ge 0$. Достатньою умовою є строга додатнiсть другої похiдної у стацiонарнiй точцi: \frac{d^2\phi(x^)}{dx^2} > 0. Загальна достатня умова екстремуму вказує, що якщо першi $k-1$ похiдних дорiвнюють нулю, а $k$-та похiдна $\frac{d^k\phi(x^<em>)}{dx^k} \neq 0$, то $x^</em>$ є точкою мiнiмуму за умови, що $k$ — парне число i $k$-та похiдна додатна. Якщо ж $k$ — непарне число, точка не є екстремальною. При мiнiмiзацiї на вiдрiзку $[a; b]$, якщо $x^* = a$ є точкою мiнiмуму, то $\frac{d\phi(a)}{dx} \ge 0$, а якщо $x^* = b$ — то $\frac{d\phi(b)}{dx} \le 0$.

Чисельнi методи одновимiрної мiнiмiзацiї застосовуються, коли розв’язок рiвняння $\phi'(x) = 0$ у явному виглядi неможливий. Функцiя називається унiмодальною на вiдрiзку $[a; b]$, якщо вона спочатку спадає, а потiм зростає, маючи єдину точку мiнiмуму. Симетричнi методи використовують двi точки, симетричнi вiдносно середини iнтервалу невизначеностi. У методi подiлу вiдрiзка навпiл точки $x' = a + \frac{b-a}{4}$ та $x'' = b - \frac{b-a}{4}$ дiлять вiдрiзок на чотири рiвнi частини. Метод дихотомiї використовує точки $x' = \frac{a+b-\delta}{2}$ та $x'' = \frac{a+b+\delta}{2}$, де $\delta$ — мале число. Метод золотого перетину використовує пропорцiю $\Phi = \frac{1+\sqrt{5}}{2} \approx 1.618$, де точки обчислюються за формулами $x' = a + \frac{3-\sqrt{5}}{2}(b-a)$ та $x'' = a + \frac{\sqrt{5}-1}{2}(b-a)$. Метод Фiбоначчi базується на числах Фiбоначчi $F_1=F_2=1, F_{n+2}=F_{n+1}+F_n$, де кiлькiсть крокiв $n$ визначається з умови F_{n+1} < \frac{b-a}{\epsilon} \le F_{n+2}.

Мiнiмiзацiя функцiй багатьох змiнних без обмежень

У просторi $E^n$ вектор $\frac{\partial \phi(x)}{\partial x}$ називається градiєнтом, який вказує напрямок найшвидшого зростання функцiї. Матриця других частинних похiдних $\frac{\partial^2 \phi(x)}{\partial x^2}$ називається матрицею Гессе. Симетрична матриця $A$ називається додатно визначеною, якщо квадратична форма I = x^T A x > 0 для всiх $x \neq 0$. Точка $x^<em>$ називається точкою глобального мiнiмуму на множинi $R$, якщо $\phi(x^</em>) \le \phi(x)$ для всiх $x \in R$. Якщо нижня межа $\phi^* = \inf_{x \in R} \phi(x)$ не досягається, будується мiнiмiзуюча послiдовнiсть ${x_k}$, така, що $\lim_{k \to \infty} \phi(x_k) = \phi^*$.

Теорема Вейєрштрасса стверджує: якщо множина $R$ обмежена i замкнена, а функцiя $\phi(x)$ неперервна, то множина точок глобального мiнiмуму непуста i обпежена. Класична необхiдна умова екстремуму першого порядку в $E^n$ — рiвнiсть градiєнта нульовому вектору: $\frac{\partial \phi(x^*)}{\partial x} = 0$. Необхiдною умовою другого порядку для мiнiмуму є невiд’ємна визначенiсть матрицi Гессе. Достатня умова полягає у додатнiй визначеностi матрицi Гессе у стацiонарнiй точцi. Для пошуку мiнiмуму складається i розв’язується система рiвнянь градiєнта, пiсля чого перевiряється знаковизначенiсть матрицi других похiдних у кожнiй стацiонарнiй точцi.

Мiнiмiзацiя функцiй при обмеженнях

Задачi на умовний екстремум включають обмеження типу рiвностей $g_i(x) = 0$. Правило множникiв Лагранжа використовує функцiю $L(x, \lambda_0, \lambda) = \lambda_0 \phi(x) + \sum_{i=1}^m \lambda_i g_i(x)$. Якщо $\lambda_0 = 1$, задача називається нормальною. Точка є нормальною, якщо градiєнти обмежень $\frac{\partial g_1(x^<em>)}{\partial x}, \dots, \frac{\partial g_m(x^</em>)}{\partial x}$ лiнiйно незалежнi. Необхiднi умови другого порядку вимагають невiд’ємностi квадратичної форми матрицi Гессе функцiї Лагранжа на пiдпросторi векторів, ортогональних градiєнтам обмежень.

При обмеженнях типу нерiвностей $g_i(x) \le 0$ використовується поняття активних i пасивних обмежень. Обмеження є активним, якщо $g_i(x^0) = 0$. Необхiдними умовами мiнiмуму є умови Куна-Таккера: iснування невiд’ємних множникiв $\lambda^<em>_i \ge 0$, рiвнiсть нулю градiєнта функцiї Лагранжа та умови доповнюючої нежорсткостi $\lambda^</em>_i g_i(x^*) = 0$. Достатньою умовою є додатна визначенiсть квадратичної форми матрицi Гессе функцiї Лагранжа на вiдповiднiй гiперплощинi активних обмежень.

Опукле та лiнiйне програмування

Множина $R$ називається опуклою, якщо для будь-яких двох точок вiдрiзок, що їх з’єднує, належить $R$: $x(\lambda) = \lambda x_1 + (1-\lambda)x_2, \in [0; 1]$. Функцiя $\phi(x)$ є опуклою, якщо $\phi(\lambda x_1 + (1-\lambda)x_2) \le \lambda \phi(x_1) + (1-\lambda) \phi(x_2)$. У задачах опуклого програмування будь-який локальний мiнiмум є глобальним. Важливими є теореми про вiдокремлення: якщо опуклi замкненi множини не перетинаються, iснує гiперплощина, що їх роздiляє. Теорема Куна-Таккера для опуклої задачi стверджує, що при виконаннi умови Слейтера (iснує $x_0$ таке, що g(x_0) < 0), точка $x^*$ є розв’язком тодi i тiльки тодi, коли вона є сiдловою точкою функцiї Лагранжа.

Лiнiйне програмування (ЛП) розглядає мiнiмiзацiю лiнiйної функцiї $(c, x)$ при лiнiйних обмеженнях $Ax \le b, x \ge 0$. Кожнiй такiй задачi вiдповiдає двоїста задача $\max (b, y)$ при $A^T y \le c, y \ge 0$. Теорема двоїстостi стверджує, що значення цiльових функцiй у розв’язках прямої i двоїстої задач спiвпадають: $(c, x^<em>) = (b, y^</em>)$. Розв’язок задачi ЛП завжди знаходиться в однiй iз кутових (крайнiх) точок багатогранника припустимих розв’язкiв.

Чисельнi методи безумовної мiнiмiзацiї багатьох змiнних

Методи спуску будують послiдовнiсть $x_{k+1} = x_k + \beta_k s_k$. Методи нульового порядку не використовують похiдних. Сюди вiдносяться покоординатний спуск, метод Нелдера-Мiда (метод симплексу, що деформується, з операцiями вiдбиття, розтягування, стиснення та редукцiї) та метод Пауелла (використання спряжених напрямкiв без похiдних). Коефiцiєнти Нелдера-Мiда зазвичай обираються як $\alpha = 1$ (вiдбиття), $\beta = 0.5$ (стиснення), $\gamma = 2$ (розтягування).

Методи першого порядку базуються на градiєнтi. Градiєнтний метод використовує $s_k = -\frac{\partial \phi(x_k)}{\partial x}$. Якщо крок $\beta_k$ мiнiмiзує функцiю у напрямку спуску, метод називається методом найшвидшого спуску. Метод спряжених градiєнтiв використовує напрямки $s_k = -\nabla \phi(x_k) + \beta_k s_{k-1}$, де $\beta_k = \frac{|\nabla \phi(x_k)|^2}{|\nabla \phi(x_{k-1})|^2}$ (формула Флетчера-Рiвса). Цей метод є скiнченним для квадратичних функцiй та має швидкiсть збiжностi вищу за градiєнтний.

Методи другого порядку використовують матрицю Гессе. Метод Ньютона визначає наступну точку як $x_{k+1} = x_k - [\nabla^2 \phi(x_k)]^{-1} \nabla \phi(x_k)$. Вiн має квадратичну швидкiсть збiжностi поблизу мiнiмуму, але вимагає обчислення та обертання матрицi других похiдних. Модифiкацiї, такi як метод Ньютона-Рафсона (з кроком $\beta_k$) або метод Левенберга-Марквардта ($\nabla^2 \phi + \alpha I$), забезпечують кращу стiйкiсть. Квазiньютонiвськi методи (змiнної метрики) апроксимують обернену матрицю Гессе за допомогою формул Бройдена, ДФП (Девiдона-Флетчера-Пауелла) або БФГШ, використовуючи лише градiєнти.

Спецiальнi задачi та вплив перешкод

При мiнiмiзацiї недиференцiйовних функцiй використовується субградiєнтний метод: $x_{k+1} = x_k - \beta_k \partial \phi(x_k)$. Також застосовуються методи вiдтинаючих гiперплощин та метод елiпсоїдiв (метод Шора). Яристi (яружнi) функцiї характеризуються витягнутими лiнiями рiвня та поганою обумовленiстю матрицi Гессе ($\mu = \frac{\lambda_{max}}{\lambda_{min}} \gg 1$). Для їх розв’язання використовують яристий метод (крок вздовж дна яру) або методи змiни масштабiв змiнних.

Перешкоди (похибки) при обчисленнi градiєнта можуть бути детермiнованими або випадковими, абсолютними або вiдносними. Градiєнтний метод є стiйким до вiдносних перешкод, якщо їх рiвень менший за $100\%$. Метод Ньютона надзвичайно чутливий до похибок через погану обумовленiсть матрицi Гессе. Методи штрафних функцiй дозволяють перейти до задач без обмежень: методи внутрiшньої точки (бар’єрнi функцiї, наприклад, логарифмiчнi) вимагають початкової припустимої точки, а методи зовнiшньої точки (квадратичний штраф за порушення) дозволяють наближатися до розв’язку ззовнi. Комбiнованi методи поєднують цi пiдходи для задач iз рiвностями та нерiвностями.