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

РГЗ од

Академия Наук Беларуси Институт математики

Т'ДК 519. Г 53 . 32

Чемисова Татьяна Владимировна

КОНСТРУКТИВНЫЕ МЕТОДЫ РЕШЕНИЯ СЕПАРАБЕЛЬНЫХ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

01.01.09. - математическая кибернетика

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

Минск, 1996 г.

Работа выполнена в Институте математики Академии Наук Беларус

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

профессор

КИРИЛЛОВА Фаина Михайловна

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

профессор

МИНЧЕНКО Леонид Иванович;

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

РАКЕЦКИЙ Валерий Михайлович

Оппонирующая организация - Санкт-Петербургский

Государственный Университет

Защита состоится " 28" ию^я_1996 года в ^5°° час

на заседании совета по защите диссертаций Д 01.02.02 в Институ математики АН Беларуси по адресу: г. Минск, ул.. Сурганова, 11.

С диссертацией можно ознакомиться в библиотеке Института матемг Автореферат разослан "27 " • мая_ 1996 года.

Ученый секретарь совета по защите диссертаций

ПЯс^и -

I

Астровский А.И

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

Актуальность темы диссертации.

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

Существует большое число приложений, в которых математические ели формулируются в терминах задач ГП и задач о наименьших квад-ах. Основными областями применения алгоритмов (и программ) ГП яются: задачи управления народным хозяйством, планирование техно-ических процессов производства, капиталовложений в технологии с «одическим циклом управления запасами, задачи инженерного проек-ования, гражданского строительства, судового проектирования. Сре-задач, решаемых при помощи ГП можно назвать также проектирование рных реакторов, установок для опреснения морской воды, производ-а кислорода и т.д. В Беларуси разработанные на основе нового под-;а к решению задач линейного программирования ) алгоритмы решения ;а позиномных подзадач ГП применялись в программном комплексе оик" для автоматизированного проектирования оптимальных по сто-|сти материалов и расходу арматуры перекрестных железобетонных гок. В ИТК АН Беларуси разработан пакет программ для решения задач знойного ГП (ПП "Позином"), возникающих при решении оптимизацион-: проектных задач.

На протяжении последних десятилетий квадратичное программирова-! (КП) наряду с линейным программированием является одним из самых ¡улярных разделов современного математического программирования, .■ойчивый интерес исследователей к КП обусловлен несколькими факто-ш, среди которых в первую очередь следует отметить многочисленные юстоятельные приложения моделей КП в технике и экономике. Важной 1астью применения методов КП являются общие алгоритмы нелинейного >граммирования и оптимального управления. Сильный импульс развитию

Р.Габасов, Ф.М.Кириллова. Методы линейного программирования, 4.1-3. Изд-во БГУ, Минск, 1977,.1978, 1980.

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

Несмотря на интенсивные исследования нелинейных задач, ну» признать, что эффективные алгоритмы для решения отдельных задач создания программного обеспечения для них все еще далеки от завери ния. Одним из факторов повышения эффективности численных методов нелинейном программировании, как и в других разделах оптимизаи является дополнительный учет специфики решаемой задачи. За счет j ложнения логической структуры общего метода часто удается сниз1 его трудоемкость и требования, предъявляемые к объему памяти и мс ности вычислительной техники при решении специальных классов зaдa^

2. Связь работы с крупными научными программами, темами.

Диссертационная работа выполнялась по темам важнейших научно-исследовательских работ в области естественных наук отдела теории процессов управления Института математики АН Беларуси:

- "Математические методы и программное обеспечение нелинейные экстремальных задач" No 0187.0027644 (Постановление Президиума АН БССР No 155 от 25.12.S6);

- "Методы решения негладких экстремальных задач и их приложения" (Постановление Президиума АН Беларуси No 147 от 06.12.88).

3. Цель и задачи исследования

Целью работы является разработка конструктивных методов peuiei специальных задач ГП и КП. В задачи исследования входило:

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

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

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

- построение прямого, двойственного и комбинированного методов ? решения сепарабельных задач ГП с простыми ограничениями;

- программная реализация разработанных методов и проведение зпериментов.

Научная новизна полученных результатов.

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

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

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

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

Практическая значимость полученных результатов

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

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

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

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

7. Основные положения диссертации, выносимые на защиту-

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

- разработка прямого, двойственного, и комбинированного методо решения безусловных задач ГП;

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

- построение алгоритмов решения, задач о наименьших квадратах простыми ограничениями на переменные;

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

8. Личный вклад соискателя

Основные результаты диссертации получены лично автором. В < местных работах по ГП [1, 2] автору диссертации принадлежит ра1 ботка принципа накопления аппроксимирующих функций на итерациях ] мого и двойственного методов, а также- разработка процедур по] шага, методов решения нелинейных уравнений и систем нелинейных у] нений специального вида. В [з] автором.доказаны критерии оптим; ности для прямой и двойственной задач ГП с простыми ограничени: на переменные и разработаны прямой и двойственный методы реш! этих задач; доказана сходимость предложенных методов.

Апробация результатов диссертации.

По теме диссертации сделаны доклады на Международной конферен-DGOR, GMOOR и OGOR "Symposium on Operation Research" (SOR'95) ilaccay, Германия, 1995), Международной математической конферен-, досвященной 25 -летию Гомельского госуниверситета (г.Гомель, 4), VIII Всесоюзной конференции "Проблемы теоретической киберне-и" (г.Горький, 1988), Межгосударственной научной конференции намические системы: устойчивость, управление, оптимизация" Минск, 1993), научных чтениях "Динамические системы: устойчи-ть, управление, оптимизация" (г.Минск, 1990).

Результаты диссертации неоднократно обсуждалсь на объединенном инаре по конструктивным методам оптимизации кафедры методов опти-ьного управления Белгосуниверситета и отдела теории процессов авления Института математики АН Беларуси (руководители - профес-Р.Габасов, профессор Ф.М.Кириллова).

Опубликованность результатов.

Результаты диссертации опубликованы в 4 статьях и в 5 тезисах чных конференций.

Структура и объем диссертации.

Диссертация состоит из введения, общей характеристики работы и ырех глав, а также приложений. Объем диссертации - 100 страниц, ■ем списка использованных источников (112 наименований ) - 8 стра-;, объем приложений — 15 страниц.

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

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

0 наименьших квадратах.

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

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

В разделе 2.1. рассматривается задача:,

g(z) = ^ е 1 -> min, х = Az + Ь, ; (1'

i el -

(z e R", x e Rn, b e (Rn, A = A{I,J) — (л x и) - матрица экспонент, rank A = m).

Пусть z - план задачи (1). Во множестве I выделим подмножество

1 с I : II I = т, det А * О, где А = Ail- ,J) и положим: 1,-1/1 ,

О 'О1 О О О H о

/}„= Л(1„,J), Ь„= Ъ(Т ), Ь = Ь(Т ). Множества I , I называются соот-нн н но о о н

ветственно опорным и неопорным множествами задачи (1). Используй зависимость между опорными и неопорными компонентами векторов х, z, задачу (1) можно представить в форме

gíz) = Y е*1 -> min, x(I ) = ß(Iu,I )x(I ) + d(r), (2)

/ n Н О О Н

i el

где В(1н,10)= Аия,аи-Ч10,Л, d(JH)= - Шн.1>(Jo) + Ь(1н).

С помощью теории двойственности записывается задача, двойствен-

к (2):

pU) = ^ CA.J- Ajln Af) + ^ Xjdj -> wax,

161 leIH (3)

A(J0) + •B'(IH'Jo)X(JH) " Л a

Rn, для которой стандартно вводятся определения и основные поняВ разделе 2.2. описывается метод решения прямой безусловной чи ГП в форме (2) (прямой метод). Итерации метода называют пря-итерациями или итерациями прямого типа. Исходя из свойств экс-нциальной функции: а) е* s X + Хх - X 1пХ для любых X fc О, х е б) ех*у ь ех+ уех для любых х, у е R, на итерациях прямого ме-целевую функцию задачи (2) аппроксимируем снизу по неопорным юнентам прямого плана функциями

^(х.Х) - Х^) + (4)

16io 1еГН

*г(х,у) = У (е"1*У' + riU)yi) + V е"1 (5)

Tel 1 е J„

о н

1МИ, что g(x) ь ^(х.Х), g(x+y) г Ф2(х,у). Здесь у(1) — вектор,

¡летворяющий соотношениям у(1„) ■» В(1„,1 ) у(1 ); г (х) =

н но öl

* ,

Ъ te , X — некоторый план двойственной задачи (3).

ijHJ

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

Гк(у) = max {(!> (хк+у,Х), 0 ,хк-х°+у)} -> шл , (6)

seM 1 2 У1,1б1о

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

Построение миноранты Fk(y) на основании аппроксимирующих функ-, использующих информацию о прямых планах, полученных в ходе всех

проведенных итераций метода и выбор направления поиска . исход;

решения подзадачи минимизации этой миноранты лежат в основе под:

который назовем принципом накопления аппроксимирующих функций.

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

лением убывания целевой функции задачи (2) на к -той итерации i

да. Для решения подзадачи поиска минимума миноранты разработана

циальная процедура, позволяющая свести эту подзадачу к решению г.

нейного уравнения на отрезке, либо к решению системы нелине

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

функций в (6). Для задачи (2) доказано достаточное условие с - а

мальности прямого плана, являющееся критерием останова на итера

метода и разработана процедура нахождения шага в = аrgmin g(x*+e

osesi

данная процедура описана в приложениях (П.З).

В разделе 2.3. описываются итерации метода решения двойстве задачи (3) (двойственного метода). На к -той итерации метода нап ление у возрастания двойственной целевой функции р(Х) строим из ловия максимума специально построенной для нее мажоранты

4>k(i>) = min {р (Ak+ i>,x), р"(А.1,**- Аv)}, 16N 1

где N с {1,2.....к}, PjU, х) - ^¡Г е 1 + ^ (Х4 + А^- Х^лХ^,

P2(A,V)= ^ \i + ^Г +vt+ (Vj+A^q^A) - (X^l^lnU^Vj)),

о н ^

(р(х) г р (А,х), <р(Х+1>) а р (А,у), ц

(А) = й + ) ъ,1п А,, «Т.

1 2 11 { 1 J Н

Здесь вектор !>(!), компоненты которого удовлетворяют соотношеш

у(Г ) - - £(Г ,1 )'У(Г„), Хк(1н) + 1>(1и) * О,, о н ■ о н н н

является допустимым направлением изменения двойственного плана А1* помощью решения ук экстремальной задачи

Фк(1>) -» шах

на итерациях двойственного метода строится последовательность п ближений Ак*1= Ак+ <г к е И к оптимальному двойственному пл

О к

X . Описаны процедуры выбора шага сг вдоль направления V и преоб зования опорного множества'I задач (2), (3). Предложено прав

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

Существующая связь между решениями прямой (2) и двойственной ) задачами безусловного ГЛ и специфика итераций прямого и двойст-нного методов из разделов 2.2, 2.3 лежат в основе комбинированных горитмов, описанных в 2.4. Суть комбинированных алгоритмов заклю-ется в том, что в ходе решения информация, необходимая для постро-ия аппроксимирующих функций постоянно уточняется. На итерациях мбинированных алгоритмов преобразуется некоторая пара (х,А) из 1ямого и двойственного планов соответствующих задач. План х может меняться на итерациях прямого типа, а X — на итерациях двойственно типа. Комбинированный алгоритм состоит в последовательном !ключении" то прямого, то двойственного метода. Приведены различные :емы комбинированных алгоритмов.

Третья глава посвящена алгоритмам решения безусловных задач о шменьших квадратах. В разделе 3.1, принцип накопления аппроксими-дацих функций применен к решению прямой безусловной задачи о наи-5НЫ1ШХ квадратах в форме:

г(х) - V х* / 2 -> лип, х(1н) = В(Г ,1 )х(1 ) + сК1н). (7)

¡71

Следуя общей схеме составления двойственных задач имеем двойст-энную к (7) задачу:

<р(\)= Л'Ь ~У А2/ 2 -> тах, А(Г Н В'(1 ,Г )*(ГН)- О. (8)

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

вадратах в форме (7) преобразуется пара (х,А) из некоторого началь-

ого плана х задачи (7) и двойственного плана А задачи (8), связан-

ых соотношением: х(1„) = А(Г„).

м к

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

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

В разделе 3.2. описаны итерации метода решения двойственной задачи о наименьших квадратах в форме (8). В основу метода положе: принцип накопления функций, аппроксимирующих целевую функцию задач: (8) и построенных с использованием свойств ее выпуклости и сепара бельности. Обоснован выбор подходящего направления улучшения текущего двойственного плана на итерациях метода и доказано достаточно» условие с - оптимальности. Доказана сходимость предложенного метода

В 3.3. описаны конструкции прямо-двойственных методов решени пары безусловных задач о наименьших квадратах (7), (8), использующи свойства конкретных алгоритмов из разделов 3.1, 3.2 и позволяющи находить оптимальные планы данных задач одновременно. Эти методы основаны на теории двойственности выпуклого программирования, а такни на том факте, что решая одну из задач (7), (8) мы привлекаем инфор мацию о плане другой и поэтому естественно поочередно улучшать эт: планы с целью добиться наибольшей эффективности алгоритмов.

В разделе 4.1 рассматривается задача о наименьших квадратах I простыми ограничениями на переменные. В отличие от безусловной задачи о наименьших квадратах (7) на переменную г здесь накладывайте: дополнительные ограничения в виде неравенств .• *

'с}. £ 2 а й , (9)

(¡., й 6 К™.

Назовем опорой задачи (7), (9) совокупность множеств, Ко= {I «70), 10 £ I, 3о с Ц I - , для которой матрица Ао = А {I ^ невырождена. Множества индексов I , J будем называть опорными, множества Г = 1/1 , J=J/J - неопорными, н о н о

На итерациях прямого метода решаем эквивалентную (7), (9) задач; в форме:

g(z.X) х* / 2 -> лил, хн = В(1н>1о)хо+ лин..у V Сн'

;61 . . ао:

<4 3 С (хо - 'нЧ - "с) 5 "'„ 4 2н 5 Йн'

где хо = х(1о), хн = х(1н). го = = л(^), сн = с^),

"•о - "-"«Л <4 - "'ЧЛ < - ан ~ ^ЧЛ '

Совокупность из плана (г, х) задачи (10) и опоры К будем называть опорным планом {г, х, Ко) этой задачи. Опорный план (г, х, Ко) назовем невырожденным, если 2й.

Двойственная к (7), (9) задача имеет вид:

<р{X, v., V ) - Х'Ь - ^Г aV 2 + v'. d. - v 'd -> max,

| «I . (U)

Л'Х - v. + V ■= О, v. г 0, V г О.

Совокупность векторов (Л, v., v ), A s Rm, v., v <= И", удовлет-ющая ограничениям задачи (11), называется двойственным планом I задачи.

Назовем двойственный план (X, v., V ) согласованным, если

V.J = О, vj - - 8з при 6} < 0; v^ - ejf (12)

v = О при а О, jfej, где 5 е R", 6 = Л'Х.

заданном векторе А на согласованном плане (X, v., v ) достигает-максимум целевой функции двойственной задачи (11), поэтому рас-триваются только согласованные двойственные планы. Докаэан критерий оптимальности для задачи (10).

1) Пусть (z, х, К ) - невырожденный опорный план задачи (10). его оптимальности необходимо, чтобы выполнялись соотношения:

х + г =0, iеГ ; Д >0 при z = d.

1 . ° j j • da)

Д < 0 при z = d , Д = О при d„ < 2 < d , jej.,

J J J J K J J J J н

r.= riU) ieIo' v Vx) JeJH-

JeJH '. ,eIH

2) Пусть для опорного плана (z, х, К ) выполняются соотношения ). Тогда план (z, х) является оптимальным.

Согласованный двойственный план X = (X, v., v ) назовем невы-

денным, если S * 0 для всех jsl .

J н

Критерий оптимальности для двойственной задачи (11). 1) Пусть X — невырожденный согласованный план задачи (11). Для > оптимальности необходимо выполнение соотношений:

Л = О, iel ; p=d, при S >0,

н J J J (14)

dj при < 0, d.j- p^ < d^ при 5j= 0, j £ Jq,

где Л » Эр(х)/ах , , р =У а []п (V а г -V Ь X )-

I 1 Н J ¿^ Jl >1 В 81 В

"I V 63>

,&7и 1еь7н

2) Пусть для двойственного плана X выполняются соотнош« (14). Тогда А — оптимальный план задачи (11).

Принцип накопления аппроксимирующих функций применен в раз; 4.1 для решения задачи (10). Пусть на к -той итерации метода уел; оптимальности (13) не выполняются для' прямого опорного ш (2к,х*,Ко). На основании свойств выпуклости и сепарабельности Ц( вой функции задачи (10) построена миноранта

I ,у) = тах С2к+1,х1,+у,Х). VI и',гк- ,хк- х*+у)} , (

веМ 1 2

где М с {1,2,...,А} — подмножество, формирующееся в ходе итеращ (г',х')— прямой план, полученный на я-той итерации метода.

Очередное направление 11,у): 1 = КЛ), у - у(1) такое, что

у(1И) = всгн,1о)у(1о), шо) = А-уо^о)(у(1о) - Аа0,;н)шн)), - гин) * * - гин),

находится из решения подзадачи

Кк(2,у)-» ш , й.(^)- ¿(О г Ш ) * (Г 07) - (

ИНН ни

Доказано, что решение подзадачи (16) является направлением у ния целевой функции задачи (10) на к -той итерации метода. Ите метода решения подзадачи (16) подробно описаны в разделе 4.1. Для шения возникающих в ходе работы метода вспомогательных задач раз таны специальные процедуры. Особое внимание уделено преобразо опоры, тесно связанному с процедурой нахождения шага вдоль выбра направления.

В разделе 4.2. описаны итерации решения двойственной задачи наименьших квадратах в форме (11). Применение принципа накопле аппроксимирующих функций в сочетании с разработанной процедурой шения подзадачи поиска максимума мажоранты позволяет свести реше; исходной задачи к решению задачи квадратичного программирования одним ограничением-равенством. На итерациях также производится п]

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

В разделе 4.3. рассматривается прямая сепарабельная задача ГП с [ростыми ограничениями на переменные в форме '

Z*.

е -> min, х •= Az + Ъ, d. s z s d , (17)

l€l

- (г,, jeJ), j - {1.2.....m}; x - (x, , iel) , I - {l,2, . . . , n) ;

J I »

. -(л x w) матрица экспонент, л > m, ranic А = /л, b e Rn; d„ , de Km. Б разделе 4.4 описан метод решения задачи, двойственной к (17):

» i 4 » »

р(Х, V., V ) = \ X + Х'Ь - X'lnX -I- v'.d. - v 'd -» тах,

.1б1 . (18) А'\ - V. + v = О, v, г= 0, v а О; X t О,

6 й"1, V.. v'e R".

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

Все описанные в четвертой главе методы могут быть объединены в эмбинированные (или прямо-двойственные) алгоритмы, позволяющие рвать прямую и двойственную задачи данного типа одновременно.

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

1.3), а также метод накопления оптимальных признаков, адаптирован-]й специально для решения возникающих в разделах 4.1, 4.2 задач !адратичного программирования с одним ограничением-равенством

1.4). В П.5 приводятся результаты численного эксперимента по решено безусловных задач ГП.

выводы

По результатам диссертационной работа можно сделать следующие выводы.

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

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

3. Применение принципа накопления аппроксимирующих■ функций сочетании с использованием основных принципов опорных методов линей' ного программирования при решении оптимизационных задач позволило р; работать новые прямо-двойственные методы решения сепарабельных зада' ГП и специальных задач о наименьших квадратах с простыми ограничениями на переменные. Методы являются точными, релаксационными, сходящимися к оптимальному решению; методы просты в программной реализации.

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

СПИСОК ОПУБЛИКОВАННЫХ АВТОРОМ РАБОТ

{асько Т.В., Покатаев A.B. Алгоритм линейной аппроксимации для эешения задачи безусловной оптимизации геометрического программирования.- Препринт / Ин-т мат-ки АН БССР.- Минск, 1988.- 24 с. 1окатаев A.B., Касько Т.В. Алгоритм линейной аппроксимации для решения безусловной задачи геометрического программирования // Лроблемы теоретической кибернетики: Тез. докл. конф.- Горький, 1988.- С. 81-82.

Чемисова Т.В. Алгоритм решения задачи о наименьших квадратах // Becni АН БССР. Сер. ф1з-мат.навук.- 1991,М>1.- С. 13-19. Чемисова Т.В. Алгоритм решения безусловной задачи о наименьших квадратах // Динамические системы: устойчивость, управление, оптимизация: Тез. межгос. научн. конф,- Минск, 1993,- С. 110. Чемисова Т.В. Двойственный метод решения задачи о наименьших квадратах / Ред.ж. "Изв. АН Беларуси. Сер. физ.-мат. н.- Минск, .1.994,- 7 е.- Деп. в ВИНИТИ 16 .06.94 . Ы» 1493 - В 94. Чемисова Т.В. Один метод решения задачи о наименьших квадратах // Международная математическая конференция, посвящ. 25-летию Гомельского госун-та им. Ф.Скорины: Тез. докл. конф.- Гомель, 1994,- С. 65.

Покатаев A.B., Чемисова Т.В. Алгоритм решения задачи геометрического программирования с простыми ограничениями на переменные // Вестник БГУ. Сер.1,- 1994, Уо 2.- С. 68-73. Чемисова Т.В. Двойственный метод решения сепарабельной задачи геометрического программирования // Негладкие и разрывные задачи управления, оптимизации и их приложения: Тез. III Международного семинара.- Санкт-Петербург, 1995.- С. 125-126. Tchemisova Т. The Combined Method for Solving the Geometric Programming Problems with the Box Constraints // Symposium on Operation Research: Abstr.- Passau, Germany, 1995,- P. 45.

РЕЗЮМЕ

Чемисова Татьяна Владимировна

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

Ключевые слова: план, опора, выпуклая функция, критерий оптимал ности, аппроксимирующая функция, миноранта, мажоранта, подходящее н правление, метод решения.

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

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

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

РЭЗЮМЕ

Чэмд.сава 'Гаццпна Уладз1м1рауна

Канетруктыуныя метады рашэнкя сеплрабелышх задач выпуклага праграмгравпшш

Ключавыя словы: план, апора, выпуклая функция, крытэрьи апты-.льнасц]., апракс1м1руючая функция, м1наранта, мажаранта, падыходзя-I нппрпмак, метад рашэння.

Для рашэння прамой.безумоунай задачы геаметрычнага праграм1ра-1ння у сепарабельнай форме 1 задачы, два!.стай да яе, пабудаваны |амы 1 два1сты метады, заснаваныя на ].дэ1 апракегмацый мэтавых фун-(ый задач м1нарантай 1 мажарантай спецыяльнага вз.ду адпаведна 1 (бару падходзячага напрамку змянення бягучых планау, зыходзячы з ;стрэмальных уласл1васцей пабудаваных функцый. Для гэтага распраца-1ны прынцып накаплення апракс1м1руючых функцый на 1.тэрацыях адпа-|Дных метадау 1 апз.саны працэдуры выбару напрамку 1 пошуку шагу. |апанаваны схемы камбз.наваных алгарытмау для рашэння безумоуных [дач геаметрычнага праграмхравання.

Прынцып накаплення апракс1м1руючых функцый выкарыстаны пры ■варэнн! новых метадау рашэння прамой 1 двагстай безумоуных задач \ найменьшых квадратах 1 для канстру^равання на 1х базе прама-два-:тых алгарытмау.

Асновай прамых 1 дваахтых метадау "рашэння сепарабельных задач гпуклага праграм1равання з простым! абмежаванням1 на пераменныя :еперебельных задач геаметрычнага праграм1равання 1 задач аб най-¡ньшых квадратах) з'яуляецца канструкцыя,• якая называецца апорай 1 1эваляе разбз.ць мноства ус1х пераменных зыходнай задачы на пад-гаствы залежных 1 незалежных пераменных 1 ул1чыць простыя абмежа-1нн1 задачы. Пабудаваныя апракс1мацы1 мэтавых функцый дазваляюць >ымянз.ць на а.тэрацыях метадау прынцып накаплення апракс1м1руючых гнкцый для выбару напрамкау. Пры гэтым эффектыуна выкарыстоуваецца 1яуная з.нфармацыя аб пачатковых планах задач, двад.стых да рашаемых. 1ацэдуры пошуку шагу на ].тэрацыях метадау заснаваны на даказаных >ытэрыях аптымальнасц! 1 цесна зязаны з перабудовай апоры, якая (ыццяуляецца на кожнай 1.тэрацы1 метаду.

SUMMARY

Tchemisova Tatiana Vladimirovna

Constructive Methods for Solving Separable Problems of Convex Programming

Key words : feasible solution, support, convex function, opt lity criterion, approximation function, minorant, majorant, suit direction, method of solution.

in separable form and the problem dual to it the primal and du methods have been constructed. These methods are based on the id of approximation of the goal functions by minorant and majorant o special form and of selection the suitable directions for improv ment the current feasible solutions starting from the extremal pr> perties of these functions. The principle of accumulation•the appr ximation functions on iterations of corresponding methods has bei elaborated; the procedures of selection the suitable direction a: of search for the step along this direction have been describe! Schemes of combined methods for solving the unconstrained geometr programming problems have been suggested.

The principle of accumulation the approximation functions h; been exploited to construct the new methods for solving • the prim; and dual unconstrained least squares problems.

The construction called the support which permits to divide t] set of all unknowns of the initial problem in the sets of dependei and independent unknowns and to take into account the box cons raints on variables lies in base of primal and dual methods of soli tion the separable box constrained problems of convex programmii (separable geometric programming problems and least squares prol lems). The goal function's approximations constructed make it po: sible to use the principle of accumulation of the approximation fui ctions on iterations of methods for selection of the suitable direi tions. The available information about initial feasible solutions ( dual problems is efficiently used here. .The procedures of search f< step are based on optimality criteria proved and closely connect! with transformations of support on itera*"'

To solve the primal unconstrained geometric programming probl