Green-sell.info

Новые технологии
16 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод пауэлла оптимизация

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

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

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

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

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

Имеем

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

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

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

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

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

Стр.: . 2, 3, 4

Методы одномерной оптимизации:

Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php

Дата публикации: 03.04.2014 2014-04-03

Статья просмотрена: 4993 раза

Библиографическое описание:

Зарипова А. А. Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php // Молодой ученый. — 2014. — №4. — С. 13-20. — URL https://moluch.ru/archive/63/10106/ (дата обращения: 03.04.2020).

Читать еще:  Обновление андроид оптимизация приложений что это

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

Ключевые слова: одномерная оптимизация, квадратичная интерполяция, метод Пауэлла, квадратичная аппроксимация.

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

Задача одномерной оптимизации в общем случае заключается в поиске экстремума функции одной переменной либо в какой-то определенной окрестности, либо на всей оси абсцисс.

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

Если известны значения функции f(x) в трех различных точках , и , равные соответственно , и , то функция f(x) может быть аппроксимирована квадратичным полиномом g(x):

(1)

где A, B и C определяются из уравнений, найденных постановкой , и в функцию f(x),

(2)

(3)

(4)

После решения системы, состоящей из уравнений (2), (3) и (4), получаем

(5)

(6)

(7)

Очевидно, что функция g(x) будет иметь минимум в точке , если A>0. Значит, можно аппроксимировать точку минимума функции f(x) значением

(8)

Опишем краткий алгоритм метода Пауэлла:

1. Необходимо задать начальную точку , от которой будет начинаться поиск минимума, величину шага h и точность расчетов ε.

2.

3. Вычислить и и сравнить их между собой для вычисления третьей точки .

— Если > , то ;

— Если > , то .

4. Вычислить и выбрать минимальное значение из , и . Обозначить , которое находится из.

5. По формуле (8) вычислить и . Если знаменатель по формуле (8) равен нулю, то следует принять и перейти к шагу 2.

6. Проверить условие . Возможны три случая:

— Условие выполнено, алгоритм закончен, окончательный ответ найден;

— Условие не выполнено и , то следует выбрать наилучшую точку ( или ) и две точки по обе стороны от нее;

— Условие не выполнено и , то следует принять, что и перейти на шаг 2.

Опишем один из возможных вариантов реализации метода Пауэлла на языке php с применением html.

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

Читать еще:  Оптимизация андроид при включении

На первой странице для ввода первоначальных данных будет находиться 4 текстовых поля для ввода и кнопка, выполняющая функцию подсчета.

Рис. 1. Вариант расположения элементов на странице для ввода начальных данных

Код страницы для ввода первоначальных данных выглядит следующим образом:

Алгоритм метода Пауэлла

Начальный этап. Выбрать x1 — начальную точку, Dx — величину шага по оси x. Задать точность поиска по х и f(x) e1=0,01 и e2=0,1. Перейти к основному этапу.

Шаг 5. По трем точкам x1, x2, x3 вычислить используя формулу для оценивания с помощью квадратичной аппроксимации.

Шаг 6. Проверка на окончание поиска:

— является ли разность Xминдостаточно малой(/Xмин/

— является ли разность Fминf( ) достаточно малой (/Fминf( )/ 2 + 2x-1 методом Паулла. Выбираем начальную точку x1=0 и Dx=1 — величину шага по оси x, а также точность поиска по х и f(x) e1=0,01 и e2=0,1.

Результаты расчета минимума функции f(x) = (3-x) 2 + 2x-1 представлены в таблице 2.8.

Результаты расчета минимума функции f(x) = (3-x) 2 + 2x-1 методом Пауэлла

Из расчетов видно, что экстремум найден за одну итерацию, что говорит о высокой эффективности метода.

МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ

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

2.3.1. Метод Ньютона.

В рамках схемы Ньютона предполагается, что функция f дважды дифференцируема. Работа алгоритма начинается в точках x1, которая представляет начальное приближение и строится по рекурентному соотношению xk+1 = xk — [f’(xk)/(xk)], где присутствуют первая и вторая производные. Однако, в зависимости от выбора начальной точки и вида функции алгоритм может как сходиться к истинной стационарной точке, так и расходиться. Несмотря на этот недостаток метод Ньютона требует наименьшего количества расчетов функции.

Основы теории оптимизации (стр. 72 )

где λ[j] — величина шага итерации по каждому из параметров хi;

si[j] — параметр выбора “направления”, который обычно определяется по итерационной формуле.

Данная формула обеспечивает сходимость исследуемой функции к некоторому решению при j→∞. Величина шага λ[j] на каждой j-й итерации определяется одним из методов оптимизации однопараметрической оптимизации, например методом деления отрезка пополам или методом “золотого сечения” или Фибоначчи.

Читать еще:  Задача безусловной оптимизации

Наискорейший подъем с использованием одномерного поиска

В некоторых методах поиска информация о градиенте используется для ведения одномерного поиска в направлении наискорейшего подъема или спуска, причем используется соотношение

, (6)

где λ- величина шага, значение которого определяются в направлении градиента.

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

Рис. 1. Бимодальная целевая функция

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

Алгоритм наискорейшего спуска

Данный алгоритм основан на использовании итерационной формулы

,

,

причем все производные вычисляются при λі =хі [j];

λ[j] — величина шага, значение которого изменяется (уменьшается или вычисляется) методом половинного деления.

Алгоритм метода наискорейшего спуска:

1. Выбираем начальные значения координат вектора

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

2. Задаем номер итерации k = 1.

3. Вычисляем значение целевой функции в точке с координатами .

4. Вычисляем значение градиента si.

5. Вычисляем норму вектора градиента NG.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector