1 Общая постановка задачи оптимизации и основные положения. Необходимые и достаточные условия безусловного экстремума (Лекции по теории оптимизации и численным методам)

ЛЕКЦИИЛекция 1Раздел I. ТЕОРИЯ ОПТИМИЗАЦИИ1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИИ ОСНОВНЫЕ ПОЛОЖЕНИЯПостановка задачи поиска минимума функций содержит: целевую функцию f ( x) , где x  ( x1 ,..., xn )T , определенную на n-мерном евклидовом пространстве R n . Ее значения характеризуют степень достижения цели, воимя которой поставлена или решается задача; множество допустимых решений X  R n , среди элементов которого осуществляется поиск.Требуется найти такой вектор x  из множества допустимых решений, которомусоответствует минимальное значение целевой функции на этом множестве:f ( x )  min f ( x) .(1.1)x XЗ а м е ч а н и я.1.

Задача поиска максимума функции f ( x) сводится к задаче поиска минимума путем замены знака перед функцией на противоположный (рис. 1):f ( x )  max f ( x)   min   f ( x)  .x Xx Xff ( x )f ( x)xx f ( x) f ( x )Рис. 12. Задача поиска минимума и максимума целевой функции f ( x) называется задачей поиска экстремума: f ( x )  extr f ( x) .x X53. Если множество допустимых решений X задается ограничениями (условиями),накладываемыми на вектор x , то решается задача поиска условного экстремума. ЕслиX  R n , т.е.

ограничения (условия) на вектор x отсутствуют, решается задача поискабезусловного экстремума.4. Решением задачи поиска экстремума является пара ( x , f ( x )) , включающаяточку x  и значение целевой функции в ней.5. Множество точек минимума (максимума) целевой функции f ( x) на множествеX обозначим X  . Оно может содержать конечное числo точек (в том числе одну), бесконечное число точек или быть пустым.Определение 1.1.

Точка x  X называется точкой глобального (абсолютного) минимума функции f ( x) на множестве X , если функция достигает в этой точке своего наименьшего значения, т.е.f ( x )  f ( x) x  X .Определение 1.2. Точка x   X называется точкой локального (относительного)минимума функции f ( x) на множестве допустимых решений X , если существует   0 ,такое, что если x  X и x  x    , то f ( x )  f ( x) . Здесь x  x12  x 22 ... x n2 –евклидова норма вектора x .З а м е ч а н и я.1. В определении 1.1 точка x  сравнивается по величине функции со всеми точками из множества допустимых решений X , а в определении 1.2 – только с принадлежащими ее  -окрестности (рис.

2).x2Xxx1Рис. 22. Если в определениях 1.1 и 1.2 знак неравенства  заменить на  , то получимопределения глобального (абсолютного) и локального (относительного) максимумов.3. Глобальный экстремум всегда является одновременно локальным, но не наоборот.6Определение 1.3. Поверхностью уровня функции f ( x) называется множество точек, в которых функция принимает постоянное значение, т.е.

f ( x)  const . Если n  2 ,поверхность уровня изображается линией уровня на плоскости R 2 .Пример. Построить линии уровня функций:x1222а) f ( x)  x1  x2 ; б) f ( x)  x22 ;4 Уравнения линий уровня имеют следующий вид:а) f ( x)  x12  x22  const  r 2 – уравнение окружностей с центром в точке 0, 0Tирадиусом, равным r (рис. 3, а);x2б) f ( x)  1  x22  const – уравнение эллипса. Если const  1 , то a  2 и b  1 –4большая и малая полуоси (рис. 3, б) . x2ff ( x) x12f ( x)  const  42x221x2x12f ( x)  0f ( x)  const  1x1а)x2ff ( x) x1242 x22f ( x)  4142f ( x)  0x2x1б)Рис. 374f ( x)  1x1Определение 1.4. Градиентом f ( x) непрерывно дифференцируемой функцииf ( x) в точке x называется вектор-столбец, элементами которого являются частные производные первого порядка, вычисленные в данной точке:  f ( x)   x1   f ( x) f ( x)    x2  .    f ( x)  x n Градиент функции направлен по нормали к поверхности уровня (см.

определение1.3), т.е. перпендикулярно к касательной плоскости, проведенной в точке x , в сторонунаибольшего возрастания функции в данной точке.Определение 1.5. Матрицей Гессе H ( x) дважды непрерывно дифференцируемойв точке x функции f ( x) называется матрица частных производных второго порядка, вычисленных в данной точке:H ( x)  где hij  2 f ( x)x12 2 f ( x)x2 x1 2 f ( x)xn x1 2 f ( x) 2 f ( x) x1x2x1xn   h11 2 f ( x) 2 f ( x)  h21x2 xn   x22     hn122 f ( x) f ( x) xn x2xn2 h12  h1n h22  h2n ,   hn 2  hnn  2 f ( x), i , j  1,...

, n . xi  x jЗ а м е ч а н и я.1. Матрица Гессе является симметрической размеров n  n  .2. Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению. Он указывает в сторонунаибольшего убывания функции в данной точке.3. С помощью градиента и матрицы Гессе, используя разложение в ряд Тейлора,приращение функции f ( x) в точке x может быть записано в формеf ( x)  f ( x   x)  f ( x)  f ( x)T  x 21 T2 x H ( x)  x  o (  x ) ,2(1.2)где o (  x ) – сумма всех членов разложения, имеющих порядок выше второго; xT H ( x)  x – квадратичная форма.8Пример. Для функции f ( x)  x12  x24 вычислить градиент и найти матрицу Гессе вточках x 0  0, 0 , x 1  1,1 . Согласно определениям 1.4 и 1.5 имеем:TT0 2, H ( x)  ; 0 12 x 2 2 2 0Tf ( x 0 )   0, 0  , H ( x 0 )  ;0 02 0 Tf ( x1 )   2, 4  , H ( x1 )  .

 0 12 Определение 1.6. Квадратичная форма xT H ( x)  x (а также соответствующая матf ( x)  2 x1 , 4 x23Tрица Гессе H ( x) ) называется: положительно определенной H ( x)  0  ,если для любого ненулевого  xвыполняется неравенство  xT H ( x)  x  0 ; отрицательно определенной  H ( x)  0  , если для любого ненулевогоxвыполняется неравенство  xT H ( x)  x  0 ; положительно полуопределенной  H ( x)  0  , если для любого x выполняетсянеравенство  xT H ( x)  x  0 и имеется отличный от нуля вектор  x , для которого  xT H ( x)  x  0 ; отрицательно полуопределенной  H ( x)  0  , если для любого  x выполняетсянеравенство  xT H ( x)  x  0 и имеется отличный от нуля вектор x , для которого  xT H ( x)  x  0 ;x , что неопределенной ( H (x )  0 ) , если существуют такие векторы x ,  ~выполняются неравенства  xT H ( x)  x  0 ,  xT H ( x)  x  0 ; тождественно равной нулю  H ( x)  0  , если для любого x выполняетсяравенство  xT H ( x)  x  0 .2.

НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ БЕЗУСЛОВНОГОЭКСТРЕМУМАПостановка задачиДана дважды непрерывно дифференцируемая функция f ( x) , определенная намножестве X  R n .Требуется исследовать функциюf ( x) на экстремум, т.е. определить точкиx   R n ее локальных минимумов и максимумов на R n :f ( x )  min f ( x) ;xRf ( x )  max f ( x) .nxR9n(2.1)Стратегия решения задачиНаходятся точки x  локальных экстремумов с помощью необходимых условийпервого и второго порядка (порядок условий определяется порядком используемых производных), а также достаточных условий безусловного локального экстремума.

Вычисляются значения f ( x ) функции в найденных точках локальных экстремумов.Утверждение 2.1 (необходимые условия экстремума первого порядка).Пусть x   R n есть точка локального минимума (максимума) функции f ( x) намножестве R n и f ( x) дифференцируема в точке x  . Тогда градиент функции f ( x)в точке x  равен нулю, т.е.f ( x  )  0(2.2)или f ( x ) 0, xii  1,...

, n .(2.3)Определение 2.1. Точки x  , удовлетворяющие условию (2.2) или (2.3), называютсястационарными.Утверждение 2.2 (необходимые условия экстремума второго порядка).Пусть точка x  есть точка локального минимума (максимума) функции f ( x) намножестве R n и функция f ( x) дважды дифференцируема в этой точке.

Тогда матрица Гессе H ( x ) функции f ( x) , вычисленная в точке x  , является положительно полуопределенной (отрицательно полуопределенной), т.е.H ( x )  0 ,(2.4)( H ( x )  0 ) .(2.5)Утверждение 2.3 (достаточные условия экстремума).Пусть функция f ( x) в точке x   R n дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной), т.е.f ( x  )  0 и H ( x  )  0 ,(2.6)( H ( x )  0 ) .(2.7)Тогда точка x  есть точка локального минимума (максимума) функции f ( x) на множестве R n .10Определение 2.2.

Рассмотрим определитель матрицы Гессе H ( x ) , вычисленнойв стационарной точкеh11hdet H ( x )  21hn11. Определители 1  h11 ,2 h12  h1nh22  h2n.  hn 2  hnnh11h12h21h22h11  h1n,...,  n называютсяhn1  hnnугловыми минорами.2. Определители m -го порядка ( m  n ), получающиеся из определителя матрицыH ( x ) вычеркиванием каких-либо ( n  m ) строк и ( n  m ) столбцов с одними и теми женомерами, называются главными минорами.Для проверки выполнения достаточных условий экстремума и необходимых условий второго порядка используются два способа.Первый способ (с помощью угловых и главных миноров – табл. 1). Критерий проверки достаточных условий экстремума (критерий Сильвестра).Для того чтобы матрица Гессе H ( x ) была положительно определенной( H ( x )  0 ) и точка x  являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:1  0 ,  2  0 ,...,  n  0 .(2.8)Для того чтобы матрица Гессе H ( x  ) была отрицательно определенной( H ( x  )  0 ) и точка x  являлась точкой локального максимума, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного:1  0 ,  2  0 ,  3  0 ,...,1n  n 0.(2.9) Критерий проверки необходимых условий экстремума второго порядка.1.