Metodi_optimizatsiyi

Це означає, що кутові коефіцієнти дотичних до ліній рівня f 0(x1,x2) = zk і до функції, заданої неявно рівнянням f 1(x1,x2) = 0 співпадають у точках умовного екстремуму (див. рис. 8.1).

Вточці x1 досягається локальний мінімум, в точці x2 — локальний максимум,

вточці x3 — глобальний максимум.

§ 3. Метод множників Лагранжа у випадку обмежень-нерівностей

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

Будемо вважати, що функції f 0(x ), f i(x ), h l(x ), i=1,...,m, l=1,...,k, визначені і

диференційовні у всіх точках простору x En.

Введемо нові допоміжні змінні y = (y1,...,yk), за допомогою яких систему

Тоді задача відшукання екстремумів функції f 0(x ) при умовах (8.15), (8.16) зводиться до рівносильної задачі відшукання екстремумів тієї ж функції при обмеженнях (8.15), (8.17). Під еквівалентністю цих задач розуміється те, що якщо x *— точка локального мінімуму (максимуму) функції f 0(x ) при обмеженнях (8.15),

(максимуму) f 0(x ) при обмеженнях (8.15), (8.17), то x * — точка локального

мінімуму (максимуму) f 0(x ) при обмеженнях (8.15), (8.16).

Для відшукання екстремумів функції f 0(x ) при умовах-рівностях (8.15), (8.17)

введемо функцію Лагранжа

161

Розв’язавши систему (8.18), знайдемо точки ( x, y ), підозрілі на умовний екстремум. Дослідивши їх за допомогою достатніх умов, остаточно отримаємо точки x* = ( x* ,y *) умовного локального мінімуму та умовного локального максимуму функції f 0(x ) при умовах (8.15), (8.17).

Відкинувши змінні y * = ( y1* ,...,y k *), отримаємо точки екстремуму f 0(x ) при умовах (8.15), (8.16).

Приклад 8.4. В n-вимірній одиничній кулі X = {x En : ||x ||2 = (x ,x )≤1} знайти

точку, сума квадратів відстаней від якої до m даних точок x1,...,x m En була б

мінімальною.

За умовою треба мінімізувати функцію

при обмеженні (x,x)≤1.

В прикладі 8.1 було показано, що глобальний мінімум функції f 0(x ) у всьому

i=1

ізаписуємо необхідні умови умовного екстремуму:

162

Розглянемо випадок λ0 = 0. З умови нормування отримаємо |λ1 |= 1≠0, а тому з

першого та другого рівнянь буде x = 0, y = 0. Але ці значення не задовольняють третє рівняння. Отже, при λ0 = 0 система необхідних умов розв’язків не має.

Тому покладемо λ0 = 1 > 0 і перепишемо систему необхідних умов, відкинувши

Отже при λ1 = 0 система несумісна.

б) Розглянемо випадок, коли λ1 ≠ 0. З другого рівняння отримаємо у= 0. Тому

точках x (1) та x

Запишемо гессіан функції Лагранжа по змінних (x , y ) En+1:

163

вточці ( x (1), λ1(1) ) функція f 0(x ) має локальний умовний мінімум.

Вточці ( x (2 ), λ1(2) ) маємо

локальний мінімум, а в точці −x 0/|| x 0|| — локальний максимум.

Оскільки точок, підозрілих на екстремум, тільки дві, а множина Х опукла,

замкнена і обмежена, то ці точки і будуть точками глобальних екстремумів функції f 0(x ) на одиничній кулі.

Розділ 9. Опукле програмування

§ 1. Загальна теорія. Теорема Куна-Таккера

Розглянемо задачу

С: min { f 0 ( x ) : f i ( x ) ≤0 , i = 1,...,m, x X } ,

де X — опукла множина. Якщо функції f i ( x ) , i = 0 , 1,...,m, опуклі на X, то задачу С називають задачею опуклого програмування (ЗОП). До опуклого програмування відносять також задачі максимiзацiї вигляду

max{ g 0 ( x ) : g i ( x ) ≤0 , i = 1,...,m, x X } ,

якщо X опукла множина, функція g 0 ( x ) опукла доверху на X, а система обмежень (тип яких, тобто, "≤", "=", "≥" не є суттєвим) може бути зведена до вигляду f i ( x ) ≤0 , i = 1,...,m, x X , де функції f i ( x ) , i = 1,...,m, опуклі донизу на X.

164

Як i у класичних задачах оптимізації функцією Лагранжа задачі С назвемо функцію

m

L( x , u ) = f 0 ( x ) + ∑ u i f i ( x ) , i=1

де x X , u = ( u 1 , u 2 , . . . , u m ) ≥0 .

Означення 9.1. Пара векторів ( x *, u * ) називається сiдловою точкою функції Лагранжа на множині x X , u ≥0 , якщо x * X , u * ≥0 i для довільних x X , u ≥0

Дiйсно, якби для деякого k було б f k ( x * ) > 0 , то, поклавши u i = 0 при i ≠k i u k = M , де M > 0 як завгодно велике число, ми порушили б нерівність (9.4), а разом з нею i умови теореми. Отже, x * DC .

Покладемо у нерівності (9.4) всі u i = 0 , i = 1,...,m. Отримаємо

додавши їх, отримаємо

i=1

Iз (9.6) та (9.7) випливає правило доповнюючої нежорсткостi (9.2).

Розглянемо тепер праву частину нерівності (9.3). Врахувавши умову (9.2),

для довільних x X отримаємо

165

Тоді, помноживши кожну з нерівностей (9.9) на відповідне u i * ≥0 та додавши їх,

отримаємо

i=1

Далі, розглядаючи нерівність (9.8) на множині DC X та враховуючи (9.10),

остаточно отримаємо: f 0 ( x * ) ≤f 0 ( x ) x DC, тобто x * є оптимальним розв'язком

задачі C

Теорема доведена.

Умови регулярності

Означення 9.2. Якщо для кожного i = 1,...,m існує точка x i DC , в якій

то говорять, що множина DC задовольняє умову регулярності.

Цю умову ми будемо використовувати в еквівалентній формі, яка називається

то говорять, що множина DC задовольняє умову Слейтера.

Геометричний зміст умови Слейтера дуже простий — множина внутрішніх точок множини DC , яка задовольняє умову Слейтера, непорожня: int DC ≠ .

Теорема 9.2 (про еквівалентність умов регулярності).

Умова регулярності (9.11) та умова Слейтера (9.12) еквівалентні.

Доведення. Iз умови Слейтера безпосередньо випливає умова регулярності,

для цього досить i покласти x i = x.

Щоб довести, що із умови регулярності випливає умова Слейтера, покладемо

Оскiльки всі x k DC , а DC — опукла множина, то x DC .

Скористаємось нерівністю Iєнсена для кожного i=1,...,m. Маємо при i=1,...,m

166

внаслідок того, що всі αk ≥ 0 i завжди можна вибрати αk > 0 при k= i i, а при k= i

виконується f i ( x i ) < 0 за умовою регулярності.

Теорема доведена.

Теорема 9.3 (Куна-Таккера). Нехай

С: min { f 0 ( x ) : f i ( x ) ≤0 , i = 1,...,m, x X } —

задача опуклого програмування, допустима множина

DC = { x E n : f i ( x ) ≤0 , i = 1,...,m, x X }

якої задовольняє умову регулярності Слейтера.

Допустимий розв'язок x * DC задачі С є її оптимальним розв'язком тоді i

тільки тоді, коли існує невід'ємний вектор u * ≥0 такий, що точка ( x *, u * ) є сiдловою точкою функції Лагранжа задачі С на множині x X, u≥0.

Доведення.

Достатнiсть випливає з теореми про достатні умови оптимальності. Необхiднiсть. Нехай x * є оптимальним розв'язком задачі C , тобто для

довільних x DC виконується f 0 ( x * ) ≤ f 0 ( x ) .

Введемо у просторі Em+1 множини Y i Z за допомогою співвідношень

Z = { z = ( z 0 , z 1 , . . . , z m ) Em+1: z 0 < f 0 ( x * ) , z i <0 , i=1,...,m},

Y = U Y( x) , x X

де Y ( x ) для довільного x X визначається так:

Y(x ) = { y = ( y 0 , y 1 , . . . , y m ) Em+1: f i ( x ) ≤y i , i=0,1,...,m}.

Геометрична інтерпретація множин Z та Y( x ) приводиться на рис. 9.1.

167

Z = { z = ( z 0 , z 1 ) : z 0 < f ( x* ) , z 1 < 0 } .

Y = { y = ( y 0 , y 1 ) : y 0 ≥f ( x ) , y 1 ≥g ( x ) , x ≥0 } ,

Покажемо, що множини Z i Y опуклі.

Опуклiсть множини Z очевидна: Z є перетином скiнченного числа m+1 пiвпросторiв у просторі E

Аналогiчно стверджуємо, що для довільного x X множина Y( x ) також опукла як перетин скiнченного числа m+1 пiвпросторiв у просторі E

Далі, для довільних y 1, y 2 Y утворимо їх опуклу лінійну комбінацію y = =αy 1 + (1−α) y 2, α [0,1], i покажемо, що y є елементом множини Y.

Оскiльки y 1 Y, то існує x 1 X, для якого y 1 Y(x 1). Аналогiчно, існує елемент x 2 X, для якого y 2 Y(x2). Оскiльки X опукла множина, то опукла лінійна

комбінація елементів x 1 та x 2 — точка x =αx 1 + (1−α) x 2, α [0,1] , є елементом

множини X.

Враховуючи опуклість функцій f i ( x ) , i= 0,1,...,m, отримаємо f i ( x ) = f i (αx 1 + (1−α) x 2 ) ≤ αf i ( x 1 ) + (1−α) f i ( x 2 ) ≤

≤αyi1 + (1−α) yi2 = y i .

Отже, f i ( x ) ≤ y i , i= 0,1,...,m, тобто y Y( x ) Y, що означає опуклість множини Y.

Доведемо, що множини Z i Y не перетинаються. Розглянемо два випадки:

1)x DC i 2) x DC , але x X .

1)Для довільних x DC маємо:

•за умовами теореми: f 0 ( x * ) ≤ f 0 ( x ) ,

•за означенням множини Z : z 0 < f 0 ( x * ) ,

•за означенням множини Y: f 0 ( x ) ≤ y 0 .

Остаточно, для довільних x DC отримаємо: z 0 < f 0 ( x * ) ≤ f 0 ( x ) ≤ y 0 , тобто

z 0 < y 0 .

Це i означає, що множини Z та Y не перетинаються.

2) Оскiльки x DC , то знайдеться хоча б один індекс i , для якого виконується

0 < f i ( x ) . В той же час за означенням множини Y: f i ( x ) ≤ y i , а за означенням

множини Z: z i < 0 .

Таким чином, завжди існує індекс i , для якого z i < 0 < f i ( x ) ≤ y i , тобто z i < y i . А

це означає, що i в цьому випадку множини Z та Y не перетинаються.

Отже, множини Z та Y опуклі i не мають спільних точок. Тоді на основі

від’ємними координатами, то із того, що нерівність (9.13) має місце для довільних y Y , випливає умова: c = ( c 0 , c 1 ,..., c m ) ≥0 .

168

В іншому випадку, тобто, коли б знайшлося хоча б одне c i < 0 серед координат вектора c , то ліва частина нерівності (9.13) стала б необмеженою на

множині Z зверху, а, значить, стала б неможливою для довільних y Y нерівність

(9.13).

Зазначимо, що нерівність (9.13) виконується i в граничних точках множин Z та

Y. Тому, вибравши для довільних x X : y0 = f 0 ( x ) , z 0 = f 0 ( x * ) , y i = f i ( x ) , z i = 0 , i=1,...,m, отримаємо із (9.13) для довільних x X

i =1

Кожний доданок цієї суми недодатний, тому сума буде дорівнювати нулю лише тоді, коли всі її доданки для будь-яких x DC дорівнюють нулю

виконуватись тільки тоді, коли для тих i, для яких c i > 0 , буде f i ( x ) = 0 x DC . А

це суперечить умові регулярності Слейтера для множини DC , за якою існує

допустима точка x DC така, що f i ( x ) < 0 , i=1,...,m. Отже, наше припущення

невірне i c 0 > 0 .

Покладемо ui* = ci /c0 , i=1,...,m, u * = (u1*,...,um*). Очевидно, що u * ≥0 . Тоді

нерівність (9.15) набуде такого вигляду для довільних x X

i =1

169

Покладемо в (9.21) x = x *. Отримаємо

Порiвняння (9.26) i (9.27) дає подвійну нерівність

L ( x *, u ) ≤L ( x *, u * ) ≤L ( x , u * )

x X та u ≥0 , тобто ( x *, u * ) є сiдловою точкою функції Лагранжа задачі С.