Численные методы безусловной оптимизации.

I. Необходимые и достаточные условия экстремума в задачах безусловной оптимизации.

Пусть будет задано множество и функция определенная на этом множестве.

( - линейное, n – мерное пространство)

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

(1)

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

Аналогично определяются точки локального и глобального максимума на множестве х.

Точки локального минимума и максимума функции называют точками экстремума этой функции.

Задача отыскания всех локальных минимумов (max) функции , если множество х совпадает со всем n-мерным пространством, т.е. , называют задачей безусловной оптимизации, а функция - целевой функцией.

Задачи оптимизации:

(2)

(3)

Задача (3) эквивалентна задаче

Теорема 1.

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

Иначе говоря, в точке экстремума градиент функции

Равен нулевому вектору,

т.е.

Точка ч*, удовлетворяющая условию , называется стационарной точкой функции .

Квадратная матрица А называется симметричной, если . симметричная матрица А называется неотрицательно определенна, если для любого скалярное произведение векторов и ч неопределенно; т.е. ; положительно определенной, если ; неопложительно определенной, если ; отрицательно определенной, если .

Теорема 2. (критерий Сильвестра).

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

и т.д.,

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

Матрица вторых производных функции .

Называется матрицей Гессе функции .

Теорема 3.

Если точка х* - локальное решение задачи минимизации, и в этой точке имеет непрерывные частные производные до второго порядка включительно, то матрица Гесса функции в точке х* является неорицательно определенной, т.е.

Теорема 4. (о достоверных условиях локального экстремума).

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

Если точка х* является стационарной и матрица Гессе в ней отрицательно определена, то х* - строгое локальное решение задачи максимизации функции .

Для одномерной оптимизации

- условие стационарности .

- условие минимума .

(максимума) .

Пример. Решить задачу.

Решение. Находим стационарные точки :

Система имеет два решения:

Матрица Гессе:

Матрица не является неотрицательно определенной.

Матрица - положительно определена.

В.т. - минимум функции.

II. Выпуклые множества и выпуклые функции

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

Условия выпуклости:

(4)

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

Справедливо неравенство

(5)

Если неравенство (S) – строгое, то функция строго выпуклая.

Теорема 5.

Если функция выпукла на множество Х и Х*.

Является стационарной точкой функции , т.е. , то х* - строгое локальное решение задачи.

(6)

Теорема 6.

Если функция и множество х выпуклы, то любое локальное решение задачи (6) является также глобальным решением на множество х.

Теорема 7. (достаточные условия выпуклости функции).

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

Пример.

Показать, что стационарная точка функции