Поиск глобального решения в задачах выпуклой максимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

, ц К*

на правах рукописи

Васильев Игорь Леонидович

Поиск глобального

решения в задачах выпуклой максимизации

Специальность 01.01.09 - Математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

ИРКУТСК 1998

Работа выполнена на кафедре методов оптимизации Иркутского Государственного университета

Научный руководитель: доктор физико-математических

наук, профессор Стрскаловский Александр Сергеевич.

Официальные оппоненты: доктор физико-математических

наук, профессор Колоколов Александр Александрович; кандидат физико-математических наук, зав. лаб. ИСЭМ СО РАН Хамисов Олег Валерьевич.

Ведущая организация: Казанский государственный

университет.

Защита состоится 25 декабря 1998 г. в 14 час. на заседании диссертационного совета Д 063.32.04 при Иркутском государственном университете по адресу: 664003, Иркутск, б. Гагарина, 20,1-й корпус ИГУ, математический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Иркутского Государственного университета по адресу: 664003, Иркутск, б. Гагарина, 24.

Автореферат разослан 24 ноября 1998 года.

Ученый секретарь диссертационного совета к.ф.-м.н., доцент

Н.Б. Бельтюков

Общая характеристика

Актуальность темы. Современное развитие производства, техники, внедрение передовых технологий приводят к новым раннее не исследованным оптимизационным задачам и к тому, что оптимизация различных систем продолжает оставаться одной из наиболее актуальных проблем прикладной математики.

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

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

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

В теории и методах невыпуклых экстремальных задач, которым посвящена обширная литература, в настоящий момент принято различать следующие классы невыпуклых задач оптимизации:

1. выпуклая максимизация (или вогнутая минимизация) на допустимом множестве;

2. обратно-выпуклое программирование;

3. (З.с.-программирование.

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

Актуальность работы определяется необходимостью решения важной задачи использования конструктивной теории условий глобальной оптимальности для задач выпуклой максимизации и на ее основе построения для таких задач численных методов глобальной оптимизации с исследованием их глобальной сходимости и верификацией их эффективности.

Для этого необходимы:

1. Специальный аппарат исследования задач выпуклой максимизации, отражающий специфику этих задач и естественным образом порождающий условия глобальной оптимальности.

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

3. Новые методы исследования глобальной сходимости, а также сравнительной эффективности построенных алгоритмов.

Цель работы. Цель диссертационной работы заключается в развитии теории и методов глобального поиска для задач выпуклой максимизации, разработанных Стрекаловским A.C., для квадратичной задачи о назначениях и для задач оптимального управления.

Методы исследования. Для решения рассматриваемой задачи в диссертации используется аппарат выпуклого анализа, математического программирования и оптимального управления.

Научная новизна. В диссертации применены новые методы глобального поиска в задачах выпуклой максимизации для ралее не исследованных этими методами комбинаторной (квадратичной) задачи о назначениях и невыпуклых задач оптимального управления.

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

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

1. Ш-е совещание по глобальной оптимизации, 10-14 декабря, 1995, Зегед, Венгрия [4], [6];

2. 8-ая Франко-Германская конференция по оптимизации, 21-26 июля, 1996, Триер, Германия [5];

3. Байкальский международный студенческий форум "Безопасное развитие регионов", 30 июня-5 июля, 1997, Иркутск [1];

4. Международная конференция "Проблемы оптимизации и экономические приложения", 1-5 июля, 1997, Омск [2];

5. Ляпуновские чтения, 29-31 октября, 1997, Иркутский вычислительный центр СО РАН, Иркутск;

6. 11-ая Байкальская международная школа-семинар " Методы оптимизации и их приложения", 1-12 июля, 1998, Иркутск, Байкал [3].

Результаты работы обсуждались на семинарах:

• лаборатории глобальной оптимизации ИДСТУ СО РАН,

• лаборатории исследования операции ИСЭМ СО РАН,

• объединенном семинаре по методам оптимального управления кафедр методов оптимизации и вычислительной математики ИГУ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, списка литературы из 128 наименований и трех приложений. Основные результаты опубликованы в работах [1]-[6]-

Содержание работы

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

Первая глава диссертации посвящена описанию подхода, предложенного Стрекаловским А.С., исследования и построения метода поиска глобального решения в задаче выпуклой максимизации :

/(х) ->тах, х £Х, (1.1.1)

где / (•) - выпуклая, дифференцируемая и конечная функция, X -выпуклое и компактное допустимое множество из Rn.

В параграфе 1.1 дается следующая характеризация глобального решения задачи (1.1.1).

Теорема 1.1 Если точка z G X является глобальным решением задами (1.1.1), то

(V/(у) ,*-!/>< О 1 Vy: f(y) = f(z), VzeX. J l

Если, кроме того, выполнено следующее предположение:

3 v € Я" : —оо < f (v) < f (z) < +oo, (1.1.3)

то условие (1.1.2) становится и достаточным для того, чтобы z € Аг</max (1.1.1).

Заметим, что из условия (1.1.2) при у — z вытекает классическое условие для стационарной точки в задаче (1.1.1)

(Vf(z),x- z) < 0 Var G X. (1.1.7)

Можно сделать вывод о том, что условие (1.1.2) обобщает классическое условие оптимальности (1.1.7) для невыпуклой задачи выпуклой максимизации.

В параграфе 2.1 для исследования максимизирующих последовательностей задачи (1.1.1) предлагается рассмотреть функцию

p(*)=sup{(V/(y),*-»>: zGX, /(у) =/(*)}. (1.2.1)

Очевидно, что условие (1.1-2) равносильно равенству <р (г) = 0.

Для максимизирующих последовательностей условие оптимальности выглядит следующим образом.

Теорема 1.2 Если последовательность {г*} С X является максимизирующей в задаче (1.1.1) , то

limp(«*)=0. (1.2.3)

*-+оо V ' 4 '

Если для последовательности {г*} СХ выполнено условие

Эие Дп: —оо </(«)</(zk) — 7 < +оо Vfc = 0,1,2,..., (1.2.4)

где 7 > 0 - некоторое число, то условие(1.2.3) становится и достаточным для того, чтобы {.г*} была максимизирующей

lim / (г*) — SUP (/> X). (1.2.4)

fc-ЮО

Далее, предложен один способ построения максимизирующей последовательности для задачи (1.1.1).

Пусть заданы числовая последовательность {е*}, еъ > 0, к =

оо

0,1,2,..., < +оо и некоторая точка zk £ X, к — 0,1,2,.... Тогда

к=0

следующая точка zk+1 £ X выбирается из условия

(V/ (yfc), z*+1 -ук)>9 (**) - ек, (1.2.8)

где f (ук) = / (■£*) . Теорема 1.3 доказывает глобальную сходимость этого метода.

Как было показано, условие (1.1.2) равносильно равенству <p(z) = 0. Иначе говоря, для проверки этого условия необходимо решить следующую задачу одновременной максимизации по переменным х, у

(V/Ы.х - у) -> max, г £ X, f(y) = f(z). (1.3.1)

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

Первая - задача максимизации по х :

(Vf{y),x) -> шах, г £ X, (1.3.2)

где у : f(y) — /(г) - некоторый фиксированный вектор. Будем называть эту задачу линеаризованной задачей.

Вторая задача - это максимизация по v при фиксированном иеХ :

(V/H.ii -v) шах, /(«) = /(г) (1.3.3)

Эту задачу будем называть задачей уровня.

Решение семейства задач (1.3.2) и (1.3.3) для всех точек поверхности уровня является практически невозможным, поэтому возникает третья задача - задача выбора конечного семейства точек v',i= 1 ,N на поверхности уровня /(г) = /(z) (задача аппроксимации поверхности уровня). Причем эта аппроксимация должна обладать свойством, которое гарантировало бы нам решение задачи (1.3.1) при последовательном решении задач (1.3.2) и (1.3.3) для точек из этой аппроксимации.

Основываясь на этой идее, в параграфе 1.3 предлагается следующий алгоритм выпуклой квадратичной оптимизации. Пусть задача (1.1.1) задана в виде

/(*) = ! (Се, х) -4 max, х € X, (1.3.4)

где матрица С G Rnxn положительно определена и симметрична (С — С1*, С > 0), допустимое множество X компактно.

Определение 1.1 Пусть заданы точка z £ X, число е > 0, и пусть, кроме того,

U{z) = {v\...,vN : /(«••) =f[z),i = TJf,N = N{z)}, (1.3.5)

«'el: (V/ (v*'), и4) > sup (V/ (»'") ,x)-e, i- TJ7, (1.3.6)

cex

w4 G Rn : (V/ (w4) , u4 - w4) = _

= max{(V/(y) : /(y) =/(*)}, i = 1, N. i1'3'7)

Набор 3?(г) назовем (г,е)-разрешающим, если из того, что z не является е-решением задачи (1.3.4), то есть

/(*)< sup (/,*)-£, (1.3.8)

следует справедливость двух неравеств

7/ (г) = (V/ (ы»г) , - w4) > 0, (1.3.9)

2 > [sup | [/(*)]-". (1.3.10)

Далее будем считать, что в задаче (1.3.4) выполнены следующие предположения.

Предположение 1.1 Для любых с > 0 и для всякой е-стацио-нарной точки г G X можно построить [г,е)-разрешающий набор

ад.

Предположение 1.2 Для любого вектора а £ Rn и для всех е > 0 можно конструктивно отыскать точку и = и(а,е) € X такую, что

(а, и) > sup (а, х) - е. гех

При этих предположениях для решения задачи (1.3.4) предлагается следующий й-алгоритм.

5?-алгоритм

Пусть даны точка хк 6 X, к = 0,1,2,... и последовательность

со

чисел {е*}, к = 0,1,2,..., £ ек < +оо.

1=0

Шаг 1 zk £ X является е*-стационарной точкой, полученной, исходя из хк, каким-нибудь известным алгоритмом локального подъема.

Шаг 2 Строится (¿^^-разрешающий набор

Rt = Ш (zk) = {в1,..., гЛ : / (tf) = Ск, i = М^} • Шаг 3 Для всех i — 1, N^ строятся точки

ч-'бХ: (V/ (t/) , u4) > sup (V/ (w{) , х) -

Шаг 4 Для всех i— 1, Nk строятся точки

w* € Rn : (V/ (и/) , u' - и»*') = = max {(V/ (у), и' — у) : /(»)=/(*)}.

max / (и1) i<i<N 4 '

Шаг 5 Вычисляется величина

T}k=rj = (V/(uS)\u* -иР) = I<mxi (V/ (и,'),- ij) .

Шаг 6 Если щ > 0, то полагаем xk+1 := uJ, к := ¿+1 и переходим на шаг 1.

Шаг 7 Если щ < 0, то полагаем xk+1 := zk, к := ¿+1 и переходим на шаг 1.

Доказана глобальная сходимость Э?-алгоритма (Теорема 1.4).

В параграфе 1.4 для поиска е-стационарной точки на шаге 1 SR-алгоритма предлагается следующий метод локального подъема .

Пусть даны числовая последовательность {<$,}, 6, > 0, s = 0,1,2,... и допустимая точка xQ £ X. Последовательность {г5} будем строить по следующему правилу:

: <У/(*'),*,+1> > ^Р(Vf(x'),x)-S„ (1.4.2)

хех

то есть r,+1 является решением линеаризованной в х' задачи.

В предложении 1.1 доказывается, что такая простая вычислительная процедура в задаче (1.3.4) генерирует последовательность, сходящуюся к стационарной точке. Оказалось, что поиск стационарной точки в задаче выпуклой максимизации значительно проще, чем поиск решения в задаче выпуклой минимизации, поскольку нет необходимости проводить одномерную минимизацию. Однако, необходимо отметить, что стационарные точки могут быть очень далеко от глобального решения.

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

f{x) = - (Сх, х) max, х € X,

где X = {х 6 Rn : Ах = b, х > 0} ф 0 - выпуклый многогранник, С 6 Rnxn - положительно определенная симметричная матрица, А 6 Rmxn, rank А = m. Предлагается модификация симплекс-метода, которая заключается в том, чтобы на каждой итерации симплекс метода изменять целевой вектор в соответствии с направлением градиента.

Пусть уже найден г € X опорный план множества X с базисом сг = {¿1,..., 1т}. Обозначим за т — {1,..., п}\<г - множество небазисных индексов, Ва = [а*1, ...,а,т] - базисная матрица, Вт = [а;] ег, а = V/ (*) = Сг, ¿" = (Г = ед

Шаг 1 Вычисляем вектор у = .

Шаг 2 Если Д,- = (а*, у) — с,- > 0 V» € ак, то хк - стационарная точка и процесс счета останавливаем, иначе переходим на шаг 3.

Шаг 3 Выбираем индекс г £ ¿г* : Дг < 0 и подсчитываем вектор

а - В~1ат.

Шаг 4 Если а < 0, то множество X не ограничено, иначе выбираем 5 :

х"" (х?"

— = шш{ —, ¿6 {1, ...;т} : а,- > О а, « ( а,-

Шаг 5 Полагаем сгк+1 := ак П {&}\{г»}- Находим соответствующий опорный план Изменяем направление целевого вектора

¿к+1 := V f(xk^-l)=Cxk+1.

Полагаем к := к + 1 и переходим на шаг 1.

Во второй главе в параграфах 2.1 и 2.2 рассматриваются различные постановки квадратичной задачи о назначениях (КЗН). Как было отмечено во введении, эта задача имеет большое количество приложений.

Рассмотрим множество чисел {1,2, ...,п} и две п х п матрицы А = {а,^ } и В = {&,■;}. КЗН может быть сформулирована следующим образом:

л п

9(р) = ш1п' Р е 5"' (2ЛЛ)

¿=1 5=1

где Эп - множество всех перестановок множества {1,2,...га}. Другими словами, КЗН - это задача нахождения перестановки р € <5П, которая минимизирует целевую функцию д (р).

В общем виде КЗН может быть записана как

п п

9 (р) = ]С X) т1п' р е {2Л.2)

¡=11=1

где S = -{s.jtj/} - матрица размерности п2 х п2, и не умаляя общности, можем считать, что все элементы матрицы S неотрицательны.

Используя матрицы перестановок, КЗН (2.1.2) можно сформулировать как задачу целочисленного программирования с квадратичной целевой функцией

п тг п п

д(х) - {Sx,x) = -> min' х е D' (2-1-3)

¿=1 j=i t=i /=1

где допустимое множество имеет следующую структуру

п п ^

х € Я"2 : ]Г xik = 1, к = l^i; £ xik = 1, г = TT"; ®it G {0,1} >

¿=1 t=i J

В параграфе 2.2 КЗН сводится к задаче выпуклой максимизации: /(*) = i (Qx, х) = | [an - 5(а:)] шах, х Е X, (2.2.4)

где допустимое множество задается следующим образом

п П 1

х е -R"s: хи = 1»4 = Мч Е x»fc - 1 >г - М»; > о >, ¿=1 t=i J

а матрица^ представима в виде Q = ocl— S7), причем а выбирается из условия a > HSH^ , гарантирующего нам положительную определенность матрицы Q.

Как известно, квадратичная задача о назначениях может быть решена точными методами только до размерности 20 с использованием самых современных компьютеров. Поэтому возникает необходимость построения приближенных методов решения КЗН большой размерности за приемлемое время. В первой главе для общей задачи выпуклой максимизации был предложен K-алгоритм поиска глобального решения и была доказана его сходимость. Точная реализация Э?-алгоритма нуждается в адаптации для квадратичной задачи о назначениях (2.2.4), так как этот метод рассматривается для общего случая и не учитывает специфику численной реализации поставленной задачи. Поэтому в параграфе 2.3 предлагаются две модификации

3?-алгоритма, путем ослабления требования построения разрешающих наборов. Первую модификацию будем обозначать 3?i-алгоритм, вторую - алгоритм.

Допустим, существует некоторая процедура построения v' = t>* (г), i — 1, N точек из поверхности уровня целевой функции задачи (2.2.4) точки г, то есть / (и') = / (z), t = l,N. Также заметим, что д («') = 9(*)-

3?1-алгоритм.

Пусть дано z° £ X, к ~ 0. 1)«:=1.

2) Повторять до тех пор, пока г < N.

2а) Строим v' = v' (zh) .

26) Находим и* : (V/ («•') , и{) = таx(Vf (v*) ,х) .

2в) Если д (и') < д (zk) , то zt+l := и{, к := к + 1,

переходим па шаг 1). 2г) Если д (и') > д (zk) , то i := i +1, переходим на шаг 2).

3) Полагаем z' := zk и процесс счета останавливаем. Э?2-алгоритм отличается от ^-алгоритма тем, что в 3?2-алгорит-

ме на каждой итерации точки поверхности уровня рассматриваются не с первой точки (как в SRi-алгоритме), а начиная с точки, следующей за той, на которой закончилась предыдущая итерация.

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

Параграф 2.4 посвящен описанию метода Мака для решения линейной задачи о назначениях. В параграфах 2.5-2.6 строятся различные аппроксимации поверхности уровня целевой функции. В параграфе 2.7 проводится первое тестирование метода на задачах размерности от п = 3 до п = 8. В параграфе 2.8 предлагается комбинация ^-алгоритма с методом локального поиска для задач комбинаторной оптимизации. И, как видно из решения тестовых примеров размерности м от 12 до 20, взятых из библиотеки квадратичной задачи

о назначениях (QAPLIB), данная комбинация позволила значительно улучшить работу алгоритма. В параграфе 2.9 предложена новая схема метода, использующая упрощенное построение аппроксимаций поверхности уровня целевой функции и приближенный метод решения линейной задачи о назначениях с малыми вычислительными затратами, которая дала возможность получить результаты, близкие со сравниваемым методом Robust Taboo Search.

В третьей главе делается попытка применить подходы, разработанные в первой главе, к задачам оптимального управления.

В параграфе 3.1 рассматривается задача максимизации выпуклого терминального функционала с линейной по состоянию и управлению системой

Ф (и) = /(*(*!))-> max, (3.1.5)

x(t)=A (t) x(t) + B (t) и (i), x (to) = x°, t G T, (3.1.6)

r={«GL^(T) : u(t)eU V* G r}, (3.1.7)

где A(t) = {ay (*)} G СП, B(t) = {b,j (t)} G 1™Г(Т), /(•) -выпуклая и дифференцируемая функция, U - выпуклое, компактное множество из ВТ.

Для задачи (3.1.5)-(3.1.7) представлены условия глобальной оптимальности, полученные Стрекаловским A.C.. Обозначим за x(t, и) решение системы (3.1.6) при соответствующем и G V.

Теорема 3.2 Если управление w G V является глобальным решением задачи. (3.1.5)-(3.1.7), то

Ф/{у),х(^,и(1,у))-у)<0

VyGfl": / (у) = / (* (ii, w)), и (f, у) = arg max (ВТ (t)^{t),v) , V t G T,

где ф (•) является решением сопряженной системы

Если, кроме того, выполнено предположение, что

BpGfi": -оо < f{p) <f(x(tuw)) <+оо,

(3.1.9)

то условие (3.1.9) становится и достаточным для того, чтобы управление w было глобально оптимальным.

Легко видеть, что при у — x(ti, w) из условия (3.1.9) следует принцип максимума Понтрягина.

В параграфе 3.2 описывается алгоритм глобального поиска для задачи (3.2.1)-(3.2.3), которая отличается от задачи (3.1.5)-(3.1.7) тем, что f(x) = \(Сх, х), где С £ RnXn - положительно определенная симметричная матрица.

Определение 3.1 Пусть заданы управление w £ V, число е > О, и пусть, кроме того,

U(w) = {y1,...,yN : /(у') = ФИ, i = TJ7, N = N(w)},

«' € V : <ВТ (0 ф (t), u'(f)> > max (Вт (t) ф (<),«)- V t € Т,

ф (t) = -Ат (t) ф{1), ф (*х) = V/ (»/) , i = 1, N.

Набор 5J(to) назовем (ю,е)-разрешающим, если из того, что w не является Е-ретением задачи (3.2.1)-(3.2.3), то есть

Ф (ю) < sup (Ф, У) - е,

следует справедливость двух неравенств

Ф(и>) = ^шах^Ф(и1) > Ф(ы)),

[Ф (и»')] * > [sup (Ф, V)]± - [Ф (и,)]"* . (3.2.4)

Предположение 3.1 Для любых е > О и для всякого е-стацио-нарного управления w £ V можно построить [w, с)-разрешающий набор 3?(u!,f).

При этом предположении для решения задачи (3.2.1)-(3.2.3) предлагается следующий 3?-алгоритм. Пусть даны управление йк £ V,

оо

к — 0,1,2,..., последовательность чисел {е*}, к = 0,1,2,..., ек <

к—0

+00.

Шаг 1 wk £ V является -стационарным решением, полученным, исходя из йк, каким нибудь известным алгоритмом локального подъема.

Шаг 2 Строится -разрешающий набор

зг* = »(«;) = {у1,..„у"*: / (у1) =Ск, i = i,Nt}.

Шаг 3 Для всех г = 1, N¿ находятся управления и* € V :

(.Вт (í) V (t), «'(')> > max(Sr (t) ^ (i) t е Г,

¿ (*) =0(ti) = V/(y').

Шаг 4 Вычисляется величина Ф(и') = max Ф(и').

Шаг 5 Если Ф(«;") > Ф(и>*), то полагаем üfc+1 := ttJ, fc := к + 1 и переходим на шаг 1.

Шаг 6 Если Ф(ы;) <Ф(wk)

и £к меньше заданной точности, тогда процесс счета останавливаем. Если больше заданной точности, то полагаем йк := wk, к := fc-f 1 и переходим на шаг 1.

Глобальная сходимость 3?-алгоритма доказана в теореме 3.3.

В параграфе 3.3 на шаге 1 ^-алгоритма предлагается метод локального подъема для задачи (3.2.1)-(3.2.3), основанный на принципе максимума Понтрягина.

Пусть даны числовая последовательность {<5,}, S¡ > 0, s = 0,1,2,... и допустимое управление tí0 € V. Последовательность {и'} будем строить по следующему правилу:

(Вт (Í) (Í), «•+* («)) > max (В? (Í) ф> (<) v) - ^ V í G Т, ф* (<) = -Ат (í)/(í), ф> (h) = V/(г (ti, и')).

(3.3.1)

Доказана сходимость этого метода по невязке принципа максимума (теорема 3.4).

В параграфе 3.4 рассматриваются тестовые примеры максимизации нормы конечного состояния для различных динамических систем. Параграф 3.5 посвящен численному решению этих тестовых примеров и анализу полученных результатов. Можно сказать, что впервые удалось решить невыпуклые задачи оптимального управления подобного вида. Основные выводы второй главы помещены в параграф 3.6.

Основные результаты работы.

1. Предложен метод локального поиска стационарной точки в задаче выпуклой квадратичной оптимизации с линейными ограничениями, использующий процедуры симплекс-метода.

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

3. Разработана усовершенствованная схема алгоритма глобального поиска, использующая упрощенное построение аппроксимаций поверхности уровня и приближенное решение линейной задачи о назначениях. Это усовершенствование позволило получить численные результаты близкие со сравниваемым методом Robust Taboo Search.

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

5. Предложен алгоритм глобального поиска для невыпуклой задачи оптимального управления, основанный на условиях глобальной оптимальности Стрекаловского A.C., представляющих из себя некоторое семейство принципов максимумов Понтрягина. Доказана его глобальная сходимость.

6. Этот алгоритм глольного поиска впервые протестирован на ряде задач максимизации нормы конечного состояния для различных систем управления.

Публикации по теме диссертации.

Основные результаты диссертации опубликованы в следующих работах.

1. Васильев И.Л., Чубакова A.M. Квадратичная задача о назначениях. // Тезисы выступлений Байкальского международного студенческого форума "Безопасное развитие регионов".-Иркутск, 1997.-С. 218-219.

2. Стрекаловский A.C., Васильев И.Л., Чубакова A.M. Квадратичная задача о назначениях. // Тезисы докладов международной конференции "Проблемы оптимизации и экономические приложения" .-Омск: Изд-во Омского ун-та.-1997.-С. 149.

3. Стрекаловский A.C., Васильев И.Л. Об одном подходе к решению квадратичной задачи о назначениях.// Труды 11-ой Международной Байкальской школы-семинара.-1998- Т. 1.-С.

4. Strekalovsky A.S., VasilievI.L. On global search in non-convex optimal control problems, Volume of Extended Abstracts of III-rd Workshop on Global Optimization, December 10- 14, 1995, Szeged, Hungary, 113-115.

5. Strekalovsky A.S., Vasiliev I.L. On global search in non-convex optimal control problems, Abstracts of 8eme Colloque Franco-Allemand D'Optimization. Trier, 21, juli- 26, juli, 1996. P.107, Universität Trier, Fachbereich IV - Mathematik, 54286 Trier, Deutschland.

6. Strekalovsky A.S., VasilievI.L. On global search for non-convex optimal control problems, Developments in global optimization (Im. Bomze, Tiibor Csendes, Reiner Horst and Panos M. Pardalos editors) in Nonconvex Optimization and its Applications, Kluwer Academic Publishers, 1997, Printed in the Netherlands, 121-133.

183-186.