Замкнутое и одновременно ограниченное множество в метрическом пространстве (в пространстве Rn с заданным на нем понятием расстояния) называется компактным. Компактное множество называется выпуклым, если для любых , 0 ≤ a ≤ 1. То есть выпуклое множество В кроме всех своих точек содержит и все их выпуклые комбинации. Это означает, что вместе с допустимыми x1 и x2 допустимы и их смеси. Гладкой называется функция, которая в области своего определения имеет производные, то есть является дифференцируемой.
Функция f дважды дифференцируема, если для всех i,j=1,…,n существуют частные производные от частных производных, то есть
Симметричная относительно диагонали nxn- матрица называется матрицей Гессе. Задача нахождения максимального или минимального значения заданной функции на заданном множестве называется экстремальной. Имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:
(2.1)
Оптимальным решением задач (2.1) называется пара (x*,f (x*)), где x* - точка максимума (минимума), а f(x*)- значение функции f в этой точке, то есть ее максимальное (минимальное) значение на множестве Х.
Решение задачи (2.1) требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности (то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных решений. В задачах (2.1) применяются экстремальные точки двух видов: локальный максимум (минимум) и глобальный максимум (минимум). Точка называется точкой локального максимума (минимума), если
f(x0) ≥ f(x) (f(x0) ≤f(x)) для всех , где - ε-окрестность точки x0. Точка называется точкой глобального максимума (минимума), если эти неравенства выполняются для всех . Достаточное условие существования оптимальных решений задач (2.1) содержится в следующем утверждении.
Теорема (Вейерштрасса). Для того, чтобы в задаче (2.1) существовала точка глобального максимума (минимума), достаточно, чтобы допустимое множество X было компактно в Rn, а целевая функция f непрерывна на X. Ввиду сложности проверки ограниченности множества X, применяется следствие из этой теоремы.
Следствие (теоремы Вейерштрасса). Если функция f непрерывна на Rn и
то f достигает своего глобального минимума в любом замкнутом подмножестве X пространства Rn.
Признаки оптимальности приведем в случае, когда в (2.1)X
. В этом случае задачи (2.1) принимают вид:
(2.2)
и называются задачами безусловной оптимизации.
Чтобы точка была точкой локального экстремума в задачах (2.2) необходимо, чтобы
(2.3)
Все точки x0, удовлетворяющие условию (2.3) , называются стационарными точками (точки подозрительные на экстремум).
Чтобы x0 была точкой локального максимума (минимума) в задаче (2.2) необходимо и достаточно, чтобы
и (2.4)
для всех . Здесь матрица Гессе функции f в точке x0 , а - скалярное произведение.
Известно, что дважды дифференцируемая на выпуклом множестве Х функция f вогнута (выпукла) тогда и только тогда, когда для любых векторов и справедливо условие (2.4) . Матрица будет отрицательно (положительно) полуопределенной в точке x0 , если
(2.5)
для всех k =1,…,n. Здесь символом обозначен минор k-го порядка матрицы :
где - определитель порядка k * k, вычисляемый в точке x0 .
Если в (2.5) неравенства строгие, то получаем необходимое и достаточное условие отрицательной (положительной) определенности матрицы Гессе в точке x0 . Условие (2.5) называется критерием Сильвестра для знакоопределенных матриц.
Поскольку условия (2.4) труднопроверяемы, то при проверке необходимых условий оптимальности в задачах (2.2) применяют критерий Сильвестра.
Следовательно, при помощи условий (2.3) - (2.5) можно предложить следующий алгоритм решения задач (2.2) :
вычислить все стационарные точки (найти все решения уравнения (2.3) );
выяснить характер экстремума стационарных точек (с использованием условий (2.4) - (2.5) ), для чего применить критерий Сильвестра;
среди всех точек локального максимума (минимума) найти точки глобального максимума (минимума), сравнивая значение функции f в этих точках.
Пример решения
Определить максимальное значение функции двух переменных и оптимальные значения переменных
f(x,y) = x3 + y2 – 6xy - 39x + 18y +100
Берём производные по переменным, приравниваем их значения нулю и решаем систему