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

КАЗАНСКИЙ ОРДЕНА ЛЕНИНА' И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени В. И.УЛЬЯНОВА-ЛЕНИНА

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

АНДРАМОНОВ Михаил Юрьевич

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

01. 01. 07 - вычислительная математика

Автореферат

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

КАЗАНЬ - 1993

Работа выполнена на кафедре экономической кибернетики Казанского ордена Ленина и ордена Трудового Красного -Знамени государственного университета имени В.И.Ульянова-Ленина

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

профессор Заботин Я.И.

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

старший научный сотрудник Березнев В.А

Ведущая организаци. " ий государственный. университе!

заседании специализированного совета К 053.29.05 по присуждению ученых степеней по.математике в Казанском государственном университете имени В.И.Ульянова-Ленина по адресу:

420008,г.Казань,ул.Ленина, 18,корпус 2,ауд. 217

С диссертацией можно ознакомиться в научной-библиотеке Казанского государственного университета /420008,г.Казань,ул. Ленина, 18/.

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

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

1993 года.в ^Учасов на

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

1992г.

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

совета,профессор Б.Н. Шапуков

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

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

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

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

В диссертации предложена одна, общая схема сведения задачи квазивыпуклого программирования к задаче безусловной минимизации маргинальной функции.дающая возможность построить ряд численно реализуемых алгоритмов условной минимизации. Целью работы является разработка эффективных методов решения задачи квазивыпуклого программирования.основанных на ее сведении к задаче минимизации вспомогательной маргинальной функции, и построение общей схемы перехода к такой задаче. Методика исследования основана на применении фактов выпуклого и негладкого анализа,широко используется развитый Я.И.Заботиннм, А.И.Кораблевим.Р.Ф.Хабибуллиным аппарат обобщенно-опорных Фун-

- 3 -

кционалов.а также введенное В.Р.Фазыловым понятие тага,сохра-нящего опорноеть. Для обоснования результатов диссертации используются Факты из области теории маргинальных функций,установленные В. Ф. Демьяновым, A. M. Рубиновым, Б .Н. Пш еничным. Научная новизна. Предложена одна общая схема сведения задачи квазивыпуклого программирования к задаче минимизации маргинальной функции на множестве простой структуры.Построен ряд методов решения вспомогательной задачи фейеровского типа с корректировкой оценок мйнимаяьного значения.Разработан критерий £ - оптимальности итерационной точки для методов такого типа. Исследованы свойства вспомогательной функции. Практическая ценность. Предложенные методы квазивыпуклого программирования допускают простую программную реализацию.Вспомогательную задачу с простым ограничением достаточно решить один раз,не требуется пересчет штрафных параметров.Для минимизации функций различных классов используются разные варианты алгоритмов, что позволяет лучше учитывать специфику задачи. Ащюбапия работы. Результаты диссертации докладывались автором на семинарах кафедры экономической кибернетики КГУ в 1989 -1992г. /научный руководитель - проФ. Я.И.Заботин/.на итоговых научных конференциях КГУ в 1989-1992г.,на семинаре кафедры математической Физики МГУ в 1992г. /научный руководитель - проФ. Ф.П.Васильев/,на ХП -ом Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования и их использование" /г.Нарва-Йыэсуу,1992/.

Публикации. По теме диссертации опубликовано 3 печатных работы, список которых приведен в конце автореферата. Структура и объем работы. Диссертация состоит из введения,четырех глав,заключения и списка литературы.Занимает 128 страниц машинописного текста.

Основное содержание диссертации:

Во введении приводится краткий обзор литературы,указаны основные результаты диссертации и изложена ее структура.

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

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

Определение 1. Вектор ^ называется обобщенно-опорным вектором в точке к множеству Е-и ,если

Если неравенство выполняется строго,то вектор называется строго обобщенно-опорным.

Определение 2. Гиперплоскость \ х € Е =^называ-

ется обобщенно-опорной гиперплоскостью в точке ^бН к множеству »если вектор ^ или вектор — ^ является обобщенно-опорным к в этой точке.

Пусть ^ -некоторая функция,определенная на выпуклом множестве -2) .

Определение 3. Функция / называется квазивыпуклой, если . для любых двух точек £ ,для любого Я из отрезка С°>-О выполнено неравенство: ч ч , , ,'п

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

Определение 4. Число 0 называется шагом, сохраняющим опорность вектора С1€Е„, =1 к множеству ^ в точке хбЕ*,, 'если с Ъ.

В §1.1 приводится ряд утверждений относительно шагов,сохраняющих опорность к множествам.

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

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

зивыпуклой функции на выпуклом множестве с непустой внутренностью:

X о

Обозначим 2> — htflbfè^j M.Пусть для точек У и

вектора ^ .строго обобщенно-опорного к X ъ Ъ .выполнены условия: Vx*c?>\

Зададим следующую гиперплоскость: К,- ^ С^6*"

Для всех UCK определим множества:

= {-¿его, o/u + t (г - ^ f »J,

I г) = fi* € ТК -г.)| -f t*Cz- ч!)= ^¿^-J •

На гиперплоскости 1JL определим функцию s

y>/ ц) =. Me (o 4 ( w+ ¿("Z-- <-<Л ^ '

Определение 5, Будем говорить,что точки U£U>xç$> соответствуют друг другу,если существует IYтакое, что

и ~ и) — X .

Лемма 1. Для соответствующих друт другу точек выполняется-равенство V(ч)- .

Теорема 1. Пусть Тогда

1/ Существует точка u?tU* - firatnih .соответствующая

V/УVUflt

X' 655 .причем _ ,, „ч

lc<1.x «) г- су-ï,<px* 3/."г - х

2/ Число t ' - (<£> V- v)/fy? - ^принадлежит I * ( и? г). 3/

4/ В точке U* функция V принимает минимальное значение на гиперплоскости IL .

Теорема. 2. Пусть Ц,¥б11*и точка Х*^ соответствует W*. Тогда X'Cfc*

Теорема 3. Пусть для последовательности { точек из % выполнено ^'/m^Y^ -P/v*).Тогда для последовательности соответствующих точек из 2) :-ÙM-f(XK)-f(x*) .Если же существует U* такая,что êij^tl^-WJI =-0 .функция f непрерывна на и каждой U. £ И соответствует ровно одна XéS?,то ùtn //><„-X*//- О для некоторой k^é'ab*

Теоремы 1-3 могут использоваться для доказательства сходимости методов условной минимизации' квазивыпуклых функций.

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

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

Пусть выбрано множество '¿Iе-Е^ и задано многозначное отображение & , сопоставляющее каждому К (К множество ,

причем й (и) Ф- $ У и (. V.

Определим вспомогательную функцию формулой: Ц>(ц) =. i-tx) Vutu..

Xtato J

Обозначим 1 ИЛ (л) - \Jua с u).

Теорема 4. Пусть о 0 .Тогда fO *<> (и*) для

любых Х*6&,муeft ".Кроме того,если U*<i Ц * ,то а{и*} Л Ъ и Arq^in -f М^ф».

О xta(u»}J

Определение 6. Точки Ui/U,xfeS> назовем соответствующими друг другу, если X е й Си), Ч> Iw) = j (х).

Это обобщение определения 5 для функции вида (.3).

Теорема 5. Пусть L, (с)If (*)<£]. Тогда L4!0 = {u<L"U\ ip(u)4C3~ U ft'M^v е J*iq) л Lj (с).

Ддя каждого ивведем множество ~/(x)J.

Теорема 6. Пусть для любых Ui}U2 еК ts. любого выполнено условие »гДе

C(^^u2)=-fxtE»v\x = Xx1+ и-У)* г, X ^ЙСиОл- ■'.г, 3 € го,а].

Тогда,если § квазивыпукла на В ,то V3 квазивыпукла

на XL.

Теорема 7. Пусть для любых точек U1tu2eU,любых точек tefaltX/afVg) и любого leEO/iJ

(ч)

Тогда V7 квазивыпукла на V- для любой непрерывной квазивыпуклой функции J- .

Теорема 8. /обратная/ Пусть для любой квазивыпуклой непрерывной Функции _f(*J функция У квазивыпукла.Тогда выполнено условие (Ч) .

В частности .функция (Z) удовлетворяет условиям теорем 4 и 7, и поэтому квазивыпукла.

Дня нее лебеговы множества задаются формулой

L V(l)-Un (-z. + c¿>*u> cein v - -г.}) , где V- ^ í

В главе приведены другие примеры функций вида ( ^),дпя которых условия теорем 4 и 7 выполняются,что позволяет использовать такие функции как вспомогательные.Однако численные методы, построенные в диссертации,разработаны для минимизации функции вида с*).

•Теорема 9. Пусть fC*) непрерывна на .Тогда функция ¥(и) непрерывна на гиперплоскости U .

Теорема 10 т Пусть J (*,) удовлетворяет условию Липшица с константой L> о на «тожестве/«a/yr^a/J для некоторого oj>J(-z.¡, 4>(и) задана формулой Q Z.) .Тогда f удовлетворяет условию Липшица с константой'L- L (4 * & / RT) на гиперплоскости ЪС , где S(z, £)<=,&> R > O.éL - Мал Ц

Если f выпукла на °3 »где

выпуклые непрерывно дифференцируемые функции Q^fT**),и удовлетворяет условию Слейтера,то удается найти производную функции V7 по любому направлению (j еЕГ„, причем

си J ihj [ rafe*.*) i9)l

д$ \¡(*r*<u.i.9) L \ pt J \ эU 'J/y

где

Доказано,что если § соответственно-явно квазивыпуклая или строго- квазивыпуклая функция,то У обладает теми же свойствами. Если же ¿f псевдовыпукла.а ^ дифференцируема по направлениям в любой точке и i 1С »то V псевдовыпукла на множестве Lí~z) = [utUjVluXj (*)}.

В §2.3 описаны способы вычисления обобщенно-опорных векторов к лебеговым множествам функции V .

Теорема 11. Цусть Р задана формулой (%■) tu£l¿ _

соответствующая точка.Пусть также в X известен обобщенно-порный вектор аеЕ"ь^ .к множеству ^ОЧ < ^-0)3

акой.что .Тогда вектор а = Ц ,е)<?/(1 д - (д, <•) еП

бобщенно-опорный к множеству {исЫучЫ 4 в & /

Лемма 3. Пусть задана формулой и в точке и-СЪС звестен обобщенно-опорный вектор у для ^ относительно ги-ерплоскости % .Тогда вектор а - $'~г~~~ обобще-ко-опорный к множеству хеа с-*;

Теорема 12. Пусть выполнены условия теоремы 11, за исклю-ением,возможно,условия ортогональности (д,-г~й)=0,причем

ля любого рбЕГЪ, ПрНН такого,что существует <¿->0, СзЬ,

.Тогда вектор 0"—(д, обобщенно-опо-

анй к множеству {осе ^(ст^.

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

1емма 4,- Пусть Цг^иеЕц^с.ц^С«

,и в соответствующей точке известен обобще-

то-опорный вектор к множеству (хй^Сс,*) ^сс,*)- £7 с. ша->0 .сохраняющим к нему опорность .причем ^"г-^^Тогда , в эчке ЛсЦ вектор д = /! является обобщен

ю-опорным к множеству -[и^ и/фСч) 4 ¥( Ц)-с шагом £ > о, охраняющим опорность к этому множеству,где

' $ =((9|М х—^_Г^мупк-Ь

-- .....-3 - С,С,-2.)-С, . истл Ькм,*)

Теорема 13. Пусть' выполнены условия теоремы 11,л.& -шаг, )храняющий опорность вектора $ по отношению к множеству

Тогда величина £ = (& /-1-**) * 11$- ^ЭДГ.^ Ш Ь* = будет шагом,сохраняющим опорность

нстора р по отношению к множеству { и ¿г*/ <р(и) 4>(а.)— £}.

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

В §1 строятся методы решения задачи минимизации линейной нкции на выпуклом множестве:

- 9 -

В этом случае Ц,- (х^Е-С^.и вспомогательная Функция имеет вид ¥4 и) — С. -+ —£}■ т £,

Определение 7. Относительной толщиной множества назовем величину V ¿чу?/г^ з

Лемма 4. Цусть £ > о, хс^ (с.,* ¿.Тогда £ г (и, Л-1>,г)-сЗ//>,*)_(+О,

где х С $5 соответствует ас И, 1Се

Лемма 5. Пусть £ - выпуклая функция на , £^

Тогда СЯ^ ^ (Г^- А)^)*'Н0У<)+ ДФ^

Из лемм 4 и 5 вытекает

Теорема 14 Пусть - нижняя оценка относительной толщины множества С0М^е ,и известно,что ¿Ть ,где < ("с и) Те > 0 «Тогда выполнено неравенство

. (с, х) ^ ухе».

Тн ~ Та

Использование данной теоремы дает возможность построить алгоритм решения задачи (5~) ,общая схема которого такова.

Алгоритм 1. /метод минимизацми линейной Функции на выпуклом множестве/

Шаг 0. Выбипается X £ 5& .находится Тн>0,О^Ти^ (г)),

Полагаем о £ : - 0 \ 6 ; = О; : - (с, г); с 2: - с ,

и, : ~ -г + , С//IОII г; Ы^: ^

Шаг 1. Вычисляется соответствующая точка X*. по правилу: Х< = К* ■Ь * —

4 ^ х Г««,

Шаг 2. В точке Хг находится опорный к ¿£> вектор Шаг 3. Выбирается число с* С ^ -с е"в ,и вычисляется шаг, сохраняющий опсрность вектора^ с<с/н по отношению

к множеству £ис г//<р(а1)$ с«} .равный Я

[lar 4. Задается заглубление ¿tK так,чтобы выполнялось условие

Ти - 2 d? м (с, г))/(ти-- '2 ) > С £. lar 5. Находится очередная итерационная точка по формуле

4 * <с. l|Q к — (?к,с)с//

lar 6. Если < i то С^'-^с* ¡4: = о ,иг;и перехо-

щм к шагу 8. .

lar 7. б" —+ #Если (^j^to полага-

;м а,: - аr ^ 6 •• = о j £ \ЛСйт„ - 2 <0* сс, г^ги- г i переходим к шагу 8.Иначе переходим к шагу 9.

8.' Если Ce - Cf'<¿. ,то СТОП, W,.- - оптимальная то-

гка.

lar 9. Полагаем к: — Iе-* У и переходим к шагу 1.

При численной реализации можно полагать

u : А! > -

* II - Cg* Д) с ij

Во втором параграфе исследуется задача выпуклого програм-

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

Лемма 6. Пусть х еф , L ^ о, ^ - ^.с-л. J (ч } • ^ vm* (о

'огда справедливо соотношение * е ь ^

tr (u£ (а>) * tr[(^ -z.)■- c%,

|десь jCxl'ú СV

Леша 7. Пусть для некоторого $ известна нижняя

'Ценка относительной толщины множества к) ¿ f>

известна оценка JV ^ * — -j (*).Пусть также выполняет-

я неравенство

Тогда i (О ?СГ~ Vxé<3±.

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

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

Пусть $ псевдовыпукла и липшицева с константой > О на £),. ^

Лемма 8. Пусть £ £ П? и существует X такая,что = .Тогда

где 0-< 1 * $)/(>• Ц со- Ж) (тЛг)М 7*;= оЗ

Лемма 9. Пусть Я'е -^С»") - ^ ^ .Тогда шагом,сохраняющим опорность вектора /II-Р к множеству вида -[ является число 5.

Алгоритм 2. /метод условной минимизации псевдовнпуклой лишицевой функции/ 0 •

Шаг 0. Выбираются 2 £ 3 ,7*г > о, ^ > £ находится кон-

станта Липшица и >0 .Полагаем к: - о;б■ - о; иг-тц0 Задаем параметры § > О, £ > о, о X * ■ Шаг 1. Вычисляем К* с ¡^соответствующую V. Шаг 2. В точке ** определяем обобщенно-опорный вектор д К к лебегову множеству у С*) такой, что С^,^-- и к) — О. Шаг^. Полагаем ^ , = { ^ $ . ^

Вычисляем С к - шаг,сохраняющий опорность вектора по отношению к множеству

МЛ,. Полагаем \к* Ь */Ц ^-Ь^-С^^Ь

где ЯЪТн/2 + *па#Иг-%/1. * К

Щаг^ Вычисляем ^ ^ ц,-+

Полагаем + - -

Шаг 6. Бели ? (и^,) < ^ «то г >; иг; и П0Ре*о дим к шагу 8 при ($ .- — <?.

Шаг 7. Если 6 >рг ,то полагаем и переходим к шагу

8 при 6•-о-.и :- сг .Йначе переходим к шаху 9.

' 1о<- г

Наг 8. Если стш' ^ ~ оптимальная точка.

Наг 9. Переходим к шйгу 1 при Ic-^V-t 1 .

Возможно некоторое обобщение алгоритма на случай,когда функция f имеет монотонно возрастающую мажоранту

1ля всех У, у 6 .

Для построенных алгоритмов справедлива Теорема 15. Пусть £-0 .Тогда = о .и бо-

гее того -Ç в — tiivi £ £ — -Ç *.

(c — oo J k c*?

В конце третьей главы предложен способ нахождения началь-гой внутренней точки Z е с и. t 35.

Пусть ГС"") ¿о},где Г - псевдовыпуклая

пункция.Предположим,что известна Z С £Гк такая,что -f ("н/- j / Пусть также в точке 1Σ Ек известен обобщенно-опорный 1ектор о к & .

Зададим гиперплоскость

•у - { XéE^/ fy V - х) = 0, у б Г*}

■ак,чтобы выполнялись условия: ^

( , У ) , "2Л ,

Тогда она является обобщенно-опорной^гиперплоскостью к . любой точке utlA. .на гиперплоскости XX определим функцию:

V t иЛ — 1л Г(_и-V tc^z- w)) ,

г ( Г , . i t X1

де 1 (а> z; — £ Ce», ^(и-^-Ц. =5-4") Поставим следующую задачу минимизации:

у (ч ) I^ih Сб)

иск

Лемма 10. Пусть (А* - решение задачи Сб), Л* - соответ-твующая точка из множества Ес (f f) ~ /х { ^{J.ro есть у* = U^t^i-M'J, i* = ftr^KitM F i .

Тогда х SÔ * - { ÎV^f / с><)■&■ ч. О-ели значение f *_неизвестно,можно вместо суммы j ^ £ подста-ить любое число f этом случае решение задачи .(&) за-

едомо является внутренней точкой 2Э /если р'/.

Для решения задачи (<э) применимы те же методы типа опорных векторов с составным шагом,что и для минимизации функции

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

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

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

Методы опорных векторов с составным шагом выигрывают по времени и точности у метода обобщенного градиентного спуска /б( растяжения пространства/ и метода пристрелок.

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

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

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

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

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

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

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

4/ Проведены численные эксперименты,построены таблицы сравнительной эффективности методов.

Публикации:

1/ Андрамонов М.Ю.,Заботин Я.И. О сведении задачи квазивыпуклого программирования к задаче безусловной минимизации методом конического проектирования//Изв. вузов.Математика,1992, М,с.З-7.

2/ Андрамонов' М.Ю. Методы решения задач квазивыпуклого программирования.-Казань, Препринт №1,1992,16с.

3/ Андрамонов М.Ю. О минимизации линейной функции.на выпуклом множестве методом конического проектирования//Тез. докл. на

ХП - ом Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования и их использование". 1992,г.Нарва-Йыэсуу,с. 3-4.

Сдано в набор 7.12.92 г. Подписано в печать 4.11.92 г. Форм.бум. 60 х 84 1/16. Печ.л.1. Тираж 100. Заказ 686.

Лаборатория оперативной полиграфии КГУ 420008 Казань, Ленина, 4/5