1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 2
Текст из файла (страница 2)
Если функция f (x ) определена и непрерывна на непустомзамкнутом множестве X и для некоторой фиксированной точки v из Xмножество Лебега M ( v ) = {x Î X | f ( x ) £ f ( v )} ограничено, то функция достигает на множестве X своей точной нижней границы.Следствие 2. Если функция f (x ) определена и непрерывна на непустомзамкнутом множестве X и для любой последовательности точек {x k }kÎN изX , для которой lim | xk |= +¥ , имеет место соотношение lim f ( xk ) = +¥k ®¥k ®¥( - ¥ ), то функция достигает на множестве X своей точной нижней (верхней) границы.Вторая проблема связана с поиском условий, которым должно удовлетворять оптимальное решение задачи.Третья проблема состоит в том, как найти хотя бы одно такое решение.Данные проблемы соответствуют разделам теории экстремальных задач,где исследуются вопросы существования оптимальных решений, необходимые и достаточные условия экстремума и численные методы нахождениярешений.
Последний раздел и является предметом настоящего пособия.7§ 2. Элементы выпуклого анализаМножество x Î R n называется выпуклым, если lx1 + (1 - l ) x2 Î X привсех x1 , x 2 Î X , l Î [0,1] . Иными словами, множество X выпукло, если оновместе с любыми своими двумя точками x1 и x 2 содержит соединяющий их{}отрезок [ x1 , x2 ] = x Î R n | x = x2 + l ( x1 - x 2 ), 0 £ l £ 1 (см. рис. 1). Рис. 2 –пример невыпуклого множества.x2x1XXРис.
1Рис. 2На числовой прямой R выпуклыми множествами являются всевозможныепромежутки, то есть одноточечные множества, интервалы, полуинтервалы,отрезки, полупрямые, а также сама прямая. Примерами выпуклых множеств впространстве R n служат само пространство, любое его линейное подпространство, одноточечное множество, шар, отрезок, а также прямая, проходящая через точку x0 в направлении вектора h , луч, выходящий из точки x0 внаправлении вектора h , гиперплоскость с нормалью p и порождаемые еюполупространства. Пустое множество по определению выпуклое.
Нетруднопонять, что все перечисленные множества, кроме шара, являются частнымислучаями выпуклого множества вида{гдеA}{}X = x Î R n | Ax £ b = x Î R n | ai , x £ bi , i = 1,K, m ,– некоторая матрица размера m ´ n со строками(3)a1 ,K, am ,b = (b1 , K, bm )T Î R m , m = 1,2,K . Множества вида (3) принято называть полиэдральными или просто полиэдрами. Таким образом, полиэдр – это множество решений некоторой системы конечного числа линейных неравенств.
Или,другими словами, пересечение конечного числа полупространств.Выпуклойкомбинациейточекx1 ,K, xmназываетсяточка=z a1 x1 + a 2 x2 + K + a m xm , где a i ³ 0 , i = 1,K, m , и a1 + a 2 + K + a m = 1 .Теорема 2. Выпуклое множество X содержит выпуклые комбинации всехсвоих точек.Функция f (x ) , определенная на выпуклом множестве X Î R n , называетсявыпуклой на X , еслиf (lx1 + (1 - l ) x2 ) £ lf ( x1 ) + (1 - l ) f ( x 2 )(4)8при всех x1 , x2 Î X , l Î [0,1] .
Если при всех x1 , x 2 Î X , x1 ¹ x 2 и l Î ( 0,1) неравенство (4) выполняется как строгое, то f называется строго выпуклой наX . Функция f называется (строго) вогнутой, если функция ( - f ) (строго)выпукла.Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствующей точкисамого графика (рис. 3).Рис.
3Рис. 4Для вогнутой функции взаимное расположение хорды и графика обратно(рис. 4). Можно показать, что функции f ( x ) = x 2 , f ( x ) = e x выпуклы на R ;f ( x ) = ln( x ) вогнута на множестве положительных чисел; f ( x ) = sin x во-[0,p ]гнута наf ( x) = x2и выпукла на[p ,2p ].Функцияf ( x) = xвыпукла, aстрого выпукла на R n .Функцию вида f ( x ) = a, x + b , где a Î R n , b Î R будем называть линейной. Ясно, что для линейной функции неравенство (4) выполняется как равенство.
Поэтому она одновременно выпукла и вогнута на R n , но не строго.Приведем еще несколько полезных свойств выпуклых функций.Теорема 3. Выпуклая функция f (x ) , определенная на выпуклом множестве X , непрерывна в каждой внутренней точке этого множества.Теорема 4. Функция f (x ) , дифференцируемая на выпуклом множествеX , выпукла тогда и только тогда, когда для любых x , y Î X справедливоf ' ( x ), y - x £ f ( y ) - f ( x ) .Теорема 5. Функция f (x ) , определенная и дважды непрерывно дифференцируемая на выпуклом множестве X , (строго) выпукла тогда и толькоæ ¶ 2 f ( x) ö÷(положительно) неотрицательтогда, когда матрица B( x ) = çç ¶xi ¶x j ÷èø i , j = 1,K, nно определена для любого x Î X .9Для исследования матрицы B(x ) на знакоопределенность используют, какправило, критерий Сильвестра (см. приложение).Теорема 6. Для любой выпуклой функции f (x ) , определенной на выпуклом множестве X , и любого числа l множество {x Î X | f ( x ) £ l} выпукло.Теорема 7 (неравенство Йенсена).
Если функция f (x ) выпукла на выпуклом множествеX , тоmf ( åa i xi ) £i= 1måa i f ( x i ) ,гдеi= 1xi Î X , a i ³ 0 ,i = 1,K, m , и a1 + a 2 + K + a m = 1 .Задача (1)-(2) называется выпуклой, если S – выпуклое множество, f ,j i ( x ) £ 0, i = 1,K, m , – выпуклые функции на S .Сформулируем несколько простых утверждений, объясняющих интерес кданному типу задач оптимизации.Теорема 8. Если задача (1)-(2) выпукла, то любое ее локальное решениеявляется также глобальным.Следующее свойство выпуклых задач можно сформулировать в виде следующего общего принципа: необходимые условия оптимальности в том илиином классе задач оптимизации при соответствующих предположениях выпуклости оказываются и достаточными [2, 4, 9].
Приведем обоснование данного свойства применительно к задаче безусловной оптимизации.Теорема 9. Пусть функция f выпукла на R n и дифференцируема в точкеx * Î R n . Если f ' ( x * ) = 0 , то x * – точка минимума f на R n .Теоремы 8, 9 говорят о том, что для выпуклой задачи отыскание стационарной точки автоматически означает отыскание решения, причем глобального.Укажем еще одно полезное свойство выпуклых задач.Теорема 10. Пусть задача (1)-(2) выпукла и имеет решение. Тогда множество ее решений Q * = Arg min f ( x ) выпукло. Если при этом функция fxÎQстрого выпукла на множестве Q , то решение задачи единственно.Большинство теорем о сходимости методов оптимизации доказывается впредположении выпуклости функции, оценки скорости сходимости, которыебудут рассматриваться в параграфе 4, часто устанавливаются при еще болеежестком предположении сильной выпуклости.10Определение 1.
Дифференцируемая функция f называется сильно выпуклой (с константой l > 0 ), если для любых x и y из R n справедливоf ( x + y ) ³ f ( x ) + f ¢( x ), y + l yЛемма 1. Если функция f22.(5)является сильно выпуклой (с константойl > 0 ), то она имеет глобальный минимум на R n .Доказательство.
Из условия (5) и неравенства Коши-Буняковского следуетf ( x + y ) ³ f ( x ) - f ¢( x ) y + l y22.Пусть r = 2 f ¢( x ) l . Если y ³ r , тоf ( x + y ) ³ f ( x ) + y (l y 2 - f ¢( x ) ) > f ( x ) .(6)Рассмотрим шар B( x , r ) с центром в точке x и радиуса r . По теореме Вейерштрасса непрерывная функция f достигает своего минимума на шареB( x , r ) в некоторой точке x * . Из неравенства (6) следует, что x * – минимумна всем R n . ▄Лемма 2. Если функция является сильно выпуклой (с константой l > 0 ) иx * – ее глобальный минимум, то для любого x Î R n выполняется неравенствоf ¢( x ) ³ 2l ( f ( x ) - f ( x * )) .(7)Доказательство.
Так как функция f сильно выпуклая, то подстановкаy = x * - x в (5) дает неравенство2f ( x ) - f ( x * ) + f ¢( x ), x * - x + l x * - x 2 £ 0 .Так какf ¢( x )2l + l / 2 ( x * - x ), f ¢( x )= f ¢( x )2l + l 2 ( x * - x ) =2l + l 2 ( x * - x )2³ 0,тоf ¢( x )222l + f ¢( x ), x * - x + l x * - x 2 ³ 0 ³³ f ( x ) - f ( x * ) + f ¢( x ), x * - x + l x * - x22.После приведения подобных членов получим требуемое неравенство.
▄Лемма 3. Пусть f – дважды непрерывно дифференцируемая функция. Еслиf – сильно выпуклая функция с константой l , то выполняется неравенство|| [ f ¢¢( x )]-1 ||£ l -1 .11Доказательство. Пользуясь формулой конечных приращений для функции f , получимf ( x + y ) - f ( x) = f ¢( x), y + f ¢¢( x + t 2 y ) y, y / 2 ,где 0 £ t 1 , t 2 £ 1 . Воспользуемся условием сильной выпуклости2f ¢¢( x + t 2 y ) y, y / 2 = f ( x + y ) - f ( x) - f ¢( x), y ³ l y / 2 .Заменяя y на ty , получим:2f ¢¢( x + t 2ty )ty , ty ³ l ty .Следовательно,2t 2 f ¢¢( x + t 2ty ) y, y ³ t 2l y .Поделив на t 2 и устремляя t к нулю, будем иметь2f ¢¢( x) y , y ³ l y .Положим y = ( f ¢¢( x)) -1 z , где z – произвольный элемент из R n .
Используя неравенство Коши-Буняковского, получим l ( f ¢¢( x )) -1 z £ z . По определению нормы оператора это означает, что справедливо неравенство[ f ¢¢( x)]-1£ l -1 .▄§ 3. Начальные сведения о численных методах оптимизацииВ большинстве случаев задачу (1)-(2) приходится решать численно накомпьютере.
При этом можно с помощью необходимых условий оптимальности свести задачу оптимизации к некоторой другой задаче, а затем попытаться использовать разработанные для ее решения численные методы. Так, например, для решения задачи минимизации на R n дифференцируемой функции f можно воспользоваться каким-либо численным методом решениясистемы уравнений f ' ( x ) = 0 . Однако, наиболее эффективными оказываютсяметоды, разработанные специально для решения задачи оптимизации, так какони позволяют полнее учесть ее специфику.Любой численный метод (алгоритм) решения задачи оптимизации основанна точном или приближенном вычислении ее характеристик (значений целевой функции, ограничений, а также их производных). На основании полученной информации строится приближение к решению задачи – искомой точкеминимума x * или, если такая точка не единственна, – к множеству точек минимума.
Иногда удается построить только приближение к минимальномузначению целевой функции f * = min f ( x ) .xÎQДля каждой конкретной задачи вопрос о том, какие характеристики следу12ет выбрать для вычисления, решается в зависимости от свойств минимизируемой функции, ограничений и имеющихся возможностей по хранению иобработке информации. Так, для минимизации недифференцируемой функции нельзя воспользоваться алгоритмом, предусматривающим возможностьвычисления в произвольной точке градиента функции. В случае, когда доступен небольшой объем памяти, при решении задачи высокой размерностинельзя воспользоваться алгоритмом, требующим вычисления на каждом шагеи хранения в памяти матрицы вторых производных и т.п.Алгоритмы, использующие лишь информацию о значениях минимизируемой функции, называются алгоритмами нулевого порядка; алгоритмы, использующие также информацию о значениях первых производных, – алгоритмами первого порядка; алгоритмы, использующие, кроме того, информацию о вторых производных, – алгоритмами второго порядка.Работа алгоритма состоит из двух этапов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
