Методы Оптимизации Систем Автоматизированного Проектирования

Метод Пауэлла.

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

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

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

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

Имеем

Отсюда получаем

Аналогично получаем

Квадратичная функция q(x) достигает минимума в точке .

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

Стратегия поиска.

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

Стр.: ..., 2, 3, 4