И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Если ) и Х выпуклы и ) непрерывно дифференцируема, то необходимым н достаточным условием оптимальности точки х является включение 7~(х)~К'(х), (К~ (х) Й (у ) (у г) ~ ~0 Чг с К (х)) — сопряженный конус), т. е. Х*)~ Агу ппп ~ (х) = Х Ь (х / )Р~ (х) ~ К» (х) х ~ Х ) хсх Следствие 1. Х* = (х!(7)(х), г х) ~О»угс Х) () П Х, а в случае Х = В" имеем Х' = (х! 1)г(х) О) Вектор Ч) (х) ~ Н" называют субградиентом, или обобщенным градиентом в точке х, если ~(х) ~~1(х)+ (Ц(х), х — х) )У Множество М (х) субградиентов непрерывной выпуклой функции у в точке х является выпуклым, замкнутым и ограниченным.

утверждение 6. Для выпуклой функции Г производная 1' (х, г) по направлению г равна шах (г, у). »ем)») С л еде тв и е 1. Направление г (х) наибыстрейшего убывания функции ) в точке х равно г(х)~агяш)п 1 (х, г)=агд ппп шах (г, у). и=) ))ч Это значит, что в методах последовательных приближений в качестве Х» можно выбрать множество Х = (х) гпах (х, у) ( ( — )) ) х1) для некоторого Ц > О.

еем(х ) Сл ел с тв н е 2. Для того чтобы для выпуклой функции Г х = ага ппп Г (х) необходимо и достаточно, чтобы 0 ~ М (х). В общей задаче выпуклого программирования множество Х имеет вид Х = Х' ).") (х))) (х) ~(0, 1 = 1, т, ха У), где »'— заданное выпуклое множество, а ), — выпуклые функции. Теорема Куна — Таннера. Для того чтобы точках минимизи- ровала выпуклую функцию )» на множестве Х', удовлетворяющем условию Слейтера: 3х'ЕУ Ч1= 1, т )) (хт)(0, необходимо и достаточно, апобы суи(ествовало решение и,, ..., и системы )»(х) + 2.; и)))(х)~()»(х)+ 2, и)г)(х) ))ха)', и)ф)(х) =О, и)>0 )г'1'= 1, т. 29 Такое рещение й„..., й называют множителями Лагранжа, а пару (х, и) — точкой Куна — Танкера.

Функцию <р (х, и) юю юе (х) + + ~' и<<< (х) называют Функцией Лагранжа. Пару (х, й) называют / 1 еедлаеой точкой функции <р на множестве У х В+, если хр 1', й~О и выполнены неравенства <р(х, и)(<р(х, й)(<р(х, и) УхР У, ю<<и,'> О. Поэтому теорему Куна — Таккера можно сфор- мулировать следующим образом: если выполнено условие Слейте- ра, то необходимым и достаточным условием оптимальности х яв- ляется существование такого вектора и ~ О, прн котором пара (х, и) является седловой точкой функции Лагранжа на множестве У х х В+. Утверждение 7.

Если выполнено условие Слейтера, то для оп- тимальности точки х (минимизирующей выпуклую функцию Ге на выпуклом множестве Х'), необходимо и достаточно существо- вание таких векторов ЧГ< (х) р М, (х) и чисел и„ю = 1, т, что ил(х) О, и,(0, ю'=1, пю, ЧДе(х) = ~„и<ЧГ< (х). < 1 3. Необходимые уелоеия первого и второю'о порядие для еедеи велипейвого прогреммироиепвя Утверждение 8. Для того чтобы точка хе являлась точкой локального минимума функции го на множестве Х (х)г< (х) (О, ю Е и<, Г< (х) =. О, (Е Оо) необходимо существование таких не всех равных нул<о чисел и„и„ю Е гю, о„ю Е Р, что иеЧюе(х~)+ ле и<Ч(<(х*) + л о<Ч<<(х ) = О, <ЯУ <ер' ие~О, и<~0, <сгю, иА(х') О, ю'со Точку локального минимума х* называют регулярной, если линейно независимы все вектора Чг< (х*) с теми индексами ю, для которых выполняются равенства г< (х") О.

Сл еда тв и е 1. Если точка х' регулярна, то можно положить и, = 1, остальные множители и<, о, определяются однозначно. Следующее утверждение дает необходимые условия оптимальности второго порядка. Утверждение 9, Если функции г„1р Р () Г () (0), дважды непрерывно дифференцируемы н х — регулярная точка минимума, то существуют такие числа и„о„что Че<р(х, и, и) = О, и,~О, иД(х) = О, <ЕУ, (Ч <р(х, и, п)<ю, <ю)~0 для всех )с, удовлетворяющих условиям (Ч1с(х), )с)(0, сЕ(с!1с(х)=0, ис(0 сЕ0 ); (Ч1с(х), й) = О, с'с(с'(ис)0, 1~6 ) () Оо„.

ф(х и о)~1с(х)+ ~, 'ил(х)+ ~ ос1,(х). ся.У село 4. Уодовоо омтммодьмоотд дло оодоч мммммоэодма могдодммт фудмцмй Простейшим примером негладкой функции является часто встре- чающаяся функция вида 1,(х) = шах 1, (х), й й (1, 2, ..., лс). сея' Утверждение 10. Если х = агд ппп шах 1, (х) для заданных о дифференцируемых функций 1о 1р й, то существуют такие числа и, ~ О, ~ и, = 1, что выполняются равенства се~ ~ исЧ1,(х) =О, и,(1,(х) — тах1,(х)) = О, ссИ.

се.т сбт Выше приводилось весьма важное свойство выпуклых функций, состоящее в том, что производная по направлению г1' (х', г) рав- няется шах (у, г). Это свойство положено в основу определения еемсоч класса квазидисрференс(ируемых функций, т. е. таких функций 1, для которых в каждой точке х определено замкнутое выпуклое мно- жество Мс(х) 1множество квазиградиентов), удовлетворяющее для всех г Е Л" равенству 1' (х, г) снах (у, г) (314). Поэтому все выуемсскс пуклые функции принадлежат классу квазидифференцируемых функций.

Квазидифференцируемыми являются также и все функ- ции 1„вида 1, (х) шах 1 (х, у) с дифференцируемыми 1 и замкгег нутым ограниченным множеством )' (в данном случае Мг(х) = со (г (г = Ч,1 (х, у*), у' =* агд шах 1(х, у))), а также все сла- ссеУ бовыпуклые функции (272) (те функции 1, для которых существу- ет непустое множество ссс (х), удовлетворяющее условию ча Е Е Ос(х) Чу б 71" 1(у) — 1(х) ~ (И, у — х) + г (х, у), равномерно по х в каждом ограниченном замкнутом множестве 9 3 х) и функции вида 1„(х) шах 1 (х, а), где1 (х, а) — непрерываел ны по а и слабовыпуклы по х при любом фиксированном а из ком- пактного топологического пространства А. В последнем случае. Мп (х) = со () бсс.,м (х). аел Утверждение 11.

Для того чтобы точка х Е В" минимизирова- ла квазидифференцируемую функцию 1, необходимо, чтобы ОЕ Е Мс(х). зг Утверждение 12. Вектор г(х') = ага ппп гпах (у, г) опреде- ~~ к,"=1 ге мбкч ляет направление наибыстрейшего убывания функции ) в х». В работе [129) дано более общее определение квазидифференцируемой функции, а именно: функция ): В"-» В называется квазидифференцируемой в точке х, если оиа дифференцируема в этой точке по направлению и если существуют такие выпуклые компакты д~ (х) с: В" и д~ (х) с В", что для любого г Е В" Г'(х, г) = шах (г, у)+ ппп (г, у). «ЕЕП1> «бенд Множество таких функций замкнуто относительно операций взятия максимума и минимума по конечяому числу функций и относительно всех «алгебраических» операций.

Теорема [129). Если х = ага ппп Г (х), то — дГ' (х) с: д) (х); если х = ага гпах )'(х), то — д) (х) ~ д)'(х). к Задачу условной (и параметрической) оптимизации можно привести методом развязывающей декомпозиции к более простой задаче минимизации ), (х, р) иа реализуемом носителе г (х, р) = О, определяющем функцию р -э х (р) [22). УтвеРждение 13, КвазидиффеРенциалы (» фУнкции )л (х (Р), Р) по р в точке р вычисляются с помощью квазидифференциалов Ц», у функций Г„) по х в точке (х (р), р) как квазидифференциалы по р в р для функций г, (х, р) + г () (х, р), р) при г» = г (г, р) по переменной х. 0.5.

Методы последовательных приближений Методами последовательных приближений строят такую последовательность х', х', ..., х" ~ Х, которая либо является лшнимизируюи(ей, т. е. удовлетворяет условиям !пи(х") = [п[1(х), (0.21) л-~ л кЯХ либо сходится к решению, т. е. 1ппх" = хк агйгп[п~(х), (0.22) л сл ксх либо определяет спин(ионарное решение, удовлетворяющее тем или иным необходимым условиям оптимальности, например, 1)ш [[ Ц (х") [1 = О. (0.23) Л ко Очевидно, сходимость (0.22) обеспечивается выполнением неравенств [[х"+' — х» [( у„[~ х" — хк[ 32 при о„( о( 1 для всех и = 1, 2, .... В данном случае говорят, что метод сходится со скоростью геометрической прогрессии, или с линейной скоростью; в случае оа-е. 0 — со сеерхлинейной скоростью, в случае о„( С)х" — хе ) — с квадратичной скоростью, а в случае о„( С)х" — х' ))с — ' — со скоростью й-го порядка.

Способы вычисления (и + 1)-го приближения х"+' обычно основаны на использовании получаемой информации о значениях ) (х"), 7 (х" — '), ..., а иногда и производных первого ЧГ (х"), Ч1'(х"-'), ..., второго Ч',.1(х"), Ч„',): (х -'), ...

Характеристики

Список файлов книги