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

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

ЦЭВЭЭНДОРЖИЙН ИДЭР

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

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

Автореферат

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

ИРКУТСК 1996

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

Научный руководитель

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

Официальные оппоненты:

доктор физико-математических наук, профессор Дыхта Владимир Александрович; кандидат физико-математических наук, доцент Семеней Петр Тимофеевич.

Ведущая организация

Московский Государственный университет им. М.В. Ломоносова Факультет ВМиК

на заседании диссертационного совета д uo3.az.ui при VIл / но адресу: 664003, Иркутск, 6. Гагарина, 20, 1-й корпус ИГУ, математический факультет.

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

Защита состоится

Автореферат разослан

1996 года.

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

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

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

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

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

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

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

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

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

• (^.-программирование (минимизация разности двух выпуклых функций);

• минимизация липщицевых функций.

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

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

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

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

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

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

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

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

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

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

Апробация работы Результаты диссертации докладывались на научных семинарах по методам оптимизации кафедры вычислительной математики факультета ВМиК МГУ им. М.В. Ломоносова, кафедры высшей математики ИГЭА, лаборатории исследования операции СЭИ СО РАН и на объединенном семинаре по методам оптимального управления кафедр методов оптимизации и вычислительной математики ИГУ, на международной 17-й конференции 1ИР-95 по моделированию систем и оптимизации (Прага, Чехия), на 10-й международной школе-семинаре по методам оптимизации и приложениям на Байкале (Иркутск, 1995 г.), в Ш-м международном совещании по глобальной оптимизации (Зегед, Венгрия) и на 8-ой совместной Франко-Германской конференции по оптимизации (Триер, ФРГ).

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

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

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

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

1. доказательство условий оптимальности;

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

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

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

5. тестирование алгоритмов на известных из литературы задачах;

6. решение этими алгоритмами практических задач;

7. анализ численных экспериментов.

Так, первая глава диссертации посвящена теоретическому изучению задачи обратно-выпуклого программирования.

f{x) -)• min, д(х) >0, х £ А, (PR)

где (/(-)-выпуклая функция.

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

В параграфе 1.1 рассматривается задача (PR) в предположениях, что функция / : X -> R необязательно выпуклая, а полунепрерывная сверху в рефлексивном банаховом пространстве X, А-некоторое непустое подмножество из X, а функция д : X —> R U + является выпуклой и собственной.

A.C. Стрекаловским было получено необходимое и достаточное условие оптимальности, которое для дифференцируемой функции д(-) имеет следующий вид:

Теорема 1 Если z является глобальным решением задачи (PR) и выполнено предположение

Agr min(PR) П {z / ф) > 0} = 0, (G)

то

Vr/ : g(y) = g(z) = 0, )

> (Е)

{g\y),x-y) <0, VxEA, f(x)<f(z). }

Кроме того, при выполнении следующих дополнительных предположений:

-оо < inf{gr / X} < g[x) = 0, V¡/ € А : g(y) =0, ЭЛ = h{y) 6 clco A,

iU)

W (y),h-y)> 0, следующее усиление условия (E)

Vy : g(y) = g(z) = 0,

Ухе clco A, /(r)</(z);

становится и достаточным для того, чтобы z являлось глобальным решением задачи (PR).

Проверка условия (/J1) сводится к рассмотрению семейства задач, называемых "линеаризованными":

(g'{y),x) max, х G clco A, f(x) < f(z), (РЦу))

где у € = {í/ / д(у) = g(z) = 0}, с последующей проверкой

условия

(д'(у),Ау)-у}< о,

где х°(у) решение задачи (PL(y)).

Далее в параграфе 1.2 исследуются свойства минимизирующих последовательностей. При этом используется следующее понятие.

Определение 1 г) Назовем последовательность {г*} из рефлексивного банахова пространства X минимизирующей в задаче {РЯ), если

Шп/(**) = /.= 1п£(/,27), (£>1)

к-¥ оо

Л

{г } С А, (П2)

ИтЫд{гк) > 0, (£>3)

к—юо

где Б = {х £ А ,д(х) > 0}.

И пусть

1ро{г) =8ир{хуу.){(у*,х -у) /х € А, Дх) < /(г),

9{у) = Иг)> У* € дд(у)}.

(1)

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

Теорема 2 Пусть имеет место следующее предположение

не существует минимизирующей )

последовательности {гк} : > (^1)

д(гк) > 0. ]

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

Нт <ро{гк) = 0. (Е0)

к-уоо

Следующий результат дает достаточные условия того, что последовательность - минимизирующая. Для этого, вместо функции <£>о(-) определенной в (1) введем функцую:

<р(г) = вир(е,У1У.){(у*,х-у)/хЕ с!соА, }{х) < /(г),

9{у)=9{*), У*едд(у)} ™

Теорема 3 Пусть в задаче (РИ) функция /(•) полунепрерывна сверху на X и выполнено предположение ([/). Пусть, кроме того, для некоторой последовательности {.г*1} € А, удовлетворяющей

1|у*||>Х>0, V/ едд[у), Чу : д(у) = (Я)

выполняются следующие условия:

lim фк) = О,

оо

lim g{zk) < 0.

К —тСО

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

lim /(**) = /. = inf {//£>}.

к-уоо

Если вместо (3) выполнено условие

lim g{zk) = О,

i—Юо

(£1) (3)

(4)

то последовательность {гк} оказывается минимизирующей е задаче {РЩ. #

Далее, в параграфе 1.3 предложен теоретический метод решения задачи (РЩ, основное правило которого выражается следующим неравенством:

Ы,гк+1-ук)>фк)-*к, (5)

9{ук) = Ук 6 дд(ук), € скоА, /(г*+1) < /(*') (6)

Основным результатом этого параграфа является следующая теорема.

Теорема 4 Пусть выполнено предположение

Зц > 0 31/ > 0 : Уе, в е Я+\0, ' Уж е Л : £г(ж) > < -6>,

или Уе 6 (с?соЛ)\А

Зи = и(х) £ А, —9< д{и) < г/£,

/(«)</(«)-с;

и заданы числовые последовательности со свойствами {е*}, {вк} {$*}, ек > ек+1 > 0 вк5к > 0 : в0 < р, ЕГ= 1 ^ <

+ 9к) <£к~ £к+1-

Пусть, наконец, функционал /(-) непрерывен и удовлетворяет усло-

вию

/, > -оо, Зх0 G X f(x0) ф +оо.

Тогда генерируемая по вышеописанному методу последовательность {zk} удовлетворяет условию оптимальности:

lim <p{zk) = 0. (El)

оо

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

3*>0, Зр > 0, \ ,

НУ* II > X ViT € дд(у), Му : д (у) > -р. / ^

и предположение (U), то эта последовательность оказывается минимизирующей.

Вторая глава посвящена построению алгоритма глобальной оптимизации для задачи (PR) в пространстве R" с ограничением

Ф)= \(Сх,х)-1>0, (7)

где С > 0, С = Ст, 7>0. Кроме того, предполагается, что функция /(•) и множество А -выпуклы.

Пусть множество St(e) обозначает совокупность всех е-стационар-ных точек в задаче (PR).

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

3i/ > 0 : Ve, 0 < е < ет, 1 g(x) <ve Vx G St(e)\ J

3/i > 0 3d > 0 Ve > 0 Vt? > 0 Va € A\Si(de) можво ьай-хй точку и : и G St(de), и £ А, д(и) > -в f(u)< f(x)~Mg(x)+e

(GS) (HS)

Предположение (£75) означает, что все приближенно стационарные в задаче (РII) точки удовлетворяют ограничению д(х) < 0 с некоторой точностью. Смысл же условия (Н Б) состоит в том, что для всякой точки, допустимой, но не являющейся стационарной в задаче (РЯ), можно найти приближенно стационарную и допустимую точку, неухудшающую значение целевого функционала.

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

(HL)

Ve > О, VS > 0, Vz Е St(de) : g(z) > -в Vv £ {я / д(х) = д(г)} можно найти точку

и £ А, и = u(e,S,v), : (g'(v), и) > sup/ * € F(z)} - S;

raeF(z) = {x£A/f(x)<f(z)}. #

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

Далее предполагается возможность приближенного решения связанной опять с условием [El) 'задачи уровня'

{g'{v), и - v) ->• max, g{v) = < - 7. (8)

Оказывается, что для квадратичной функции д(-) вида (7) эта задача решается аналитически.

Лемма 1 Пусть ( — 7 > О иф 0. Тогда точка

( 2С ^

w — аи, гсс а — I ———г- ! , (у)

является решением задачи (8).

Естественно, что построение алгоритма, основанного на условия (Е1), не может быть осуществлено с использованием всей поверхности уровня {х / д(х) = g(z)j, отвечающей точке z. Нужно на этой поверхности уровня выбрать некоторое конечное семейство точек v' , g(v') = g(z),i = 1,..., N, и используя эти точки, осуществить если это возможно, спуск из уровня f(x) = f(z) на более низкий. С этой целью вводится следующее понятие.

Определение 2 Пусть заданы числа £ > 0, <5 > О, 9 > 0 и точка

z&A, g(z) > ~в, g(z) — С ~ J Далее, пусть (N — N(z))

R(z, е, 6) = {v1,.., vN/g(vi) = g{z), i = 1,N}, u{ e F{z) = {x e A/f{x) < f(z)} :

(ffVW) >8ир{(/К),х)№)}-5, (10)

X

we Rn : д{у?) = g(z) :

(g'{wi),ui-v>i)=Bup{(9'(v),«i-v)/9{v) =д(г)}. (11)

V

Тогда набор R(z,e,5) называется разрешающим, если из того, что z не является е-решением задачи (PR), то есть

f(z) >/♦+£,

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

ф) = тах{(д'(и/)Х - w{) / i = ljf] > 0, (12)

i -(тах(С|Л«•'))' > ^sup{(Cz, х)/х е F[z)}J * - (13)

где (Cz, z) = 2£, g{z) = С - 7-#

Далее, наряду с предположениями (HL) и о решении задачи "уровня" рассматривается предположение

Ve > 0, 45 > О, W : 0 < 0 < р Ï

Vz€S*(<fe), g(z)>-9 I можно построить разрешающий набор [ ' '

R{z,e,5); )

Пусть справедливы предположения (HL), (HR). Тогда для решения задачи (PR) предлагается алгоритм, называемый далее R- алгоритмом.

Пусть известны точки

хк G А, д(хк) >0;fc= 1,2,... и последовательности {ек), {Sh] {@к} :

ск > 0, 8к > 0, вк > О к = 0,1,2,... Опишем /¿ алгоритм по шагам.

1. Точка zk

zk € А, ~вк <g(zk) <vdekl

является (с/£^)-стацио11арной точкой, полученной исходя из хк, согласно предположению (Я5).

2. Для zk € St{dek) строится (^¿¡^-разрешающий набор:

R(zk,ek,8k) = = g(zk) = Çk - у, г = TJTk}.

3. Vi = 1, ...,Nk, согласно (HL) находятся точки

А, Ди'") </(**), (д'(у<),и{) > sup{(«,V),z)/* G F(zfc)} - 8к. (14)

т,

4. Vi = 1,..., Art строятся точки w' по формуле (9).

5. Вычисляется величина:

щ = (g'(wi),uj - vJ) = max (д'(ыг),и1 - w*) . (15)

6. Если rjk > 0, то полагаем хк+1 := и', к := к + 1, и переходим на шаг 1.

7. Если щ < 0, то полагаем x-fc+i := zk, к := к + 1, и переходим на шаг 1. #

При численной реализации Ji-алгоритма для достаточно малого £к на шаге 7 при щ < 0 производится останов процесса счета и zk принимается за приближенное решение задачи (PR), поскольку из определения разрешающего набора вытекает

/(**)</.+£*,

где /« = гп/{/(х) / х е А,д(х) > 0}.

Условия глобальной сходимости Ji-алгоритма даются следующей теоремой.

Теорема 5 Пусть в задаче (PR) с функцией </(•), заданной в (7) выполнены предположения (GS), (ЛS), (НR), (НL),а также

Vy € А : д(у) =0, 3h = h(y) 1 п

(g'(y),h-y)> 0; J {u)

3d > 0 Ve 0 < е < £т \ , ™

х е St(d£) Vx € А , f(x) </,+£/ 1 J

Пусть, кроме того, числовые последовательности {с*}, {¿к} и {вк}таковы, что

£k > £k+1 >0, h > 0, вк > 0 v(sk + вк) < ек - £к+1, = 0,1,2,...

0 < во < Р < Т, ЕГ=1 £к < оо.

Пусть, наконец, для точки х° € А выполнено соотношение

Ф0) >-р> -У,

а для последовательности {г*}, генерируемой Я-алгоритмом выполнено неравенство

(16)

Тогда последовательность {г^} является минимизирующей в задаче (ЯД). #

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

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

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

где АТ = (а1, а2,..., ата), а*(г = 1,п),</,г £ Я", Ь Е Ят, матрица С(п х п) положительно определена и симметрична, число у положительное. И доказано следующее утверждение.

Предложение 1 Пусть предположение ({/) имеет место. Тогда множество

(¿,1)4тт, Ах <Ъ, д{х) = ^ (Сх, х) - у > О, (Р1)

Щг) = {V = щС'1^, (г = Т^гп) , г;т+1 =

где

ßm+1

K{C~ld,d)

является разрешающим в задаче (PI).

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

Так, в параграфе 3.1 приведено численное решение /¿-алгоритмом тестовой задачи

/(«) = |||х - yf min, х 6 П= {ж € RT/ai < Xi <bi, i = Т77г>, (P2)

g(x)=%{Cx,x)- 7>0,

где (С = CT, С > 0), 7 > 0 и вектора у,а,Ь £ Яп( а,- < Ь,-, г = Ln) фиксированные.

При решения задачи типа (PR) следует обратить внимание на следующие три фундаментальных момента, вытекающих из описания R- алгоритма:

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

2. выбор численного метода решения линеаризованной задачи;

3. построение аппроксимации поверхности уровня.

Принимая во внимание характер допустимого множества, в качестве метода локального спуска предложен метод, комбинирующий стандартные методы проекции градиента, возможных направлений и характерную для задачи (РЯ) процедуру последовательной линеаризации "плохого"ограничения д(х) > 0. Исследованы свойства

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

Далее, строится аппроксимация поверхности уровня, отражающая специфику задачи (Р2). Построенная аппроксимация состоит простых, легко строящихся точек, таких как .например, (г = 1, п,)

V= (¿1, ..,2п)Т = г + оце', а,- : д{у') = 0, ё - (0,.., 1,,.., 0)т,

или ьг = (гь ..,-г,-,-г;+1.., гп)т, г = 1,..,п- 1,» = -ги V = г — а/'(г), где а выбирается из условия </(г>(а)) = 0. В конце параграфа излагаются результаты численного решения задачи (Р2), с конкретными данными.

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

{V' = (г1,...,2,-_1,-2,-,-г1-+1,г,-+2,...,2п)т,г=1,п- 1; ]

>

г;" = г-2/'(г)-</'(*),* >/1!Л*)||2 )

С использованием этой аппроксимации задача решена до размерности 400 за вполне приемлемое время (3 часа 58 мин 18.65 сек), насколько можно судить по изученной нами литературе не удавалось сделать ранее другими алгоритмами.

Параграфы 3.2-3.3 посвящены численному решению задачи о рюкзаке

(с, х) шах, {а, х) < /3, х £ {0,1}" . (РК)

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

В настоящий момент существует множество приемов перехода. Одним из них является следующее:

Целочисленное ограничение ж,- = {0,1} заменяется на следующие

На основе этого приема получена следующая непрерывная задача

Однако в полученной задаче не выполняется предположения ([/) теоремы 5, что не позволяет здесь обоснованно применить /¿-алгоритм. Поэтому вместо задачи (17) рассматривается связанная с ней возмущенная задача ((5 > 0):

Для задачи (Р$) как нетрудно проверить выполняются все предположения теоремы 5.

Далее доказывается утверждение говорящее о существование верх-ной границы числа <5 для которого с помощью решения задачи (Р$) можно находить решение исходной задачи.

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

х\ — Х{ > 0, 0<ж,-<1.

(е=(1,1,...,1)т):

(17)

На основе развитой теории решения задачи (Ре) проведены численные эксперименты. Результаты сравнения, например, с материалом книги Алексеева О.Г. "Комплексное применение методов дискретной оптимизации, Наука, 1987"свидетельствуют о том, что предложенный подход ни в чем не уступает известным методам решения задач целочисленного программирования.

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

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

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

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

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

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

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

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

1. Стрекаловский А. С., Идэр Цэвээндоржийн.Я' решению обратно-выпуклой задачи математического программирования // Тезисы докладов Международной 10-ой Байкальской школы - семинара "Методы оптимизации и их приложения", Иркутск, 1995, Изд-во СЭИ СО РАН, с 131-133.

2. Strekalovsky A. S. and Ider Tsevendorj. Reverse Convex Programming. Theory and Algoritms// Springer-Verlag, Collection of Abstracts of 17th IFIP Conference on System Modelling and Optimization,(J. Dolezal and J. Fiddereds) vol 2, pp 678-681, Prague ,Czech republic, july 10-14, 1995,

3. Strekalovsky A.S. and Ider Tsevendorj. Reverse Convex Programming. Theory and Algoritms// Volumeof extended abstracts of Illrd Workshop on Global Optimization, ( Austrian and Hungarian Operations research Societies) Szeged, Hungary, December 10-14, 1995, p.119-121.

4. Alexander Strekalovsky and Ider Tsevendorj. Testing R-algorithm for a reverse convex problem. Journal of Global Optimization, находится в редакции, 1995.

5. Strekalovsky A.S., Tsevendorj Ider, Kuznetsova A.A.

Convergence of the R-algorithm for a reverse convex problem.// Universität Trier, Program and Abstracts of 8th French-German Conference on Optimization, (8eme Colloque Franco-Allemand D'Optimization, 8. Franzosisch-Deutsche Konferenz über Optimiering) (M Ries), Trier, Deutschland, 21.-26. juli, 1996, p. 105.

Подписано к печати 16.09.96 г. Формат бумаги 60x84 1/16. Бумага офсетная. Объем 1,0 п.л. Заказ 22. Тираж 100 экз.

Отпечатано на RISO в ОПВЦ ИГУ 664003, Иркутск, б.Гагарина, 20, тел. 33-22-10