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

Возможны два подхода к решению задачи отыскания минимума функции многих переменных f(x)=f(x₁,х₂,х₃,…хn) при отсутствии ограничений на диапазон изменения неизвестных.

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

(∂f/∂x_i)_x=x*= 0, i=1,...,n

Вектор f′(x), составленный из первых производных функций по каждой переменной, т.е. f′(x) = (∂f/∂x₁, ∂f/∂x_2,…, ∂f/∂x_n)^т называют градиентом скалярной функции f(x). В точке минимума градиент равен нулю. Решение системы нелинейных уравнений – задача весьма сложная и трудоемкая, поэтому на практике используют второй подход к минимизации функций, составляющих основу прямых методов.

Суть их состоит в построении последовательности векторов х[0], х[1],…, х[n], таких, что f(х[0])>f(х[1])>…>f(х[n]), > …. В качестве начальной точки х[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка х[0] располагалась как можно ближе к точке минимума.

Переход (итерация) от точки х[k], к точке х[k+1], k=0,1,…n состоит из двух этапов:

1) выбор направления движения из точки х[k],

2) определение шага вдоль этого направления.

Методы построения таких последовательностей часто называют методами спуска (т.к. происходит переход от больших значений функции к меньшим). Впервые такая задача была рассмотрена О.Коши в 1845г.

Математически методы спуска описываются соотношением

х [k+1] = х [k] + а_кр[k], k=0,1,… (9.1)

где р[k] – вектор, определяющий направление спуска,

а_к – длина шага.

В координатной форме:

х₁[k+1] = х₁ [k] + а_к р₁ [k],

х₂[k+1] = х₂ [k] + а_к р₂ [k],

…………………………….

х_n[k+1] = х_n [k] + а_к р_n [k].

Различные методы спуска отличаются друг от друга способами выбора двух параметров – направления спуска и длины шага вдоль этого направления. На практике применяются только методы, обладающие сходимостью, число итераций k →∞.

На практике вычисления прекращаются при выполнении некоторых критериев (условий) например: ||х[k] – х[k-1]|| ≤ ε – условие малости приращения аргумента, или - функции ||f(х[k]) – f(х[k-1])|| ≤ γ.

Методы поиска минимума называются детерминированными, если оба элемента перехода от х [k] к х [k+1] (направление движения и величина шага) выбираются однозначно, по доступной в х[k] информации. Если же при переходе используется случайный механизм, то алгоритм называется случайным поиском минимума.

Детерминированные алгоритмы безусловной минимизации делятся на классы в зависимости от вида используемой информации. Если на каждой итерации используется лишь значение минимизируемой функции f′(x), то метод называется методом нулевого порядка. Если требуется вычисления первых производных минимизируемой функции, то - методы первого порядка, вторых – второго порядка.

В настоящее время разработано множество методов для задач условной и безусловной оптимизации. Качество численного метода характеризуется:

- скоростью сходимости;

- временем выполнения одной итерации;

- объемом памяти РС;

- классом решаемой задачи.