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

Лекция 4. Нелинейное программирование

Задача нелинейного программирования формулируется в виде:

(1)

(2)

При этом в (1), (2) хотя бы одна из функций , , – нелинейная.

Как известно, при изучении оптимизационных задач важное место занимает вопрос об условиях оптимальности. Это обусловлено тем, что условия оптимальности:

1.Используются при построении и обосновании вычислительных методов решения указанных задач;

2. Позволяет в ряде случаев явно решить оптимизационную задачу.

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

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

Достаточные условия – это условия, из которых следуют, что данная точка является решением задачи.

Взаимосвязь между необходимыми и достаточными условиями геометрически интегрируется в терминах теории множеств на рис. 1.

Рис. 1.

- множество допустимых решений оптимизационной задачи

- множество оптимальных решений

- множество решений, для которых необходимо выполнить условия оптимальности.

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

Некоторые результаты теории необходимых и достаточных условий оптимальности рассмотрим для следующих классов задач:

- безусловной оптимизации (без ограничений);

-оптимизации с ограничениями в виде равенств;

-оптимизации с ограничениями в виде неравенств.

 

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

Постановка задачи:

(3)

В (3) допустимое множество совпадает с евклидовым пространством (т. е. ограничения отсутствуют).

Теорема 1 (Необходимые условия)

Пусть функция непрерывно дифференцируема в точке по переменным .

Если - локальное решение задачи (3) то

(4)

где - градиент функции в точке .

Замечание 1. Данное утверждение справедливо и для точки локального максимума.

Замечание 2. Необходимые условия (4) выполняется так же в точках перегиба и седловых точках.

Поэтому точки, удовлетворяющие условию (4) называются стационарными.

 

 

 

а) точка перегиба б) седловая точка

Рис 2.

Очевидно, что стационарные точки необязательно являются решением задачи (3).

То есть (4) – не является достаточным условием оптимальности.

Достаточные условия того, что стационарная точка является экстремальной, формулируется в виде следующей теоремы:

Теорема 2. Пусть:

1. функция - дважды непрерывно дифференцируема в точке по

2. - стационарная точка.

Для того чтобы была решением задачи (3) достаточно, чтобы матрица Гессе в точке была:

1. положительно определенной (точка - min)

2. отрицательно определенной (точка - max)

Определение. Матрица Гессе (гессиан) – это симметрическая матрица векторных производных:

Определение. Симметрическая матрица называется положительно (отрицательно) определенной, если соответствующая ей квадратичная форма положительно (отрицательно) определенной.

Для установления знакоопределенности квадратичной формы (гессиана) удобно применять критерий Сильвестра.