Багатовимірна безумовна оптимізація (методи першого та нульового порядків). Численні методи пошуку екстремуму функцій багатьох змінних

Анотація: Дана лекція розглядає основні методи розв'язання задач багатовимірної оптимізації, зокрема такі як метод Хука – Джівса, метод Нелдера – Міда, метод повного перебору (метод сіток), метод покоординатного спуску, метод градієнтного спуску.

Досі ми обговорювали одновимірні завдання оптимізації, у яких цільова функція залежала лише від одного аргументу. Однак переважна кількість реальних завданьОптимізації, що становлять практичний інтерес, є багатовимірними: у них цільова функція залежить від кількох аргументів, причому іноді їх кількість може бути дуже великою.

Математична постановка таких завдань аналогічна до їх постановки в одновимірному випадку: шукається найменше (найбільше) значення цільової функції, заданої на деякій множині G можливих значень її аргументів.

Як і в одновимірному випадку, характер завдання і відповідно можливі методи вирішення істотно залежать від інформації про цільову функцію, яка нам доступна в процесі її дослідження. В одних випадках цільова функція задається аналітичною формулою, будучи при цьому функцією, що диференціюється. Тоді можна обчислити її приватні похідні, отримати явний вираз для градієнта, що визначає в кожній точці напрямки зростання та зменшення функції, і використовувати цю інформацію для вирішення задачі. В інших випадках ніякої формули для цільової функції немає, а є лише можливість визначити її значення в будь-якій точці області (за допомогою розрахунків, в результаті експерименту і т.д.). У таких завданнях у процесі вирішення ми фактично можемо знайти значення цільової функції лише у кінцевому числіточок, і за цією інформацією потрібно приблизно встановити її найменше значеннядля всієї області.

1. Метод Хука – Джівса

Цей метод був розроблений у 1961 році, але досі є дуже ефективним та оригінальним. Пошук складається з послідовності кроків досліджуючого пошуку навколо базисної точки, за якою у разі успіху слідує пошук за зразком.

Опис цієї процедури наведено нижче:

А. Вибрати початкову базисну точку b 1 і крок довжиною h j для кожної змінної x j j = 1, 2, ..., n . У наведеній нижче програмі для кожної змінної використовується крок h, проте вказана модифікація теж може бути корисною.

Б. Обчислити f(x) у базисній точці b 1 з метою отримання відомостей про локальну поведінку функції f(x). Ці відомості будуть використовуватися для знаходження відповідного напрямку пошуку за зразком, за допомогою якого можна сподіватися досягти більшого зменшення значення функції. Функція f(x) у базисній точці b 1 знаходиться так:

1. Обчислюється значення функції f(b 1) у базовій точці b 1 .

2. Кожна змінна по черзі змінюється додаванням довжини кроку.

Отже, ми обчислюємо значення функції f(b 1 + h 1 e 1) , де e 1 - одиничний вектору напрямку осі х 1 . Якщо це призводить до зменшення значення функції, то b1 замінюється на b1+h1e1. Інакше обчислюється значення функції f(b 1 – h 1 e 1) і якщо її значення зменшилося, то b 1 замінюємо на b 1 -h 1 e 1 . Якщо жоден із зроблених кроків не призводить до зменшення значення функції, то точка b 1 залишається незмінною і розглядаються зміни у бік осі х 2 , тобто. перебуває значення функції f(b 1 + h 2 e 2) тощо. Коли буде розглянуто всі n змінні, ми матимемо нову базову точку b 2 .

3. Якщо b 2 = b 1 тобто. зменшення функції був досягнуто, то дослідження повторюється навколо тієї ж базисної точки b 1 , але з зменшеною довжиною кроку. Насправді задовільним є зменшення кроку (кроків) вдесятеро від початкової довжини.

4. Якщо , то здійснюється пошук за зразком.

У. Під час пошуку за зразком використовується інформація, отримана в процесі дослідження, і мінімізація функції завершується пошуком у напрямку, заданому зразком. Ця процедура проводиться так:

1. Розумно рухатися з базисної точки b 1 у напрямку b 2 - b 1 оскільки пошук у цьому напрямку вже призвів до зменшення значення функції. Тому обчислимо функцію у точці зразка

(1.1)

Завдання оптимізації (пошуку найкращого рішення) не найпопулярніші серед 1С-негов. Справді, одна справа - облік виконання будь-яких рішень, і зовсім інша справа - прийняття цих рішень. У Останнім часом, однак, мені здається 1С кинулася наздоганяти конкурентів у даному питанні. Дійсно захоплююче об'єднати під одним дахом все, що може знадобитися сучасному менеджеру, наздоганяючи у цьому питанні SAP та замінюючи MS Project та інші системи планування.

Втім, розмова про подальших шляхахрозвитку 1С - це тема окремої публікації та дискусії, а поки що я задумав цикл статей, що пояснюють та демонструють сучасні математичні та алгоритмічні підходи до багатовимірної нелінійної оптимізації, або, якщо хочете - механізмів пошуку рішень. Всі статті будуть супроводжуватися демо обробками з універсальними процедурами та функціями багатовимірної оптимізації - Ваша справа знайти за бажання їм застосування або прийняти на баланс корисного знання та інструментарію (тільки тим, природно, хто подужає цю статтюдо кінця). Чесно обіцяю вищу математикувикладати найбільш доступною мовоюі з прикладами того, як ці моторошні формули можна перетворити на програмно розв'язувані завдання:) Поїхали...

Отже, перша тема - метод градієнтного спуску.

Сфера застосування методу - будь-які завдання на знаходження масиву з nзмінних, які забезпечують мінімальне (максимальне) значення цільової функції. Цільова функція при цьому - функція від цих самих nзмінних найдовільнішого виду - єдина умова, що накладається методом на цільову функцію - її безперервність принаймні на відрізку пошуку рішення. Безперервність практично означає, що з будь-якого поєднання значень змінних можна визначити дійсне значення цільової функції.

Давайте введемо позначення:

Безліч змінних Х,від яких залежить значення цільової функції

І сама цільова функція Z, що обчислюється довільним чином з безлічі Х

Тепер пояснимо, що таке градієнт. Градієнт це вектор багатовимірного простору, що вказує напрям найбільшого зростання певної функції. Компонентами градієнта є диференціали всіх змінних функцій Z.

Ось звідси й випливає головне обмеження застосування методу градієнтного спуску - диференційованість (безперервність) функції протягом усього області пошуку рішення. Якщо ця умова дотримується, то пошук оптимального рішенняпитання чисто технічне.

Класичний метод градієнтного спуску реалізовується для мінімізації цільової функції через антиградієнт (тобто вектор протилежний градієнту), який виходить із градієнту самим простим чином- множенням на -1 всіх компонентів градієнта. Або в позначеннях:

Тепер самий головне питання: а як нам знайти ці самі dZі dX1 , dX2і т.д.? Дуже просто! dXn- це нескінченно мале збільшення змінної Xnскажімо 0,0001 від її поточної величини. Або 0,0000000001 - головне, щоб воно (прирощення) було дійсно малим:)

А як же обчислюється dZ ? Теж просто! Обчислюємо Zдля набору змінних X, а потім змінюємо в цьому наборі змінну Xnна величину dXn. Знову обчислюємо значення цільової функції Zдля цього злегка модифікованого набору ( Zn) і знаходимо різницю - це і буде dZ = Zn - Z. Ну а тепер якщо нам відомі dXnі dZзнайти dZ/dXn простіше пареної ріпи.

Знайшовши послідовно всі компоненти градієнта та антиградієнта ми отримуємо напрямок зміни змінних, який якнайшвидше дозволить досягти мінімуму функції.

На наступному (k+1) етапі потрібно обчислити нові значення масиву змінних X. Очевидно, що для наближення до мінімуму цільової функції Zми повинні коригувати значення Xпопереднього (k-го) етапу у напрямку антиградієнта за такою формулою:

Залишається розібратися з цією альфою у формулі. Навіщо вона потрібна і звідки береться.

α - це коефіцієнт на який примножується антиградієнт для забезпечення досягнення можливого мінімуму функції заданому напрямку. Сам по собі градієнт або антиградієнт не є мірою змінного зсуву, а вказують лише напрямок руху. Геометричний змістградієнта - це тангенс кута нахилу щодо функції Zу точці Xn(Ставлення протилежного катета dZдо прилеглого dXn), але рухаючись по дотичній, ми неминуче відхилимося від лінії функції до досягнення її мінімуму. Сенс щодо в тому, що вона дає відображення у вигляді прямої довільної криволінійної функції у дуже вузькому проміжку - околицях точки Xn .

Пошук значення параметра α виконується одним із методів одновимірної оптимізації. Значення змінних (X)нам відомі, відомі та їх градієнти - залишається мінімізувати цільову функцію на околицях поточного рішення за одним єдиним параметром: α .

Зупинятися на одновимірній оптимізації я тут буду - методи досить прості для розуміння та реалізації, скажу лише, що я використав у своєму рішенні метод "золотого перерізу". ОДЗ для α знаходиться у проміжку від 0 до 1.

Отже, резюмуючи написане, сформулюємо послідовність кроків для пошуку рішення методом градієнтного спуску:

Формуємо початкове опорне рішення, присвоюючи шуканим змінним випадкові значенняз ОДЗ.
Знаходимо градієнти та антиградієнти для кожної змінної як відношення приросту цільової функції при відносно малому збільшенні значення змінної до значення приросту цієї змінної.
Знаходимо коефіцієнт α , який потрібно множити антиградієнти перед додаванням до вихідним значенням опорного рішення методом одномірної оптимізації. Критерій оптимізації - найменше з можливих значення цільової функції для скоригованих таким чином значень (X).
Перераховуємо (X)відповідно до наділених значень антиградієнтів та коефіцієнта зсуву α .
Перевіряємо, чи досягнута необхідна точність ( ε ) обчислення мінімуму цільової функції:

6. Якщо умова виконана і від етапу до етапу значення цільової функції змінилося нижче встановленого нами критерію це означає, що необхідна точність досягнута і поточна безліч(X) є рішенням завдання,інакше – перехід до кроку 2.

Тепер давайте перейдемо до практичного завдання, яке вирішено в обробці.

За умовою завдання необхідно встановити ціну на товар таким чином, щоб прибуток від його реалізації в планованому періоді була максимальною. При цьому потрібно враховувати, що обсяг реалізації залежить від встановленої нами ціни, а закупівельна ціна товару (що впливає на валовий прибуток) також залежить від обсягу закупівлі товару: постачальник готовий надавати знижки тим більше, чим більше буде обсяг нашої закупівлі. Тобто нам потрібно одночасно із встановленням ціни розуміти, скільки товару ми зможемо реалізувати і за якою ціною і, отже, скільки товару нам потрібно для цього закупити, і тоді ми знатимемо, якою буде закупівельна ціна. Загалом така трохи рекурсивна логіка пошуку рішення:)

Найголовніше, що ми маємо – це безперервність змінних (ціни та обсягу закупівлі/реалізації) та цільової функції (прибуток є завжди і може набувати будь-якого значення, навіть якщо він з мінусом, то називається збиток), а значить, метод градієнтного спуску – найголовніше воно.

Для вирішення задачі даний методзастосовується двічі: першому етапі ми бачимо параметри рівняння попиту продукцію за даними продажів попередніх періодів. Тобто, припускаючи певний вид залежності попиту ціни, обчислюємо значення параметрів цієї залежності, мінімізуючи суму квадратів відхилень між розрахунковими і фактичними даними про продажах. На другому етапі, користуючись знайденими параметрами залежності між обсягом продажів і ціною реалізації, ми оптимізуємо прибуток і також методом градієнтного спуску, хоча б застосовується лише для однієї змінної. Так як метод градієнтного спуску мінімізує цільову функцію, а прибуток як ніщо інше потребує максимізації, ми використовуємо не твіальну цільову функцію з назвою "МінусПрибуток", яка всього й робить, що обчислює прибуток за отриманим значенням ціни, а перед поверненням множить її на -1:) І працює! Тепер чим менше стає "МінусПрибуток", тим більше насправді найбільш реальний прибуток від продажів.

Приклад рішення в обробці, а також універсальна функціяпошуку рішення шляхом градієнтного спуску. Суть універсальності в тому, що змінні (X)передаються до неї як масиву, а цільова функція передається як параметр рядком. Цільову ж функцію, яка приймає масив змінних і повертає значення, пишіть самі будь-якого виду - головне, щоб вона повертала число. І таке число, що чим менше воно буде, тим ближче подано масив аргументів до оптимального рішення.

Чому не навів тут готової процедури, а викладаю обробку? По-перше, процедура і так довга, а по-друге, без цільових функційвона не працює, так що потрібно затягувати все, та ще й у взаємозв'язку. Я сподіваюся, що викладеної в статті теорії цілком достатньо для того, щоб Ви змогли реалізувати своє рішення, можливо навіть кращим, ніж у мене, чином. Ну якщо вже зовсім не виходитиме - качайте готову обробку і користуйтеся:)

Ось, власне, і все. Запитання, побажання та зауваження чекаю у коментах. Спасибі за увагу.

Розглянемо способи відшукання екстремуму функції R ( x ) без активних обмежень. Активними прийнято називати такі обмеження, на межі яких є рішення. Величина кроку  х у співвідношенні

x i +1 = x i +  x i

обчислюється з використанням градієнта цільової функції R ( x ), тобто.

x i =  ( gradR ( x i )),

при цьому крок може визначатися з використанням градієнта в одній (поточній) або двох (поточної та попередньої) точках. Напрямок градієнта, як відомо, показує напрями якнайшвидшого зростання функції, яке модуль - швидкість цього зростання.

Обчислення градієнта передбачає безперервність функції багатьох змінних

Пошукові методи оптимізації містять параметри, що задаються, які істотно впливають на ефективність пошуку, внаслідок чого один і той же метод може дати абсолютно різні траєкторії пошуку. Тому для всіх методів, що розглядаються далі, на рис.3.5 наводиться лише одна з можливих траєкторій.

Рис. 3.5. Ілюстрація траєкторій пошуку мінімуму функції градієнта

методами:

1 - Оптимум; 2 - Траєкторія методу градієнта; 3 - траєкторія методу

важкої кульки; 4 - траєкторія методу якнайшвидшого спуску;

5 - Траєкторія методу сполучених градієнтів;

Крім того, для всіх наведених траєкторій обрані різні початкові умови, щоб не захаращувати побудови. На цьому та наступних малюнках залежність R ( x 1 , x 2 ) наведена у вигляді ліній рівня на площині в координатах x 1 - x 2 .

Основні методи

Метод градієнта.

Метод градієнта в чистому виглядіформує крок по змінним як функцію від градієнта R ( x ) у поточній точці пошуку. Найпростіший алгоритм пошуку minR ( x ) записується у векторній формі наступним чином:

або у скалярному вигляді:

- порядковий номер аргументу,

Величина робочого кроку у напрямку градієнта h grad R ( x ) залежить від величини градієнта, який заздалегідь врахувати важко, та від коефіцієнта пропорційності кроку h , з допомогою якого можна керувати ефективністю методу.

Пошук кожної нової точки складається з двох етапів:

1) оцінка градієнта R ( x ) шляхом обчислення приватних похідних від R ( x ) по кожній змінній х j ,

2) робочий крок по всіх змінних одночасно.

Величина h сильно впливає ефективність методу. Більшою ефективністю має варіант методу, коли крок по змінній визначається напрямними косинусами градієнта.

де cosφ j =

У цьому випадку величина робочого кроку не залежить від величини модуля градієнта і нею легше керувати зміною h . У районі оптимуму може виникати значне " нишпорення " , тому використовують різні алгоритми корекції h .

Найбільшого поширення набули такі алгоритми:

1. h i= const = h(без корекції);

2. h i = h i -1 /2, якщо R(x i ) < R(x i -1 ) ; h i = h i -1 , R(x i ) > R(x i -1 ) ;

3. h i = h i -1 якщо  1 ≤  ≤ 2 ; h i =2h i -1 якщо  1 >;
якщо 2 < .

де  - кут між градієнтами на попередньому та поточному кроці;  1 і  2 - задані граничні значення вибираються суб'єктивно (наприклад,  1 = π/6,  2 = π/3).

Вдалині від оптимуму напрямок градієнта змінюється мало, тому крок можна збільшити (другий вираз), поблизу оптимуму напрямок різко змінюється (кут між градієнтами) R ( x ) великий), тому h скорочується (третій вираз).

Для оцінки приватних похідних використовуються різницеві методи:

1 . Алгоритм із центральною пробою

2. Алгоритм із парними пробами

де g j - пробний крок по j -й змінної, вибирається досить малим для різницевої оцінки похідної.

Перший алгоритм вимагає менших витрат у порівнянні з другим (зазвичай витрати виражаються кількістю обчислень критерію оптимальності), але дозволяє отримати рішення менш точно, ніж другий, і це похибка залежить від величини пробного кроку.

На рис. наведено одну з можливих траєкторій пошуку мінімуму двовимірної функції градієнтним методом (поряд з іншими методами, що розглядаються нижче).

Умовою закінчення пошуку може бути трохи модуля градієнта R ( x ) , тобто. | grad R ( x ) | <  .

Рис. Ілюстрація отримання похідної з центральною та парними пробами.

приклад 1.

Потрібно знайти мінімум функції

R ( x 1 , x 2 ) = х 1 3 + 2 х 2 2 - 3х 1 - 4x 2 ,

2. Інтервал пошуку квадрат: х 1поч = -2, х 1кон = 2, х 2поч = -2, х 2кон = 2.

3. Початкова точка: х 10 = - 0,5, х 20 = -1.

4. Параметри пошуку: коефіцієнт кроку h = 0,1, пробний g = 0,01, похибка  = 0,01.

5. Алгоритм методу: алгоритм 1 (х i +1 =х i - h grad R ( x i ) ).

6. Алгоритм корекції кроку: без корекції коефіцієнта пропорційності кроку ( h = const).

7. Спосіб обчислення похідної: обчислення gradR із парними пробами.

Результати обчислень. У початковій точці обчислюємо градієнт функції:

Значення критерію R = 7,3750. Робимо робочий крок за формулою 5, отримуємо

х 1 = - 0,275, х 2 = - 0,2.

У новій точцізнову обчислюємо похідні:

Значення критерію R = 1,3750.

Робимо робочий крок, отримуємо x 1 = 0,002, х 2 = 0,280.

Таблиця 18

			dR/dx 1	dR/dx 2

В останній точці модуль градієнта менший за задану похибку (0,0063< 0,01), поэтому поиск прекращается.

Побудувати залежність градієнта від № кроку

приклад 2.

Відрізняється від попереднього лише величиною коефіцієнта пропорційності кроку h , тепер h = 0,4. Нижче, у табл. 19 наведено лише перші 14 кроків (як і в попередньому випадку). Доцільно зіставити їх шляхом побудови траєкторій пошуку при обох значеннях h у координатах х 1 – х 2 .

Таблиця 19

			dR/dx 1	dR/dx 2

У цьому випадку пошук має явно коливальний характер, погано наближаючись до рішення.

номер ітерації	параметр оптимізаціїh = 0,4	параметр оптимізаціїh=0, 1

Рис. 2.5. Порівняння збіжності градієнтного методу під час використання різного кроку.

Метод якнайшвидшого спуску.

Основним недоліком градієнтного методу є необхідність частого обчислення похідних від R ( x ) . Цього недоліку позбавлений метод якнайшвидшого спуску, який у наступному.

У поточній точці обчислюється grad R ( x ) , а потім у напрямку градієнта шукається min R ( x ) . Практично це може бути здійснено будь-яким методом одновимірної оптимізації (пошук по одному напрямку - напрямку градієнта), що найчастіше використовується скануваннядо першого локального мінімумуу напрямку grad R ( x ) .

В результаті далеко від оптимуму ефективність методу підвищується, ми швидше потрапляємо в район оптимуму, в околиці якого ефективність методу знижується через часті зміни напряму пошуку і наближається до ефективності методу градієнта.

Метод, як і всі градієнтні методи, має невисоку ефективність в яружнихфункціях. У ряді випадків можна підвищити швидкість виходу в район оптимуму пред'явленням невисоких вимог до точності пошуку min у напрямку (задається величиною h - кроком пошуку за напрямом).

Умовою закінчення може бути трохи модуля градієнта R ( x ) | gradR ( x ) | <  . Можна також використовувати й небагато прирощень за змінними в результаті кроку, але тільки в тому випадку, якщо на цьому кроці ми "проскочили" оптимум, інакше може виявитися, що небагато кроку обумовлена не близькістю до оптимуму, а трохи коефіцієнта пропорційності кроку h .

У ряді випадків використовують зменшення кроку пошуку оптимуму за напрямом після кожної зміни напрямку. Це дозволяє з більшою точністю щоразу знаходити оптимум, але різко знижує ефективність пошуку в яружних функціях. Метод використовується для локалізації "дна яру" у спеціальних яружних методах. Умовою закінчення пошуку у разі є досягнення заданої малої величини кроку.

Одна з можливих траєкторій пошуку мінімуму двовимірної функції методом якнайшвидшого спуску наведена на рис. вище.

приклад.

Для порівняння з методом градієнта розглянемо рішення попереднього прикладу при h = 0,1.

Результати розрахунків. Розрахунок похідних детально розглянуто вище, тому не наводиться. Нижче, у табл. 20 наводяться результати руху градієнтом з постійним кроком.

Таблиця 20

			dR/dx 1	dR/dx 2

У наступній точці (0,400, 2,00) значення критерію (R = -0,256) виявляється гірше, ніж у останній ( R = -2,1996). Тому в знайденій точці оптимуму за напрямом знову обчислюємо градієнт і по ньому робимо кроки, допоки не знайдемо найкращу точку (табл. 21).

Таблиця 21

	dR/dх 1	dR/dх 2
Другий пошук за градієнтом




Третій пошук за градієнтом



Четвертий пошук за градієнтом



П'ятий пошук за градієнтом

Метод сполучених градієнтів (пропустити).

Градієнтні методи, що базуються лише на обчисленні градієнта R ( x ) , є методами першого порядку, тому що на інтервалі кроку вони замінюють нелінійну функцію R ( x ) лінійної.

Більш ефективними можуть бути методи другого порядку, які використовують при обчисленні не тільки перші, а й другі похідні від R ( x ) у поточній точці. Однак у цих методів є свої проблеми, що важко вирішити - обчислення других похідних у точці, до того ж далеко від оптимуму матриця других похідних може бути погано обумовлена.

Метод сполучених градієнтів є спробою поєднати переваги методів першого та другого порядку з виключенням їх недоліків. на початкових етапах(далеко від оптимуму) метод веде себе як метод першого порядку, а в околицях оптимуму наближається до методів другого порядку.

Перший крок аналогічний першому кроці методу якнайшвидшого спуску, другий і наступний кроки вибираються щоразу у напрямі, утвореному вигляді лінійної комбінації векторів градієнта у цій точці і попереднього напрями.

Алгоритм методу можна записати так (у векторній формі):

Величина  може бути приблизно знайдена з виразу

Алгоритм працює в такий спосіб. З початкової точки х 0 шукають min R ( x ) у напрямку градієнта (методом якнайшвидшого спуску), потім, починаючи з знайденої точки і далі, напрямок пошуку minвизначається за другим виразом. Пошук мінімуму за напрямом може здійснюватися у будь-який спосіб: можна використовувати метод послідовного сканування без корекції кроку сканування при переході мінімуму, тому точність досягнення мінімуму за напрямом залежить від величини кроку h .

Для квадратичні функції R ( x ) рішення може бути знайдено за п кроків ( п - Розмірність завдання). Для інших функцій пошук буде повільнішим, а в ряді випадків може взагалі не досягти оптимуму внаслідок сильного впливуобчислювальних помилок.

Одна з можливих траєкторій пошуку мінімуму двовимірної функції методом сполучених градієнтів наведена на рис. 17.

Розмір: px

Починати показ зі сторінки:

Транскрипт

1 Курс: Методи оптимізації в машинному навчанні, Просунуті методи багатовимірної оптимізації Розглянемо задачу безумовної оптимізації в багатовимірному просторі: f(x) min x R N. Раніше для вирішення цього завдання були розглянуті методи покоординатного та градієнтного спуску, метод Ньютона, а також комбіновані методи. У всіх цих підходах черговий напрямок оптимізації d обчислюється лише з використанням інформації від оракула у поточній точці x. Таким чином, траєкторія оптимізації не враховується. У методах оптимізації, що розглядаються нижче, черговий напрямок оптимізації d суттєво залежить від траєкторії оптимізації і, зокрема, залежить від попередніх напрямків d,...,d. Розв'язання СЛАУ за допомогою методу сполучених градієнтів Розглянемо задачу мінімізації квадратичної функції з позитивно-визначеним гесіаном: Прирівнюючи до нуля градієнт f, одержуємо: f(x) = xt Ax x T b min x, A = A T. () f(x) = Ax b = Ax = b. Таким чином, задача мінімізації f еквівалентна рішенню СЛАУ Ax = b. Назвемо набір векторів (d i ) сполученим щодо позитивно-визначеної матриці A, якщо виконано умову: d T i Ad j = i j. Прикладом сполучених напрямків є набір власних векторівматриці A. Справді, у цьому випадку d T i Ad j = i d T i d j =. Остання умова виконано, т.к. власні вектори, що відповідають різним власним значенням, ортогональні, а серед власних векторів з однаковим власним значеннямзавжди можна вибрати ортогональний набір. Набір сполучених векторів є лінійно-незалежним. Розглянемо нетривіальну лінійну комбінацію сполучених векторів: α i d i =, α i. Домножимо ліворуч це рівняння на d T j A для деякого j. В результаті отримаємо: i d T j Ad i = j = j =. Остання умова випливає з того, що матриця A є строго позитивно визначеною. З лінійної незалежності випливає, що сполучений набір (d i ) N є базисом всього простору rn. Зокрема, рішення СЛАУ x можна розкласти за цим базисом з деякими коефіцієнтами α i: Домножуючи це рівняння зліва на d T j A, отримуємо: d T j Ax = N x = N α i d T j Ad i = α j α j = dt j Ax α i d i. () = dt j b d T j Ad. () j це не зовсім так при використанні адаптивної корекції довжини кроку Насправді набір сполучених векторів можна розглядати як ортогональний базис щодо скалярного твори x,y= x T Ay. Звідси стає очевидним лінійна незалежністьвекторів, а також те, що матриця A повинна бути позитивно визначеною (інакше не буде скалярного твору).

2 Остання рівність випливає речей, що x рішення СЛАУ, тобто. Ax = b. Тут стає очевидною перевага сполученого набору векторів щодо інших базисів для пошуку x: для сполученого набору коефіцієнти розкладання α j обчислюються аналітично. Пошук x за формулою () з коефіцієнтами () можна у вигляді ітераційного процесу: x =, x + = x +α d, α = dt b d T Ad, =,...,N. Через війну x N+ = x. Тепер отримаємо аналогічний ітераційний процес пошуку x, який починається з довільного ненульового вектора x. Для цього розкладемо вектор x x по сполученому базису: Домножуючи цю рівність на d T j A зліва, отримуємо: x x = N d T j A(x x) = j j j = dt j A(x x) α i d i. = dt j (b Ax) = dt j g = dt j g j d T j Ad. (4) j Тут і далі через g j позначається градієнт функції f у точці x j. Для квадратичної функції gj = Axjb. Доведемо останній перехід у формулі (4): (j) d T j (g j g) = d T j (Ax j b Ax +b) = d T j A j α i d i = α i d Tj g. (5) Таким чином, отримуємо наступний ітераційний процес пошуку x з довільного початкового наближення x: x + = x +α d, α = dt g d T Ad, =,...,N. (6) Можна показати, що даний ітераційний процес є процесом якнайшвидшого спуску для функції f вздовж сполучених напрямків (d i ) N. Для цього достатньо переконатися в тому, що коефіцієнт α j, що обчислюється за формулою (4), доставляє мінімум α функції f (xj+αdj). Дійсно, α f (x j + α d j) = f (x j + α j d j) T d j = g T j + d j = (Ax j + j Ad j b) T d j = α = αj = (Ax j b) α j = g T j d j d T j g j =. (7) Одночасно тут було доведено, що g Tj + dj =. Покажемо, що g T j+ d i = i j. Дійсно, g T j+ d i = (Ax j+ b) T d i = (A(x + j α i d i) b) T d i = (Ax b) T d i + α i d T i Ad i = g T d i g T i d i =. Остання рівність випливає з (5). Умова ортогональності градієнта g j+ всім попереднім напрямам оптимізації означає, що x j+ доставляє мінімум функції f лінійної оболонці L(d,...,d j). Більше того, можна показати, що точка x j +αd j мінімізує функцію f у лінійній оболонці L(d,...,d j) для будь-якого α. Дійсно, f(x j + αd j) T d i = (A (x j + α d j) b) T d i = (A x j b) T d i + αd T j Ad i = g T j d i =. i< j. Таким образом, при движении вдоль очередного сопряжённого направления оптимизацию по предыдущим направлениям проводить не нужно. Это одна из відмінних рисметоду сполучених напрямів. Для проведення ітераційного процесу (6) необхідно вказати повний набірсполучених напрямків для матриці A. Розглянемо наступну схему генерації d: d = g, d + = g + + d, β = gt + Ad d T Ad, =, ..., N. (8) Вірна наступна послідовність міркувань: d = g L (g), g = g + Ad = g Ag L (g, Ag), d = g + β d L (g, Ag), g = g + α Ad L (g, Ag, Ag), d = g +β d L (g, Ag, Ag),...

3 В результаті набір (d,...,d i ), що генерується за схемою (8), і набір (g,...,g i ) належать одному і тому ж лінійному простору L(g,Ag,...,A і g). Отже, вектор Ad i можна уявити у базисі (d,...,d ), > i, а вектор g i можна у базисі (d,...,d i ): Ad i = g i = a j d j, (9) j = i b j d j. () j= Покажемо тепер, що схема (8) дозволяє побудувати набір сполучених напрямків для матриці A. Крім того, покажемо, що при її використанні g T d i = i< и g T g i = i <. Проведём доказательство по индукции. Пусть известно, что g T d i = i <, d T Ad i = i <, g T g i = i <. Докажем, что аналогичные утверждения верны для +. Из рассуждений (7) следует, что g T + d =. Далее g T +d i = (g +α Ad) T d i = g T d i +α d T Ad i =. Последнее утверждение выполняется, исходя из предположения индукции. Покажем теперь, что d T + Ad i = i. Используя (8), получим, что d T + Ad = (g + +β d) T Ad = g T + Ad +g T + Ad =. Далее с помощью (9) заключаем, что для i < d T + Ad i = (g + +β d) T Ad i = g + Ad i = g + a j d j = Осталось показать, что g T + g i = i <. Используя (), получаем i g T + g i = g T + b j d j = j= j= i b j g T + d j =. j= a j g T + d j =. В результате получаем, что набор {d,...,d N } действительно является сопряжённым относительно матрицы A. Заметим, что в доказательстве сопряжённости существенно используется тот факт, что первое направление выбирается в соответствии с антиградиентом. При другом выборе d итерационный процесс (8) не приводит к набору сопряжённых направлений. С помощью доказанных выше свойств g T d i = i < и g T g i = i < можно несколько упростить выражения для α и β в итерационных процессах (6), (8): α = g d d T Ad β = gt + Ad d T Ad = g (g +β d) d T Ad = gt g d T Ad, = gt + (g + g) d T Ad = gt + g + α g T g. () В результате получаем итоговый алгоритм решения СЛАУ Ax = b, который получил название метода сопряжённых градиентов:. Задаём начальное приближение x и требуемую точность ε;. Инициализация d = g, = ;. x + = x +α d, где α = gt g d T Ad ; 4. Если α d < ε, то стоп; Пространства такого вида известны в линейной алгебре как пространства Крылова j=

4 5. d + = g + + β d, де β = gt + g + g T g; 6. = + та перехід до кроку. Цей алгоритм гарантовано сходить до рішення за N кроків, де N розмірність простору рішення. На кожному кроці ітераційного процесу потрібно проводити лише одне множення матриці A на вектор d (вектор ax + при цьому обчислюється как ax + Ad). Інші операції в алгоритмі є векторними: скалярний добуток двох векторів та сума двох векторів. На рис. показаний приклад застосування цього алгоритму. Для порівняння показано також траєкторію методу якнайшвидшого спуску Рис. : Приклад роботи методу якнайшвидшого спуску (зелена траєкторія) та методу сполучених градієнтів (червона траєкторія) для оптимізації квадратичної функції. Основні переваги методу сполучених градієнтів пов'язані з просторами великої розмірності. При N методи рішення СЛАУ, засновані на матричних розкладаннях, наприклад, розкладанні Холецького або QR-розкладанні, перестають бути застосовними через необхідність ітераційного перерахунку матриць, розмір яких збігається з розміром матриці A. Навпаки, у методі сполучених градієнтів всі операції проводяться тільки для векторів розмірності N, а найскладніша операція в алгоритмі це множення матриці на черговий вектор d. Для ряду матриць спеціального виду, наприклад, розріджених матриць або матриць, що представляють базис Фур'є, таке множення може бути ефективніше загального випадку. Розглянемо тепер завдання оптимізації довільної гладкої функції f. Тоді в схемі методу сполучених градієнтів матрицязамінюється на гессианh в поточній точціx. Практично цей підхід перетворюється на метод Ньютона, у якому квадратична апроксимація функції мінімізується за допомогою сполучених градієнтів. Тому метод сполучених градієнтів має квадратичну швидкість збіжності в малій околиці оптимального рішення. Для того, щоб застрахуватися від можливої неадекватності квадратичного наближення функції f у поточній точці, у методі сполучених градієнтів пропонується вирішувати одновимірне завдання оптимізації при русі вздовж чергового напрямку d: x + = x + d, x = argmin f (x + d) . Зауважимо, що у разі відпадає необхідність обчислення гессиана, і метод перетворюється на метод оптимізації першого порядку. При використанні формули () для β відповідний метод сполучених градієнтів отримав назву Флетчера-Рівса (Fletcher-Reeves). У методі Полака-Ріб'є (Pola-Ribiere) пропонується використовувати іншу формулу для β: β = gt + g + g T + g g T g. Для випадку квадратичної функції остання формула перетворюється на формулу (), т.к. g T + g =. Однак, для довільної функції вона дозволяє досягти більш стійкої та якісної роботи методу. У методі сполучених градієнтів напрямок d + залежить від d, отже, неявно залежить від попередніх напрямів d,...,d. Для підвищення стійкості роботи методу неквадратичної функції пропонується встановлювати β = після кожної N-ой ітерації, тобто. періодично «очищати» передісторію, де можуть накопичуватися невдалі напрями. Обнулення відповідає вибору напряму оптимізації по антиградієнту. На рис., a показаний приклад застосування методу сполучених градієнтів без використання обнулення. В результаті в ході ітерацій метод «проскочив» оптимальну точку [,] T за рахунок 4

5 (a) (b) (c) Мал. : Приклади методу сполучених градієнтів для функції Розенблока. Випадок (a): без використання обнулення β, всього 64 ітерації, випадок (b): з використанням обнулення, всього 6 ітерацій, випадок (c): використання bactracing, всього 6 ітерацій. сильну залежність від попередніх напрямів. Навпаки, використання обнулення (див. рис., b) дозволило успішно виявити мінімум меншу кількість ітерацій. Як було зазначено вище, у методі сполучених градієнтів черговий напрямок оптимізації вибирається таким чином, щоб під час руху вздовж нього зберегти мінімум у всіх попередніх напрямках. За рахунок цього вдається уникнути ступінчастої поведінки, характерної для покоординатного та градієнтного спуску. Проте, такий підхід неявно припускає, що вздовж чергового напряму проводиться точна оптимізація, т.к. надалі повернення до цього напряму не заплановано. На рис., c показаний приклад роботи методу, в якому на етапі одновимірної оптимізації використовується bactracing. В результаті метод починає працювати вкрай нестійко, а збіжність досягається лише за 6 ітерацій. Насправді метод сполучених градієнтів може стійко сходитися і з використанням неточної одновимірної оптимізації. Однак її використання пов'язане з певними ризиками. Квазі-ньютонівські методи У квазі-ньютонівських методах оптимізації перерахунок здійснюється за формулою x + = x α S g. () Тут S деяка позитивно визначена матриця. Умова позитивної визначеності S гарантує можливість зменшення функції f вздовж напрямку d = Sg. Дійсно, α f(x αs g) = g T S g<. α= Если S = I, то () переходит в градиентный спуск. Если S = H, то () переходит в метод Ньютона. По аналогии с методом сопряжённых градиентов, рассмотрим сначала квази-ньютоновские методы для случая минимизации квадратичной функции (). Введем обозначения: δ = x + x = α S g, γ = g + g. Для квадратичной функции γ = g + g = Aδ. В результате [γ γ... γ N ] = A[δ δ... δ N ]. Пусть в первый момент времени задано некоторое начальное приближение x. Положим S = I 4 и будем пересчитывать S по правилу S + = S + C, где C некоторая матрица. Проведем N шагов вида () и получим набор {δ,...,δ N }, набор {γ,...,γ N } и набор матриц S,S,...,S N. Если оказывается, что S N [γ γ... γ N ] = [δ δ... δ N ], то матрица S N = A и следующий шаг по схеме () соответствует шагу Ньютона, т.е. x N+ = x. По аналогии с методом сопряжённых градиентов, в котором существуют разные формулы для β и, соответственно, разные итерационные схемы пересчета d, для квази-ньютоновских методов также предложено несколько способов выбора C. Однако, все эти способы гарантируют выполнение следующих свойств:. Метод сходится за N шагов для квадратичной функции; 4 это соответствует использованию направления антиградиента 5

6 (a) (b) Мал. : Приклад роботи методу L-BFGS для функції Розенблока. Випадок (a): точна одновимірна оптимізація, випадок (b): використання методу Флетчера. Для квадратичної функції набір векторів (δ,...,δ N) утворює сполучений базис щодо матриці A; Матриця S завжди залишається позитивно визначеною. Остання властивість важлива для принципової можливості зменшення f на кожній ітерації. Розглянемо кілька схем вибору С: Схема DFP (Davidon-Fletcher-Powell). Схема BFGS (Broyden-Fletcher-Goldfarb-Shanno). S + = S + δ δ T δ T γ S γ γ T S γ T S. γ (S + = S + + γt S) γ δ T T T T T T T T T T S δ. Схема L-BGFS (Limited Memory BFGS). Формула перерахунку аналогічна BFGS, але для S = I: Підставляючи цю формулу в (), отримуємо: (S + = I + + γt γ) δ δ T γ T δ γ T δ γ T +γ δ T γ T δ. d + = S + g + = g + + A δ + B γ, A = gt + δ (γ T δ + γt γ) γ T δ + gt + γ γ T δ, B = gt + δ γ T δ. Зауважимо, що всі квазіньютонівські методи є методами першого порядку. У разі квадратичної функції напрямку δ,...,δ N є сполученими щодо A. Тому в цьому випадку всі квазіньютонівські методи еквівалентні методу сполучених градієнтів. При цьому суттєвим моментом є використання напрямку антиградієнта у перший момент часу (S = I). З використанням інший матриці S генеровані напрями оптимізації δ,...,δ N втрачають властивості спряженості, а сам метод властивість гарантованої збіжності за N ітерацій. На рис., а показаний приклад роботи методу L-BFGS для функції Розенблок. Зауважимо, що на відміну від методу сполучених градієнтів, у квазіньютонівських методах немає необхідності «очищати» передісторію і періодично прирівнювати S = I. Крім того, квазіньютонівські методи є більш толерантними до використання неточної одновимірної оптимізації (див. рис., b). ). 6

Лекція 4 МЕТОДИ ПЕРШОГО ПОРЯДКУ Постановка задачі Нехай дана функція f (), обмежена знизу на множині R n і має безперервні похідні приватні у всіх його точках. Потрібно знайти локальний мінімум

ЛЕКЦІЯ 6 1. Метод покоординатного спуску 2. Градієнтний метод 3. Метод Ньютона Методи вирішення кінцевих задач оптимізації (Завдання безумовної оптимізації) -1- Чисельні методиНЛП Завдання пошуку безумовного

Методи оптимізації, ФКН ВШЕ, зима 2017 Практичне завдання 2: Просунуті методи безумовної оптимізації. Термін здачі: 9 березня 2017 року (23:59). Мова програмування: Python 3. 1 Алгоритми У цьому завданні

Методи оптимізації, ФКН ВШЕ, зима 2017 Семінар 7: Квазиньютонівські методи 21 лютого 2017 р 1 Квазиньютонівські методи 11 Мотивація Розглянемо стандартне завдання гладкої безумовної оптимізації: min f(x),

САНКТ-ПЕТЕРБУРГСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Факультет прикладної математики процесів управління О. П. ІВАНОВ, Ю. В. ОЛЕМСЬКИЙ ПРАКТИКУМ ЗА КРАМНИЧИМИ МЕТОДами МІНІМІЗАЦІЯ КВАДРАТИЧНОЇ ФУНКЦІЇ Методичні

ЛЕКЦІЯ 11 БАГАТОМІРНА ІНТЕРПОЛЯЦІЯ ЗАДАЧА ОПТИМІЗАЦІЇ На минулій лекції були розглянуті методи розв'язання нелінійних рівнянь Були розглянуті двоточкові методи, що використовують локалізацію кореня,

УДК 59.8 О. А. Юдін, аспірант ПОШУК МІНІМУМУ ФУНКЦІЙ, ЯКІ МАЮТЬ РОЗРИВИ ПРИВАТНИХ ВИРОБНИЧИХ Проаналізовано можливі варіанти вирішення задачі пошуку мінімуму функції, яка має розрив приватної

ЛЕКЦІЯ 14 Чисельні методи нелінійного програмування 1. Градієнтний метод 2. Теореми збіжності 3. Метод Такахаші (дуалізація/градієнтний метод) -1- Чисельні методи НЛП Завдання пошуку безумовного мінімуму:

ОПТИМАЛЬНИЙ ГРАДІЄНТНИЙ МЕТОД МІНІМІЗАЦІЇ ВИПУКЛИХ ФУНКЦІЙ М. В. Довгополік [email protected] 10 листопада 2016 р. Анотація. У доповіді обговорюється у певному сенсі оптимальний градієнтний метод

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Ортогональні та ортонормовані набори векторів З визначення кута між векторами

К. В. Григор'єва Методичні вказівки Тема. Методи вирішення задачі мінімізації квадратичної функції Факультет ПМ-ПУ СПбГУ 7 р. ЗМІСТ. ПОСТАНОВКА ЗАДАЧІ. ДОПОМОЖНІ ВІДОМОСТІ.... МЕТОДИ СПУСКУ

Семінари з лінійних класифікаторів Євген Соколов 27 жовтня 2013 р. Нехай X R d простір об'єктів, Y = ( 1,+1) безліч допустимих відповідей, X l = (xi, y i) l i=1 навчальна вибірка. Кожен об'єкт

ЛЕКЦІЯ 15 1. Метод Ньютона (метод другого порядку) 2. Метод зовнішніх штрафів 3. Метод внутрішніх штрафів 4. Метод покоординатного спуску -1- МЕТОД НЬЮТОНА Нехай f двічі безперервно функція, що диференціюється

Лекція 5 Постановка та можливі шляхи вирішення завдання навчання нейронних мереж Часткове завдання навчання Нехай у нас є деяка нейромережа N. У процесі функціонування ця нейронна мережа формує вихідний

Санкт-Петербурзький державний політехнічний університет Факультет технічної кібернетики Кафедра розподілених обчислень та комп'ютерних мереж Реферат Тема: «Методи оптимізації без обмежень,

ЛЕКЦІЯ 6 СПЕКТРАЛЬНІ ЗАВДАННЯ. Методи спуску На минулій лекції було розглянуто ітераційні методи варіаційного типу. Для системи Au = f, для якої виконується A = A, було введено функціонал Φ(u, u)

Тема 2-11: Власні вектори та власні значення А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія

Лекція 0. Розділ 4. Матриці. У цьому розділі ми розглянемо основні види матриць, операції з них, поняття рангу матриці та його застосування до розв'язання систем лінійних алгебраїчних рівнянь. 4. Основні поняття.

РОЗДІЛ 8. ПІДПРОСТОР 1 1. СУМА І ПЕРЕСІЧ ПІДПРОСТОР Множина L векторів лінійного простору X називається підпростором, якщо з того, що x, y L випливає, що αx + βy L при будь-яких комплексних

Московський державний технічний університет імені Н.Е. Баумана Факультет «Фундаментальні науки» Кафедра «Математичне моделювання» À.Í. Êàíàòíèêîâ,

Методи оптимізації у машинному навчанні, ВМК+Фізтех, осінь 2017 Практичне завдання 3: Метод бар'єрів. 1 Метод бар'єрів Термін здачі: 15 листопада 2017 (середа), 23:59 для ВМК 17 листопада 2017 (п'ятниця), 23:59

Перелік методів, включених у завдання до екзаменаційних квитків. Квиток 20 (мітка) Метод Ньютона Квиток 12 (мітка) калькулятор http://math.semestr.ru/simplex/simplex_manual.php Побудувати подвійне завдання

Тема 2-4: Підпростори А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія для механіків (2 семестр)

Елементарна теорія похибок. Рішення СЛАУ. 4. Норми в кінцевомірних просторах... 4. Обумовленість СЛАУ............ 5.3 Ітераційні методи вирішення лінійних систем................... ...

Симплекс-метод розв'язання задач лінійного програмування Основним чисельним методом розв'язання задач лінійного програмування є так званий симплекс-метод. Термін «симплекс-метод» пов'язаний з тим

Московський державний технічний університет імені Н.Е. Баумана Факультет «Фундаментальні науки» Кафедра «Математичне моделювання» À.Í. Êàíàòíèêîâ

А.П.Попов Методи оптимальних рішень Посібник для студентів економічних спеціальностей вузів Ростов-на-Дону 01 1 Введення У прикладній математиці є кілька напрямків, націлених насамперед

1 Матеріали до настановної лекції Питання 37. Ітеративні методи розв'язання рівнянь. Метод Ньютон. 1. Розв'язання скалярних рівнянь. Метод Чебишева Розглянемо рівняння f(x) =0,x і нехай на зазначеному

Московський державний технічний університет імені НЕ Баумана Факультет «Фундаментальні науки» Кафедра «Вища математика» Е Б Павельєва Я Томашпільський Лінійна алгебра Методичні вказівки

Розв'язання нелінійних рівнянь Не завжди алгебраїчні або трансцендентні рівняння можуть бути вирішені точно Поняття точності рішення має на увазі:) можливість написання «точної формули», а точніше кажучи

Лінійні перетворення Визначення лінійного перетворення Нехай V лінійний простір Якщо зазначено правило, за яким кожному вектору x з V ставиться у відповідність єдиний вектор y з V то

Системи лінійних рівнянь алгебри Основні поняття Системою лінійних рівнянь алгебри (СЛАУ) називається система виду a a a, a a a, a a a Її можна представити у вигляді матричного рівняння

ЗАСТОСУВАННЯ МЕТОДУ НЬЮТОНА У СИМЕТРИЧНІЙ ПРОБЛЕМІ ВЛАСНИХ ЗНАЧЕНЬ О.О. Хамісов Іркутський держуніверситет Існує безліч різних проблем, таких як стійкість системи лінійних рівнянь або

УДК 519.615.7 Фізико-математичні науки Пропонується квазіньютонівський чисельний метод безумовної мінімізації, показуються його переваги перед методом Бройдена Флетчера Гольдфарба Шанно. Ключові

Лекція3. 3. Метод Ньютона (дотичних. Задамо деяке початкове наближення [, b] і лінеаризуємо функцію f(в околиці за допомогою відрізка ряду Тейлора f(= f(+ f ")((-. (5 Замість рівняння))

Розв'язання задач з алгебри за другий семестр Д.В. Горковець, Ф.Г. Корабльов, В.В. Корабльова 1 Лінійні векторні простори Завдання 1. Чи лінійно залежні вектори R 4? a 1 = (4, 5, 2, 6), a 2 = (2, 2, 1,

Лабораторна робота Методи мінімізації функцій однієї змінної, що використовують інформацію про похідні цільової функції Постановка задачі: Потрібно знайти безумовний мінімум функції однієї змінної (

Методи розв'язування сіткових рівнянь 1 Прямі та ітераційні методи В результаті різницевої апроксимації крайових завдань математичної фізики виходять СЛАУ, матриці яких мають наступні властивості:

МОСКІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ім. М.В.ЛОМОНОСОВА Механіко математичний факультет Кафедра обчислювальної математики І. О. Арушанян Практикум на ЕОМ Безумовна мінімізація функцій багатьох змінних

Чисельні методи Лінійної Алгебри У розділі «Чисельні методи лінійної алгебри» розглядаються чисельні методи вирішення систем лінійних рівнянь алгебри (СЛАУ) і чисельні методи вирішення завдань

41 Симетричні оператори Лінійні оператори, що діють у евклідових просторах, мають додаткові властивості порівняно з лінійними операторами у векторних просторах без скалярного.

1. Векторний аналіз. 1.1. Короткий теоретичний вступ. Фізичні величини, Z Z (M) для визначення яких K достатньо задати одне число Y K (позитивне або негативне Y) називаються

4 Ітераційні методи вирішення СЛАУ Метод простих ітерацій При великій кількості рівнянь прямі методи вирішення СЛАУ (за винятком методу прогонки) стають важкореалізованими на ЕОМ насамперед через

Лекція 3 Чисельне рішення СЛАУ Згадаймо основні результати, отримані на попередній лекції 1 Норма вектора = u Були введені наступні норми вектора: =1 1 Октаедрична норма: 1 = max u, де p = 2 Кубічна

Лекція 11. Оптимальне управління 11.1 Постановка задачі Задано динамічну систему з управлінням, що описується системою диференціальних рівнянь у формі Коші ( ẋi = f i (x, u(t)), (11.1) (i = 1,...,

САНКТ-ПЕТЕРБУРГСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Факультет прикладної математики процесів управління М. Е. АББАСОВ МЕТОДИ ОПТИМІЗАЦІЇ Навчальний посібник Санкт-Петербург 014 УДК 519.85 ББК.18 А 13 Р е

ЛІНІЙНА АЛГЕБРА РАЗОМ З MAPLE Усов В.В. 1 Скалярне твір в арифметичному просторі 1.1 Визначення. Основні властивості Скалярний добуток (X, Y) векторів X = (x 1, x 2, ..., x n), Y =

Методи розв'язування сіткових рівнянь 1 Прямі та ітераційні методи В результаті різницевої апроксимації крайових та початково-крайових завдань математичної фізики виходять СЛАУ матриці яких мають наступні

Math-Net.Ru Загальноросійський математичний портал Л. Н. Полякова, Деякі методи мінімізації максимуму квадратичних функцій, Владикавк. матем. журн., 2006, том 8, номер 4, 46 57 Використання Загальноросійського

6 Методи наближення функцій. Найкраще наближення. Розглянуті в попередньому розділі методи наближення вимагають суворої належності вузлів сіткової функції результуючого інтерполянту. Якщо не вимагати

Тема 2-15: Ортогональність О. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія для механіків (2 семестр)

12. Лінійні оператори на векторних просторах (продовження) Єдиність жорданової нормальної форми F алгебраїчно замкнуте поле Теорема 9. τ Нехай A M n (F), A J і A J де J, J жорданові матриці.

1. Чисельні методи розв'язування рівнянь 1. Системи лінійних рівнянь. 1.1. Прямі методи. 1.2. Ітераційні методи. 2. Нелінійні рівняння. 2.1. Рівняння з одним невідомим. 2.2. Системи рівнянь. 1.

79 Лінійні функції Визначення та приклади лінійних функцій Визначення Будемо говорити, що на лінійному просторі L задана функція від одного вектора, якщо кожному вектору x L зіставлено число (x)

МІНІСТЕРСТВО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ ПЕНЗЕНСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ЧИСЛІВІ МЕТОДИ ЛІНІЙНОЇ АЛГЕБРИ Методичні вказівки до виконання лабораторних робіт ПЕНЗА 7 Наведено методику та

Міністерство освіти і науки Російської Федерації Федеральна державна бюджетна освітня установа вищої професійної освіти «Комсомольський-на-Амурі державний технічний

Мітюков В.В. Ульянівське вище авіаційне училище цивільної авіації інститут, програміст ОВТІ, [email protected]Універсальне моделювання дискретно заданих множин безперервними залежностями.

Плани відповідей на питання екзаменаційних білетів держекзамену з курсу ОПТИМІЗАЦІЯ ТА ЧИСЛІВІ МЕТОДИ, лектор проф. М. М. Потапов Питання: 4. Симплекс-метод для канонічного завдання лінійного програмування:

345 4 Ряди Фур'є по ортогональних системах функцій Нехай ((x - ортогональна система функцій в L[;]) Фур'є по

Чисельна оптимізація Функції багатьох змінних: умовна оптимізація 26 листопада 2012 р. Чисельна оптимізація 26 листопада 2012 р. 1 / 27 1,..., J k = 1,...,

Таблиця 1

Таблиця 2

№	Вид квадратичної форми	Вид обмежень
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.	2

Таблиця 3

Координати початкової точки
№	1	2	3	4	5	6	7	8	9	10	11	12	13
	3	0	-2	5	6	7,5	3	3	1	4	7	4	7
	-2	1	12	-3	-2	-2	0	4	2	3	1	4	3

Етапи проектування

Постановка задачі відповідно до варіанта завдання.
Подання заданої квадратичної форми у матричній формі запису.
Дослідження характеру екстремуму.
Опис у матричній формі методу пошуку та складання алгоритму.
Упорядкування структурної схеми алгоритму пошуку.
Програмування серед Math Cad.
Розрахунок.
Висновки щодо роботи.

Постановка та вирішення завдань багатовимірної безумовної оптимізації

Завдання багатовимірної безумовної мінімізації

Для заданої функції вирішити задачу багатовимірної безумовної мінімізації f(x 1 , x 2), xX (XR) та початкової точки x 0 .
Нехай f(x) = f(x 1 , x 2 , … ,x n) – дійсна функція n змінних, визначена на множині X Ì R n . Точка x* Î X називається точкою локального мінімуму f(x) на множині X, якщо існує така
e-околиця цієї точки, що для всіх x з цієї околиці, тобто, якщо
|| x - x * | |< e, выполняется условие f(x*) £ f(x).
Якщо виконується умова f(x*)< f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x*Î X называется точкой глобального минимума f(x) на множестве X, если для всех x Î X выполняется условие f(x*) £ f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X. Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.

Теорема 1 (необхідна умова екстремуму)
Нехай є точка локального мінімуму (максимуму) функції f(x) на множині і диференційована в точці х *. Тоді градієнт функції у точці х* дорівнює нулю:

Теорема 2 (достатня умова)
Нехай функція f(x) у точці х* двічі диференційована, її градієнт дорівнює нулю, а матриця Гесс є позитивно визначеною (негативно визначеною), тобто.

Тоді точка х* є точка локального мінімуму (максимуму) функції на множині .
Для визначення символу матриці Гессе вживається критерій Сильвестра.

Завдання 1.1 Знайти мінімум функції класичним методом, використовуючи необхідні та достатні умови.
Це завдання вирішуватимемо для функції f(x 1 ,x 2).
Початкова точка x 0
; x 0 = (1.5,1.5)

Знайдемо приватні похідні першого порядку функції f(x):

; ; ;

Знайдемо похідні другого порядку функції f(x):

Складемо матрицю Гессе

Класифікуємо матрицю Гессе, використовуючи критерій Сільвестра:

Отже, матриця є позитивно визначеною.
Використовуючи критерії перевірки достатніх умов екстремуму, можна дійти невтішного висновку: точка - є точкою локального мінімуму.
Значення функції у точці мінімуму:
;

Завдання 1.2
Знайти мінімум цієї функції шляхом градієнтного спуску з дробленням кроку.

Метод градієнтного спуску з дробленням кроку

Метод градієнтного спуску є одним із найпоширеніших і найпростіших методів вирішення задачі безумовної оптимізації. Він заснований на властивості градієнта функції, згідно з яким напрям градієнта збігається з напрямом якнайшвидшого зростання функції, а напрямок антиградієнта – з напрямком найшвидшого зменшення функції. При розв'язанні задачі безумовної мінімізації за напрямок спуску з точки x(m) вибирається

p(m) = –g(x(m)) = –f”(x(m)).

Таким чином, ітераційна процедура для цього методу має вигляд

x(m+1) = x(m) – a(m)g(x(m)) (*)

Для вибору кроку a(m) можна використовувати процедуру дроблення кроку, яка полягає у наступному. Довільно фіксують початкове значення кроку a(m) = a(m – 1) = a. Якщо у точці x(m+1), обчисленій відповідно до (2.24), виконується нерівність

f(x(m+1)) > f(x(m)),

то крок дробиться, наприклад, навпіл, тобто. належить a(m +1) = 0.5a(m).
Застосуємо метод градієнтного спуску з дробленням кроку для мінімізації квадратичної функції

В результаті вирішення цього завдання було знайдено мінімум
x* = (-0.182; -0.091),
значення функції f(x*) = -0.091,
кількість ітерацій n=17.