Постановка задач минимизации

Классификация задач и методов

Постановка задачи поиска безусловного экстремума Дана дважды непрерывно дифференцируемая функция f (x), определенная на множестве .

Требуется исследовать функцию f (x) на экстремум, т. е. определить точки ее локальных минимумов и максимумов на :

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

Постановка задачи поиска условного экстремума.

Общая постановка задачи и основные положения изложены в случае поиска безусловного экстремума. Здесь мы рассмотрим случаи, когда множество допустимых решений Х задается равенствами и неравенствами, т. е.

.

где, m и p-числа; f (x) — целевая функция,.

j=1,., p — функции, задающие ограничения (условия).

Будем считать функции f (x),, j=1,., р дважды непрерывно дифференцируемые на множестве .

Экстремальные задачи являются крупным разделом теории оптимизации управления и встречаются в различных дисциплинах курса математики. Существуют различные методы аналитического решения таких задач, но применение необходимых и достаточных условий безусловного экстремума эффективно для решения ограниченного числа задач. Для решения большинства практических задач они не могут быть рекомендованы по следующим причинам.

1. Целевая функция (x) может не иметь непрерывных производных до второго порядка включительно.

• 2. Использование необходимого условия первого порядка связано с решением системы n в общем случае нелинейных алгебраических уравнений, что представляет собой самостоятельную задачу, трудоемкость решения которой сравнима с трудоемкостью численного решения поставленной задачи поиска экстремума.
• 3. Возможны случаи, когда о целевой функции известно лишь то, что ее значение может быть вычислено с нужной точностью, а сама функция задана неявно.

Подавляющее большинство численных методов оптимизации относится к классу итерационных, т. е. порождающих последовательность точек в соответствии с предписанным набором правил, включающим критерии окончания. При заданной начальной точке x0 методы генерируют последовательность x0, x1, x2. Преобразование точки xk в xk+1 представляет собой итерацию.

Для определенности рассмотрим задачу поиска безусловного локального минимума:

(1.1).

Численное решение задачи (1.1), как правило, связано с построением последовательности xk точек, обладающих свойством.

(xk+1) < (xk), k = 0,1,… (1.2).

Общее правило построения последовательности xk имеет вид.

xk+1 = xk + tk dk, k = 0, 1,… (1.3).

где точка x0- начальная точка поиска; dkприемлемое направление перехода из точки xk в точку xk+1, обеспечивающее выполнение условия (1.2) и называемое направлением спуска; tk — величина шага.

Начальная точка поиска x0 задается, исходя из физического содержания решаемой задачи и наличия априорной информации о положении точек экстремума.

Приемлемое направление спуска dk должно удовлетворять условию.

k = 0,1, (1.4).

обеспечивающему убывание функции (x).Примером приемлемого направления является направление вектора антиградиента: dk =.

Величина шага tk > 0 выбирается либо из условия (1.2), либо из условия минимума функции вдоль направления спуска:

(1.5).

Выбор шага tk из условия (1.5) делает спуск в направлении dkнаискорейшим.

В зависимости от наивысшего порядка частных производных функции f (x), используемых для формирования dk и tk, численные методы решения задачи безусловной минимизации (1.1) принято делить на три группы.

• 1. Методы нулевого порядка, использующие только информацию о знании функции (x).
• 2. Методы первого порядка, использующие информацию о первых производных функции (x).
• 3. Методы второго порядка, требующие для своей реализации знания вторых производных функции (x).