Описание методов оптимизации

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

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

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

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

Выбор метода для минимизации конкретной функции зависит от многих причин. Общая рекомендация состоит в том, что первые итерации строить методами нулевого или первого порядка, а затем в случае необходимости перейти к методам второго порядка. Метод сопряженных градиентов, будучи методом первого порядка, по объему итераций на итераций мало отличается от градиентных методов, но обладает сверхлинейной сходимостью. Следует однако, отметить его большую чувствительность к ошибкам округления. Методы второго порядка накладывают ограничение на функцию, необходимо чтобы она была дважды диффиринцируема и эта производная была положительна. Поэтому для нахождения минимума реализуем метод двумерной оптимизации - покоординатным спуском и сканированием, а одномерной - метод "золотого сечения" и метод сканирования. Покажем как функционируют эти методы.

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

Метод покоординатного спуска заключается в нахождении экстремума поочередно по каждой переменной.

Пусть задана функция двух переменных, линии равного уровня которой изображены на рисунке 6.2.

Рисунок 6.2 - Метод покоординатного спуска

Из некоторой начальной точки Х⁰= (х₁, х₂) производится поиск минимума вдоль направления оси х₁ с получением точки Х⁰. В этой точке касательная к линии равного уровня параллельна оси х₁. Затем из точки Х⁰ производится поиск минимума вдоль направления оси х₂ с получением точки Х¹_.Следующие итерации выполняются аналогично. Для минимизации функции F (x) вдоль осевых направлений может быть использован любой из методов одномерной оптимизации.

Приведем описание метода “золотого сечения”.

Пусть экстремум локализован в интервале [x₁,x₃] (рисунок 6.5).

Алгоритм поиска экстремума складывается из следующих этапов:

а) вычисляются и запоминаются значения функции F (x) на концах исходного интервала [x₁,x₄], то есть значения F (x₁) и F (x₄);

б) вычисляются и запоминаются значения функции F (x₂), где

;

в) вычисляются и запоминаются значения функции F (x₃), где

;

г) по найденным значениям F (x₁), F (x₂), F (x₃) и F (x₄) определяется интервал, в котором локализован экстремум, состоящий из двух интервалов l₁ и l₂ неравной длины.

д) внутри большого интервала l₂ находится точка, отстоящая от конца общего интервала l₁+l₂ на расстоянии.

;

е) в этой точке рассчитывается значение функции F (x), после чего снова выбирается сокращенный подинтервал в интервале l₁+l₂, локализующий экстремум, то есть вычисления повторяются, начиная с пункта.

г) до тех пор, пока не будет получена заданная точность нахождения положения экстремума.