Основы теории оптимизации (стр. 61 )

Если же множество X принадлежит какому-либо пространству то задачу (1) называют задачей на минимум в ограниченной обгасти. Когда множество Х выделяется из пространства системой ог­раничений типа равенств и/или неравенств то говорят об условной минимизации и задачу (1) назы­вают задачей на условный экстремум (или задачей математического программирования)

Задачи математического программирования по виду функции f(x) разбиваются на следующие классы

— функция f(x) линейная и ограничения линейные: задача линейного программирования;

— функция f(x) не линейная и/или ограничения нелиненые (или ограничения нелинейные, а f(x) —линейная функция) задача нелинейного программирования

В свою очередь если ограничения линейны, то задача нелинейного пpoграммирования может быть разбита на следующие подклассы:

— f(x) дробно-рациональная функция: задача дробно-рационального программирования,

— f(x) выпуклая квадратичная функция: задача квадратичного программирования.

Все перечисченные задачи называют еще задачами оптимизации.

Отдельный класс оптимизационных задач представляют задачи оптимального цправления. Если в задачах оптимального управления процесс оптимизации можно представить в виде ряда последова­тельных этапов (шагов), то такие задачи называют многошаговыми задачами оптимизации (управле­ния). Для их решения используются методы динамического программирования, которые применимы к непрерывной модели многошаговою процесса оптимизации, когда управления и векторы состо­яния могут непрерывно изменяться. Однако для многих экономических и производственных задач характерной является дискретная модель, когда величины, описывающие процесс, могут принимать только дискретный ряд значений. В таких задачах применяются дискретные методы динамического программирования

Оптимизационная задача называется детерминированной в том случае, если погрешностями вычи­сления или экспериментального определения значении функций f(x) можно пренебречь В противном случае оптимизационная задача называется стохастической. Для этого клacca задач разработаны специальные методы

Необходимые и достаточные усло­вия экстремума

1) Если целевая функция f (х) ≡ f (х1,..., хп), х Rп, то минимизация f (x) приво­дит к задаче:

(4)

Введем в рассмотрение градиент и гессиан функции f:

Toгда разложение функции в ряд Тейлора в окрестности точки при ∆ =h ; || || = 1; h = ∆ x имеет вид:

Величина (( ), ) ≡ — производная f в точкe по направлению ; — "кривизна'' поверхности и = f( ) в точке по направлению .

2) Необходимые и достаточные условия минимума для дважды дифференцируемой функции f (х1,..., хп). Напомним

(матрица А > 0, если х≠0(Aх, х) > 0 — положительно определенная квадратичная форма.

Заметим, что по существу многокритериальная задача отличается от обычной задачи оптимизации только наличием нескольких целевых функций вместо одной.

6.3. Критерий оптимальности для функции многих переменных

Разложим f( ) в ряд Тейлора в окрестности некоторой точки  (здесь и далее через х обозначается вектор ).

,

где  - точка разложения в пространстве Rn;

 ∆x=x- - величина изменения х;

 - n-мерный вектор столбец первых частных производных f(x) , вычисляемый в ;

 - матрица Гессе – симметричная матрица n×n вторых частных производных f(x). Элемент матрицы Гессе, расположенный на пересечении i-ой строки и j-го столбца равен

 о3(∆x) - члены порядка выше второго по ∆x. Ими можно пренебречь.

Запишем изменение функции ∆f в соответствии с изменением аргументом ∆x:

Для всех точек в окрестности минимума ∆f ≥0.

  Определение 1.

Точка  является точкой глобального минимума, если ∆f ≥0 выполняется для xRn. Обозначим её как x**.

Определение 2.

Точка  является точкой локального минимума, если ∆f ≥0 выполняется в некоторой δ-окрестности точки . Обозначим её как x*.

Если ∆f  больше 0, меньше 0 или равно нулю в зависимости от выбора δ - окрестности, то  - седловая точка.

Для того, чтобы знак ∆f  не менялся при произвольном варьировании ∆x нужно, чтобы ∆f ( )=0, то есть  была бы стационарная точка функции ∆f. Если это выполняется, то

Теперь знак ∆f определяется квадратичной формой:

такая f(x), что ;

Стационарная точка  является точкой локального минимума, если матрица Гессе H( ) положительно полуопределена, то есть  для всех x.

Стационарная точка  есть точка локального максимума, если H( ) отрицательно полуопределена, то есть  для всех x.

Стационарная точка  есть седловая точка, если H( ) не определена (главная диагональ и главные определители не равны нулю).

Анализ  можно провести в другом аспекте.

Рассмотрим стационарную точку  с δ-окрестностью и векторами, исходящими из .

При этом любую точку  из этой δ-окрестности можно получить как ,

где α - коэффициент.

Путём соответствующего подбора α и  можно получить все точки δ - окрестности. Подставим это значение в ∆f (вместо ∆x подставим - )

Получим

Теперь мы можем определить направление S, определить как направление спуска, подъёма или общего вида.

Спуск – если ∆2f (х) положительно полуопределена.

Подъём – если ∆2f (х) отрицательно полуопределена.

Общего вида – если ∆2f (х) не определена.

Необходимые и достаточные условия оптимальности.

  Необходимые.

Для наличия в точке  локального минимума необходимо, чтобы

∆f ( ) =0 и ∆2f ( )≥0.

  Достаточные.

Если выполняются необходимые условия оптимальности, то этого достаточно чтобы =x* (была локальным минимумом).

Если f(x) выпуклая, то x* является и x**.

Пример. Критерии оптимальности

Рассмотрим функцию

,

линии уровня которой изображены на рис. 1.

 

  Рис. 1. Линии уровня нелинейной функции двух переменных

необходимо классифицировать точку =[0,0]T.

Решение.

,