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

АКАДЕМИИ. НАУК ССОР СИБИРСКОЙ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи УДК »19.353

ШСАДОРОВ Игорь Александр о бич

КРИТЕРИИ ШЗ'.ШПУКЛОСТИ ЦЕЛЕЕ1К ФУНКЦИЯ В ЗАДАЧАХ ДРОБНОГО ПРОГРАММИРОВАНИЯ

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

Автореферат

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

Нопосио'нрск - 1990

'Рабою выполнена в Институте математики СО ЛИ СССР

Научный руководитель - доктор (¿шико-матаиатичеоких наук, : ' профессор Г.Ш.Рубинштейн

ицшмальние оппоненты: .{октор физико-математических ил™

Э.Х.Гиыади

кандидат физшсо-иатема!гичеош.х наук Н.П.Дементьев

Ведущая организация - Институт кибернетики : т. В.МЛ'луш..эва АН УССР

Защита состоится " _11___ 1990 г. и _ часов

на заседании Специализированного совета К 002.23,01 по присуждению ученой степени кандидата наук при Институте математики СО АН СССР (630050, Новосибирск, 90, Университетский проспект!

С ди. сертацией можно озьакомиуься в библиотеке Института математи"я СО АН СССР.

Автореферат разослан " _"__1990 г.

Учений секретарь Специализированного совета К 002.23.01"

и а н ди да т ф и з и к о-ыо т е м ат и че о к и х

наук 4 у Ю.Л.Васильев

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

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

Существенный вклад в становление и развитие дробного программирования внесен в работэх М.К.Гагарина, Е.Г.Гольштейна, Я.И.Заботина, Г.И.Рубинштейна, Д.И.Соломона, А.Г.Тетерева, Н.З.Шора, Р.Джаганнатана, В.Динкельбаха, Б.Д.Кравена, К.-П. Кроузе, В.Купера, О.Л.Мангасаряна, Б.Иартоша, Б.Ыонда, И.М. Станку-Шшасяна, Дж.А.Ферлан, .а, Дк.фон Неймана, И.Хирхо, А. Чарнса, т.Шайбле и многих других.

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

В то ке время условие квазивыпуклооти является весьма существенным, поскольку для задач кваэивыпукло.о програмииро-' вания разработана теория двойственности (в работах Е.Г.Голь-ша-йна, Х.Дк.Гринберга, Б.Д.Кравена, К.-П.Кроузе, В.П-Пиерска-ллы и других), а также достаточно эффективные численные методы (в работах Я.И.Уабтгина, А.И.Кораблева, Р.Ф.Хабибуллина, Г.Ш. Рубижг'ейна, В.И.Имы["ва, Б.Мартоша и других).

Что касается методов минимизаций конечных сумм дробно-линейных <> нкци.'! в общем случае (т.и. без предпо.". гения ква -зивыпуклости), то их постпоению посвящены работы А.Ё.Крупицко-го, А.Р.Ьир^уртоьа, л.Канбини; Л.Лартои», З.шайоле и других. Однако эти методы является практически реализуемыми, по-в"ди-мому, лишь в случае двух слагаемых.

Целью работы является получение эффективно проверяемых критериев ки-зивыпуклооти конечных сумм дробно-ли"ейпых (фук

ций, а также некоторых дробных функций более общего вида. !

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

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

Апробация пботы. Материалы диссертационной работы сис -■"ематически докладывались и обсуждались в Институте математики СО АН CCCj. на семинарах лаборатории методов оптимизации, к 1те-матико-31 "шомического отдела и отделения прикладной математики. Кроме того, основные результаты диссертации докладывались'на У1 всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989 г.), а также на семинаре кафедры экономической кибернетики Казанского госунивеоситета (рук. Я.И.Заботин) и на семинаре отдела методов решения сложных задач оптимизации в Институте кибернетики АН УССР (рук. Н.З.Шор).

Публикации. Основные результаты выполненных исследований опубликованы в работах [l ~ b] .

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

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

1

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

Первая глава посвящена, в основном, дифференциальным критериям квазиныпуклости конечных сумм дробно-лиизйных функций. Каждая из указанных сумм определс ш на открытом б пуклом множестве XЩ.П и при некоторых ГЬ -мерных векторах Q■¿ и ё. ( I, . . - , пг") , прсдставима в виде

7"

причем 6. х > О , е1. ос е X.

§ 1.1 посвящен обзору известных результатов об условиях квазивыпуклости функций (I). Определенная на выпуклом множестве X Функция /"" называется ква1 .[выпуклой, если для всех X и у, из X и Я <=(0,1) имеют место нерь-енитва

Г((1-Я)х + [С (х), Г (у)},

которые при Пос) ФГ(у) являются строгим!..

До недавнего времени были известны достаточные критерии к: ^ивыпуклости лишь для сумм малого числа дросшо-линейиих функций весьма специального вида. В то жо ьремя известно еле-' думцев эффективно проверяемое необходимое условие квззивыпук- 1 лости чроизвольной о~оедслснной на открытом выпуклом множество X дваждм дифференцируемой ...ункции ¡~ :

х*Х, у-е^* тгтчГ(эс)~0 (?-)

где через V/- (х) ■■ Ч^р(з) обозначены градиент и вторл прэкзиоднал •!•»• в то- се X е X . Од -ако условие

о

(2), воо(>в:о говорл, ьо является диЛг-Л'О'ит.

1.2 низведен ьиделеня» классов функций вид., (I), дл»,

5

[ква;. лвыпуклости которых условие (2) является не только необ' •ходиыкм, но и достаточным. При атоы важную роль играет следу'

УТВЕРЖДЕНИЕ 1.2.2. Если при фиксированных ХеХк ;

функция

;

<

/ а?-ГУ- сХ)

удовлетворяет уел вию

то эта функция является псгоянноМ ко множестве 7" .

С помощью утверждения 1.2,2 доказывается следующий факт. ТЕОРЕМА 1.2.5.. функция (I) в той и только в том случае является квазивыпуклий на открытом выпукла множестве X » рели для всех X » еЩ.к и любого четного числа (Я0<,Щ из выпо нения условия

С10) = °>

следует, что

Х,1г

. . Фигурирующее в теореме 1.2.5 условие квазивылуклости в абцеи случае является труднопроверпемыи. Однако при «КЗ оно совпадает с условием (2), т.е. ии^ет место следующий факт.

СЛЕДСТВИЕ 1.2.6. При 3 ФУНКЦИЯ в ТиМ 11 то-'-ько 11 «г 1 случае является квазивынуклой на шшжестче X ■ еили ино удовлетворяет условии, (2).

Что касаето случая т. > 3 > т0 установлен следующий ф. кт, ,.ри доиРчательотве которого существенно попользовалась

6

'однородность функции (I). I

СЛЕДСТВИЕ 1.2.8. Если функция (I) удовлетворяет условию !

vF(x)=@ v2F(X)>.П-у, (3) :

то она в ' au н только в том случае является квазивцпуклой на множестве X t если выполнено условие (2).

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

УТВЕРЖДЕНИЕ 1.3.3. Если функ'чя (Г) является квазчвнпук-лой нь множестве X » т0 0 помощью подходящего линейного преобразования пврьлвнних она предстовима в виде

27 cL..Xj + Д- Xm+i

--:, (4)

ui хг

где

X G HÜ! т.. > О, i GX }.

Кроме того, отметим следующие результаты. УТВЕРЖДЕНИЕ 1,3.9. Если сради чисел J£. имеются н нуле-•вце, то функция (4) в том и только з тон случае является ква-зиныпуклой на инонестве % . если она удовлетворяет ^оловшо (2).

СЛЕДСТВИЕ 1.3.11. Если функция (4) представила в виде

vo оьа не может бить квазивыпуклрМ на гчояесгве ^ •

УТВЕРЖДЕНИЕ 1.3.13. чсли функция (I) представима в виде

б у.

то она в т.;м и толшо в том случае являет?« кзазивнпуклой на ;.!H0F.ecT3C Х\ < е0;ш является выпуклой функц..л ¿> ^ G (jj).

7

! В этом .не параграфе показано, что условие (2), вообще го--воря, не является достаточным для квазивыиуклости произвольной 'функции вида (I).

В § 1.4 результаты § 1.2 обобщаются на случай отношений двух произьлышх полино-'ов, т.е. определенных на открытых выпуклых множествах Функций /- , представимых в виде

' хеХ-

где Р и О - полиномы степени т^ и Ш2 соответственно, причем О, (Х)>0, Х^Х-

следствие 1.^.5. При пьа.£ ( т,, тг} ^ 3 Функ -цип (Ь) в том и только в том случае является квазивыпуклой на множестве X , если она удовлетворяет условию (2).

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

СЛЕДСТВИЕ 1.4.6. Пусть функция (5) удовлетворяет условию (3), полиномы Р и являются однородными, причем

ПХ 2 > О . Тогда (функция (¡3) в том и только в тем случае является к -азивынуклой на множестве X , если она удовлетворяет условию (2).

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

В § ¿.I и § 2.2 исследуются суммы двух и, соответственно, трех дробно-линейных функций. Для квазивыпуклости таких фуш'чий условие (И) в силу следствия 1.2.6 является необходимым и достаточным. При этом для случая суммы двух дробно-ли -нрчних функций в § 2.1 показано,что "если множество X является 'шох'ограшшм, то таковыми ае будут соответствующие подмножества, Не которых функция (4) является квазивипуклой (см. утверждение .11.

Что касается случая /72=3, то в § 2.Г. достаточно подробно разобраны различные частные случаи, В частности, н^луче-

Ни следующие результат.

I УЧЪШЩЖ 2.2.1. Если =0, , тэ функция

(4) в тон и только в том случае Является квазивииуклой на ино-жестве { Xе X I ЭСу ^-0} , если выполнено одно из следующих двух условии:

с) существует р^лно один такой номор I'£ Т, что* О, при этом г

хеХ.

¿¿Г I

УТВЕРЖДЕНИЕ 2.2.4. Еслио(1 • »О, т1' Фи-

кция (4) является квазивыпуклой на ыкок^стве Д '.

УТВЕРЖДЕНИЕ 2.2.5. Если функция (4) представила в виде

Ш-^+л^+гЬ , х*Х,

то она является квазивыпуклой на множестве

[хеХ I (с(2#)% - + Ъ сЯ

В § 2_^3 изучаются суммы произвольного числа дообно-лп -нейных функций специального вида. Для квазивыпуклооти тких функций условие (2\ вообще говоря, не является достаточным. Однако удалось выделить следующг^ частные случаи функций ида (4), для квазивыпуклости которых условие (2) является достаточный:

1)1ЬС =0

. Х1 ■ л - ^ 1'€ -Г

-'г J

(см. утверждение 2.3.3);

2) С619

, /¿«"p" j=m> f , 1 ~ / 01J лри 4 * J€ \

J L 0 в остальных случаях, L^J^X

(cw. утверждение 2.3.4).

Кроне 'iro, в § 2,3 рассмотрены следующие частные случаи;

ФЯкаий вида (4):

3) cLi • —Ot (eu. утверждение 2.3.1);

'О= i^l^ii} (CM' утверждение 2.3.2).

Отметим, что в случаях 3) и 4) „оловие (2) в силу слод -

iiThiip 1,3.9 пвляетоя необходимым и достаточным для квезивыгу-

к ости функции (<♦).

Наконец, в1 § 2Л_ изучаются функции вида т

F(x) = z ^Д+уМП^, хсХ (6)

¿с-1 S.X ici 1 > .

где M -некоторая -онстанта. Доказано следующее

УТВЕ" 1ДЕНИЕ "\4.3. Функция (6) является квазивыпуклой на иновествэ

¡теXI F(x)<Ot ajx ъО} t*l}é

(?)

Кроне того, в § 2.4 показа э, что функция (6), вообще говоря, яьляется к" чзивыпуклой на множествах более широких, чей

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

I

I. Установлено, что пологителк'ая лолуопределенн^сть ге зиана на касательных направлениях является достаточным условием квазивыпуклости сумм не более трех дробно-линейных функций.

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

; 3.Перечисленные резуль: .tu обобщены на случаи отношений 'произвольных полиномов от многих переменных.

Получено упрощенное представление квазивниуклих сунн дробно-линеГших функций.

5'. В' -елены новые классы квазивыпуклых суш дробно-ли -нейных функций.

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

Основное содержание диссертации опубпиковано в следующих работах:

1. Еыкадоров H.A. Об условиях квазивыпуклости суш дробно-линейных функций //Оптимизация. - Новосибирск, 1986.

Вып. 39(55). - С. ¿6-41. - '

2. Е-жадоров И.А. Некоторые признаки квазивыиуклг-ти суш дробно-линейных функций //Методы математического программирования и программное обеспечение: Тез.докл. У1 Всесоюз. копф., Свердловск, февр.-март 1989 г. - Свердловск, 1989. -

С. 33-34.

3. Еыкадоров И.А.Дифференциальные признаки квазивыиук^ь-сти конечных oyitj дробно-линейных функций, - Новосибирск, 1у89. - 23,с. - (Препринт /АН СССР. Сиб.ь/д-ние. Ин-т математики; № Z'i].

Еыкадоров Й.А. Дифференциальные признак.' квази-чпук-.»ости отношений полиномов от многих переменных, - Новоси''чрск, 1990. - 20 с. - (Препринт /АН СССР. Сиб.отд-ние. Ин-т математики; № 12).

5. Еыкадоров H.A. Условия квазивыпуклости для некоторых классов дробных функций. - Новосибирск, 1990. - 40 д. - (Пре принт /АН СССР. Сиб. отд-ние. Ин-т математики; № 18).