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

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

Автореферат

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

МЕТОДИ РОЗВ'ЯЗАННЯ НЕГЛАДКИХ ОПУКЛИХ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ ТА ЇХ ЗАСТОСУВАННЯ

Спеціальність: Теоретичні основи інформатики та кібернетики

Ненахов Едуард Іванович

Київ, 2000 рік

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Негладкі опуклі задачі виникають у матричній оптимізації. Це, наприклад, задачі мінімізації суми k найбільших власних чисел симетричної матриці, елементи якої афінним чином залежать від параметрів та задачі з обмеженнями на доданню визначеність. Задачі першого типу виникають при аналізі цілого ряду екстремальних задач на графах оцінювання Ловаса для числа елементів максимально внутрішньо стійкої множини графа, задача про розбиття графа. До другого типу відноситься задача побудови еліпсоїда максимального об'єму, вписаного у многогранник, яка зводиться до задачі опуклого програмування з обмеженнями на додатною визначеність матриці. Далі, це задачі високої розмірності з блочною структурою й порівняно невеликим числом зв'язків між блоками. Використання схем декомпозиції приводить до задач мінімізації негладких функцій від зв'язуючи змінних, або від множників Лагранжа, які відповідають зв'язуючи обмеженням. Такі ж задачі нелінійного програмування, для розв'язання яких застосовується метод негладких штрафних функцій. Ці функції штрафу мають переваги порівняно з гладкими функціями штрафу, бо для них не має необхідності спрямовувати штрафні коефіцієнти до +? і можна обмежитись розв'язуванням задачі за певних значень штрафних коефіцієнтів.

Крім того, негладкі функції виникають при розв'язанні варіаційних нерівностей, у задачах дискретного програмування, в задачах оптимального керування з неперервним і дискретним часом, у моделях ігрового характеру. Функції з розривним градієнтом можуть безпосередньо входити до моделі задачі оптимального планування, проектування або дослідження операцій, як наслідок кусково-гладкої апроксимації техніко-економічних характеристик реальних об'єктів. Актуальність вибору теми досліджень підсилюється й тим, що з прикладної точки зору немає різкої межі між негладкими та гладкими функціями. З позицій прикладної математики та обчислювальної практики функція з градієнтом, що швидко змінюється, “близька” за своїми властивостями до негладкої функції. Все це стало стимулом до всебічного розвитку теорії негладкої оптимізації, вагомий внесок у розвиток якої внесли В.Ф. Дем'янов, Ю.М. Єрмольєв, І.І. Єрьомін, В.С. Михалевич, Б.М. Пшеничний, І.В. Сергієнко, Н.З. Шор, А.С. Немировський, Д.Б. Юдін, Б.Т. Поляк, М.Є. Примак, Л.Г. Хачиян та багато інших. Одними з перших фундаментальних робіт, у яких досліджуються чисельні методи розв'язання негладких опуклих задач математичного програмування, стали монографії В.Ф. Дем'янова, В.М. Малозьомова “Введение в минимакс” (1972), В.П. Булатова “Методы погружения в задачах оптимизации” (1977), Н.З. Шора “Методы минимизации недифференцируемых функций и их приложения” (1979), А.С. Немировського, Д.Б. Юдіна “Сложность задач и эффективность методов оптимизации” (1979).

Для мінімізації опуклих функцій Н.З. Шор побудував метод узагальненого градієнтного спуску (УГС), різні способи вибору кроку для якого були запропоновані Ю.М. Єрмольєвим, Б.Т. Поляком. На Заході перша стаття про достатньо загальні аспекти використання УГС вийшла лише в 1974 році. Там усвідомили важливість градієнтних методів і цей напрямок останні роки розвивався в роботах C. Lemarechal, R. Mifflin, P. Wolfe, K. Kiweel, N. Karmarkar.

Починаючи з 70-х років головні зусилля з розробки детермінованих методів негладкої опуклої оптимізації були спрямовані на побудову алгоритмів, що мають прискорену збіжність. Н.З. Шор запропонував два класи алгоритмів градієнтного типу з розтягненням простору в напрямку градієнту (УГСРП) і алгоритми з розтягненням простору в напрямку різниці двох послідовних градієнтів (r-алгоритми). Один з варіантів методу УГСРП під назвою “метод еліпсоїдів” був розроблений незалежно Д.Б. Юдіним, А.С. Немировським і Н.З. Шором. За складністю r-алгоритми близькі до методу УГСРП і практично забезпечують відносну похибку порядку ? за Nlog1/? кроків, хоча теоретичне обґрунтування їх швидкості збіжності для негладких функцій не наведене.

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

Такі ж процедури, в яких замість центру ваги розглядається чебишевський центр, досліджувалися М.Є. Примаком. На основі модифікацій методів бар'єрних штрафних функцій А.С. Немировським і Ю.Є. Нестеровим побудовані нові алгоритми розв'язання деяких класів задач опуклого програмування - алгоритми внутрішніх точок. У дисертації такого роду методи не використовуються.

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

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

Наукова новизна результатів роботи.

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

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

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

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

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

6. З метою знаходження рівноважних станів моделей математичної економіки вивчені характеристичні властивості моделей обміну, моделей обміну з виробництвом, моделі Ерроу-Дебре, моделі обміну з доплатою Пшеничного і лінійними функціями корисності станів цих моделей.

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

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

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

Реалізація і впровадження. Результати роботи використовувалися для розробки спеціалізованого програмного забезпечення систем проектного аналізу конструкцій (ЦНДІМаш, НДІСталі, НДІТеплотехніки, м. Москва), при дослідженні та розробці теоретичного апарату для автоматизації оптимального конструювання технічних об'єктів на ВО “Завод ім. Малишева” (м. Харків). Багато з теоретичних і прикладних результатів даної роботи є складовою частиною держбюджетних науково-дослідних робіт, госпдоговорів, наприклад: “Підвищення надійності та довговічності машин та конструкцій” (№ДР 04.03/2205), “Розробка теоретичних методів та програмно-алгоритмічних засобів для розв'язання проблеми оптимальної прокладки комунікацій та трас” (№ДР 0195U024584), “Задача проектування та аналізу комунікаційних мереж: моделі, методи, алгоритми та програмне забезпечення” (№Др 0197U015902), ИП.110.08 (1994-1996 рр.), “ВФ.110.03” (1997-1999 рр.).

Апробація роботи. За результатами, що увійшли до дисертації, було зроблено такі доповіді: на 3-му Всесоюзному семінарі “Чисельні методи нелінійного програмування” у 1979 р. (Харків), на науковому семінарі КДУ (науковий керівник - академік АН МРСР П.С.Солтан) у 1983 р. (Кишинів), на Всесоюзній конференції “Оптимизация и ее приложения в экономике” у 1984 р. (Ашхабад), на Республіканському семінарі “Дискретна оптимізація” (науковий керівник - академік АН УРСР І.В. Сергієнко) у 1985 р. (Ужгород), на Всесоюзному семінарі “Оптимизация и ее приложения” у 1986 р. (Душанбе), на симпозіумі “Питання оптимізації обчислень” у 1987 р. (Алушта), на міжнародній конференції “Негладкий анализ и его приложения к математической экономике” у 1991 р. (Баку), на симпозіумі “Питання оптимізації обчислень” у 1993 р. (Київ), на 3-й Українській конференції з автоматичного управління у 1996 р. (Севастополь), на науковому семінарі “Обчислювальна математика” КДУ ім. Т.Г. Шевченка (наукові керівники - академік НАНУ І.І. Ляшко, професор С.І. Ляшко) у 1997 р. (Київ), а також на відомчих конференціях у Москві, Києві.

В цілому дисертація доповідалася на науковому семінарі Інституту прикладного системного аналізу НАН України та Міносвіти України “Прикладні методи системного аналізу” (науковий керівник - академік НАНУ Б.М. Пшеничний), на науковому семінарі Інституту кібернетики ім. В.М. Глушкова НАН України “Теорія оптимальних рішень” (науковий керівник - академік НАНУ Н.З. Шор).

Основні результати дисертації опубліковані у 30 друкованих роботах (1-30), більшість з них (16) написані автором самостійно. У роботах (5, 8, 15) автору належить загальне формулювання другого методу чебишевських центрів, обґрунтування його збіжності у випадку опуклої цільової функції, ним вказані процедури очищення від надлишкової інформації і сформульоване алгоритм з використанням симплексів для розв'язування систем лінійних нерівностей. У роботах (4, 7, 14, 30) автором досліджені лінійні й нелінійні в логарифмах моделі Ерроу-Дебре, модель обміну з періодичними цінами, модель виробництва-обміну з фіксованими бюджетами, модель обміну з доплатою Пшеничного, наведені умови монотонності відображень колективного і надлишкового попитів. У роботах (28, 29) автором проведена редукція задачі вгнутого програмування та проблеми куль до задачі опуклого програмування за умови, що нуль не належить опуклій оболонці, яка натягнута на подвоєні центри даних куль. У роботах (1, 25-27) ним побудовані необхідні умови екстремуму в матричних задачах оптимізації, наведені нижні апроксимації опуклих функцій, а також йому належить остаточне формулювання алгоритмів. Решта робіт написані автором самостійно.

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

Загальний обсяг роботи - 318 сторінок, список літератури налічує 229 найменувань.

2. ЗМІСТ РОБОТИ

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

Розділ 1. Задача опуклого програмування та матричні задачі оптимізації.

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

Нехай задані опуклі неперервні функції цj(x), а також j=0.1,…m, або x?Rn, й опукла замкнена множина ?R№. Задача опуклого програмування полягає у відшуканні вектора x*??, такого, що:

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

Наближення Xk+1 визначаємо так:

Швидкість збіжності методу встановлюється теоремою.

Теорема 1.2. Якщо виконується умова Слейтера, то існує 0<x<1 таке, що для всіх достатньо великих k справедлива оцінка:

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

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

У розділах 1.5, 1.6 досліджуються властивості конуса симетричних додатне визначених матриць і побудовані необхідні умови екстремуму для важливого класу задач математичного програмування - матричних задач оптимізації. Розглянемо простір Mn всіх матриць A розміром NЧN з дійсними елементами aij, де i - індекс рядка, j - індекс стовпця. Так як кожній матриці A?MN можна поставити в однозначну відповідність вектор ??Rn2, котрий можна отримати, якщо стовпці матриці A вишукувати в один довгий стовпець вимірності n2, то між Mn та Rn2 є взаємно однозначна відповідність. Введемо у Rm скалярний добуток:

Він індукує в Mn скалярний добуток:

Нехай тепер Sn?Mn - простір симетричних матриць. Простір Mn розкладається на пряму суму просторів Sn. Позначимо Sn+?Sn конус додатне визначених матриць, конус строго додатних матриць Sn+, і будемо писати A?0.

При проведенні досліджень оптимізаційних задач необхідно дослідити конус, спряжений до конуса Sn+:

Теорема 1.9. Має місце рівність S^n*+=Sⁿ⁺.

Нехай A⁰Sⁿ⁺ і розглянемо конус:

Теорема 1.10:

Якщо A?0, то:

Нехай:

Теорема 1.11. Якщо A0 - розв'язок гладкої екстремальної задачі, то знайдуться числа uk, які не всі дорівнюють нулю, такі, що виконуються співвідношення:

Розглянемо тепер опуклий випадок:

Де функції:

- неперервні опуклі. Знову побудуємо функцію Лагранжа:

I матрицю:

Теорема 1.12. Нехай A0 - розв'язок опуклої задачі. Тоді знайдуться такі числа uk, які не всі дорівнюють нулю, що виконуються співвідношення (2), (3). Якщо виконується умова Слейтера, то множник u0=1 і умови (2), (3) є достатніми.

Зауваження. І в гладкому, і в опуклому випадках матриця L(A,u) симетрична за означенням, але не знак-визначена. Проте вона додатне визначена в розв'язку.

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

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

1) елементи матриці:

- є не перервно-диференційованими функціями:

- гладка функція і позначимо:

2) для k?0 у розв'язку початкової задачі:

Де:

hk(x,p) - неперервна опукла, додатне однорідна функція по:

Формально задача не вкладається прямо в теореми Б.М. Пшеничного, але за допомогою теореми віддільності у просторі:

Rl + 1 Ч Sт

- за зроблених припущень доведена теорема.

Розділ 2. Метод відтинання і його застосування. В основі всіх розглядуваних у роботі багатоточкових методів оптимізації лежить операція відтинання, яка вперше застосована Келлі в алгоритмі січної площини, котрий можна інтерпретувати як алгоритм, в якому на кожному кроці будується гіперплощина, що відокремлює точку, яка не належить опуклій множині, від цієї множини. Ні теоретичні властивості методу відтинання (МВ), ні досвід практичних розрахунків не дає підстав вважати, що цей метод має переваги перед іншими швидкозбіжними методами опуклого програмування. Дійсно, МВ є повільно збіжним, кожне наближення, побудоване цим методом, є неприпустимим. Окрім того, метод потребує резервування великої кількості пам'яті. Частково останній недолік знищується підключенням процедур відсіву надлишкової інформації і можливістю використання одноточкового аналога методу. Проте цей метод має велике значення для теорії оптимізації, тому що дає інструмент теоретичного дослідження і розв'язання деяких задач, недоступних для інших швидко збіжних методів (наприклад, знаходження розв'язку моделі Неймана-Гейла, розв'язку загальної задачі про рівновагу, розв'язку задачі вгнутого програмування, нескінченної опуклої програми). МВ сприяє встановленню тісного зв'язку і походженню різних багатоточкових методів (наприклад, двоїстого МВ і блочного методу опуклого програмування).

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

З використанням МВ знайдено економічний темп зростання моделі Неймана-Гейла, а також стан рівноваги лінійної моделі Ерроу-Дебре. Розділ 2.2 присвячений важливій проблемі МВ - звільненню від надлишкової інформації у випадку, коли цільова функція не є сильно опуклою. Встановлений зв'язок між МВ і блочним методом опуклого програмування дозволяє сформулювати й обґрунтувати модифікацію блочного методу, в якій на кожному кроці здійснюється повна очистка. Характерною особливістю МВ є заміна задачі опуклого програмування послідовністю більш простих задач, що розглядаються на опуклих множинах, які містять припустиму множину початкової задачі. В цьому сенсі МВ можна вважати методом, апроксимуючим припустиму множину зовнішнім чином. Двоїстий МВ є наслідком загального МВ і породжує блочний метод опуклого програмування, який можна інтерпретувати як метод внутрішньої апроксимації припустимої множини. Враховуючи тісний зв'язок між цими двома методами, в розділі 2.3 наведене точне формулювання методу внутрішньої апроксимації пошуку розв'язку задачі опуклого програмування і точки опукло-вгнутої функції.

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

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

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

Перший МЧЦ виник для знаходження точок рівноваги вгнутих ігор багатьох осіб.

А потім був застосований до задачі опуклого програмування. Досліджуваний другий МЧЦ ґрунтується на теоремі 1.2, в якій установлена геометрична швидкість збіжності методу центрів Хьюарда.

Розділ 4. Методи центрованих відтинань. У розділі 4.1 розглядається загальний метод центрованих відтинань у вигляді, що припускає конструктивне знаходження центрів тяжіння відповідних множин. Відома властивість еліпсоїдів, у відповідності до якої пів еліпсоїд E/2, отриманий з еліпсоїду E відтинанням гіперплощиною, яка проходить через центр його тяжіння, можна занурити в еліпсоїд E0 такий, що:

- не залежить від січної площини. Аналогічну властивість мають симплекси.

Нехай у загальному методі центрованих відтинань за опуклі тіла Qk вибираються еліпсоїди. Відповідна конкретизація, яка називається методом еліпсоїдів, збігається з методом узагальненого градієнтного спуску з розтягненням простору. Останній має наглядну геометричну інтерпретацію, яка підтверджує думку про те, що в більшості методів оптимізації в свою чергу закладені оптимізаційні принципи. У даному випадку виявленням цього принципу є знаходження еліпсоїда мінімального за об'ємом. Показано, що в класичній формі узагальненого градієнтного спуску також закладений оптимізаційний принцип. У розділі 4.2 досліджується "багатокроковий" метод еліпсоїдів. Ідея загального методу еліпсоїдів вельми проста. Звичайний метод еліпсоїдів представляє собою найпростіший метод відтинань: кожне нове обчислення функції і субградієнта дозволяє відтяти від поточного локалізатора-еліпсоїда "половину", яку потім приходиться заключати в новий еліпсоїд, щоб підтримати геометричну стабільність форм локалізаторів і гарантувати тим самим помірну (N2) арифметичну вартість ітерації. Після кількох відтинань знову будується новий локалізатор-еліпсоїд. Загальна схема такого підходу запропонована в. Метод забезпечує збіжність за функцією до розв'язку початкової задачі.

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

Розділ 5. Чисельні методи математичної економіки. При застосуванні методів оптимізації для відшукання рівноважних станів моделей математичної економіки попередньо вивчаються характерні властивості моделей.

Теорема 5.2. Якщо додатне однорідне степені a?1 відображення надлишкового попиту задовольняє закону Вальраса, то воно не є монотонним.

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

Для моделі обміну з доплатою Пшеничного у випадку лінійних функцій корисності встановлюється єдність рівноважних цін, монотонність її функції надлишкового попиту, що забезпечує можливість чисельного відшукання рівноважного стану. У розділі 5.3 для знаходження рівноважної ціни лінійної моделі чистого обміну використовується метод чебишевських центрів. Для таких моделей з змінними бюджетами вводиться поняття періодичної ціни і наводиться аналітичний спосіб обчислення рівноважної ціни. У розділі 5.4 наведені рівноважні стани моделей обміну з виробництвом. Для моделей виробництва-обміну з лінійними в логарифмах функціями корисності обчислення рівноважного вектора цін зводиться до розв'язання задачі опуклого програмування, а потім рівноважні асортиментні набори споживачів обчислюються аналітично. Дослідження та чисельне відшукання рівноважних станів моделі Ерроу-Дебре ґрунтується на її зведенні до деякої системі скінченої кількості лінійних рівностей і нескінченої кількості опуклих нерівностей. Зокрема, встановлюється опуклість множини векторів рівноважних цін. Рівноважний стан лінійної моделі Ерроу-Дебре знаходиться також за допомогою методу чебишевських центрів, застосованого до моделі Ерроу-Дебре. Це можливо через те, що функція надлишкового попиту моделі Ерроу-Дебре зі строго вгнутими функціями корисності задовольняє умові виявленої переваги.

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

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

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

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

ВИСНОВКИ

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

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

2. Сформульовані достатні умови розв'язності не комбінаторними методами проблеми куль.

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

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

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

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

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО В ТАКИХ ПРАЦЯХ

1. Немировский А.С., Ненахов Э.И. Многошаговый метод эллипсоидов // Экономика и мат. методы. - 1991. - 27, - №6. - С. 1115-1120.

2. Ненахов Э.И. Об одном варианте субградиентных алгоритмов для минимизации негладкой функции // Теория оптимальных решений: - Киев: Ин-т кибернетики АН УССР, 1979. - С. 38-43.

3. Ненахов Э.И. Об алгоритме e-субградиентного типа для минимизации выпуклой функции // Методы исследования экстремальных задач: - Киев: Ин-т кибернетики АН УССР, 1981. - С. 34-38.

4. Ненахов Э.И., Примак М.Е. Об одном алгоритме отыскания решений модели Эрроу-Дебре // Кибернетика. - 1983. - №3. - С. 127-128.

5. Ненахов Э.И., Примак М.Е. Об одной быстро сходящейся модификации метода чебышевских центров // Там же. - 1983. - №4. - С. 88-91.

6. Ненахов Э.И. Алгоритм проектирования для решения нелинейной задачи о дополнительности // Методы решения задач нелинейного и дискретного программирования: - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1984. - С. 36-40.

7. Ненахов Э.И., Примак М.Е. К исследованию равновесных состояний экономической системы // Кибернетика. - 1985. - №6. - С. 93-99.

8. Ненахов Э.И., Примак М.Е. О сходимости метода чебышевских центров и некоторых его приложениях // Кибернетика. - 1986. - №2. - С. 60-65.

9. Ненахов Э.И. О сходимости одного метода типа отсечения // Исследования методов решения экстремальных задач: - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1986. - С. 17-21.

Размещено на Allbest.ru