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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<h2>Квадратичная интерполяция (Метод Пауэлла)</h2><br>

Введите функцию с одной переменной f(x)=

После нажатия на кнопку «Далее» происходит загрузка второй страницы kvadr_interpol_rez.php и с помощью метода post передаются значения переменных function1 (функция), x1 (начальная точка), step (шаг) и toch (точность). Стоит заметить, что в функции, введенной пользователем, в качестве переменной обязательно выступает буква х и она может иметь в своем составе экспоненту и натуральный логарифм.

Далее подробно и по частям рассмотрим код второй основной страницы, в которой реализован сам метод.

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

$str=$_POST['function1']; //получили функцию пользователя в виде строки

//если встречается в функции exp(), т.е. эспонента

$s1 = strpos($str, "exp"); //позиция с которой начинается exp

$s2 = strpos($str, ")", $s1); //номер элемента, где кончается exp

$expon=substr($str, $s1, $s2+1); //вырезаем выражение экспоненты

$s1 = substr($expon, $s1, $s2); //вырезает выражение под экспонентой

$s1 = str_replace("x",$arg,$s1);//заменяем все x на аргумент в функции

//подсчитаем выражение под знаком exp

$rezexp=exp($vexp);//вычисляем непосредственно экспоненту

//замена выражения exp() в строке $str на посчитанное число

//если встречается в функции пользователя ln(), т.е. натуральный логарифм

$l1 = strpos($str, "ln"); // позиция, с которой начинается ln()

$l2 = strpos($str, ")", $l1); // конец выражения ln()

$lnln=substr($str, $l1, $l2+1); // все выражение логарифма

$l1 = substr($lnln, $l1, $l2); //вырезает выражение под логарифмом

$l1 = str_replace("x",$arg,$l1); //заменяем все x на переданный аргумент

//подсчитаем выражение под знаком логарифма

$rezln=log($vln); //вычисляем непосредственно натуральный логарифм

$str = str_replace($lnln,$rezln,$str);//замена ln() на посчитанное число

//замена х на переданное число

Функция func1() преобразует функцию пользователя, которая введена в виде строки, в настоящую функцию, в которую можно подставлять любые значения и получать результат.

Для удобства вставим в код php-функцию подсчета полинома по формуле (8):

Теперь начнем описание основной части алгоритма. Рассмотрим первый кусок кода:

// получаем значения начальных данных

$x2=$x1+$step; // вычисляем х2

$f1 = func1($x1); // вычисляем f(x1)

$f2 = func1($x2); // вычисляем f(x2)

$fmin=min($f1,min($f2,$f3)); // находим минимальное среди f(x1), f(x2), f(x3)

//вычислим знаменатель полинома и проверим его на 0

//если знаменатель 0, то х1=Xmin и заново пересчитываем

$x1 = $xmin; $x2=$x1+$step; $f1 = func1($x1); $f2 = func1($x2);

$sr=polinom($x1,$x2,$x3,$f1,$f2,$f3); //вычислим значение по формуле (8)

$l=0; //счетчик циклов

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

Рассмотрим второй кусок кода, который проверяет условия на точность вычисления и выводит окончательный ответ:

while ((($fmin-$fsr) > $toch) || (($fmin-$fsr) < -$toch))

// пока не достигнута заданная точность

$l=$l+1; // счетчик итераций

// ПЕРВЫЙ СЛУЧАЙ, если (где )

// выбор наилучшей точки и двух точек по бокам

if ($xmin < $sr) // если лучшей точкой является Xmin

// сортируем массив методом пузырька по возрастанию

for ($j = 0; $j < count($massiv)-2; $j++)

📎📎📎📎📎📎📎📎📎📎