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

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

РГ6 од

ЗАБРОДИН Игорь Сергеевич

' ЧИСЛЕННЫЕ ЫЕТОДЫ ЫИНИШАЩИ НЕДИМЕРЕНЦИРУШП еУНКЦЙЙ, ОСНОВАННЫЕ НА НЕПРЕРЫВНОЙ АППРОКСКЫАЩШ

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

АВТОРЕФЕРАТ

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

На правах рукописи УЖ 519.3

САНКТ-ПЕТЕРБУРГ

1993

Работа выполнена на факультете прикладной математики -процессов управления Санкт - Петербургского государственного университета

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

профессор В. Ф. ДЕМЬЯНОВ

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

профессор В. Н. МАЛОЗЕМОВ

кандидат физико-математических наук . Л. В. ВАСИЛЬЕВ

Ведущая организация - Вычислительный центр РАН (г. Москва)

Защита состоится : 1993г. в {¿I часов на

заседании специализированного совета K-063.57.I6 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском университете по адресу: 190004, С"нкт-Петербург, 10-я линия В. 0., д. 33, ауд. 88.

С диссертацией можно ознакомиться в библиотека им. A.M. Горького Санкт-Петербургского университета.

Автореферат разослан ¡-(O. iujUL' 1993 г.

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

В. Ф. Горьковса

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

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

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

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

Научная новизна. В диссертационной работе

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

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

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

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

государственного университета, на семинаре кафедры исследования операций математике - механического факультета Санкт-Петербургского государственного университета, на семинаре Щ РАН.

Структура и объем работы. Диссертация состоит аз трех глав, списка использованной литературы из 38 наименований, я трех приложений. Диссертация изложена на 81 странице машинописного текста и содержит 9 рисунков, 5 таблиц ■ распечатки текстов программ.

Публикации. Основное содержание диссертации отражено в работах 11-31.

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

Первая глава диссертационной работы посвящена общей схеме

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

Х(х + 11) = 1(х) + <р(х,11) + ф (х,Ь) VII е Л", |Ь| * X > О. О

(здесь ф

непрерывна по обеим переменным и ф(х,0)*0

Введено отображение

Н(хД) - { h « Rn| JhJ $ min <р(х,р) = (p(x,h)}

IpB^.

а показано, что это отображение полунепрерывно сверху по х. Предложен следующий метод шпшшзащш функции i(x) на R":

1. Выбирается любые хо е Rn, А.0 е (0,Х). бе (0,1), 9 в (0,1).

Пусть ухе найдено х1, тогда:

2. Полагается \ = Хо.

3. Вбирается лвбое е Н(хк,\), и пусть 0к = <р (xt,hk).

4. Если ßk = О, го процесс завершен, пра ßk < О переход к пункту 5.

5. Вычисляется 0Ь = ——--.

" Pk -

6. При ök < Q полагается \ = и переход к пункту 3.

7. Полагается хк>1= хк+ Ь^, к = к+1 и переход к пункту 2.

Введено определение <р- стационарной точки. Показано, что если х^ не является <р - стационарной точкой, то,используя еппрокгашацив <p(x,h), можно построить следупдуо точку xt^i шпапгазирукцеА последовательности. Доказано, что

последовательность {f(xl)> монотонно убывающая а справедливо

Утверждение. Если множество D(xo)= . ix е R" | f (х) $ i(ro)> 01равнчен0, то существуют пре- . дельные точка канкиияируддеЗ последовательности {^l.a

В 62 прзвэдэпэ доказательство сходимости об^еа схекы изт'лвешвга csnpsрнвшх фуиярй. Доказана

- б -

Т е о р е u а 2.1. Пусть функция f (х) и ее аппроксимация Ф(х,Ь) удовлетворяют условиям 51. Тогда любая предельная точка минимизирующей последовательности {х^ является <р -стационарной.»

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

Доказательство сходимости этих методов опирается на

доказательство теоремы 2.1 и заключается в исследовании множества ф-стационарных точек Ф*(1,ф) с If. Так как разложение (1)* существует всегда, в пунктах 1,2 рассмотрены тривиальные случаи, когда ф = О и ф = 0.

В п.З строится метод минимизации на R* к раз непрерывно дифференцируемых функций. Показано, что в любой ф -стационарной точке либо выполнено достаточное условие минимума порядка 1:

^'(х) > О, 1 - четное, 1 ^ к, f'(x)= О VI < 1 УХеФ*(1,ф),

либо необходимое условие минимума к-ого порядка: fО vi ^ k VX. е Ф*(2,<р).

В п.4 содержится доказательство следующего утверждения:

Утв.е ряде н и е. Если функция i (х) дифференцируема по направлениям, ф(х,Ь) = Oi/dh + o(x,h), причем |hf>h^— |{ь|| '->V °(s>h) непрерывна no h, тогда

для любого х е Ф*(1,ф) и любого h с В" dS/Oh 2 О.в

В пункте 6 конструируется нетод е - наискорейшего спуска. В пункте 7 на основании общей схемы строится один из вариантов метода линеаризации для миншЕзацни функция i(x)= . пах 1(х).

i 6 I . ■

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

У т в ерждение. Пусть 1(2) непрерывно кодафференцируема при х с R" , кодафференциал функции . 1(х) ограничен, множество,D(x0) ограничено и имеет место представление:

<p(x,h) = max (a+(v,h)) + min _ lb+(w,h)],

[a,v]€d[(x) [b,vt€df(xl

где а,Ь С R1, У,я e R". г Тогда. минимизирующая последовательность íxk) содержится в D(x0), а последовательность Щх^.)) - цонотонно убывающая. При этом если (х^) - конечная последовательность, т.е. k í N < о», жы - стационарная точка, а если (з^) -бесконечная, то любая ее предельная точка стационарная, т.е. выполнено необходимое условие минимума первого порядка. ■

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

<p(x,h) -► min . (2)

В $5 содержится оценка скорости сходимости, доказала теоремы!

Т е о р е м а 5.1. Пусть существует единственная ф-стационарная точка х* и минимизирующая последовательность (хк) сходится к х*. Кроме этого, пусть существует в>0, такое, что для любых х е Ве(х*) выполнены следующие УСЛОВИЯ!

, 1. Six) - í(x*)> kf|x-xV, где а>0, kf> О

sup 1*," x »

2. ' * ? -— ç M < » ,

lni Jx2- x Ц

x € D(x)Mnt D < x >

3. 1Ф (x,h) I $ ц ||hf, b>a, \i < (3)

Тогда существует N, такое, что для любых ' k > H выполнено неравенство:

s К Sik - xV" , К <

Теорема 5.2. Пусть существует единственная <р -стационарная точка х" и миниыизирупцая последовательность (хк> сходится к х*. Кроме этого, пусть существует е > О, такое, что для любых x е В£(х*) выполнены следующие условия:

1). X(x) - f(x*) » kJx-xT, где а>0, к, > О,

2).|ф (x,h)| $ p. |hjb. Ъ>а, ц < Тогда справедливо неравенство: eup Jx - х*| < К sup Jx - х*8ь-/а- К < оо.«

С € IXX , Ï x € Dix. > .

le ♦ I к

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

В §6 ' рассмотрена модификация схемы минимизации при наличии простых ограничений. Доказана

Теорема 6.1. Пусть функция i(x), х « А с Rn и ее аппроксимация удовлетворяют условиям §1. Тогда любая

| предельная точка иягтаж-уу.гыуа последовательности ) | является ф - стацисшгрхиЗ. ■

В 57 приведено <и ».мы итатнииД реализации схеиа шпшыизации функции я ртярянв! тестсенх задач. В прянгре 1 рассматривается задача Еггаргесзз ешвнзксвых квадрзтургых формул. Эта задача трг£хгг тззхзхЗ. точности вычисления, так как целевая функция презгягзхзт потреяность »шадратурнсЗ формулы. В пр!мере 2 пзуггажга ггдача разменная - цдш-.тца» обслуживания! при этса Сувппя является иепрер'тао

кодифференцируемой на ЯГ- йнязетрвнз некоторые встгртса машинной реализации пдяржЕга Ец^йерекциалоз в репевза вспомогательной задаст £21»

Глава 2 посн,,-,,'""ч зидвсиа гшнимязади (Дет^З, ссдерзг^и опер:"; та г пгпргрквнего ыггспфЕЭ по

коапэкту. Наиболее гтагаД путь ратания тагах задач

заключается в дискретазгзя гт-.к.ятаош кнсзестээ, по которому берется ыаксксэ^ чзтэ ггогет приЕгстп к пегзггпгэ локальных экстреиуиоз. Г/: ггд потазано в зтса ггээ,

еСЛИ ПОСЛ9 >1"";?'» ГуГТ'.ЗЗ фуНКЦЗЯ ЕЗЯЙЕТСЗ

непрерывно - кодиффереЕ^зтзгЭ, то благодаря ккяавнноетя

алгоритма выходить из ясззянза уляцдумои» устет Сдть получана оценка репевпя псзветсД ззцэчяг ?(х) = пах X(х,у) —» с2а « Ж, (4)

(здесь з с йп,

В 58 содерзатся свздапзя п сгаредаггЕЗЯ.

Взодятся конус допустетазс г: "¿я-чянаа 7 (хо»5.У) в ксяус зозмогкых направлений Есзаззэается, что дез

справедливости соотнсж~п

е?(х0) аг(х0.у)

вир ггр ----(5)

у « ""«о* д^.д)

у е у

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

Условие 1. Если q, то

0f(xo,y) ах(хо,у)

- = ГШ -- vy е R(K ) .о

ötg.ql к - * » dtg.qj

Условней. Пусть ук е R(xoiovg), ук у. Если X допускает аппроксимацию первого порядка в хо, то Уь = У + 0(0,,). у е R(XJ, qk- ограничены. ч

Условие 3. Функция г- лишшцева в некоторой окрестности мнохества 1а ■

В {9 рассматривается случай, когда 1(х,у) в (4) непрерывно кодифференцируfiua. Показано, что -для справедливости (5) достаточно выполнения условия 2 и условия 3. Вышесказанное утверждение приводится . как теорема 9.1. Приведенный пример иллюстрирует, что условие 2 является существенный, т.е. когда оно не выполнено, соотношение (5) может не иметь места.

В (10 дан подробный разбор примера, когда функция f(х,у) непрерывно ко дифференцируема. Условие 2 выполнено, поэтому можно воспользоваться (5) для вычисления производной по направленно. Показано, что в этой случае дискретизация приводит к появлению локальных минимумов, выход из которых возможен при использовании метода минимизации непрерывно кодифференцируемых функций, предложенного в }4.

В 511 приведен пример решения на ЭВД задачи вида (4), при которой дискретизация приводит к. появлению локальных минимумов.

К достоинствам '• предлагаемого подхода следует отнести отсутствие необходимости детально исследовать

Мишпшанруемув функция. Алгоритм позволяет с набольшими

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

Глава 3 посвящена сетевым моделям кусочно-линейных аппроксимаций первого порядка.

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

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

В § 14 разработаны правила исчисления сетевых моделей, легко реализуемые на ЭВМ.

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

прилегают содержатся только £рагаента вычисланая

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

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

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

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

3. Построен вариант катода пря наличии ' сшейпых сграгапесй!. ' '

4. Рассмотрены вопросы щницммшаа реализации методов

- прлучешмх вз oGqesto зшп^кшз •

5. Предлоге вы констружззшаав ¡правила исчисления шпрокгапиций первого поредга

Список работ, сцублвеевав&их автором по гае дагаеротцЕИ

1. Ахриева О.Х., ЗабродхЕ Об интерполяционных 1вашыахсш1х квадратуршх фдрстзшх // Вестн. Ленингр. ун-та. Сср.1, 1S90.- «8.- С. 9S-99

2. Забродин И.С. Об cjsmsZ оСврС схеие ииншшзавди нрдрррнвнмх функций // Веста. СШПГ. Сер. 1, 1992. -

С. 11 - 23

3. Denyanov V.F., Zateo&in US. EtLrectlonal dlfilrenti-abllity of a ecattimal mgnrimim function on quaalД1 fterentlable finctJLona: BattralUcal Prograiuning study 29 (1966) 108-117 ВагШ-ВаИшай .