3. Необходимые и достаточные условия условного экстремума. Численные методы поиска условного экстремума (1013383), страница 3

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

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

Значения функции в точках экстремума: f  A   , f B   1, f C   5 . 4x2g1 ( x)  0f ( x) 1g 2 ( x)  0B1211554A2x1 1X2CРис. 4163f ( x)  1f ( x)  0f ( x)  5ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМАМЕТОД ШТРАФОВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x)  f  x1,, xn ифункцииg j ( x)  0 ,ограниченийg j ( x)  0 ,j  1,  , m ;j  m  1,  , p ,определяющие множество допустимых решений Х.Требуется найти локальный минимум целевой функции на множестве Х , т.е.такую точку x   X , чтоf ( x  )  min f ( x) ,xXгде X   xm  n .j  m  1, , pg j ( x)  0,j  1, , m;g j ( x)  0,АлгоритмШаг 1. Задать начальную точку x 0 , начальное значение параметра штрафа r 0  0 ,число C  1 для увеличения параметра, малое число   0 для остановки алгоритма.Положить k  0 .Шаг 2.

Составить вспомогательную функциюF x, rkrk f ( x) 2 m2  [ g j ( x) ]  j 1pj  m 1[ g j ( x) ] 2  .Шаг 3. Найти точку x  ( r k ) безусловного минимума функции F x , r k по хспомощью какого-либо метода (нулевого, первого или второго порядка):F x  (r k ), r k  min F x, r k .xR nПри этом задать все требуемые выбранным методом параметры. В качестве начальнойточки взять x k . Вычислить P x  (r k ), r k .Шаг 4. Проверить условие окончания:а) если P x  (r k ), r k   , процесс поиска закончить:x   x  (r k ),f ( x  )  f x  (r k ) ;б) если P x  (r k ), r k   , положить: r k 1  C r k , x k 1  x  ( r k ), k  k  1 иперейти к шагу 2.164Пример 1. Найти условный минимум в задачеf ( x)  x 2  4 x  min,g1 ( x)  x  1  0. 1. В поставленной задаче m  0 (ограничения-равенства отсутствуют), p  1 .Решим задачу аналитически при произвольном параметре штрафа r k , а затем получимрешение последовательности задач поиска безусловного минимума.2.

Составим вспомогательную функцию:F x, r k  x 2  4 x rk max  0, x  1  2 .23. Найдем безусловный минимум функции F x , r kпохс помощьюнеобходимых и достаточных условий (см. гл. 2 – лекция 1): F x, r k 2 x  4  0, x  1  0,x 2 x  4  r k x  1  0, x  1  0 .Отсюда x   2 , но при этом не удовлетворяется условие x   1  0 , а такжеkx (r ) 4rk2rk.В табл. 1 приведены результаты расчетов при r k  1, 2,10,100,1000,  , а на рис. 1 данаграфическая иллюстрация процесса поиска решения.Таблица 1krkx  (r k )F x  (r k ), r k01533,66123 1,523,52103,16631004100057 1,1666652 1,019651502 1,0019950113,0193,0023165f  x , F x , r kr1  2x  10 x  2 x  1Xx21x3r0  11f x 234Рис.

1Так как 2 F x  (r k ), r kx2  2 rk  0при r k  0 , то достаточные условияминимума F x , r k удовлетворяются. При r k   имеемx   lim4 rkr   2rkkf ( x  )  3 . 1,Найдем решение этой задачи с применением необходимых и достаточных условийэкстремума. Функция Лагранжа имеет видL  x ,  0 , 1    0 x 2  4 x  1  x  1 .Необходимые условия минимума первого порядка:а) L x ,  0 ,  1 x  0 2 x  4   1  0 ;б) x  1  0 ;в) 1  0 ;г) 1  x  1  0 .Решим систему для двух случаев.Первый случай:  0  0 , тогда из условия «а» получаем 1  0 , что неудовлетворяет утверждению.166Второй случай:  0  0 .

Поделив уравнения системы на  0 и заменив1на 1 ,0получим 2 x  4  1  0 . Из условия «г» имеем 1  0 или x  1 . При 1  0 из условия«а» следует, что x  2 , но при этом не удовлетворяется условие «б». При x   1 имеем1  2 .Достаточные условия минимума первого порядка удовлетворяются, так как1  2  0 и число активных ограничений l  1  n . Пример 2. Найти условный минимум в задачеf ( x)  x12  x 22  min,g1 ( x)  x1  x 2  2  0. 1. В поставленной задаче m  1 , ограничения-неравенства отсутствуют. Решимее аналитически.2.

Составим вспомогательную функцию:rkx1  x 2  22 .2F x, r k  x12  x 22 3. Найдем безусловный минимум F x , r kдостаточных условий:по хс помощью необходимыхи F x, r k 2 x1  r k x1  x 2  2  0 , x1 F x, r k 2 x 2  r k x1  x 2  2   0 . x2Вычитая из первого уравнения второе, получаем x1  x 2 иx1 (r k )  x 2 (r k ) rk.1 r kВ табл.

2 приведены результаты расчетов при r k  1, 2, 10, 100, 1000,  , а на рис. 2дана графическая иллюстрация процесса поиска решения.Таблица 2krkx1 (r k )  x 2 (r k )F x  (r k ), r k011122103100410005122310111001011000100111,3331,811,981,9982167x22Ax 2x  101xx   2x11 2x1  1g1 ( x)  x1  x 2  2  0Рис. 2kТак как матрица Гессе H x (r ), rk2 rk rkдостаточные условия безусловного минимума F x , r kимеемlimrkrk  1 rk 1  x1  x 2 ; f ( x  )  2 . 168rk   0 при r k  0 , тоk2r удовлетворяются. При r k  .

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

Список файлов лекций