Минимизация функции, имеющих вогнутую миноранту на компактном множестве, и их свойства тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Г 1 ■>

1 5 МАП 1393

*

МИНИСТЕРСТВО НАУКИ, ВЫСШЕЙ ШКОЛЫ И ТЕХНИЧЕСКОЙ ПОЛИТИКИ РОССИИ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ХАМИСОВ Олег Валерьевич

МИНИМИЗАЦИЯ ФУНКЦИИ, ИМЕВДИХ ВОГНУТУО МИНОРАНТУ НА КОМПАКТНОМ МНОЖЕСТВЕ, И ИХ СВОЙСТВА

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата Физико-математических наук

.ИРКУТСК - 1993

Работа выполнена в лаборатории "Исследование операций" Сибирского Энергетического Института СО РАН

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

профессор В.П. Булатов

Официальные оппоненты: член-корреспондент РАН,

профессор И.И. Ербнин

кандидат физико-математических наук, доцент A.C. Стрекаловский

Ведущая организация: Институт математики СО РАН

Защита состоится " 30 " марта " 1993 г. в 10

часов на заседании специализированного совета К 063.32.06 по присуждению ученой степени кандидата физико-математических наук в Иркутском государственном университете (664003, бул. Гагарина, 20, 1-й корпус ИГУ).

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

"1993 года

Н.Б. Бельтшов

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

*Яв » m&W-sLZL

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

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

Актуальность темы-. Многоэкстремальные задачи широко встречается в различных областях науки и техники. По определении задача многоэкстремальной глобальной оптимизации состоит в отыскании глобального минимума вещественнозначной функции, которая имеет несколько отличных локальных минимумов. Допустимая область в Еп обычно определяется системой неравенств. Хорошо известно, что многие задачи, возникающие в различных прикладных исследованиях, являются по существу многоэкстремальными, Стандартные методы нелинейного программирования не приводят к успеху при решении таких задач. В • большинстве случаев это связано с многоэкстремальностью и в меньшей степени зависит от гладкости, размерности или других свойств целевой функции и допустимой области. Используя такие локальные понятия как градиент, субградиент или матрица вторых производных при решении достаточно сложных многоэкстремальных задач, мохно надеяться лишь на получение локального решения. Кроме того, классические методы, как, правило не дают оценки отклонения локального решения от глобального. По этой причине возникла необходимость в разработке -новой техники решения многоэкстремальных задач. К настоящему времени созданы три мощные вычислительные схемы, которые составляют современную вычислительную базу решения задач глобальной оптимизации. Первая схема объединяет различные методы отсечения, вторая - методы ветвей и границ, третья - методы аппроксимации. В сочетании с мощной современной вычислительной техникой эти методы или различные комбинации этих методов позволяют решать достаточно сложные многоэкстремальные задачи. Наиболее широкий класс задач, решаемых на основе данной вычислительной базы, составляют задачи, в которых целевая функция и функции-ограничения являются локально липшицевыми функциями. Известно, что большинство задач глобальной оптимизации, встречающихся нц практике, являются задачами данного класса. Однако эффективность методов решения таких задач существенным образом зависит от точности оценивания константы Липшица, а

. з

достаточно точное оценивание константы Липшица - задача сама по себе весьма сложная.

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались на конференциях "Методы математического программирования и их программное обеспечение" (Свердловск, 1987, 1991), на международных семинарах "Методы оптимизации и их приложения" (Иркутск, 1989, 1992), на 15-й Международной конференции ПТР по системному . моделированию и оптимизации (Цюрих, 1991), на международной конференции 15ЕМА-92 (Еензень, Китай, 1992), на втором советско-китайского семинаре (5Е1-ШИ, Иркутск, 1992), на конференции молодых ученых СЭИ (Иркутск, 1991)., на научных семинарах СЭИ и ИММ УрО (Екатеринбург).

Структура работы. Диссертация состоит из введения, трех глав и заключения, списка литературы, содержащего 71 наименование. Она содержит 4 рисунка. Работа изложена на 64 страницах. Всего 68 страниц.

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

Введение содержит краткое изложение полученных результатов.

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

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

В параграфе 1 описаны основные свойства функций, имеющих вогнутую миноранту на компактном множестве.

Пусть заданы компактное множество И с еР и скалярная функция Пх) определенная всюду на И, Г:й . Е^.

Определение 1 Будем говорить, что функция 1(х) имеет

вогнутую миноранту на R, если существует функция *>(х,у), р : Е^Е11 • Е1, непрерывная по х для любого у, такая, что

1. р(х,у) - вогнута по х;

2. Ш) ^ р(х,у) vr.y е R; (1)

3. i(y)=p(y,y) Vy е R. (2) Функцию р(х,у) будем называть вогнутой минорантой функции f(x), построенной в точке у. Мнохество всех функций f(x), f:A-»E^, A=R, имеющих вогнутую миноранту на мнохестве R.обозначим через CM(R), а сами функции f «= CM(R) будем называть с.т. функциями (с.т. -первые две буквы английских слов concave minorant - вогнутая миноранта)

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

Теорема 1 Пусть (1=1.....ш) есть с.ш. Функции. Тогда

справедливы следующие утверждения.

(I) - -Любая неотрицательная линейная комбинация функций

1^1=1 есть с.ш. функция.

(II) • - max (х) и min f.,(x) есть с.ш. функции.

1 ia<m 1

(Iii) i+(x)=max (0,f(х)} и i~(x)=min (0,i(x)} есть c.m. Функции.

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

Теорема 2 Всякая функция f «= CM(R) является полунепрерывной снизу на R.

Рассмотрим следующую задачу математического программирования.

min f(x), (3)

g±(x) < 0, 1=1.....m, (4)

X е R, (5)

где R с i - компактное мнохество, i, gj^ е CM(R) (1=1,...,m). В силу Теоремы 2, функции g^ (1=1,...,m) полунепрерывны снизу на R и поэтому множества G* = { х е R : g^(x) i 0 } компактны. Тогда и допустимое мнохество в задаче (3)-(5) Т = G^nG^o■-ffi™ компактно и так как функция i такхе полунепрерывна снизу, то в силу известной теоремы Вейерштрасса о достихении полунепрерывной снизу

функции минимального значения на компактном множестве задача (3)-(5) имеет конечное решение.

В дальнейшем, задачу (3)-(5) будем называть задачей с.т. программирования. Очевидно, что задачи линейного, выпуклого и вогнутого программирования являются частными случаями задачи с.ш. программирования.

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

Определение 2 Функция Ь :ЕП •» Е', называется с1.с. функцией на Н, если существуют выпуклые Функции 7:ЕП-ЕЧ и:Еп»Е1 такие, что

Мх)= у(х)-и(х), ух с И. (б)

Множество всех й.с. функций обозначим через БСШ). Известно, что множество БСШ) всюду плотно в С (Я), где С (Я) множество непрерывных на й Функций. Этот факт подчеркивает в.ажность исследования и использования <1.с. Функций в задачах оптимизации. Пусть 1г е СС(Ы) и справедливо разложение (6). Из выпуклости т(х) следует, что функция

р(х,у) = 7(у) + рт(х - 7) - у»(х), р е 37(у) ( где ву(у) обозначает субдифференциал функции у в точке у ) вогнута по х при любом фиксированном у.- Нетрудно проверить, что р(х,7) будет вогнутой минорантой Ь(х) на' И.. Следовательно ЬеСЬКЮ. Следующий пример показывает, что не всякая с.т. Функция является й.с. Функцией. _ .

Пример 1. Пусть И = [-1, Т] с Е1. Рассмотрим функцию одного переменного

' 1. х<0

fix) = 0, х=0

2. х>0

Легко проверить, что Функция

' mln{1, х/у}, у<0 р(х,У) =0, у=0

mln{2, 2х/у>, у>0 является вогнутой минорантой f(x). Таким образом, Г(х) есть с.ш. функция. Она не является d.c. Функцией, поскольку всякая d.c.

Функция является локально липшицевой и, следовательно, непрерывной. Кроме того, для многих функций ieDC(R) намного легче построить вогнутую миноранту р(х,у), чем найти d.c. разлохение. Из сказанного следует, что задача d.c. программирования такхе является частным случаем задачи с.т. программирования.

Параграф 2 посвящен ыетоду отсечений в En+1 для минимизации с.т. Функции на многограннике.

Рассмотрим следующую задачу математического программирования :

min f(x), (7)

X е R = { ХеЕ11 : Azib, а X äi ft }, (8)

где f е CM(R), А - пьсп матрица, b е Еш, a,ß <= Еп. Обозначим через X* одно из решений задачи (Т)-(8) и 1* =Г(х*). Напомним, что мнохество

V = { : i<z) * w XcR }

называется надграфикои Функции f(x) на R. Тогда задача (7)-(8) эквивалентна следующей задаче

min х^, (9)

(r.zn+1) - Rn+1. (10)

Опишем теперь метод решения задачи (9)-(10), предлохенный В.П. Булатовым.

Предполохим.что известны оценка p<f*n мнохество

(например, в качестве мнохества мохно взять

мнохество (x,xn+1): х.^ ^ е^, 1=1,...,п, хп+1^р>, где вектор

а определен в (8)). Пусть w «= R - некоторая допустимая точка. Шаг 0. Задать с^О, установить f®=+a>, k=1, v®=w. Определить

14+1-С<х.гп+1rJ+1 : x^R>.

Шаг 1. Решить вспомогательную задачу

minxn+1 k (11)

(х.х^) = R£+1. (12)

Пусть yk = ) решение задачи (11)-(12).

Шаг 2. Определить fk=min ilk-1, i(xk) }. Если iKtiJ*), то vk=xk, иначе Если

то останавливаемся : - е оптимальное решение задачи

(9)-(10) (см. замечание 1 ниже). В противном случае переходим к Шагу 3. Шаг 3. Определим конус

й£+1 « < У е : < Бк >.

образованный активными в .точке у^ ограничениями задачи (11)-(12), т.е.

IVе = Бк. (14)

В предположении невырожденности задачи (11)-(12) существует

матрица = обратная к матрице Столбцы

к, Л к, 5 к,3 и

Б = (з , вп+ ^) матрицы Б взятые с обратным знаком

являются направляющими векторами ребер конуса .

Следовательно, лучи, описываемые уравнениями к,3 к.З к,3 и к,Л к,3 к.З у =(х ,хп+1)=зГ-^ Б >0, 3=1,....п+1, (15)

определяют ребра конуса Н^. Шаг 4. В точке построим 'вогнутую миноранту р,,(х) =р(х,хк)

— 1--------Л

функции 1(х). Найдем числа

к.З V _к.З к.З" т, _к,3 к,3

а : »>к0г- в )= 8п+1> -И.....П+1

Тогда точки

" к,3 к,3 к,3" к,3 к,3

• . Ъ Б , 3=1.....П+1 (17)

есть-точки пересечения лучей (15) с поверхностью ^(х)=хп+1 "Проведем через точки (17) плоскость

Н^у = (18)

Шаг 5. Определим множество

" П < У*ЕП+1: Н^ £ ^ } (19)

Установим к = к + 1 и перейдем на Шаг 1. ■1

Как показано В.П. Булатовым, отсечения определяемые плоскостью (18) являются правильными, т.е.

Н^ ^ Ук. Уу «= нп+1.

Замечание 1. В силу (19) Ук = » следовательно

решения вспомогательной задачи (11)-(12) удовлетворяют

неравенствам

* — < ••• <20>

С другой стороны в силу построения ^ ... > I*. Поэтому

справедлива следующая двусторонняя оценка

< 1* < *к, Ук. (21)

Поэтому, как только выполнено неравенство (13) алгоритм останавливается на Шаге 2 : найдено с - оптимальное решение.

Замечание 2. Необязательно вычислять обратную матрицу как это требуется на Шаге 3. В [Семеней, Хамисов, 19871 описан

простой способ определения направляющих векторов ребер конуса

Он состоит в следующем : пусть у вершина и 3=1,...,п+1

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

. л

Ку ^ : Ну^. Требуется найти вершину у являющуюся решением задачи : тш хп+1

<*»*п+1> е П <У : Ну 6 >

А 1 А

и направляющие вектора Б1* , 3=1,...,п+1 ребер конуса й активных в

А А

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

где

- _ в - НУ _10

2 - НУ Т„1

3° = агетш { „ , , 3 : НТ53 < 0 ),

А

а направляющие вектора ребер конуса к^ ^ вычисляются по формуле

5*®, если =0

Б3 = - у, если НЧЗ3 <0, у - если >0

где

г3 = У--=г-г- Н 53 * О, 3=1.....п+1,

Нт53

В [ Семеней, Хамисов, 1987 ] описан метод решения задачи линейного программирования основанный на приведенных выше формулах.

Уравнение отсекающей плоскости (18) мохно записать в следующем виде

= <1/£к)Бк - 1, (22)

ь. к,1 к,п+1 k,i

где (1/\*)=(1/*: , ...,1/\ ), числа Г , 3=1,...,п+1

определены в (16), а (п+1)х(п+1) матрица 1к и вектор 5к определены в (14).

Перейдем теперь к описанию некоторых свойств алгоритма и обоснованию его сходимости.

Лемма 1. Если int R * о и JHk5'J<5>0, k=1,2,3.....то Эо-, С>0:

a) h£+r-0,

b) ¡h^+1|ï»>0, о' - const,

lüÄl - -

c) -Tz— С, С - const.

В дальнейшем уравнение отсекающей плоскости (18) будем записывать в следующем виде

^ - b£+1*n+1 = <23>

где Обозначим через d(x,R) = in! { lb - yll , y e R }.-

Лемма 2. Пусть уравнение отсекающей плоскости (18) записано в виде (22), т.е. Hk = (1/£k)îk и £ = (1/£k)5k - 1,

"к = cKyV), (24)

где Рк =4 у En+1 : Н1^ = £ }. Тогда

<ок = 1Ик1Г1. (25)

Следующий результат, полученный ранее другим путем В.П.Булатовым, непосредственно следует из Леммы 2.

Теорема 3. Если IIH^l ^ Ь, Ь - const, vfc, то приведенный алгоритм конечен.

Условие IB&l ^ L сформулируем в эквивалентной, более удобной

для дальнейших рассухдений форме. Представим = ( )»

где и определены в (23). Справедлива следующая Лемма.

Лемма 3. Предполохим, что vk

О < г < IßAl «S г < +со, (26)

где г и г - некоторые константы. Тогда Ш^Л < L тогда и только

IflAl

тогда, когда —- ^ а >0.

Следствие 1. Если выполнены условия (26), то ¡ffrll « <», к-»®,

llh^l

тогда и только тогда, когда —г--. о, к-»®.

Условие (26) не является жестким и почти всегда выполняется на практике.

Условие HH^üsiL, гарантирующее конечность алгоритма, весьма существенно. В практических расчетах очень часто при достаточно больших величинах IIH^Il отсечения становятся малоэффективными, т.е. в силу Леммы 2 «; <s, где б мохет быть сколь угодно мало, и в силу Следствия 1 отсекающие плоскости становятся "почти" параллельными друг другу и "почти" ортогональными вектору е En+1,

en+1 = (0.....0,1). Однако условие |Щ1,С11 < L не является

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

Теорема 4. Пусть величины определенные в (24) таковы, что

m

'{ v Jг

lim <л> = 0 и ряд ) расходится. Тогда приведенный выше

к-ш

алгоритм конечен.

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

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

Пример 1. Пусть I е С2(й), Са(Ю - множество двахды непрерывно дифференцируемых на И функций. Известно, что существует ^ ^ О

такое, что функция *>(х)= i(x) + - выпукла. Тогда f(x) есть

d.c. Функция поскольку справедливо разложение

i(x) = р(х) - ЛЫ12.

А всякая d.c. Функция является с.т. Функцией.

Пример 2. Пусть i (х) - Функция, удовлетворявшая условию

Липшица всюду на R с константой L, т.е.

| i(X) - f(у) I < L Its — yll, vx.y е R.

Тогда вогнутой минорантой функции f(x) в точке у будет Функция

р(х,у) = i(y) - Lib - yll. гг,

Пример 3. Пусть i (х) =2aksk(x)' где Sk(x)' k=1,...,m

k=1

Функции, удовлетворяющие условию Липшица с константами Lj,. Очевидно, что вогнутая функция миноранта р(х,у) определяется следуюсим образом

р(х,у) = J ak(gk(y) - L^llx - yll) + 1 ak(gk(y) + L^lx - yll), keK+ ' keK~

где K+ = { k : a„ >0 >, K" = { k : a,. < 0 }.

К m к

Пример 4. Пусть f (x) = ^ (a^sln + b^cosi?^^). Поскольку

k=1

для любого k Функции a^sin <=<kxk и b^cos f?kxk удовлетворяют условию Липшица с константами |akc»k| и соответственно,

можно построить вогнутую миноранту р(х,у) по аналогии с примером 3

m

р(х,у) = J (aksln akyk - Bign(ak)|akck||xk - yk| + k=1

+ bkcos r?kyk - sign(bk)|bkr3k||xk - yk|).

Пример 5. Рассмотрим следующую задачу

mill f(x), (27)

X e R, (28)

Xj £ { 0,±1,±2,...}, 1=1.....n, (29)

где f e CM(R), R - компактное множество. Обозначим через R1 -

множество допустимых решений задачи (27)-(29). Предположим, что R1 * е. Введем в рассмотрение функции

п

Ь(х) = i(x) + N ]j> ]sin(rcx)I, 1=1

где N - некоторое положительное число. Справедлива следующая теорема.

Теорема 5. Для любого с > 0 существует N(e): VN^ N(e) оптимальное решение х* задачи

min h(x), (30)

X е R, (31 )

удовлетворяет соотношению

max |xj - х£| ^ с

где хс е R1 оптимальное решение задачи (27)-(29).

Для того, чтобы доказать, что h. е CM(R) достаточно показать, что функция одного переменного p(t) = sln(nt) есть c.m. Функция, поскольку в силу Теоремы 1 неотрицательная линейная комбинация c.m. Функций есть c.m. функция, a feCM(R) по определению. Из геометрических соображений видно, что функция p(t,r) определенная ниже есть вогнутая миноранта функции p(t) построенная в точке г :

О, t - целое

t - |rj

*<t.r) =

|sin(nr)l, t<r, Г - W Lr]+1 - t

|Bin(nr)|, t>r

Lrj+1 - г

где |rj - наибольшее целое, не превосходящее г. Таким образом, задача целочисленного программирования (27)-(27) может быть сведена к задаче c.m. программирования (30)-(31).

Пример 6. Рассмотрим задачу дискретного c.m. программирования

min f(r),. (32)

UR, (33)

ij <s D = { ,

(34)

, где К - компактное множество, 1е СМ(К). Обозначим через 1)=Б*х. ..хГ)11. Для любого 1 построим полином степени к. к к-1

р^) = х^ + а^х^1 +...+ + а^, 1=1,...,п

I с

такой, что р^(с1^)=0, *3=1,..., к. Введем в рассмотрение

следующие функции р^(х)=|р1(х)\ и Р+(х)= £ Р^^)• Поскольку VI

1=1

Р1(Х1) -Липшицева функция (следовательно с.ш. функция), то в силу Теоремы 1 функции р^х^, 1=1,... ,п и Р+(х) также являются с.ш. функциями. Рассмотрим теперь следующую задачу непрерывного с.ш.

программирования

min i(x) + К'Р (х),

35)

X е R, (36)

где К некоторое положительное число. Справедлива следующая теорема, аналогичная Теореме 5.

Теорема 6. Для любого е>О существует номер N(c) такой,что vN^N(c) оптимальное решение х* задачи (35)-(36) удовлетворяет соотношению

max Ixi - ^ с, Uiign х 1

где х" = (х",...,х^) - оптимальное решение задачи (32)-(34). Вогнутую миноранту ^(t.r) функции p^(t), vi в точке г можно определить следующим образом ( ср. Пример 5 )

p4(t,r) =

О,

t

г - й<

а1 - t

а1 - г

Pi (D. Pi(г),

t с D

t < г, t > г

(37)

где

Зч = max { d4 : >,

1 Kis&j 1 13

d< = min { d< : d< г }.

Ki^ 1 10

Пример 7. Пусть требуется найти решение следующей системы g^(X) = 0, 1=1,...,т, (38)

X 6 R, (39)

где R - компактное множество, g^eDC(R), 1=1....... msin и известно

явное d.c. разложение каждой функции g^, т.е. vi известны выпуклые функции v^(x) и w^(x) такие, что

g^x) = v±(x) - w^x). (40)

Очевидно, что задача (38)-(39) эквивалентна следующей задаче с.т. программирования

ш

min J IgjteH. (41)

i=1

i e R, (42)

.Такин образом приведенные выше примеры показывают, что многие важные задачи математического программирования сводятся к задаче с .т. программирования.

Параграф 2 посвящен описанию таких с.т. Функций, для которых

вогнутые миноранты могут быть достаточно просто построены.

В общем случае достаточно трудно определить имеет ли данная ч п

функция I(x), I:R - Е', R с Е , вогнутую миноранту. Даже если известно, что feCM(R), то как конструктивно построить вогнутую миноранту функции i(x) в произвольной точке y<nR? Оказывается, что для достаточно широкого класса функций можно описать правила построения вогнутых минорант.

Определение 3. Функция f(x), 1:R-»E^, RcE11, удовлетворяющая условию

I е CM(R), -1 е CM(R), (43)

называется с.т. симметричной функцией.

Из определения видно, что с.т. симметричная функция является с.т. функцией, Множество с.т. симметричных функций, определенных на R, будем обозначать через CMS(R). Из (43) следует, что для

любой функции f е CMS(R) и vy е R существуют функция *>~(х,у), *>:EnxEn-»E^, непрерывная и вогнутая по х для любого у и функция ргЕ^Е^Е1, непрерывная и выпуклая по х для любого у, такие, что

1. *>-(х.уК ШК р+(х,у), vx.y е R; (44)

2. i-(y,y)= i(y)= Р+(У,У), vy <Е R; (45) Функцию р+(х,у) будем называть выпуклой махорантой, а функцию р~(х,у) вогнутой минорантой Функции f(x), построенными в точке у. В силу Теоремы 2 с.т. симметричная функция является непрерывной. Класс с.т. симметричных функций достаточно широк, поскольку нетрудно показать, что всякая локально липшицевая функция является с.т. симметричной функцией.

Теорема Т. Пусть f <= CMS(R) и f^ CtiS(R), 1=1,...,m. m>1. Тогда справедливы следующие утверждения, ш

(1) 2 е CMS(R), G Е1, 1=1.....m.

1=1

(И) I2 <E CMS(R).

(Ill) i^Ig e CMS(R).

(vl) если f(x)>0 VX e R, TO i"1 e CMS(R).

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

В параграфе 3 приведены результаты численных экспериментов метода отсечений в Еп+^. Примеры были взяты из книги С. Флаудоса и П. пардалоса "A Collection oi test Problems for Constrained Global Optimization Algorithms", численные расчеты показали эффективность данного метода.

Автор вырахает искреннюю благодарность В.П. Булатову, под руководством которого была выполнена эта работа.

ПУБЛИКАЦИИ

1. Семеней П.Т., Хамисов О.В. 00 одной модификации метода опорного конуса // Методы математического программирования и программное обеспечение. Тезисы докладов научной конференции.-Свердловск, 1987, с. 101-103.

2. Булатов В.П., Хамисов О.В. Методы отсечения в еР+1 для решения задач на глобальный экстремум// Международная школа-семинар по методам оптимизации и их приложениям. Тезисы докладов. Иркутск, 1989, с. 36-38.

3. Хамисов О.В. Метод ветвей и границ для минимизации вогнутой функции на многограннике// Материалы XXXI конференции молодых ученых. СЭИ, Иркутск, 1991, с. 25-33.

4. Хамисов О.В. Метод отсечения в En+1 с ветвлением для решения задачи вогнутого программирования// Математическое программирование и приложения. Тезисы докладов научной конференции.-Свердловск, 1991, с. 136-137.

5. Bulatov V.P., Khamisov O.V. The cutting method in En+1 through concave extension for solving global extremism problem// 21 JAHRESTAGUIIG "Mathematische Optimierung".- Berlin, 1989, pp.16-19

6. Bulatov V.P., Khajnisov O.V. The cutting methods in concave programming// 14th Conference on System Modelling-- and Optimisation, Poster Contributions, Part I, Keif 7,- Leipzig, 1989, pp. 33-35

7. Bulatov V.P., Khamisov O.V. On the reduction of some multiextremal problems to the convex-concave programing problem// On engineering mathematics and applications, Shenzhen, China, 1992, pp. 103-107

8. Bulatov V.P., Khamisov O.V. An investigation of equality • constrained mathematical programing problems and its application

to the economic and power engineering problems// Second SEI-IPRI Seminar on methods for solving the problems on energy power 6ystem development and control.- SEI, Irkutsk, 1992, pp. 90-95

9. Bulatov V.P., Khamisov O.V. The branch and bound method with cuts in En+1 for solving concave programming problem// Lecture Notes in Control and Information Sciences, 180, Springer-Verlag, 1991, pp. 273-282