Приближенные методы оптимизации

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

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

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

Рисунок 5.10 – Метод спуска

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

Свое название методы спуска получили благодаря тому, что в большинстве учебников по оптимизации рассматриваются задачи на минимум (соответственно, поиск экстремума будет представлять собой не «подъем», как на рисунке 5.10, а «спуск»).

В зависимости от того, какая информация используется в алгоритме методов спуска, их подразделяют на:

1) методы нулевого порядка - используют только информацию о значениях самих функций;

2) методы первого порядка - используют, кроме того, информацию о значениях первых производных;

3) методы второго порядка - используют информацию о вторых производных.

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