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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

03.13.16 - Применение вычислительной техники, математического моделирования, математических методов в научных исследованиях

ГТ6 од

1 1 НОВ 1386

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

Гречка Галина Юрьевна

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

Новосибирск -- 1990

Работа выполнена в Новосибирском государственном университете.

Научный рукоБод"тель - д.ф.-м.н., профессор С.И.Кабаннхнн.

Официальные оппоненты д.ф.-м.н., профессор В.Л.Береснев,

д.ф.-м.н. В.В.Калашников.

Ведущая организация ИВТ СО РАН, г.Новосибирск.

Защита состоимся " 199 6 года в ча-

сов на заседании диссертационного совета К 0C3.9S.O5 при Новосибирском государственном университете по адресу: 630090, г.Новоснбирск-90, ул.Пирогова 2.

С диссертацией можно ознакомится в библиотеке НГУ. Автореферат разослан

" /6 " 199£года.

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

П.В.Вельтмандер

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

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

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

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

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

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

Ч

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

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

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

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всесоюзной конференции "Условно-корректные задачи математической физики п анализа'' (Новосибирск, 1902), XXIII региональной молодежной конференции (Екатеринбург, 1992), международном симпозиуме по вычислительной томографии (Новосибирск, 1993), а также на семинарах математпко-экономпческого отдела и отдела условно-корректных задач Института математики СО РАН.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, двух приложений и списка цитируемой литературы. Объем диссертации — 120 страниц машинописного текста, библиография включает -17 наименований работ советских и зарубежных авторов.

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

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

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

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

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

Именно, рассматривается задача

/(«)->пни, иеи, (1)

где / 6 С'(11") — выпуклая функция, V С П" — выпуклое замкнутое множество. Предполагается, что для задачи (1) задана система выпуклых функций штрафа 6 С'(11"), к = 1,2,....

Предложенные алгоритмы дочускают следующую общую формулировку.

Схема РМШ (регуляриэованныи метод штрафов)

Шаг 1. Пусть м1,0.е В." — произвольная точка; {е^-} — сходящаяся к О последовательность неотрицательных чисел. Полагаем I = О, /.: = !.

Шаг 2. При некоторых I. к. точка определяется из условия

. + + 2(ик'м - И*-')| <

Шаг 3 В случае выполнения критерия окончания счета < станавлп-ваемся, полагая при этом и* <=з В противном случае определяем

специальным образом величину Ф^-н- Если |и*-'+1 — ик-'| > Ф *,/+!, то полагаем I := I + 1 и перегадим на шаг 2. Если 1 - < то полагаем 1(к) = I, = к := к + 1, I := 0, затем перехо-

дим на шаг 2. Величина 1(к) в завп( :мостп от конкретного алгоритма может принимать значения ¡(к) или 1(к) + 1.

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

Вторая глава посвяще ла исследованию вариантов РМШ при различных предположениях о строении допустимого множества U задачи (1) Ii характеристических свойствах используемых систем функций штрафа. Все основные результаты этой главы получены в предположении, что множество

U* = {и € U : /(и) = 1Шп/(*)}

решений задачи (1) непусто и ограничено.

В первых двух параграфах предполагается, что допустимое множество U задано в виде

r = {«<ER":y'H<Ö, j = !,...,»»}, (2)

где У € C'(R") — выпуклые функции.

В параграфе 2.1 изучаются алгоритмы, в которых функции штрафа к = 1,2,..., удовлетворяют следующим условиям:

10, если и € int U

;

+оо, если м £ U

2) ||VVt(u)|| =>■ оо на 0U Л G для любого компактного множества G

Jb—»со

(символ ''=>" означает равномерную сходимость);

3) Vk(u) > 0 при и eU,k = 1,2,....

Кроме того, для заданных последовательностей положительных чисел {¿¿•}, {rjt} при каждом к предполагается выполненным следующее соотношение согласованности:

niaxmin\\и — vfl < (3)

иеи

где

1'ь = {и б Ü : \ 'к{и) < Sk}-

компактное множество U выбирается так, чтобы U* С [' С U.

Еще одним необходимым требов;шием является условие Слейтера: существует вектор «о, njiii котором

<гЧ«о)<0, j = 1,...,ш.

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

Метод 1 определяется пз схемы РМШ при 1(к) = Цк) н метод 2 — при l(k) = ï(k) 4- 1. Зададим

W(u*) = {?« 6 R" : Iu — u*|| < р(и*)},

», Л M ОО -

,¿1.0 _ и'1 + 2 £ Тк; W = и W(u*). Положим " *=1 u"€ If

Û = un\v. (4)

Основной результат о сходимости метода 1 отражен в следующей теореме.

Теорема 2.1. Пусть выполнены все указанные выше предположения относительно задачи (1), (2); функции штрафа 14 удовлетворяют условиям 1), 2), 3) и выполняются соотношения (3), (4). Тогда,

ОО Л

если и ! методе Î выбор параметров подчинен требованиям: £ ¿1 < оо,

со оо

£ fa < оо, £ тк < оо и

*=Il

^kf = Ci(£k + 6k + Tk), (5)

где С\. — некоторая константа; /--1,2,..., 1{к) + 1; к = 1,2,..., то последовательность {«*■'}, порожденная методом 1, сходится к решению задачи'(lj, (2). Положим

Û = {ц € U : /(u) < D}, где D > mm/(:r). (6)

Сходимос ть метода.2 утверждает теорема 2.2: пусть выполнены указанные предположения .относительно задачи (1), (2); функции штрафа 14 удовлетворяют условиям 1), 2), 3) и выполняются соотношения (3), (С). Тогда, если<в,.метод<- 2выбор параметров подчинен требованиям:

ОС ОО 1 />> ОО !./•>

£ £к < оо, £ ¿1; < оо, £ п' < оо и

к=1 *=!•. * кЫ

= С2{ек + Ьк + тк), (7)

где Ci — некоторая константа; I — 1,2,... ,1(к); к — 1,2,..., то последовательность {ик'1х, построенная методом 2, сходится к решению задачи (1), (2).

В приведенных формулировках теорем 2.1 и 2.2 указана качественная оценка выбора управляющих параметров Ф*,/. Ниже укажем количественную характеристику этих параметров . Отметим, что такая характеристика необходима с одной стороны для получения вспомогательных результатов, с другой стороны — для практических приложений методов 1 и 2.

Введем необходимые обозначения. Пусть

co = ||V/(«0)|!, с = шах ||V/(h)|| .

Для произвольного и* 6 U" определим

йк = йк(и') = argniinllu - и'\\, к = 1,2,____

II ei't

Для 1 < / < 1{к) + 1, к 6 {1,2, • • •} обозначим

Л,; = О' = 1,...,т:^(и*'')>0};

gj(uk'1)

max ■ --—если Л;

О, если Jtj — 0

= /«*, 1Щ + (1 - /«*,/)«*'';

Определим величины (h,i так, что

max ¡ukJ - й*(|Г)| < dkJ, I =0,1,..., 1(к); к = 1,2.....

Положим

ф*./ > 4/2 + + сктк + сори + £к(1к,1-1 - Щм*'1), (8)

/ = 1,2,... ,1(к) + 1; к = 1,2,..., где

с* > с, к = 1,2,..., для метода 1 и

Ск > с + 2(1, где (I = сИат II; к = 1,2,..., для метода 2.

При выполнении основных предположений данного параграфа и некоторых условий на выбор параметров доказана непротшзоре-чпвость соотношений (8),

1пп Ф^.. 1 = 0 (9)

1-—СС '

в методе 1 п требований (8),

lim <ИкЛк) = 0 (10)

к—оо '

в методе 2.

Кроме того доказывается, что утверждения теорем 2.1 и 2.2 остаются в силе при замене в их формулировках требования (5) на (8), (9) и условия (7) на (8), (10). Этот результат позволяет использовать соотношение (8) для практических приложений методов 1 п 2.

В параграфе 2.2 рассмотрен алгоритм, использующий функции штрафа V* со свойствами

1') lim H(u) = i

к—оо I

О, если и £ U +оо, если и g U '

2') Ук{и) > 0 для и € К", к = 1,2.....

Предполагается, что выбор параметров функций штрафа обеспечивает выполнение условий

И(") < 6к для и е 0, к = 1,2,..., (11)

max д*(ик-')<<тк, (12)

j=I ,...,m

/ — 1,2,...,l(k)\ k = 1,2,...,

где Ьк > 0, ak > 0, к — 1,2,...; множество U определено соотношенпем (6).

Считаем, что выполнено условие Слейтера.

Метод-3 определяется из схемы РМШ при 1(к) = 1(к) + 1,

к — 1,2..... Последовательность точек, построенная этигг методом,

при больших к лежит вне допустимого множества (это относится к случаю, когда ограничения существенны, т.е. iirf /(и) < miu /(«))•

Сходимость метода 3 устанавливается в теореме 2.?: пусть выполнены указанные выше предположения относительно задачи (1), (2); функции штрафа удовлетворяют условиям 1'), 2') п выполняются соотношения (6), (11), (12). Тогда, если в методе 3 выбор параметров

оо оо ti>2 ос j /2

подчинен требованиям Е < оо, Е «V < ос, £ a J < ос и i=i *=i t=i

*k,i = C3(£k + 6k + ak), (13)

где Сз — некоторая константа; I = 1,2,...,/(А'); к — 1,2,..., то генерируемая методом 3 последовательность {uk,l\ сходится у решению задачи (1), (2).

Для количественной оценки параметров Фk,i определим величины d'k l так, чтобы

шах ||U*'' - и* j < d'kp / = 1,2,..., ¡(к) - 1; к = 1,2,..,

и, используя введенные выше обозначения, положим

Фи > 4/2 + ^ + <Ш,1 + Skd'u-i + ~ (14)

где ик > 0, lim vk = О, I = 1,2,..., /(А;); fc = 1,2.....

Jb—*оо

Доказывается, что условия (14), (10) в методе 3 непротиворечивы, и, кроме того, утверждение теоремы 2.3 остается в силе при замене требования (13) на (14), (10). Теорема 2.3 в такой формулировке позволяет использовать метод 3 в практических приложениях.

В параграфе 2.3 рассматривается случай, когда допустимое мно- • жество U задачи (1) содержит ограничения типа равенств, т.е.

U = (,) П Я,

где

Q - {« € R" : oj{u) < 0, j = l.....«},

Я = {« 6 R" : д'(и) = 0, i = s + l.....m} ,

gi — выпуклые функции, д' — аффинные функции.

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

<7J(ü0)<0, j = l,...,e; д'(й0)=0, . г' = « + 1,...,7».

Исследуется алгоритм, использующий функции штрафа Н вида

Vk(u) = V^i^ + V^iu), где {if 'iu)}, {Vf >(«)}.......системы выпуклых

функций штрафа со свойствами

1.1) lim v'VhI 0 П1Ш!15Й;

' к-ос 1 v ' | +оо при и 0Q '

1.2) \f\u) > 0 для и € R", к - 1,2,...; 2.1) limVf>(„)=( °

' 1-х k К ' \ +ОС при 1l<£ Н

2.2) У4(а)(и) > 0 для и б И", А: = 1,2,.... Считаем, что выполнены условия (11),

.шах г/(им) < ак, 1 = 1,2,... ,1(к); к= 1,2,..., (15)

,= тах т|<7,'(«и)| < <*к, ' = 1,2,... ,1(к); к = 1,2,.... (16)

Центральным результатом данного параграфа является теорема о сходимости метода 4, определяемого пз схемы РМШ при 1(к) — 1(к) + \, к =1,2.....

Теорема 2.4. Пусть выполняются все предположения данного параграфа относительно задачи (1) и функции штрафа а . акже обеспечена справедливость соотношений (0), (11), (15), (16). Тогда,

оо

если в методе 4 выбор параметров Подчинен требованиям Т. ек < со,

Е £>\п < оо, Е <т1П < ооп к=1 *=!

Ф*./ = С4(ец. + 6к + <тк), (17)

где С4 -- некоторая константа, то последовательность {и^1'}, построенная методом 4, сходится к решению задачп (1).

Приведем количественную оценку параметров Ф*/. Обозначим

Пк1 = Р11(ик1), 1 — 1,2...../(*); к = 1,2.....

где Рц(и) — проекция точки и на множество Я. Пусть

( УЧ"*') г ,а тах -—г, если ,1к! фщ .

= I ;еЛ.1 - д>(щ) 5

( 0, если J|CJ = 0

= Рк,1Щ + (1 - ¡1к,1)йк''; = —

Используя обозначения, введенные при описании параграфа 2.2, положим 1 Фи > + ^ + П,Фк,1 + + Ъ - Ук(ик1), (18) I = 1.2,...,1(к); к = 1,2,....

Доказывается, что условия (18), (10) в методе 4 непротиворечивы и теорема 2.4 остается справедливой при замене в ее формулировке требования (17) на (18), (10). Такой результат позволяет использовать метод 4 в практических целях.

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

Параграф 3.1 посвящен выводу указанных оценок для методов, описанных в параграфе 2.1. Именно, для метода 1 получена асимптотическая оценка

/(«*■') - /» = о 1

Е /(*) + !]' жк,»ек /

где /„„•„ = min f(u), 1С = {к = 1,2,... : l(k) > 1}. Отметим, что в мето-

«£(/

де 1 для индексов к, удовлетворяющих неравенству Ju*'1 — «i,0J < Ф*^, имеем 1(к) = 0, в результате чего ui+I,° = гЛ''*' = т.е. на следующей к + 1-ой итерации оказываемся в прежней точке ик,°. Поэтому введение множества К. обуславливается необходимостью фиксирования тех индексов к, для которых точка и*'0 реально участвует в построении минимизирующей последовательности {uk,i}.

В предположении, что функция / удовлетворяет условию

inf /("} "{"'"' > р > 0 (19)

и параметры' достаточно быстро стремятся к 0, доказано, что в методе 1 выполняется соотношение

' • , L п . £ '(«)

I« • - u"| < Cq'<k '^K , где 0 < q < 1, С — константа,

означающее линейную скорость сходимости последовательности {и1,1} к решению и" задачи (1), (2).

Для метода 2 при некоторых дополнительных условиях на выбор управляющих параметров получена оценка

/

Я«*1') - /min = О

1

\J = I

(20)

В предположении (19) доказано,-что при подчинении управляющих параметров определенным требованиям, последовательность «*■' сходится к решению и" задачи (1), (2) со скоростью геометрической прогрессии:

где 0 < <7 < 1, С — константа.

В параграфе 3.2 исследуется скорость сходимости алгоритмов внешней точки, рассмотренных в параграфах 2.2, 2.3. При некоторых условиях на выбор управляющих параметров устанавливается оценка (20), а в предположении (19) — оценка (21). Отметим, что техника вывода этих оценок для методов, рассмотренных в данном параграфе, несколько сложнее, чем при выводе оценок для методов внутренней точки, что связано с тем, что минимизирующая последователь!, ость, вырабатываемая методами 3 и 4, не принадлежит допустимому множеству.

В главе 4 проводится более детальное исследование пред юженпых методов.

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

соотношение (3) выполнится для каждого к, если выбор параметров гк, к = 1,2,..., подчинить условиям

(21)

т

Ук(п) = ег*»'<">, где гк > 0, Нт гк = со,

. _ I к—оо

>> > т тах 1, тк 1 тах ||и — ко|| при 6к < тп д("о) иеди

, Л = 1,2,.

г к > 0

прп > т

где »о — точка Слейтера, д(щ) — тах д'(по).

Если же выбирается система функций штрафа

Ук = гк £ шах2[Г д1(ы)], гк > 0, Нш гк = оо,

2

1.1

которая, очевидно, удовлетворяет свойствам 1'), 2'), то условия (11) и

Е ь)/1 < с» выполняются автоматически при = ОД- = 1,2,..., а для ¿=1

обеспечения соотношений (12) п Е с^2 < оо достаточно потребовать

Е < ¿=1

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

•}. Предложены два рег, ляризованных алгоритма, основанные на методе внешнего штрафа, один из которых предполагает отсутствие

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

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

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

6. На основе предложенного подхода проведены численные распеты решения обратной задачи об определении источника стороннего тока.

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Грязина Г.К). Алгоритмы с внутренней прокс-регулярнзас :ей, основанные на методе штрафов. Новосибирск, 1993. 30с. (препринт СО РАН, Ин-т матем; гики).

2. Gryazina G.Yu., Kahauikhin S.I. Penalty Method with Internal Prox-Regularization for an Inverse Source Problem. Computerized Tomography - 93. VSP. 1994. P.194 - 200.

3. Грязина Г.Ю. Некоторые алгоритмы решения задач выпуклой оптимизации. Тезисы докл. Всесоюзн. конф. ''Условно-корректные задачи математической физики и анализа". Новосибирск, 1992. С.1Т - 18.

4. Kabanikhin S.I., Gryaziua G.Yu. Regularized penalty method in inverse problem of external source. International Symposium on computerized tomography. Abstracts. Novosibirsk. Russsia. P.65.

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

АВТОРЕФЕРАТ

Подписано к печати 8.07.96. Формат бумаги 60x80 Объем 0.75 п.л. 1 уч.-лэд. л. Заказ N 298. Тираж 100 экз. Бесплатно.

Ротапринт НГУ. 630090, г. Новосибирск, Пирогова 2.