Задача математического программирования

(1)

- допустимое множество задачи математического программирования,

.

- функция Лагранжа задачи (1), где .

- градиент функции Лагранжа по координатам вектора , то есть вектор, составленный из частных производных функции Лагранжа по координатам вектора :

.

- матрица вторых частных производных функции Лагранжа по координатам вектора .

Сформулируем известный из курса математического анализа результат о существовании решения задачи (1):

Теорема 1 (Теорема Вейерштрасса)

Пусть - компакт (ограниченное и замкнутое множество) в , - непрерывная функция на . Тогда точка глобального минимума функции на (глобальное решение задачи (1)) существует.

1. Пусть - замкнутое множество на , - непрерывная функция на , причём при некотором множество ограничено. Доказать, что тогда точка глобального минимума функции на существует.

2. Известно, что функция непрерывна на и удовлетворяет следующему условию: для любой последовательности такой, что , . Доказать, что тогда функция достигает своего минимального значения на любом замкнутом множестве из .

3. Пусть непрерывная функция имеет точку глобального минимума на . Следует ли отсюда, что функция имеет точку глобального минимума на любом замкнутом множестве из ?

4. Пусть - точка строгого локального минимума функции на (). Можно ли утверждать, что убывает в некоторой левой полуокрестности точки и возрастает в некоторой правой полуокрестности ?

5. Убедиться, что функция достигает локального минимума в точке = (0,0) вдоль каждой прямой, проходящей через , но не является точкой локального минимума этой функции.

Задача математического программирования (1) называется задачей безусловной оптимизации, если , то есть

(2)

Теорема 2 (Необходимое условие локальной оптимальности первого порядка)

Пусть функция дифференцируема в точке . Если - локальное решение задачи (2), то

. (3)

Теорема 3 (Необходимое условие локальной оптимальности второго порядка)

Пусть функция дважды дифференцируема в точке . Если - локальное решение задачи (2), то матрица - неотрицательно определена, то есть

при всех . (4)

Теорема 4 (Достаточное условие локальной оптимальности)

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

при всех , . (5)

Тогда - строгое локальное решение задачи (2).

Теорема 5 (Критерий Сильвестра)

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

Пример 1.

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

.

Решение:

1. Выпишем необходимое условие локальной оптимальности первого порядка:

Решениями этой системы являются точки = (0,0),

1. Рассмотрим гессиан функции в точках и :

, .

Матрица по критерию Сильвестра не является неотрицательно определённой, то есть необходимое условие локальной оптимальности второго порядка не выполняется. Отсюда следует, что точка = (0,0) не может быть решением задачи.

Матрица положительно определена. Следовательно, выполняется достаточное условие локальной оптимальности. Точка – строгое локальное решение задачи.

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

6. Глобальные максимум и минимум достигаются в бесконечном числе точек.

7. Функция ограничена, глобальный максимум достигается, а глобальный минимум не достигается.

8. Функция ограничена, но глобальные минимум и максимум не достигаются.

9. Функция ограничена, имеет локальные минимумы и максимумы, но глобальные максимум и минимум не достигается.

10. Имеется единственный локальный экстремум, не являющийся глобальным.

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

12. Найти все точки локального минимума и локального максимума функции на .

Найти локальные решения в задачах 13-16.

13. .

14.

15.

16.

17. Найти наименьшее значение функции , где ; - заданные числа.

18. Показать, что в методе наискорейшего спуска направления и - ортогональны.

Напомним, что метод наискорейшего спуска предназначен для отыскания локального минимума функции и задаётся расчётной формулой для заданной точки и , которые выбираются из условия минимизации функции вдоль направления антиградиента для каждого .

Задача математического программирования (1) называется классической задачей на условный экстремум, если , то есть

(6)

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

Теорема 6 (Необходимое условие локальной оптимальности первого порядка)

Пусть функции непрерывно дифференцируемы в некоторой окрестности точки . Если - локальное решение задачи (6), то существует число и вектор не равные нулю одновременно и такие, что

. (7)

Если градиенты линейно независимы, то .

Условие линейной независимости градиентов ограничений в точке называется условием регулярности. Числа называются множителями Лагранжа. Функция Лагранжа, для которой , называется регулярной.