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

Предварительно напомним, что латинское слово extremum означает "крайнее". Оно в математике имеет два конкретных значения: maximum (сокращенно max) - наибольшее и minimum (сокращенно min) - наименьшее. В таком понимании extremum имеет более узкий смысл, чем optimum, переводимый от латинского как "наилучшее".

Пусть дана функция , где . Говорят, что в точке достигается максимальное (минимальное) значение функции f , если выполнено неравенство для всех . Этот факт записывается следующим образом:

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

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

Как видим, имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:

(1)

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

Решить задачу (1) это значит: либо найти оптимальное решение; либо убедиться, что оптимальное решение не существует.

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

В экономической практике встречаются случаи, когда поставленная цель не может быть достигнута ввиду тех или иных объективных причин. Подобно этому, оптимальные решения экстремальных задач существуют не всегда.

Сформулируем условия, при которых такие решения существуют.

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

Достаточное условие существования оптимальных решений задач (1) содержится в следующем утверждении.

Теорема (Вейерштрасса). Для того, чтобы в задаче (1) существовала точка глобального максимума (минимума), достаточно, чтобы допустимое множество X было компактно в Rⁿ, а целевая функция f непрерывна на X.

Ввиду сложности проверки ограниченности множества X, на практике часто применяется следствие из этой теоремы.

Следствие (теоремы Вейерштрасса). Если функция f непрерывна на Rⁿ и

то f достигает своего глобального минимума в любом замкнутом подмножестве X пространства Rⁿ.

Необходимые и достаточные признаки оптимальности играют важную роль в решении экстремальных задач.

Необходимые признаки всегда "сопровождают" оптимальное решение, поэтому с их помощью можно вычислить точки, подозрительные на экстремум.

Достаточные признаки всегда сопровождаются решением, т.е. другими словами гарантируют решение, однако, при этом можно "потерять" решение.

Поэтому достаточные признаки можно использовать для нахождения оптимального решения из совокупности допустимых точек, удовлетворяющих необходимым признакам.

Признаки оптимальности приведем в случае, когда в т.е. будем рассматривать задачи безусловной оптимизации.

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

(2)

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

Пример 1.

Нет экстремума.

Пример 2.

Условия 1-го порядка

Система несовместна, т.е. стационарных точек нет вообще.

Условия (2) выполняется как для точки максимума, так и для точки минимума. Поэтому для выяснения характера экстремума стационарных точек применяют к ним более сложные необходимые признаки оптимальности 2-го порядка.

Пусть в (1) функция дважды дифференцируема в точке x⁰ . Для того, чтобы x⁰ была точкой локального максимума (минимума) необходимо, чтобы

(3)

и достаточно, чтобы

(4)

Условие (3) и (4) связаны с вогнутостью и выпуклостью функции f. Известно, что дважды дифференцируемая на выпуклом множестве Х функция f вогнута (выпукла) тогда и только тогда, когда для любых векторов справедливо условие (3). В случае же выполнения условия (4) говорят о строгой вогнутости (выпуклости) функции f.

С другой стороны условие (3) является признаком отрицательной (положительной) полуопределенности матрицы Гессе. Напомним, что матрица будет отрицательно (положительно) полуопределенной в точке x⁰ , если

(5)

для всех k=1,…,n. Здесь символом обозначен минор k-го порядка матрицы Гессе:

=

где | · | определитель порядка k, вычисляемый в точке x⁰.

Если в (5) неравенства строгие, то получаем необходимое и достаточное условие отрицательной (положительной) определенности матрицы Гессе в точке x⁰ . Условие (5) называется критерием Сильвестра для знакоопределенных матриц.

Таким образом, можно предложить следующий алгоритм решения задач (1):

1. вычислить все стационарные точки;

2. выяснить характер экстремума стационарных точек (с использованием условий (3) – (4) ), для чего применить критерий Сильвестра;

3. среди всех точек локального максимума (минимума) найти точки глобального максимума (минимума), сравнивая значение функции f в этих точках.

Пример 3.

Для точки x⁰=(0,0) имеем:

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

Для точки x⁰⁰=(1,1) имеем:

Следовательно, матрица положительно определена, для точки x⁰⁰ , т.е. выполнено достаточное условие локального минимума.

Легко установить, что , то есть x⁰⁰⁰=(-1,-1) так же является точкой локального минимума.

Точки x⁰⁰ и x⁰⁰⁰ являются точками глобального минимума - -

т.к

Задачи условной оптимизации

Если множество допустимых решений задается с помощью системы уравнений:

(1)

где g_i называется ограничением. Если среди всех функций f, g_i, имеется хотя бы одна нелинейная функция, то (1) называется задачей нелинейного программирования. Если все эти функции дифференцируемы в Rⁿ , то (1) называется гладкой задачей нелинейного программирования.

Пример 1. при условии .

Выражая x₂=1-x₁ и подставляя в y получим функцию одной переменной, сведя, таким образом, задачу условной оптимизации к задаче безусловной оптимизации которую мы с вами уже умеем решать:

Однако, такой способ не может быть использован в качестве универсального, т.к. очень редко можно исключить одну из переменных.

Будем считать, что задача (1) гладкая и составим для нее так называемую функцию Лагранжа, зависящую от n+k переменных ):

где - вектор множителей Лагранжа, причем все множители Лагранжа одновременно не могут быть равны нулю.

Теперь можно составить следующий алгоритм решения задачи (1) , который называется методом множителей Лагранжа:

1. составить функцию Лагранжа;
2. выписать все необходимые условия;
3. вычислить все стационарные точки;
4. определить характер экстремума стационарных точек.

Сделаем несколько замечаний. Оптимальному решению задачи (1) соответствует (единственная) совокупность множителей Лагранжа. Поэтому для вычисления стационарных точек x^* требуется предварительно найти значения всех множителей Лагранжа. Таким образом, имеется всего n+k неизвестных .

Для определения характера экстремума (п.4 алгоритма) применяют те или иные достаточные условия. В связи с этим заметим, что введение функции Лагранжа, по существу, сводит задачу условной оптимизации к задаче безусловной оптимизации этой функции. Поэтому необходимые условия II порядка и достаточные условия для функции Лагранжа являются обобщениями соотношений для задач безусловной оптимизации.

Пример 2. ;

Решение.

Из первых двух уравнений найдем: x₁=x₂, x₃=2λ₁ .Подставляя результат в последнее уравнение найдем: -2x₁+1=x₃. Используя это в четвертом уравнении получим результат.

Задача 1. Найти параметры цистерны, которая при заданной площади поверхности S₀ имеет максимальный объем.

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

Задача 3. Фирма-монополист производит два вида товаров в количествах Q₁ и Q₂ соответственно. Функция затрат имеет вид: , а кривые спроса для каждого товара: - цены за единицу.

Фирма имеет квоту на эти товары: . Найти максимальную прибыль.

Построим целевую функцию: где П – прибыль, R –доход.

Доход от продаж 1-го товара: второго: и .

Сформулируем задачу.