автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Итеративные методы решения задач многокритериальной оптимизации

И 32

ЧЕРНОВИЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЮРИЯ ФЕДЬКОВИЧА

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

Кушнирчук Василий Иосифович

ИТЕРАТИВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

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

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

Черновцы - 1992

Работа выполнена в Вычислительном Центре Российской Академии Наук.

Научные руководители: член-корреспондент РАН

Евтушенко Ю.Г.

кандидат физико-математических наук Иадан В.Г.

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

наук, профессор Данилин Ю.М.

кандидат физико-математических наук, доцент Маценко В.Г.

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

имени Тараса Шевченко.

Защита состоится " ^" Аая^/л 1992 г. в часов на заседании специализированного ученого совета К.068.16.05 в Черновицком государственном университете им.Юрия Федьковича ( 274012 г.Черновцы, ул.Коцгбинского, 2 ).

С диссертацией можно ознакомиться в научной библиотеке Черновицкого государственного университета ( ул.Леси Украинки, 23 ).

Автореферат разослан - -т— 1992 г.

Ученый секретарь специали- . зироввнного совета К.068.16.Садовяк A.M.

•.■'' :] '•.■'••л .• БИБЛИОТЕКА 1 .1'. Л

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность проблемы. Стремительно развивающаяся вычислительная техника в настоящее время проникает во все сферы человече' •• .. > деятельности. Трудно охватить все разнообразие задач, для решения которых используются ныне ЭВМ. Но не подлежит сомнению, что различные задачи оптимизации и методы решения таких задач составляют одно из наиболее динамичных направлений развития математической науки. Широкий спектр приложений является мощным стимулом для интенсивной разработки методов математического программирования. Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума и т.д. Это одна из причин постоянного и неослабевающего в течении последних трех десятилетий внимания математиков к задачам оптимизации.

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

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

Многие практические задачи конструирования, принятия ре-

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

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

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

Научная новизна полученных в работе результатов заключается в следующем:

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

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

3) Обосновано применение вспомогательной функции типа негладкой штрафной функции для решения обцей задачи многокрите^ риальной оптимизации методом линеаризации.

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

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

Апробация и публикации. По результатам делались сообщения и доклады на

- на девятом Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования";

- на шестой Всесоюзной конференции по управлению в механических системах;

- на восьмой Всесоюзной конференции "Проблемы теоретической кибернетики";

- на семинаре отдела "Прикладные проблемы оптимизации" ВЦ АН СССР и ВЦ РАН;

- на республиканском семинаре 19.16 "Математические проблем^ управления";

- в Черновицком государственном университете.

По результатам диссертационной работы опубликованы 5 работ.

На защиту выносятся следующие результаты:

- две версии метода возможных направлений для решения за-

дач выпуклой многокритериальной оптимизации; '

- метод линеаризации для общей задачи многокритериальной оптимизации;

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

Объем и структура диссертации Диссертация, объемом 110 страниц, состоит из введения, трех глав, заключения и списка литературы, вклочающего 80 наименований.

СОДЕРЖАНИЕ РАБОТЫ.

Рассмотрение задач в работе проводится по следующей схе-

j

ме: метод возможных направлений (глава I), метод линеаризации (глава 2), приложения теории к решению задаче проектирования строительных конструкций (глава 3).

В главе I "Метод возможных направлений" обобщены применяемые в нелинейном программировании две версии метода возможных направлений на случай решения задачи выпуклой многокритериальной минимизации

min KD, X = { xeR" | ad)<0). (i)

>s X

Под решением задачи (I) понимается множество слабо оптимальных по Парето (оптимальных по Слейтеру ) точек s пространстве R", определяемое следующим образом:

X* = { x„eX I mat [f'(x) - Г(х*)Ь 0, VxeX ). (2)

1 < i < r

В параграфе I.I формулируются основные предположения и ограничения, используемые в дальнейшем. Вводится в рассмотрение i-мерная ("e=z+m) вектор-функция h(x, а), для 'jerr, первыми 1 компонентами которой являются функции $ '(х)-а ' (1.=1,2,...,2), а последующими П1 компонентами - функции 9J(l) (L-i,2,...,m). Составлена вспомогательная Функция

H(i, а) = max h'(x, а).

1 <С t it

Сформулируем условия существования решений задачи (I). Лемма I.I. Для того чтобы вектор X»eR* был решением задачи (I) (т.е. Х*ЕХ*), необходимо и достаточно, чтобы существовал вектор a*ERr такой, что

Н(х, а) = о, (з)

х*е Агзш1погН(х, а«). (ч)

ХЕп

Точки X*eR" и a«ERr, в которых выполнены условия (3)-(4) назовем особые точками функции Н(х, а). Лемма I.I сводит решение исходной задачи (I) •< нахоедешт особых точек Функции

Н(х, а).

В параграфе 1.2 рассматривается задача линейного программирования

max <5 (5а) О, О

< hx4(x, а), Ó > * а <0, leí (I, а), (50)

е

I ÓJ I < 1, ¿=1,2,...,П, (5в)

где I (I, а) = {i<L<í | h *(Х, э) > Н(Х, а)-в) - множест-

V

во индексов С-активных компонент функции h(X, а). Решение этой задачи задает направление убывания функции Н(Х,Я). Изучаются свойства решений задачи (5). В частности показано, что значение целевой функции б 0(Х, ¡0 в задаче (5) будет положительным, если XQÉX*. А достаточным условием попадания точки Хм в множество X« есть выполнение (3) и равенство нулю целевой функции задачи (5) в этой точке б о(Х« , а*)=0.

Выписана также двойственная к (5) задача. С ее помощью

, г

устенлоно, что вектор

р(х, а) .= u'íx, a)hxJ(x, и), leí (х,а)

е

где U(x» а) = {u.'tx, а)» leí (X, а)) - вектор двойственных

С

переценных, является Б-субградиентом функции Н(ХЛ) в точке

[х, а]- А направление убывания функции Н(Х, а) вектор ó {х, а)

Б

обладает тем свойством, что из всех векторов Ó, удовлетворяющих условию нормировки (5в), скалярное произведение вектора

-6 (X, а) на вектор р(Х> а) есть наибольшее возможное. Е

В параграфе 1.3 рассматривается численный метод отыскания особых точек функции Н(Х, а). Поскольку функция Н(Х, а) негладкая, То используется С-алгоритм. Задаются начальные зна-

чения I0eR", УоЕГ» » направление B6R + , В >0. Очередная итерационная точна строится по правилу

»«♦i = а» - , а, , е)в, (ва)

+ а„ ó (i, , з,41), (бб)

е

у' - f *lx)

где jifoc, 'J, В) = mln -j- , a параметр Б изме-

1 С i i. Г В

няется по стандартной, для метода возможных направлений, схе- • ме. Для удобства изучения свойств итерационного процесса (6) в?здены обозначения

•,<, - ¡'-ил. i V \Х) - j, = паи.

1 < I <r i ( I ím

Предлагаемый численный метод таков, что на каждой итерации наряду с равенством Н(ХК , Ук + i) = V(Хк) выполняется тарже равенство Т {1« , + = 0, что характерно для прямых методов условной оптимизации, lilar спуска ОС* в итерационном процессе (6) находится путем деления пополам начального шага (X пока но будег выполнено условие

Hd.+rt^, , + < Н(х„ , - a,K.sj2.

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

> Bia [ ТПГ ' в^'гкп*7*-1

Лолученч также оценка снизу для велич«'".1 Р(Х, " й) на каждой итэрлции.

Пусть G(X0) = { xeR" I VdXVdo) ), a Y(X0, B> -множество предельных точек последовательности {ij. Доказательство теоремы о сходимости метода проведено при выполнении следующих условий

Условие Aj. Градиенты функций 1=1,2,..., 2

и j=i,2.....Ш, удовлетворяют на R" условию Липшица

с константой L.

Условие А г. Существует константа К<+°о такая, что

шаг шаг Ц ^(i) ||<К,

i * кг leb(io)

шах шш: II IUK.

1 i i * г Хсщ1о/

Условие Aj. Множество X ограничено.

Тогда справедлива

Теорема I.I. Пусть выполнены предположения Ai-Aj. Тогда У(Х0» В)сЯм.

В параграфе 1.1 предлагается обобщение еще одного варианта метода возможных направлений, а именно версии Топкиса-Вей-нотта. Отличио этой версии метода от версии, рассматриваемой в предыдущих параграфах состоит в том, что задача линейного программирования здесь имеет вид:

шах б (?а)

à,tí

<hj(x»a), л> ♦ Их,») - Н(Х.У)*0 <0, 1=1,2,. ..,1, (76) I à' I < 1, j=1,2,...,П. <7в)

Бели в (56) попадали лишь Б-активные компоненты вектор-функ-

- TI -

ции h(X, 3). то в (76) входят все компоненты. Изучены свойства решений задачи (7). Предлагается численный метод, итерации в котором проводятся по схеме (6) с решением на каждом шаге вспомогательной задачи (7). Итерационный процесс обладает свойствами, аналогиными свойствам, рассмотренными в предыдущем параграфе. Доказана теорема о сходимости второй версии метода возможных направлений.

Обобщению еще одного широко используемого в нелинейной программировании метода на случай решения общей задачи многокритериальной оптимизации посвящена глава 2 "Метод линеаризации" .

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

И(х, з, t) = чмх, а) ♦ t44x), (в)

где функции fefX.'J) и Ч^(Х), для выбранного направления ке:tili in > задаются следующим ооразои

ЧМх, з) = ¡пах * (1) Г a , ЧЧх) = шах з'(х).

1 1 I t г в О < I < m

г (п

Коэффициент t > T(U* , ö») = (£ uje "* E U„\ вектор

<•1 t«i

36 Ha« , з) = { aeRr | 3 = 3* ♦ ее, веЯ1 }.

Пусть множество l = { [х, a]eR"*r | f.(X, 3)=0), a

Ъщ - множество точек Н* = [х* , 3*3ЕЙ, в котогчх выполнены необходимые условия первого порядка. Точку [х, а, t]ERntrtl будеи называть особой точкой функции (8) если [i, »JeZ,

vdH и

• „ , H(x, a, t)

гаи ^ >

Основным результатом этого параграфа является лемма, выражающая связь между точками множества Еи и особыми точками функции м(х, а» t):

Лемма 2.1. Если [х* , У„]еЕ* , тогда [х* , 9Н , t]-особая точка функции М(Х, у, t) для всех t> T(U* , U*). Обратно, если [х», t*] - особая точка функции М(Х, у, t), то . [х„ , .

Таким образом, решение задачи (I) равносильно отысканию особых точек функции М(Х, t). Численный метод их нахождения предполагает решение на каждой итерации некоторой вспомогательной задачи линейно!о программирования. В параграфе 2.2 рассмотрен* эта задача: найти

Щ1П [п + Р(Х, у)б], (9а) ¿»П ,<S

< f^x), ь > ♦•I'd) < а' + в'п, Lelg(x, а), (96)

< ?J(x), ь > + a'(i) < о, LeO^d), (9в)

1 й' | < 1 ♦ <5, i <j<n, es> 0, (9г)

¡■да <5e-Rn, <3>0, Р(Х, Ч) - произвольная непрерывная на RnxRr функция такая, что

Р№»: Ln'^j^iltol/B'.

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

I^d, а) = С 1<1<г I hid, а)> «p.d, ») - 8 }, 3g(x) = С i<j<m I aJ(x)> 4Чх) - 8 }

здесь h'(X, a) = [ Г(х) - a' ]/e* для всех i < I < Z.

Далее изучаются основные свойства вспомогательной задачи. Доказано, что если допустимое множество в задаче (9) не пусто, то ее ресение существует и конечно. С помощью двойственной к (9) задаче показано, что если точка [х, a]eZ, то направление 6(1, а)» найденное из решения задачи (9), является направлением убывания функции М{х, а» t) по X при достаточно больших t. Кроме того существование особой точки функции Н(Х, а» t) эквивалентно наличие среди решений [д, П » б ] = 4EQ(X, а) задачи (9) нулевого решения.

Численный метод нахождения особых точек функции H(X,a»t) рассмотрен в параграфе 2.3. Пусть X06R", аоЕЙг. выбраны шаг ООО и параметр 0< £<1, Итерационный процесс ведется по следующим формулам:

= а (а, , а, , в)е, (юа)

X« + i = I, + OC.K Л(хк , »„♦!), (106)

'(х)-а1

где А (X, a, О) = ШХ -—I- . , Я«*.) - решение

1 i I t г В

задачи (9) в точке [х* , 3« + i]. Шаг спуска 0С.К получается делением пополам начального шага Л пока не будет выполнено неравенство

- и -

При этой на каждой итерации шаг ОС „ ограничен снизу

„ ч т;пг~ 8__(1-Р)[^(х,)-П (Хк.Ц.ч)] 1

* ' ^(хк)+К и Ж (1/е0^)Лак ||6КГ

Итерационный процесс (10) построен таким образом, что все точки [х„ , '¿к+О принадлежат множеству Ъ, так что на каждом шаге кроме спуска по переменной X осуществляется коррекция путем выполнения равенства Ч* е(Хк , Зк+1)=0. Если точка

[хк , , то шаг спуска из этой точки всегда строго

положителен и может быть получен делением начального шага ОС пополам за конечное число раз.

Обозначим У(х) = { аеКг I [х, у]еЕ ),

Х^о. е) = { хеИ", ае К(а0, в) | [х, у]еЕж},

л

Х(Хо > Но) - множество предельных точек последовательности

{хл.

Теорема о сходимости метода доказана при следующих предположениях:

Условие В1. Множество С*(х0 , ао)={хеП,> I М(х, Уо, 1)<М(Хо , :(о , 1)3 ограничено. Условие В 2. Для любых

хеБЛхо , Но), аеУ(х)

задаче линейного программирования (9) разрешима и

Т^(и(х, а))«1: - 1 для всех ч(х, а)еО(х, а).

Условие Вэ. Градиенты функций |'(х), 1<1<2 и э"*(х)» 1 < ^ <ш удовлетворяют на Б«(х0, Чо) условию Липшица с константой Л .

Теорема 2.1. Если выполнены условия В* - Вэ ,

то Х(Х0 , Уо)=Х«(У0 , Е) ПС *(Хо , У о).

В результате работы методов получается одна слабо оптимальная по Парето оценка. Для получения различных точек из множества Парето следует либо изменить начальный вектор Зо и двигаться в том же направлении В, либо наоборот, закрепив начальный вектор Чо варьировать' направлено В. Если при этом Но > ?'(я) Для всех 1=1,2,...,2, то изменяя направление

1Е X

В в пределах положительного ортанта Я" можна получить любую точку из X».

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

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

предложенных в работе методов.

ОСНОВНОЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ.

Основными результатами диссертационной работы являются:

- разработка двух вариантов метода возможных направлений для решения задач выпуклой многокритериальной оптимизации;

- разработка метода линеаризации для решения общей задачи многокритериальной оптимизации;

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

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

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

1. !Кадан В.Г., Кушнирчук В.И. Об одном обобщении метода возможных направлений для решения задач многокритериальной оптимизации// Материалы девятого Всесоюзного симпозиума "Системы программного обеспечения решения задач оптимального планирования. М., 1986. С.39-40.

2. Шадан В.Г., Кушнирчук В.И. Пакет методов многокритериальной оптимизации в системе ДИСО// Пакеты прикл. программ: Программное обеспечение оптимизационных задач. М.: Наука,19С7. С.17-26.

3. Жадан В.Г., Кушнирчук В.И. Метод возможных направле-

ний для решения задач выпуклой многокритериальной оптимизации // Ж. вычисл. матем. и матем. фиэ. 1987. Т.27. N6. С.829-838.

4. Кушнирчук В.И. Об одном методе решения задач многокритериальной оптимизации// Материалы восьмой Всесоюзной конференции "Проблемы теоретической кибернетики". Горький. 1988. С. '4-5.

5. Кушнирчук D.H. Решение задачи многокритериальной оптимизации методом возможных напрг>влений//Материалы шестой Всесоюзной конференции по управлению в механических системах. Львов. 1988. С.98.