Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации
 Скачать 3.42 Mb.
|
|
Пример 2. Проведем одну итерацию наискорейшего спуска для функции 13 8 6 4 ) ( 2 1 2 2 2 1 x x x x x f из начальной точки 0 1 0 X Найдем градиент функции ) ( X f в точке 0 X : 8 4 8 8 6 2 ) ( 0 2 0 1 0 x x X f Запишем выражение для следующей точки последовательности: 8 4 1 8 4 0 1 ) ( 0 0 X f X X и строим функцию 8 80 272 13 8 8 ) 4 1 ( 6 ) 8 ( 4 ) 4 1 ( ) ( ) ( 2 2 2 X f Минимизируя ее с помощью необходимого условия 0 80 544 ) ( находим оптимальное значение величины шага 34 5 544 80 0 a Определяем точку минимизирующей последовательности 3 17 20 17 27 34 5 8 34 5 4 1 ) ( 0 0 0 1 X f a X X Первая итерация завершена. Замечание 1. Метод наискорейшего спуска имеет простой геометрический смысл: очередная точка 1 k X минимизирующей последовательности лежит на луче 0 ), ( : k k n X f X X E X . Причем, если k определяется из условия (3.56), т.е. когда по лучу осуществляется исчерпывающий спуск, то 1 k X находится в точке касания луча с линией уровня, проходящей через эту точку (см. рис. 2). Рис. 2. Ортогональность направления k S градиенту ) ( 1 k X f при исчерпывающем спуске. Далее можно понять, что чем ближе линии уровня const X f ) ( к окружности, тем быстрее сходится градиентный метод. Метод Ньютона минимизации функции многих переменных До сих пор мы рассматривали методы безусловной минимизации первого порядка, для реализации которых использовались лишь первые производные минимизируемой функции. Если же минимизируемая функция дважды непрерывно дифференцируема, то возможно применение методов минимизации второго порядка, которые используют квадратичную часть 4 разложения этой функции в ряд Тэйлора. Поскольку квадратичная аппроксимация гораздо точнее линейной, естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого порядка. Опишем метод Ньютона для задачи n E X X f ) ( min , ( 2) где ) ( X f - дважды непрерывно дифференцируемая функция. Пусть известно k -е приближение и матрица Гессе ) ( X f положительно определена при всех n E X , следовательно, невырождена 0 ) ( (det X f ). Тогда существует обратная матрица 1 ) ( X f . Тогда найдем точку минимума 1 k X квадратичной функции (3.51), аппроксимирующей ) ( X f в окрестности точки k X X из выражения: ,... 1 , 0 ), ( ) ( 1 1 k X f X f X X k k k k ( 3) Итерационный процесс (3), начатый из произвольной точки n E X 0 , называется методом Ньютона минимизации функции многих переменных и является обобщением метода Ньютона в одномерном случае. Очевидно, для квадратичной функции с положительно определенной матрицей A применение метода Ньютона обеспечивает получение точки глобального минимума ровно за один шаг из любой точки n E X 0 Отметим, что даже сходящаяся последовательность } { k X метода Ньютона не всегда обеспечивает монотонное убывание ) ( X f , т.е. неравенство ) ( ) ( 1 k k X f X f для некоторых ,... 1 , 0 k может нарушаться. Этот недостаток устранен в обобщенном методе Ньютона: ,... 1 , 0 ), ( ) ( 1 1 k X f X f X X k k k k k , где величина 0 k находится на каждом шаге из условия исчерпывающего спуска по направлению ) ( ) ( 1 k k k X f X f S 5 Недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации. Пример 3. Методом Ньютона решить задачу n E X x x x x x X f 1 2 1 2 2 2 1 4 3 4 ) ( min , ) 0 ; 0 ( 0 X Градиент 0 1 4 6 1 4 8 ) ( 1 2 2 1 0 x x x x X f , матрица Гессе 6 4 4 8 ) ( 0 A X f Найдем обратную матрицу. Для этого сначала найдем определитель матрицы: 0 32 16 48 6 4 4 8 Следовательно, обратная матрица существует. Далее: допишем к исходной матрице единичную матрицу справа: 1 0 0 1 6 4 4 8 и при помощи элементарных преобразований получим единичную матрицу слева: 8 / 2 8 / 1 16 / 2 16 / 3 1 0 0 1 2 1 16 / 2 16 / 3 8 0 0 1 2 1 2 3 8 0 0 16 2 1 0 2 8 0 8 16 2 1 0 1 8 0 4 8 2 0 0 1 12 8 4 8 1 0 0 1 6 4 4 8 Следовательно: 4 1 8 1 8 1 16 3 ) ( 1 0 X f . С помощью формулы (3) получаем 8 1 16 3 0 1 4 1 8 1 8 1 16 3 0 0 ) ( )] ( [ 0 1 0 0 1 X f X f X X Так как 6 ) 0 ; 0 ( ) ( 0 X f , то задача решена: 1 * X X . Целевая функция квадратична, поэтому решение задачи получено за одну итерацию. Описанный метод Ньютона может применяться лишь для минимизации функций, у которых матрица вторых частных производных обратима. Лекция №7. МЕТОДЫ ОПТИМИЗАЦИИ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ Постановка и классификация задач математического программирования Многие практические задачи оптимизации сводятся к математическим моделям вида (max) min ) ( X f , U X , ( 1) где допустимое множество U не совпадает со всем пространством n E . В этих случаях говорят об условной минимизации функции n переменных. В большинстве случаев допустимое множество U определяется ограничениями-равенствами и (или) неравенствами, т.е. рассматривается задача (max) min ) ( X f , n E X , ( 2) 1 , 0 ) ( I i X g i , ( 3) 2 , 0 ) ( I i X g i , ( 4) где m I I ,..., 1 , 2 1 - заданные множества индексов. Соотношения (5) - (7) представляют собой запись условий так называемой задачи математического программирования. Решение задач математического программирования, как правило, связано со значительно большими трудностями, чем решение задач безусловной минимизации. На рис. 3 приведены возможные случаи расположения точки минимума * x в задаче математического программирования min ) ( X f , , 0 ) ( X g i 3 , 2 , 1 i , 2 E X на допустимом множестве U (множество U окрашено). Пунктиром изображены линии уровня целевой функции. Рис. 3. К задаче математического программирования для 2 E U ( 0 ) ( 1 X g , 0 ) ( 2 X g , 0 ) ( 3 X g ):а - точка * X совпадает с точкой безусловного минимума функции ) ( X f в 2 E ; б - не совпадает с точкой безусловного минимума Для решения большинства практических задач используются приближѐнные численные методы. Рассмотрим некоторые из них, представляющие две группы методов. 1. Методы, использующие преобразование задачи условной оптимизации в эквивалентную последовательность задач безусловной оптимизации путѐм введения в рассмотрение вспомогательных функций. Эти методы называют методами последовательной безусловной оптимизации. 2. Методы решения задачи условной оптимизации, основанные на движении из одной допустимой точки, где выполняются все ограничения, к другой допустимой точке с меньшим значением целевой функции. Таким методом является, например, метод возможных направлений. Задача оптимизации с ограничениями типа равенств (задача на условный экстремум). Задача с ограничения ми типа равенств записывается в виде: (max) min ) ( X f , n E X , ( 5) m i X g i ,..., 1 , 0 ) ( , ( 6) Здесь множество U задается ограничениями-равенствами (2). Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f (Х) над множеством U (см. рис. 1). f(x 1 ,x 2 ) x 1 x 2 U Рис. 1. Геометрическая интерпретация задачи на условный экстремум в двумерном случае с одним ограничением. Точки, удовлетворяющие всем ограничениям (2) (т. е. точки множества U), называют допустимыми. Допустимая точка X * называется условным минимумом функции f(Х) при ограничениях m i X g i ,..., 1 , 0 ) ( (или решением задачи (1)–(2)), если при всех допустимых точках X U: ) ( ) ( * X f X f Если данное условие выполняется только для допустимых Х, лежащих в некоторой окрестности ( X * ) точки X * , то говорят о локальном условном минимуме. Классический метод решения задачи на условный экстремум Пусть в задаче min ) ( X f n E X m i X g i ,..., 1 , 0 ) ( , функции ) ( X f и m i X g i ,..., 1 ), ( , дифференцируемы в n E и ранг матрицы Якоби m i x g j i ,..., 1 , , n j ,..., 1 равен m в каждой точке допустимого множества U , определенного системой (2). Последнее условие означает, что градиенты ) ( X g i в точках U X не обращаются в ноль и линейно независимы. В этом случае равенства (2) задают связь между m зависимыми и m n независимыми переменными из j x n j ,..., 1 . Пусть, для определенности, этими зависимыми переменными являются m x x ,..., 1 и система (2) такова, что можно получить явные выражения ) ,..., ( 1 1 1 n m x x x , …………………… ( 7) ) ,..., ( 1 n m m m x x x Подставляя их в формулу для целевой функции ) ( X f из (1), получим задачу минимизации min ) ,..., ( ) ,..., , ,..., ( 1 1 1 n m n m m x x F x x f f функции m n переменных без ограничений. Пример1. Имеем задачу с тремя неизвестными при ограничении: f( x 1 , x 2 , x 3 )= x 1 x 2 + x 3 g( x 1 , x 2 , x 3 )= x 1 +x 2 +x 3 - 1 = 0. Исключив переменную x 3 с помощью уравнения g(Х)=0: x 3 = 1 -x 1 -x 2 получим оптимизационную задачу с двумя переменными без ограничений: f(x 1 ,x 2 ) = x 1 x 2 +1 -x 1 -x 2 Данная задача может быть решена любым численным методом, например, градиентным спуском. Или классическим методом: 0 1 2 1 x x f * 1 x =1 0 1 1 2 x x f * 2 x =1 Тогда * 3 x = 1 - * 1 x - * 2 x =1-1-1=-1 Окончательно получим точку минимума для исходной задачи: ) 1 ; 1 ; 1 ( * X На практике решение системы (3) относительно m зависимых переменных часто оказывается невозможным или весьма затруднительным, поэтому в классическом математическом анализе разработаны другие методы решения задачи (1) - (2), в частности Метод множителей Лагранжа. Пусть * X - точка минимума в задаче (1) - (2). В ней выполняются все ограничения задачи: 0 ) ( * X g i , m i ,..., 1 . Рассмотрим допустимые в точке * X приращения ) ,..., ( 1 n x x X , т.е. такие, при которых 0 ) ( * X X g i m i ,..., 1 . Для таких приращений с точностью до бесконечно малых величин, меньших чем X имеем: n j j i i i m i x X g X X g X X g 1 * * * ,..., 1 , 0 ) ( ) ( ) ( ( 8) Для рассматриваемых приращений j x разность 0 ) ( ) ( * * X f X X f , так как * X - точка минимума ) ( X f на множестве U . Это говорит о том, что для ) ( X f точка * X является точкой локального минимума на допустимых приращениях. Следовательно, в этой точке для допустимых приращений выполняется необходимое условие экстремума: 0 ) ( * j x X f |