На головну    

 Завдання квадратичного програмування з параметром в правих частинах обмежень та її застосування при формуванні портфеля цінних паперів - Економіко-математичне моделювання

Реферат

Дипломна робота містить 78 сторінок, 2 додатки, 1 рисунок.

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

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

Зміст

1. Введення 3

2.Аналітіческій огляд 9

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

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

3.1 Постановка завдання: 11

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

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

3.4. Метод субоптімізаціі на многовидах. Опуклий випадок. 18

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

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

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

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

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

4.1 Постановка завдання 52

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

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

5.Економіческая частина 57

6.Бібліографія 65

1. Введення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 (3.1.1)

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

Має місце також умова невід'ємності компонентів вектора x:

x і 0.

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

 (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, lkі Dk- множники Лагранжа умов Куна-Таккера. Запишемо систему 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) має властивість єдиності, і серед Dj, що задовольняють умовам Куна-Таккера існує негативне Dj0, тобто

 (3.4.5)

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

 (3.4.6)

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

 (3.4.7)

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

 f (x * ')

© 8ref.com - українські реферати