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

↑

▷ Содержание

⇐ ПредыдущаяСтр 17 из 17

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

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

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

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

                                                       (1)

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

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

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

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

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

                                (2)

                                (3)

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

Теорема 1.

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

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

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

т.е.

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

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

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

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

     и т.д.,

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

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

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

Теорема 3.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     (4)

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

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

                              (5)

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

Теорема 5.

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

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

                                              (6)

Теорема 6.

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

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

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

Пример.

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

Является глобальным решением задачи  .

Решение.

Находим стационарную точку функции :

Точка  - решение системы.

Находим матрицу Гессе .

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

Точка х* - решение глобальной задачи минимизации.

Литература

1. Б.П. Демидович, И.А. Марон. «Основы вычислительной математики»

М.: Наука, 1970, 664 с.

2. Н.В.Копченова, И.А. Марон

«Вычислительная математика в примерах и задачах».

М.: Наука, 1972, 367 с.

И.С. Березин, Н.П. Жидков. «Методы вычислений», т 1,т 2. М.: 1962

4. Р.В. Хемминг. «Численные методы для научных работников и инженеров» М.: Мир,, 1977

5. Б.П. Демидович, И.А. Марон, Э.З. Шувалова

«Численные методы анализа». М.: Наука 1967, 368 с.

6. В.И. Ракитин, В.Е. Первушин. «Практическое руководство по методам вычислений». М.: Высшая школа, 1998, 383 с.

7. М.Малькольм, К. Фоулер «Машинные методы математических вычислений». М.: Мир, 1980, 279 с.

8. С.В. Михайленко. «Численные методы (учебное пособие)». Харьков, из-во ХАИ, 1978, 126 с.

9. С.В. Михайленко. «Численные методы (учебное пособие по лабораторному практикуму)». Харьков, из-во ХАИ, 1978, 92 с.

10. Н.С. Бахвалов. «Численные методы». М.: СПб - 2000, 622 с.

11. Н.С. Бахвалов. «Численные методы в задачах и упражнениях». М.: Высшая школа - 2000, 622 с.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США