4. Теорема существования решения оптимизационной задачи.

Существование решения поставленной задачи вытекает из следующей теоремы.

Теорема 1 (теорема Вейерштрасса) Пусть D — компакт в Rn (т.е. замкнутое ограниченное множество), функция f0(x) непрерывна на D. Тогда точка глобального минимума и точка глобального максимума функции f0 на D существуют. Доказательство теоремы 1 можно найти, например, в [8]. Иногда бывает полезной и другая форма данной теоремы.

Теорема 2 Пусть D — замкнутое множество в Rn , f0(x) — непрерывная функция на D. Если для некоторой точки a ∈ Rn множество N (a) = {x ∈ D |f0(x) ≤ f0(a)} ограничено, то у функции f0 на D существует точка глобального минимума. Доказательство. Так как множество D замкнуто, а функция f0 непрерывна, то множество N (a) замкнуто, и кроме того оно ограничено, а следовательно, является компактом. Очевидно, что inf D f0(x) = inf N(a) f0(x) Из теоремы Вейерштрасса следует, что на множестве N (a) существует точка глобального минимума, следовательно, она же будет являться точкой глобального минимума на D. Теорема доказана.

5. Необходимые условия экстремума первого и второго порядков (гладкие функции одной переменной).

Необходимые условия экстремума первого порядка. Пусть X^*  R^* есть точка локального минимума (максимума) функции f (x ) на множестве Rⁿ и f (x) дифференцируема в точке x . Тогда все частные производные функции f (x ) первого порядка в точке x равны нулю, т.е.

Точки x , удовлетворяющие необходимому условию, называются стационарными

5.2 Первый способ проверки достаточных и необходимых условий второго порядка.

Критерий проверки достаточных условий экстремума (критерий Сильвестра). Если знаки угловых миноров строго положительны: 1  0 , 2  0 ,..., n 0 , то точка x является точкой локального минимума. Если знаки угловых миноров чередуются, начиная с отрицательного: , 1  0 2  0 , 3  0,..., -1 ⁿ _n  0, то точка x является точкой локального максимума

5.2.2Критерий проверки необходимых условий экстремума второго порядка

1. Для того чтобы матрица Гессе H x( )  была положительно полуопределенной ( ()0 H x и точка   ) x может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры определителя матрицы Гессе были неотрицательны. 2. Для того чтобы матрица Гессе H x( )  была отрицательно полуопределенной ( ()0 H x и точка   ) x может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны, а все главные миноры нечетного порядка – неположительны. Второй способ проверки достаточных и необходимых условий второго порядка (с помощью собственных значений матрицы Гессе).

6.Достаточные условия экстремума (гладкие функции одной переменной).

Теорема (достаточное условие экстремума).

Пусть функция у = f(x) дифференцируема в некоторой окрестности точки х₀. если в точке х = х₀ производная функции f(x) равна нулю и меняет знак при переходе через точку х₀, то точка х₀ является точкой экстремума, причём: 1) х₀ ─ точка максимума, если знак меняется с плюса на минус; 2) х₀ ─ точка минимума, если знак меняется с минуса на плюс.

7. Необходимые условия экстремума первого порядка (гладкие функции многих переменных).

8. Матрица вторых производных. Необходимые условия экстремума второго порядка (гладкие функции многих переменных).

Матрица составленная из вторых производных функции,называется матрица Гессе

9. Матрица вторых производных. Достаточные условия экстремума (гладкие функции многих переменных).

Матрица составленная из вторых производных функции,называется матрица Гессе

10. Одномерная безусловная оптимизация. Унимодальная функция. Лемма о свойстве унимодальных функций.

11. Пассивные методы поиска экстремума.

12. Метод перебора.

13. Алгоритм оптимального пассивного поиска.

14. Теорема об оптимальности пассивного поиска

15. Последовательные методы поиска экстремума.

16. Поразрядный поиск.

17. Метод дитохомии

18. Метод деления отрезка пополам.

деления отрезка пополам (метод дихотомии и метод золотого сечения).

19. Метод золотого сечения

Для того чтобы уменьшить отрезок неопределённости [a,b], нам необходимо вычислить значение целевой функции f(x), по крайней мере, в двух точках на отрезке [a,b].

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [a,x₂] или [x₁,b]. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки x₁ и x₂ должны быть симметричны относительно середины отрезка [a,b]. В этом случае длины отрезков [a,x₂] и [x₁,b] будут равны. Таким образом, остаётся вопрос как выбрать точку x₁.

В методе золотого сечения точка x₁ выбирается из соображения, что должно выполняться соотношение:

т.е. точка x₁ делит отрезок [a,b] по правилу «золотого сечения», где л - есть «золотое отношение». Точка x₂ определяется как точка симметричная к x₁ относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости [a,x₂], содержащий точку x₁, или отрезок неопределённости [x₁б], содержащий точку x₂. Оказывается, что остающаяся точка на суженном отрезке неопределённости делит его вновь по правилу «золотого сечения». Следовательно, чтобы, в свою очередь, уменьшить новый отрезок неопределённости, нам не достаёт одного эксперимента, а именно,

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

а)

б)

где буквы со штрихами обозначают новый отрезок неопределённости. Вариант а) соответствует случаю, если новым отрезком неопределённости будет [a,x₂], а вариант б) - отрезку [x₁,b].

В приводимой ниже схеме алгоритма остающиеся отрезки неопределённости переименовываются каждый раз как [a,b], а точки, в которых проводятся эксперименты на этом отрезке, обозначается через x₁ и x₂, причём . Кроме того, y₁ и y₂ имеют следующие значения: y₁ =f(x₁) и y₂ =f(x₂).