Метод Біла для розв’язку задач квадратичного програмування

Метод Біла для розв’язку задач квадратичного програмування

Метод Біла для розв’язку задач квадратичного програмування

1.     
Теорема Куна-Такера

Центральне місце в теорії нелінійного програмування займає теорема Куна-Такера.

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

   (1)

Побудуємо функцію Лагранжа для даної задачі

         (2)

Якщо виконуються умови регулярності [існує принаймні одна точка , для якої (для всіх )], то має місце наступна теорема.

Теорема 1. Вектортоді і тільки тоді є оптимальним розв’язком задачі (1), коли існує такий вектор, що при і для всіхімає місце нерівність (3)

 (3)

Точка називається сідловою точкою для функції , а теорема теоремою про сідлову точку.

Доведемо умову (3).

Доведення. Нехай і- сідловка точка функції. Якщо в (3) підставити (2), то одержимо

При , .

Права нерівність справедлива при будь-якому , тому

.

Тоді із лівої нерівності отримаємо

при .

Так як при цьому , то .

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

Доведення необхідності умови (3) через його складність не розглядається.

Якщо  і  - диференційовані функції, то (3) еквівалентні наступним локальним умовам Куна-Такера:

     (4)

   (5)

Вираз  означає, що значення частинної похідної функції Лагранжа береться в точці , де   Ці умови можна записати в векторній формі:

 (4’)

 (5’)

В подальшому при розгляданні задачі квадратичного програмування використовуватимуться умови (4) і (5).

2.     
Квадратичне програмування

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

є лінійними функціями, а функція  є сумою лінійної і квадратичної функції:

Квадратична функція  змінних називається квадратичною формою і може бути представлена в наступному виді:

де

При цьому передбачається, що  - симетрична матриця (матриця називається симетричною, якщо ).

Запишемо задачу квадратичного програмування в матричній формі:

при

                            (6)

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

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

Питання про те, чи буде квадратична форма вигнутою або опуклою, залежить від того, чи є вона негативно визначеною, негативно напіввизначеною, позитивно визначеною, позитивно напіввизначеною або взагалі невизначеною.

Квадратична форма  називається від’ємно визначеною, якщо  для усіх , окрім .

Квадратична форма  називається від’ємно напіввизначеною, якщо  для усіх  існує , для якого .

Квадратична форма  називається додатньо визначеною (додатньо напіввизначеною), якщо квадратична форма - від’ємно визначена (від’ємно напіввизначена).

Квадратична форма називається невизначеною, якщо вона позитивна для одних значень  і негативна для інших.

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

Приклад. Задана квадратична форма

.

Привести цю форму до канонічного виду.

Розв’язок. Запишемо матрицю, що відповідає цій квадратичній формі:

.

Перепишемо форму , виділяючи члени, що містять :

.

Доповнюючи вираження, що стоїть в дужках, до повного квадрата, отримуємо

Припустимо, що

        (7)

запишемо квадратичну форму в наступному виді:

де

Із співвідношень (7) маємо

               (8)

Перетворимо :

               (9)

звідки

     (10)

Тоді

Остаточно маємо

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

Перетворенню (10) - матриця

Знайдемо матрицю :

Знайдемо матрицю :

Матриця  відповідає квадратичній формі . Остаточно отримуємо

.

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

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

Теорема 2. Якщо для квадратичної форми

якщо визначники  відмінні від нуля, то цю форму можна трикутним перетворенням привести до виду

де

   (11)

Доведення. Оскільки , то, виділяючи перший квадрат, отримуємо

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

Оскільки , то можна виділити ще один квадрат.

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

….………………………….

або. Оскільки  відмінні від нуля, то. Теорема доведена. Таким чином, знаки коефіцієнтів  визначаються знаками визначників .

Випадок 1. Якщо усі визначники  позитивні, то і усі коефіцієнти  позитивні, отже, квадратична форма позитивно визначена.

Випадок 2. Якщо у ряді  знаки чергуються, то усі коефіцієнти  негативні, в цьому випадку форма є негативно визначеною.

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

Випадок 4. Якщо ранг матриці  рівний , у ряді знаки чергуються і , то квадратична форма негативно напіввизначена.

Випадок 5. Якщо у ряді чисел  немає чергування знаків, причому є негативні , то відповідна квадратична форма є невизначеною.

Приклад. Визначити вид квадратичної форми

Розв’язок. Маємо:

Ряд - знакозмінний, отже, квадратична форма - негативно визначена.

Повернемося до завдання (6), в якому вважаємо, що - увігнута функція. Обмеження в завданні лінійні, тому можна використати умови Куна-Такера (4’) і (5’) для отримання необхідних і достатніх умов оптимальності рішення. Складемо функцію Лагранжа для завдання (6):

    (12)

Оскільки

то

Аналогічно маємо

Сформулюємо умову (4’) для завдання (6). Якщо  - оптимальний план завдання квадратичного програмування, то повинен існувати такий вектор , що задовольняє умові . Введемо допоміжний вектор

Тоді умову (4) можна записати так:

                (13)

Умова (5’) в даному випадку має вигляд . Оскільки обмеження в завданні представлені у вигляді рівнянь, то на вектор  не накладається умова позитивності, умову  виконується при будь-якому допустимому рішенні і його можна виключити. Отже, якщо існують і , ті, що задовольняють умовам

 (14)

то вектор  - оптимальне рішення задачі квадратичного програмування (6). Розглянемо методи рішення завдань квадратичного програмування.

3.     
Метод Біла

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

Нехай задана задача квадратичного програмування:

де квадратична форма відмінно визначена, тобто функція увігнутості.

Припустимо, що систему рівнянь вдалося розв’язати відносноперших змінних:

     (15)

Вираз (15) дозволяє представити як функцію тільки вільних змінних:

 (15’)

дедля усіх і .

Розглянемо випадок, коли залежна змінна, наприклад , тобто незалежними змінними єоднозначно визначається

       (16)

Використовуючи вираз (16), виключимо з інших рівнянь (6) змінну . В результаті одержимо разом з (16) нову систему (17)

      (17)

Це перетворення є аналогічним до перетворення, яке виконується у симплексному методі. За допомогою формули(16) перетворимо вираз для :

Таким чином, відмінність отриманого розв’язку від початкового полягає у тому, що зміннііпомінялися місцями.

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

       (18).

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

 (19)

За допомогою формули (19) перетворимо вирази для  та інших залежних змінних. В результаті число базових змінних збільшилось на одиницю.

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

Приклад. Знайти при обмеженнях

Розв’язок. Ввівши додаткові змінні, запишемо систему обмежень у вигляді

Розв’яжемо відносно базових змінних ісистему обмежень

Припускаючи що вільні змінні дорівнюють нулю, одержимо початковий розв’язок: .

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

Друга точка розв’язку задачі:.

Так як , то додаємо в базис змінну  і визначаємо можливі її зміни. Зі зростанням  значення  може тільки збільшуватись;  перетворюється на нуль при , змінна  перетворюється на нуль при , при . Тому виключимо з базису і введемо змінну.

Для третьої точки маємо:

Третя точка розв’язку задачі:

Тепер збільшимо значення функції , збільшуючи . Зміннаперетворюється в нуль при , при при збільшенні  збільшується;перетворюється на нуль при . Звідси слідує, що замість вводимо нову змінну. Визначимо координати четвертої точки:

Четверта точка розв’язку:

Похідна, а , тому четверта точка дає оптимальний розв’язок задачі.

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

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

Таблиця 1

Сформулюємо правила переходу від однієї таблиці до іншої.

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

2.      Ділять елемент , вибраний у відповідності до правила 1, на модуль відповідного діагонального елементу нижньої частини таблиці . Порівнюють одержане число з частками від ділення нам модуль, знак яких співпадає зі знаком . Рядок, який дає мінімум цих співвідношень, є направляючим. Елемент, який знаходиться на перетині направляючого рядка та направляючого стовпчика, називається розв’язуючим. Якщо направляючий рядок знаходиться у верхній половині таблиці, то у проміжній таблиці на місці змінної, яка відповідає направляючому стовпчику, записують змінну, яка відповідає направляючому рядку. Якщо остання змінна знаходиться в нижній частині, то замінюється на нову змінну.

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

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

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

 (20)

Елементи іобчислюють по аналогічним формулам.

6.      Верхню частину завершальної таблиці переписують без змін з проміжної.

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

Щоб одержати -й рядок нижньої частини кінцевої таблиці, від елементів цього рядка в проміжній таблиці обчислюють елемент другого направляючого рядка, множення на елемент вихідної таблиці, знаходиться на перетині першого направляючого рядка і -го стовпчика. В табл. 2-8 приведено розв’язок задачі.

10

-1

-2

1

0