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

,

.

Отсюда, точка — стационарная.

,

Отсюда,

Матрица является неопределенной, так как квадратичная форма принимает положительное значение при z=(0,1) и отрицательное значение при z=(1,1). Поэтому представляет собой седловую точку, которая и изображена на рис. 1.

6.4 Квадратичная функция аргумента

Опираясь на тейлоровское разложение естественно в качестве удобной апроксимации гладкой функции f(х) в окрестности некоторой точки (в том числе и точки возможного экстремума) использовать квадратичную функцию Ψ ():

где А - симметричная, невырожденная матрица А = АТ, dеtA ≠ 0. Установим вид градиента Ψ и гессиана G = hess Ψ функции Ψ ():

(1) Стационарная дочка для Ψ () удовлетворяет условию:

(2)

Решение системы (2) зависит от ранта матрицы А. В случае совместной системы решение может быть и не единственным.

В окрестности стационарной точки *:

И поведение квадратичной функции определяется только свойствами матрицы А. Если А — симметричная невырожденная матрица, то сущеествует ортонормированный базис (ОНБ) из собственных векторов матрицы А. Пусть {λі, і} собственные значения и собственные векторы матрицы А. {і } - ОНБ. Разложим направление по базисутогда

Характер изменения Ψ() при движении вдоль k полностью определяется шагом λk. Если А>0, то все λі> 0 и х* точка минимума.

6.5 Рельеф поверхности целевой функции f(х). Поверхности уровня

Трудности и проблемы задачи минимизации, характерные для общего случая, столь же ясно проявляются и при рассмотрении минимизации функции двух переменных f(х, у). Геометрию поверхности z = f(х, у) представляют с помощью "плоских" линий уровня

L0 = {( х, у) : f(х, у)= f (х0, y0) = f0 = const} ,

являющихся проекциями на плоскость OXY сечения поверхности z = f(х, у) плос­костью z0 = f0.

Выделяют три основных типа рельефа поверхности.

а) котловинный - линии уровня похожи на концентричекские эллипсы с главными осями параллельными собственным векторам ness f(х, у). В малой окрестности невырожденного минимума (х*, у*) hess f(х, у)> 0 и рельеф поворхности именно котловиниый.

б) овражный - если линия уровня кусочно-гладкая, то геометрическое место точек (ГМТ) излома по всем линиям уровня называют истинным оврагом (если угол излома направлен в сторону возрастания функции) или истинным гребнем (если угол излома направлен в сторону убывания функции).

Однако чаще приходится иметь дело с разрешимыми оврагами и гребнями (ГМТ наибольшей кривизны - рисунок b')). Например, одна из стандартных тестовых функций многомерной минимизации (функция Розенброка)

f(х, у) = 100 (у - х2)2 + (1 - х)2

обладает пологим серповидным (''банановидным") ущельем и имеет абсолютный ми­нимум в точке х* (1.1).

в) неупорядоченный тип рельефа — характеризуется наличием многих максиму­мов, минимумов и седловин. Приведем в качестве примера функцию

f(х, у) = (1 + sin2x) (1 + sin2 у) с достаточно неупорядоченным рельефом:

Если рассматривать дифференцируемую в каждой точке функцию f (), то её производная по направлению

=(grad f, )=∙

обладает характерными свойствами на поверхности уровня

- производная по направлению радиента - максимальна;

- вдоль линии уровня - равна нулю и градиент перпендикулярен линии уровня в каждой точке.

6.6. Введение в методы безусловной минимизации функций многих переменных

6.6.1. Вводные понятия

Пусть заданы множество X, принадлежащее некоторому метрическому пространству, и скалярная функция f(x), определенная на этом множестве Х. Напомним, что задача на минимум функции f(x)записывается в виде

f(x)→ min, х X. (1)

В этой записи функцию f(x) называют целевой функцией, X — допустимым множеством, любой элемент х X - допустимой точкой задачи (1)

Поиск максимума функции f(x) на X эквивалентен задаче вычисления минимума функции - f(x) и записывается в виде

- f(x)→ min, х X. (2)

Точки минимума и максимума называют точками экстремума, а задачи (1) и (2) называются экстремальными задачами. Вопрос о существовании решений этих задач, как мы занем, базируется на теореме Вейерштрасса:

Пусть X — компакт в евклидовом п-мерном пространстве Rn (т. е. X — замкнутое ограни­ченное множество), a f(x) — непрерывная функция на X. Тогда существует точка глобального минимума f(x) на X

Теорема Вейерштрасса имеет важное следствие: если функция f(x) непрерывна на Rn и f(x)→+∞, то f(x) достигает своего глобального минимума на любом замкнутом подмножестве в Rn.

Мы будем иметь дело с конечномерными задачами, когда допустимое множество X совпадает с Rn, т. е. когда задача (1) является задачей безусловной минимизации функций многих переменных. Дадим ряд определений

Градиентом функции f(x) называется векгор первых частных производных

Антиградиентом функции f(x) называется вектор первых частных производных, взятых со зна­ком минус, т. е — grad f.

Матрицей Гессе функции f(x)называется матрица вторых частных производных

Ниже будем предполагать, что смешанные производные функции f(x) второго порядка непрерывны; следовательно, имеем

а это означает, что матрица Гессе является симметричной.

Функция f(x) называется дифференцируемой в точке х*, если она имеет в этой точке полный дифференциал, т. е. для полного приращения f(x) в точке х* имеет место равенство