Основные понятия.

1. X- множество вариантов или допустимое множество.

2. f : XR₁­ - целевая функция.

3. Точка x*X называется точкой локального минимума, если >0: xX такого что ||x-x*||< верно f(x)  f(x*). Если f(x)  f(x*) при всех xX, то x* называется точкой глобального минимума на X.

Надо найти минимум функции f на множестве X.

Содержание курса состоит в изучении методов поисках экстремумов.

Будем искать min f(x), xX , так как max f(x)= - min(-f(x)), xX и поэтому поиск максимумов f(x) сводится к поиску минимумов f(-x).

Множество X бывает:

1. Конечным (конечное множество элементов, например графы).

2. Конечномерным (когда оно является подмножеством множества евклидова пространства).

3. Бесконечномерным (обладает бесконечным набором линейно-независимых элементов. Пример: множество непрерывных функций на отрезке).

Соответствие методов и множеств.

1. Методы решения переборных задач (метод ветвей и границ, динамическое программирование и др.)

2. Методы решения задач математического программирования (условная/безусловная минимизация, нелинейное, выпуклое и линейное программирование).

3. Методы вариационного исчисления и методы оптимального управления (уравнение Эйлера-Лагранжа, принцип максимума).

1. Безусловная оптимизация (многомерные функции)

Требуется найти min f(x), на всём X = R­ⁿ, то есть минимизация на всем пространстве.

Определение: Минимизация функции на множестве, заданном неравенствами, равенствами и другими ограничениями называется условной.

Пусть:

1. X = Rⁿ (евклидово n-мерное пространство);

2. Функция f дифференцируема хотя бы один раз, тогда в точке минимума выполняется равенство:

f(x)=0, где (вектор частных производных по каждому аргументу)

В большинстве случаев это приводит к решению системы нелинейных уравнений, что само по себе проблема. Существуют релаксационные методы, в основе которых лежит построение последовательности {x_i}, x_iX со следующими свойствами:

1. f(x₀)>f(x₁)>...;

2. x_ix* = argmin{ f(x), xX}.

Рассмотрим методы нахождения локального минимума (т.е. корня уравнения f(x) =0). Все рассматриваемые методы делятся на несколько групп в зависимости от того, какой максимальный порядок производной функции f используется для вычисления последовательности. Порядок метода равен порядку старшей производной f, вычисляемый пр реализации этого метода. Если производные не используются, то методы нулевого порядка, затем - первого и так далее. Мы будем рассматривать порядок не выше второго.

Общая схема безусловной оптимизации

Основная итерационная формула:

x_k+1 = x_k+ t_kS_k , где S_k -вектор, определяющий направление изменения x_k

t_k - скаляр, определяющий длину шага.

S_k может зависеть от x_k: S_k = (x_k), а может от (x_k ,x_k-1), от (x_k ,x_k-1, x_k-2) и т.д.. В зависимости от этого критерия методы делятся на:

• одношаговые ((x_k));

• многошаговые ((x_k, x_k+1)).

Одношаговые и двухшаговые методы имеют основное распространение.

1.1 Методы первого порядка (градиентные методы)

Для вычисления t и S используются значение функции и первая производная.

Известно, что градиент функции в точке дает направление наибольшего возрастания функции в точке. Направление наибольшего убывания - это направление антиградиента.

Пусть S_k = -f(x_k), t_k > 0 - длина шага.