Задача квадратичного програмування з параметром в правих частинах обмежень і його применение

1.

ВВЕДЕНИЕ

.

2.АНАЛИТИЧЕСКИЙ ОБЗОР.

3. ТЕОРЕТИЧНА ЧАСТЬ.

3. ЗАВДАННЯ КВАДРАТИЧНОГО ПРОГРАМУВАННЯ (НЕПАРАМЕТРИЧЕСКИЙ СЛУЧАЙ).

3.1 Постановка задачи:

3.2 Умови оптимальності в завданню (3.2).

3.3. Базис завдання квадратичного програмування. Оптимальний і невырожденный базисы.

3.4. Метод субоптимизации на многообразиях. Опуклий случай.

3.5 Метод субоптимизации на многообразиях. Завдання квадратичного программирования.

3.6. Метод субоптимизации на многообразиях в завданню квадратичного програмування. Теоретичне обоснование.

3.7. Обчислювальна схема алгоритму субоптимизации для завдання квадратичного программирования.

3.8. Деякі особливості обчислювальної схеми методу субоптимизации на многообразиях для завдання квадратичного программирования.

4. ЗАВДАННЯ КВАДРАТИЧНОГО ПРОГРАМУВАННЯ З ПАРАМЕТРОМ У ПРАВЫХ ЧАСТИНАХ ОГРАНИЧЕНИЙ.

4.1 ПОСТАНОВКА ЗАДАЧИ.

4.2 Деякі властивості рішення параметричної завдання квадратичного программирования.

4.3 Застосування методу субоптимизации на многообразиях до вирішення параметричної завдання квадратичного программирования.

5.ЭКОНОМИЧЕСКАЯ ЧАСТЬ.

6.БИБЛИОГРАФИЯ.

7.ПРИЛОЖЕНИЕ 1…65.

8.ПРИЛОЖЕНИЕ 2…67.

9.РИСУНОК 1…78.

1.

Введение

.

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

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

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

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

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

Через це стає можливим створення рекуррентных формул, що пов’язують матриці системи лінійних рівнянь сусідніх допоміжних завдань.

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

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

Доведені теореми, складові теоретичний фундамент алгоритму, наведено доказ збіжності запропонованої обчислювальної процедуры.

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

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

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

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

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

Складено і налагоджена програма мовою З++, функціонуюча серед операційними системами UNIX (AIX, Solaris) і навіть Microsoft Windows, реалізує описані алгоритми. Зазначена програма застосована до вирішення завдання про пошуку оптимальних інвестицій у завданню про портфелі цінних паперів, ці рішення і текст програми приведено у приложениях.

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

2.Аналитический обзор

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

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

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

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

3. Теоретична часть.

3. Завдання квадратичного програмування (непараметрический случай).

3.1 Постановка задачи:

Завданням квадратичного програмування називатимемо завдання наступного вида:

(3.1.1).

тут x-вектор стовпець розміру n, Звектор-строка розміру 1? n, D — матриця розміру n? n, симетрична і неотрицательно певна (D? 0). b — стовпець довжини m. A — матриця розміру m? n, ранг її дорівнює m (R (A) = m).

Наявне також умова неотрицательности компонентів вектора x:

x? 0.

Оскільки наявність компонента Cx не надає істотно на результати, викладені у справжньої роботи, будемо без обмеження спільності припускати вектор З нульовим. У такій постановці завдання приймає вид:

(3.1.2).

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

3.2 Умови оптимальності в завданню (3.2).

Умови оптимальності в завданню (3.2) є формулювання умов Куна-Таккера з цією завдання. Будемо розглядати таку форму записи умов Куна-Таккера для завдання опуклого программирования:

(3.2.1).

У нашому випадку получим:

(3.2.2).

Тут Aiстовпчики матриці A довжини m, Di стовпчики матриці D довжини n, Lk — рядки матриці A довжини n, ej — n-мерные стовпчики одиничної матриці. Тут і далі xi — компоненти оптимального вектора завдання x, ?k і ?k — множники Лагранжа умов Куна-Таккера. Запишемо систему 3.2.2 на більш узагальненої форме:

(3.2.3).

де складові стовпчики P0, … Pm+2n кожен довжиною m+n є стовпчиками блокової матриці P, має наступний вид:

(3.2.4).

У такому вигляді умови Куна-Таккера (3.2.3) можна записати у ще простішому виде:

(3.2.5).

Оскільки розглянута нами завдання є саме опуклого програмування, зазначені умови існування мінімуму є одночасно необхідними і достатніми. Доказ зазначених умов можна знайти у [1,2].

3.3. Базис завдання квадратичного програмування. Оптимальний і невырожденный базисы.

Оскільки ранг матриці A дорівнює m (див 3.1), система векторов.

є лінійно незалежної системою векторів. У той самий час, легко видно, що лінійна оболонка, напнута на систему векторів P збігаються з простором Em+n, тобто L (P)=En+m.

Отже із системи векторів 3.2.4 можна утворити кінцеве число базисів N евклидова простору En+m, які у собі вектори P1,. Pm. Такі базиси простору En+m називатимемо базисами завдання квадратичного програмування, і позначати наступним образом:

(3.3.1).

Для спрощення схеми алгоритму, запишемо базис (3.3.1) наступного виде:

(3.3.2).

Тут ?1 і ?2 — набори індексів. Що стосується, якщо ?1=?2 вважатимемо базис U?1,?2 породжених одним безліччю індексів ?=?1.

(3.3.3).

Коефіцієнти розкладання вектора b по базису U?1,?2 називатимемо засадничими перемінними, інші коефіцієнти — небазисными переменными.

Базис U?1,?2 назвемо оптимальним, якщо його базисні перемінні задовольняють умовам Куна-Таккера (3.2.3).

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

(3.3.4).

Завдання (3.1.2) називатимемо невырожденной, якби її базиси невырождены. Інакше назвемо завдання вырожденной.

3.4. Метод субоптимизации на многообразиях. Опуклий случай.

Аби вирішити завдання (3.1.2) пропонується використовувати метод.

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

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

(3.4.1).

Припустимо, що завдання має єдине рішення, тобто мінімум цільової функції буває у єдиною оптимальної точці x*. І тут завданню (3.4.1) еквівалентна задача:

(3.4.2).

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

Припустимо, що з завдання (3.4.2) перебування оптимального рішення істотно простіше, ніж для вихідної завдання (3.4.1). І тут, перебираючи якимось чином різноманітні безлічі індексів ?k, є подмножествами повного набору індексів {1,.n}, і вирішуючи кожного з них завдання (3.4.2), використовуючи? k замість ?*, визначити дані безліч індексів ?*.

Припустимо також, що завдання (3.4.2) має здатність.

одиничності, тобто система векторів {L1,. Lm, ej (j? ?(x*)}- лінійно незалежна. У порушення властивості одиничності завдання пошуку оптимального вектора завдання (3.4.2) ускладнюється, й надалі на цей випадок розглядатися не будет.

Алгоритм перебору множин індексів ?k грунтується ось на наступній лемме.

Основна лемма:

Нехай x* оптимальна точкою задачи:

(3.4.3).

де X? — лінійне розмаїття, обумовлений наступним образом:

(3.4.4).

Припустимо, що завдання (3.4.3) з вимогою (3.4.4) має здатність одиничності, серед? j, які відповідають умовам Куна-Таккера існує негативне? j0, т. е.

(3.4.5).

Нехай? «- безліч індексів, отримане з? відніманням індексу j0:

(3.4.6).

Тоді, якщо x* «- оптимальний вектор завдання.

(3.4.7).

то справедливо неравенство:

f (x* ").

(3.4.8).

Доказательство.

Позаяк у зв’язку з виконанням співвідношення (3.4.6) й універсального визначення множин X? і X? «випливає, що X? »? X? то має місце нерівність f (x* ")? f (x*). Отже як доказ співвідношення (3.4.8) досить показати, що f (x* ")? f (x*).

Припустимо, що тут інше. Тоді точка x* оптимальна для завдань (3.4.3) і (3.4.7), і задовольняє умовам Куна-Таккера в обох задачах:

(3.4.9).

(3.4.10).

Додамо в праву частина рівності (3.4.10) член 0ej0. Оскільки, за припущенням (3.4.5) леми коефіцієнт ?j0 різниться від нуля, отримуємо розкладання вектора градієнта функції f у системі векторів {L1,. Lm, ej (j? ?(x*)}. Отримуємо в протиріччя з умовою одиничності, отже, і з вимогою основний леммы.

Доведена лема вказує можливий напрямок перебору множин індексів ?k (отже і різноманіть), який зменшує значення цільової функції f (x).

З доведеною леми вытекает.

Алгоритм пошуку оптимального вектора.

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

Блок 1. Визначається допустима початкова точка x1 для вихідної завдання. Це то, можливо точка, отримувана з допомогою алгоритму побудови початкового базису лінійного симплекс-метода, або ж рішення, у певному сенсі близькій лінійної завдання. Передбачається ?1=?(x1), k=1.

Блок 2. Перебуває оптимальний вектор x*k для завдання.

Якщо x*k виявляється припустимою для вихідної завдання (3.4.1), відбувається перехід до блоку 3, інакше здійснюється перехід до блоку 4.

Блок 3. Обчислюється значение.

Якщо.

то зв’язку з виконанням умов Куна-Таккера для вихідної завдання (3.4.1) точка x*k оптимальна точкою завдання (3.4.1) і алгоритму заканчивается.

Если.

то предполагаем.

й відбувається перехід до блоку 2.

Блок 4. Оскільки оптимальна точка допоміжної завдання виявилася неприпустимій для вихідної, вибираємо як нової початковій точки найближчу до неї точку, допустиму для вихідної завдання (3.4.1), й лежачу на прямий, що з'єднує оптимальні точки допоміжної завдання, т. е.

Далі вважаємо ?k+1=?(xk+1), замінюємо k на k+1, і переходимо до блоку 2.

Отже побудований итерационный процес, дозволяє здійснити спрямований перебір множин індексів? k, дозволяє знайти оптимальний вектор вихідної завдання. Відповідність процедури розглянуть позже.

3.5 Метод субоптимизации на многообразиях. Завдання квадратичного программирования.

Розглянемо застосування методу субоптимизации, розглянутої в (3.4) до завданню квадратичного програмування (3.1.2). Як було раніше зазначено, умовою успішного застосування методу субоптимизации на многообразиях в завданню опуклого програмування є істотна простота виконання завдання (3.4.2) проти вихідної завданням (3.4.1).

Розглянемо еквівалентну (3.1.2) задачу:

(3.5.1).

Запишемо умови Куна-Таккера для завдання (3.5.1) з довільним набором індексів? :

(3.5.2).

Використовуючи раніше запроваджені позначення (3.2.3−3.2.4), систему умов Куна-Таккера (3.5.2) можна записати наступним образом:

(3.5.3).

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

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

Операція А. Нехай для деякого набору індексів ?0 визначено оптимальна точка x* і множники Лагранжа ?*k і ?*j задовольняють умовам Куна-Таккера що з оптимальним вектором x. Розглянемо допоміжне розмаїття.

(3.5.4).

Операція, А полягає у перебування оптимального вектора x*(?), і навіть множників Лагранжа, які відповідають умовам Куна-Таккера завдання мінімізації квадратичного функціоналу на різноманітті (3.5.4).

Запишемо умови Куна-Таккера з цією допоміжної задачи:

Якщо набір індексів ?0 породжує базис, що існує розкладання вектора Pm+j0 у цій базису, має наступний вид:

(3.5.6).

Підставляючи це розкладання в (3.5.5), та враховуючи оптимальність набору x*,?*,?*, отримуємо такі висловлювання для компонент оптимальної крапки над різноманітті (3.5.4):

(3.5.7).

Отже, у разі, якщо набір індексів ?0 породжує базис, операція, А здійснюється тривіально, й висловлюваннями (3.5.7).

Суть операції А полягає у перебування оптимальної крапки над новому різноманітті (3.5.4) відомою оптимальної точці на різноманітті (3.4.4).

Операція Б. Нехай деяке допоміжне розмаїття X?0(?1) таке, що з базисних компонент вектора x звернулася до ноль:

(3.5.8).

Суть операції Б полягає у переході від розмаїття X?0(?1) до іншого різноманіттю X?1, відповідному набору індексів ?1, визначеного наступним образом:

(3.5.9).

тобто. індекс j0 з (3.5.4) замінюється на індекс r з (3.5.8).

З огляду на (3.5.8), розкладання (3.5.5) на різноманітті X?0 можна наступним образом:

(3.5.10).

Аналогічно випадку, розглянутому в операції Хіба, коли він має місце разложение:

(3.5.11).

причому виконано соотношение.

(3.5.12).

то умовам Куна-Таккера для завдання (3.5.1) відповідної набору індексів ?1, задовольняють перемінні, одержувані з допомогою наступних формул:

(3.5.13).

где.

(3.5.14).

З огляду на вищеописані умови, операція Б виявляється здійсненною у разі, коли набором індексів ?0 і ?1 відповідає базис U?1,?0. Операція Б є аналогом блоку 4 загальної схеми методу субоптимизации на многообразиях для завдання опуклого программирования.

Для наочності можна визначити безліч L?1,?0 що було пряму, породжувану базисом U?1,?0 наступного вида:

(3.5.15).

Тут — коефіцієнти розкладання вектора P0, а xir — вектора Pm+n+r по базису U?1,?0. Зауважимо, що L?1,?0(0) є оптимальний вектор різноманіття (3.5.4) при ?=. Перехід від цього точки до нового різноманіттю з допомогою операції Б є рух щодо зазначеної прямий від дельта рівного нулю у позитивний (як буде показано пізніше) бік.

3.6. Метод субоптимизации на многообразиях в завданню квадратичного програмування. Теоретичне обоснование.

Зауважимо, що й безліч індексів? породжує базис U?, то завдання (3.5.1), відповідна цьому безлічі індексів має єдиний оптимальний вектор x*, володіючи у своїй властивістю одиничності, запровадженим раніше завдання опуклого программирования.

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

Лема 1. Нехай вектора x0, x1 задовольняють системі рівнянь умов Куна-Таккера і нехай f (x) — неотрицательно певний квадратичний функціонал виду xTDx, а ?1 вектор ограниценных за сигналом множників Лагранжа, які відповідають умовам Куна-Таккера що з вектором x1. Тоді має місце таке неравенство:

(3.6.1).

Доказательство:

Перетворимо ліву частина наступним образом:

Тут можна скористатися умовою виконання теореми Куна-Таккера:

Необхідну нерівність безпосередньо випливає з останнього соотношения.

Слідство. Нехай x0, x0(?) — оптимальні точки завдання (3.5.1) з певним безліччю індексів? і допоміжної завдання пошуку мінімуму на різноманітті (3.5.4). Тоді має місце неравенство:

Доказ. Оскільки x0, x0(?) задовольняють умовам Куна-Таккера, то виконується нерівність Леми 1:

Особливості рішень x0, x0(?) праву частина нерівності можна записати як.

що доводить справедливість следствия.

Лема 2. Нехай x0, x1 — оптимальні точки різноманіть X?0 і X?1 відповідно, задовольняють умовам Куна-Таккера що з множителями Лагранжа ?0 і ?1. Тоді справедливо соотношение:

Доказ: Аналогічно доведенню Леми 1, отримуємо, что:

Складаючи ці дві рівності, получаем:

З виконання умов Куна-Таккера слід, что:

Розкриваючи дужки у частині нерівності отримуємо дані неравенство.

Нижче буде доведено теорему, дає напрямок руху й умови застосування операції А.

Теорему 1. Нехай оптимальна точка x0 — оптимальна точка різноманіття X?0, причому сукупність індексів ?0 породжує базис U?0. Тоді, якщо серед множників Лагранжа, відповідних x0, існує негативний (припустимо, що вона має індекс j0).

то новий набір індексів.

також породжує базис і в єдиною оптимальної точці на різноманітті виконано умова.

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

з іншого боку, з умови единственности,.

Отже, якщо оптимальна точка на новому різноманітті існує, то доказуване нерівність вірно. Існування ж оптимальної точки випливає того факту, новий набір індексів породжує базис. Це правда, якщо коефіцієнт ?j0j0 в розкладанні (3.5.6) не дорівнює нулю.

Припустимо, що це коефіцієнт нульовий. І тут, з слідства з леми й умови заперечності ?j0 квадратичний функціонал f (x) виявляється негативно певним. Теорему доказана.

Теорему 1 вказує можливий напрямок руху по многообразиям з допомогою операції А. Перехід від розмаїття X?0 до урізноманітнення здійснюється з допомогою руху по многообразиям X?0 (?) за умов зростання? від нуля до деякою величины.

З огляду на виду нового безлічі індексів величина ?0 визначається з умови звернення до нуль відповідного множника Лагранжа:

Сформулюємо і доведемо аналогічну теорему для операції Б:

Теорему 2. Нехай ?0 і ?1 набори індексів, які породжують базис U?1,?0, такі, что:

причому у розкладанні.

(3.6.2).

коефіцієнт. Нехай також і безлічі индексов.

існує оптимальний вектор для завдання (3.5.1), причому такий, що вона є допустимим для вихідної завдання (3.1.2), т. е.

Тоді, якщо x1 — оптимальна точка завдання (3.5.1) на різноманітті X?1, то ?1 породжує базис U?1, а оптимальна точка x1 належить прямий (3.5.15):

(3.6.3).

Доказ. Розкладемо вектор P0 по базису U?1, а вектор Pm+n+r по базису U?1,?0 :

підставляючи друге вираження у перше, та враховуючи визначення прямий (3.5.15) отримуємо очевидне следствие:

З іншого боку, враховуючи розкладання (3.6.2), отримуємо, что.

(3.6.4).

А відповідно до лемме 2, имеем:

Звідси й з умови теореми слід, что.

Звідси й з (3.6.4) випливає доказуване нерівність. З іншого боку, з (3.6.4) слід на відміну від нуля коефіцієнта, що зумовлює висновку про лінійної незалежності системи векторів U?1. Це доводить друге твердження теореми.

Теорему 2 вказує можливий напрямок переходу від однієї різноманіття до іншого з допомогою операції Б, стверджуючи позитивність величини кроку ?1 .

3.7. Обчислювальна схема алгоритму субоптимизации для завдання квадратичного программирования.

Раніше (див 3.4) наведено загальна схема алгоритму субоптимизации на многообразиях для випадку завдання опуклого програмування і отримана блокова структура алгоритму. Конкретизуємо тепер структуру блоків для випадку завдання квадратичного программирования.

Блок1.

Визначається початковий набір індексів ?1, який породжує базис U?1, котрій оптимальна точка завдання (3.5.1) є одночасно припустимою для вихідної завдання (3.1.2). Така точка в [2] називається дополняющей.

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

Блок 3. Блок повністю ідентичний наведеній до цього часу описі алгоритму субоптимизации на многообразиях для завдання опуклого програмування.

Блок 2. У цьому блоці визначається рішення допоміжної завдання (3.5.1). Спосіб визначення рішення залежить від попереднього блоку алгоритма:

Блок 2(А). Ця частина блоку набирає чинності після блоку 3. Оптимальний вектор завдання (3.5.1) перебуває в допомогою операції А. Якщо отриманий оптимальний вектор скажімо для вихідної завдання (3.1.2), здійснюється перехід у блок 3. Інакше здійснюється перехід у блок 4.

Критерієм вибору такого кроку є порівняння двох величин:

Перша величина задає момент звернення до нуль обраної розміру ?j0, друга величина задає момент звернення до нуль перша з базисних компонент вектора x. Якщо друга величина виявляється менше першої, це, що новий вирішення завдання (3.5.1), отриманий у результаті операції А є допустимим для вихідної завдання (3.1.2), людству й потрібен перехід у блок 4.

Блок 2(Б). Ця частина блоку набирає чинності після блоку 4. У цьому вся блоці мінімум у завданню (3.5.1) перебуває в допомогою операції Б. Якщо одержуване рішення виявляється допустимим для вихідної завдання (3.1.2), то здійснюється перехід у блок 3. Інакше здійснюється перехід у блок 4.

Критерієм вибору такого кроку щодо них блоку є порівняння двох величин:

Блок 4. Цей блок цілком відповідає відповідному блоку загалом алгоритмі субоптимизации на многообразиях для завдання опуклого программирования.

3.8. Деякі особливості обчислювальної схеми методу субоптимизации на многообразиях для завдання квадратичного программирования.

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

Вище показано, що ухвалено рішення кожної допоміжної завдання методу субоптимизации зводиться для пошуку розкладання деякого вектора R розмірності (m+n) по базису U?1,?2; у своїй на сусідніх ітераціях базиси відрізняються лише якимось однією з векторов.

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

1. Від U?1 до U?2 (?2=?1 j0) з допомогою заміни в базисі вектора Pm+n+j0 на Pm+j0 .

2. Від U?1 до U?2,?1 (?2=?1 j0 U r) з допомогою заміни в базисі вектора Pm+r на Pm+j0 .

3. Від U?2,?1 (?2=?1 j0 U r) до U?2 з допомогою заміни в базисі вектора Pm+n+j0 на Pm+n+r .

4. Від U?2,?1 (?2=?1 j0 U r) до U?2 " ,?2 «(? „2=?2 U r “, ? „1=?1 U r “) з допомогою заміни в базисі вектора Pm+r на Pm+n+r » .

Процедура розкладання вектора R по базису еквівалентна рішенню системи лінійних рівнянь вида.

де B — базисна частина матриці P (тобто матриця, що складалася з шпальт матриці P, відповідних векторах даного базису). Рішення рівняння є процедура, еквівалентна зверненню матриці B.

Із загального виду матриці P (3.2.4) можна отримати роботу загальний вигляд матриці B, котра має блочну структуру наступного вида:

Можна показати, что.

Очевидно, що, знаючи матрицю S1−1 можна легко отримати значення матриці B-1. Використовуючи загальний вигляд переходів, і навіть їх загальну властивість, що зводиться заміні одного вектора в інший, можна застосувати перебування S1−1 відому формулу Фробениуса, й одержати рекуррентные формули, котрі пов’язують матриці S1−1 на сусідніх ітераціях. Це дозволяє уникнути безпосереднього звернення матриці кожному кроці алгоритму, вдаючись щодо нього через певний проміжок часу з єдиною метою корекції накопиченої помилки обчислення.

4. Завдання квадратичного програмування з параметром в правих частинах ограничений.

4.1 Постановка задачи.

Завданням параметрического квадратичного програмування з параметром в правих частинах обмежень називатимемо таку завдання опуклого программирования:

(4.1.1).

Потрібна знайти вектор-функцию x*(?), минимизирующую цільову функцію при кожному?. Інтервал зміни параметра може бути необмеженим.

4.2 Деякі властивості рішення параметричної завдання квадратичного программирования.

Нехай отримано вирішення завдання (4.1.1) попри деякий значенні параметра, рівному ?0. Це означає, що отримано вектор x*(?0), і навіть набір індексів ?(?0), і породжений оптимальний базис. Розглянемо багато тих? , котрим це рішення залишається оптимальним і допустимим. І тому запишемо умови Куна-Таккера:

(4.1.2).

Відповідно до постановки завдання, праву частина висловлювання (4.1.2) можна наступного виде:

(4.1.3).

Розклавши вектор R за вказаною базису, і підставивши це розкладання в (4.1.3), одержимо такі висловлювання для коефіцієнтів розкладання (4.1.2):

(4.1.4).

Тут — коефіцієнти розкладання вектора R по базису. Умовою порушення оптимальності рішення є факт звернення до нуль однієї з неотрицательных коефіцієнтів (4.1.4). Звідси випливає, що інтервал, у якому вихідне рішення є оптимальним, є відрізком наступного вида:

(4.1.5).

где.

(4.1.6).

а.

(4.1.7).

З висловів (4.1.4) випливає також те що, що у інтервалах (4.1.5) вектор-функция x*(?) є відрізок прямий у просторі En, і є лінійної. Отже, значення цільової функції на інтервалі є параболу.

4.3 Застосування методу субоптимизации на многообразиях до вирішення параметричної завдання квадратичного программирования.

Безпосередньо з викладеного вище слід алгоритм виконання завдання квадратичного програмування з параметром в правих частинах ограничений:

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

2. З допомогою формул (4.1.6−4.1.7) визначається інтервал у якому отримане рішення залишається оптимальным.

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

5.Экономическая часть.

Розглянемо застосування описаної теорії до завданню визначення оптимального портфеля цінних паперів. Сформулюємо задачу:

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

Покажемо, що зазначену завдання можна зводити до завданню математичного программирования:

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

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

Для переходу від завдання максимізації до завданню мінімізації, запишемо необхідну нам функцію розподілу наступним образом:

Запишемо функцію квантили рівня? з цією функції розподілу:

При заданому рівні? нам потрібно мінімізувати цю функцію, цим, максималізуючи шуканий дохід R .

І тому зауважимо, що випадкова величина (-R) розподілено також із нормальному закону з параметрами. Тоді можна записати функцію розподілу цієї величини, використовуючи функцію Лапласа:

Отже, можна зрозуміти, что:

Означимо квантиль рівня? , тобто. рішення уравнения.

З огляду на монотонність функції Лапласа, нерівність можна записати наступного виде:

Звідси можна легко отримати вираз, дає ключі до виду функції квантили:

З огляду на визначення функції квантили:

отримуємо.

Характеристики розподілу випадкової величини R виглядають наступним образом:

Отже, вихідна завдання зводиться до наступній завданню математичного программирования:

Покажемо, як зазначена завдання математичного програмування може бути зведено до завданню квадратичного програмування з параметром в правих частинах ограничений:

Введемо в розгляд параметр

Тоді завдання можна записати наступного еквівалентному виде:

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

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

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

6.Библиография.

1. Бахшиян Б. Ц., Назиров Р. Р, Эльясберг П. Е. Визначення й корекція руху (який убезпечить підхід) — М.: Наука, 1980.

2. Зангвилл У. И. Нелінійне програмування. Єдиний підхід. — М.: Радянське Радіо, 1973.

3. Муртаф Б. Сучасне лінійне програмування. — М.:Мир, 1984.

4. Припій А.І., Ядыкин Г. Б. Параметрическое квадратичне і лінійне програмування. — Автоматика і телемеханіка, 1978, т.12, NN 2,4.

5. Хедлі Дж. Нелінійне і динамічний програмування. — М.: Світ, 1967.

6. Ядыкин Г. Б. Параметричний метод в завданнях квадратичного програмування з вырожденной квадратичной формою. — Журнал обчислювальної математики математичної фізики, 1975, т.8, N4.

7. Boot J. Quadratic Programming. — Amsterdam: North-Holland Publ. Co., 1964.

8. Van de Pann З. Methods for Linear and Quadratic Programming. — Amsterdam: North-Holland Publ. Co., 1975.