Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №4 (63) апрель 2014 г.

Дата публикации: 03.04.2014

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

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

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

В работе изложен алгоритм одного из методов одномерной оптимизации, который называется квадратичная интерполяция или метод Пауэлла. Представлен и подробно описан код на языке 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. Вариант расположения элементов на странице для ввода начальных данных

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

<html>

<head>

<title>Метод Пауэлла</title>

<meta http-equiv='Content-type' content='text/html; charset=windows-1251'>

<link rel=stylesheet href='main.css' type='text/css'>

</head>

<body>

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

<form action="kvadr_interpol_rez.php" method="post">

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

<input type="text" size="40" name="function1"><br>

Начальная точка<input type="text" size="5" name="x1">

Шаг<input type="text" size="5" name="step"><br>

Точность<input type="text" size="5" name="toch"><br>

<input type="submit" value="Далее">

</form>

</body>

</html>

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

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

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

function func1($arg)

{

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

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

            if (strpos($str, "exp")!==false)

            {

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

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

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

            $s1 = strpos($expon, "("); //позиция “(“

$s2 = strpos($expon, ")"); //позиция “)“

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

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

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

            $vexp = (float) preg_replace( '/([0-9\(\)\*\-\+\/\.]*)/e', '\\1', $s1 );

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

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

            $str = str_replace($expon,$rezexp,$str);      

}

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

            if (strpos($str, "ln")!==false)

            {

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

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

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

            $l1 = strpos($lnln, "(" );

            $l2 = strpos($lnln, ")" );

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

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

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

            $vln = (float) preg_replace( '/([0-9\(\)\*\-\+\/\.]*)/e', '\\1', $l1 );

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

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

            }

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

            $str = str_replace("x",$arg,$str);

            //результат

            $str = (float) preg_replace( '/([0-9\(\)\*\-\+\/\.]*)/e', '\\1', $str );

    return $str;

}

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

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

function polinom($x,$y,$z,$fx,$fy,$fz)

{

 $rez=0.5*((($y*$y-$z*$z)*$fx+($z*$z-$x*$x)*$fy+($x*$x-$y*$y)*$fz)/(($y-$z)*$fx+($z-$x)*$fy+($x-$y)*$fz));

    return $rez;

}

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

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

$function1=$_POST['function1'];

$x1 = $_POST['x1'];

$step = $_POST['step'];

$toch = $_POST['toch'];

echo "Функция f(x) = ",$function1,"<br>";

echo "начальная точка x1 = ",$x1,"<br>","шаг ",$step,"<br>";

echo "1 итерация","<br>";

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

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

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

if ($f1 > $f2) { $x3=$x1+2*$step;} else {$x3=$x1-$step;} // вычисляем х3

$f3 = func1($x3);

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

//поиск xmin

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

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

$znam=($x2-$x3)*$f1+($x3-$x1)*$f2+($x1-$x2)*$f3;

while ($znam == 0) {

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

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

if ($f1 > $f2) {$x3=$x1+2*$step;} else {$x3=$x1-$step;}

$f3 = func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

}

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

$fsr=func1($sr);

echo "x = ",$sr,"<br>";

echo "f(x) = ",$fsr,"<br>";

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

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

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

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

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

{

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

echo $l+1," итерация","<br>";

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

if (($sr >= min($x1,min($x2,$x3))) && ($sr <= max($x1,max($x2,$x3))))

{

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

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

{ // создаем массив всех точек

if ($xmin == $x1) { $massiv[0]=$xmin; $massiv[1]=$x2; $massiv[2]=$x3; $massiv[3]=$sr;}

if ($xmin == $x2) { $massiv[0]=$xmin; $massiv[1]=$x1; $massiv[2]=$x3; $massiv[3]=$sr;}

if ($xmin == $x3) { $massiv[0]=$xmin; $massiv[1]=$x1; $massiv[2]=$x2; $massiv[3]=$sr;}

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

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

            for ($i = 0; $i < count($massiv)-$j-1; $i++) {

                        if ($massiv[$i]>$massiv[$i+1])

{$m=$massiv[$i+1];$massiv[$i+1]=$massiv[$i];$massiv[$i]=$m; }}}

            //располагаем точки в правильном порядке

if (($massiv[0] == $xmin) || ($massiv[1] == $xmin)) {$x1=$massiv[0];$x2=$massiv[1];$x3=$massiv[2];}

if (($massiv[2] == $xmin) || ($massiv[3] == $xmin)) {$x1=$massiv[1];$x2=$massiv[2];$x3=$massiv[3];}

$f1=func1($x1);

$f2=func1($x2);

$f3=func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

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

$znam=($x2-$x3)*$f1+($x3-$x1)*$f2+($x1-$x2)*$f3;

while ($znam == 0) {

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

if ($f1 > $f2) {$x3=$x1+2*$step;} else {$x3=$x1-$step;}

$f3 = func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) { $xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}}

//вычисляем ответ

$sr=polinom($x1,$x2,$x3,$f1,$f2,$f3);

$fsr=func1($sr);

echo "x = ",$sr,"<br>";

echo "f(x) = ",$fsr,"<br>";

}

else  //в противном случае, т.е. если лучшей точкой является sr

{

// заполняем массив

$massiv[0]=$sr; $massiv[1]=$x1; $massiv[2]=$x2; $massiv[3]=$x3;

//сортируем массив точек

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

            for ($i = 0; $i < count($massiv)-1-$j; $i++) {

                        if ($massiv[$i]>$massiv[$i+1])

{$m=$massiv[$i+1]; $massiv[$i+1]=$massiv[$i];$massiv[$i]=$m; }}}

if (($massiv[0] == $sr) || ($massiv[1] == $sr)) {$x1=$massiv[0];$x2=$massiv[1];$x3=$massiv[2];}

if (($massiv[2] == $sr) || ($massiv[3] == $sr)) {$x1=$massiv[1];$x2=$massiv[2];$x3=$massiv[3];}

$f1=func1($x1); $f2=func1($x2); $f3=func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

//проверим знаменатель

$znam=($x2-$x3)*$f1+($x3-$x1)*$f2+($x1-$x2)*$f3;

while ($znam == 0) {

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

if ($f1 > $f2) {$x3=$x1+2*$step;} else {$x3=$x1-$step;}

$f3 = func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) { $xmin=$x3;}}

//вычислим ответ данной итерации

$sr=polinom($x1,$x2,$x3,$f1,$f2,$f3);

$fsr=func1($sr);

echo "x = ",$sr,"<br>";

echo "f(x) = ",$fsr,"<br>";

}

}

//ВТОРОЙ СЛУЧАЙ, если  (где )

else

{

// вычисление х1, х2, f1, f2, x3, f3, fmin

$x1=$sr; $x2=$x1+$step;

$f1=func1($x1); $f2=func1($x2);

if ($f1 > $f2) {$x3=$x1+2*$step;} else { $x3=$x1-$step;}

$f3 = func1($x3);

$fmin=min($f1,min($f2,$f3));

//поиск xmin

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

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

$znam=($x2-$x3)*$f1+($x3-$x1)*$f2+($x1-$x2)*$f3;

while ($znam == 0) {

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

if ($f1 > $f2) {  $x3=$x1+2*$step;} else { $x3=$x1-$step;}

$f3 = func1($x3);

$fmin=min($f1,min($f2,$f3));

if ($fmin == $f1) {$xmin=$x1;}

if ($fmin == $f2) {$xmin=$x2;}

if ($fmin == $f3) {$xmin=$x3;}

}

$sr=polinom($x1,$x2,$x3,$f1,$f2,$f3);

$fsr=func1($sr);

echo "x = ",$sr,"<br>";

echo "f(x) = ",$fsr,"<br>";

}

}

echo "Ответ: x = ",$sr;

Метод хоть и оказался громоздким, но очень понятен и прост. Пока не будут выполнены условия на точность, просчитываются новые значения переменной sr (или ) по формуле (8). В первом случае, когда sr принадлежит промежуткам между  и , выбирается лучшая (т. е. наименьшая) точка из точек и xmin. Создается упорядоченный массив из всех найденных точек (, , , ), кроме точки, которая равна . Далее выбираем три основных точки (, ) из найденного массива, по принципу, что лучшая точка должна находится посередине или же с краю, если это невозможно. После выбора трех основных точек повторяются вычисления с 4 шага алгоритма. Во втором же случае, когда sr не принадлежит промежуткам между  и , просто предполагаем, что  и переходим на шаг 2 алгоритма метода Пауэлла.

Для наглядности и уверенности в работе приведенного алгоритма ниже покажем скриншоты второй страницы.

Рис. 2. Первый пример результата работы программы

Рис. 2. Второй пример результата работы программы

Рис. 2. Третий пример результата работы программы

Литература:

1.      Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. — М.: Радио и связь, 1988–128 с.

2.      Методы оптимизации систем автоматизированного проектирования. Метод Пауэлла. http://optimizaciya-sapr.narod.ru/bez_odnomer/paul.html

Основные термины (генерируются автоматически): POST, Функция, одномерная оптимизация, натуральный логарифм, Квадратичная интерполяция, результат работы программы, функция пользователя, квадратичный полином, окончательный ответ, вид строки.


Ключевые слова

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

Похожие статьи

Явные формулы многомерной интерполяции | Статья в журнале...

Задача интерполяции для функций многих переменных формулируется следующим образом.

Сплайны являются оптимальными в классе интерполяционных формул, например, , где -некоторый квадратичный функционал [5,6,7].

Многомерная интерполяция сеточной вектор-функции

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

Методы приближения функций параболическими сплайнами

Вопрос — ответ.

Теория интерполяции функций полиномами целых неотрицательных степеней.

Они ведут к тому, что отсутствует сходимость интерполирующих полиномов к функции.

Восстановление простых линейных и итерационных функций...

MATLAB позволяет сохранить откомпилированные М-функции в виде p-кода [1]. В

Описанный в данной работе метод основан на анализе данных, получаемых в результате работы с

Если не указать номер строки кода для точки останова, функция остановится на второй строке.

Модель оценивания пар игроков в теннис | Статья в журнале...

Результатом работы алгоритма является вектор . Для оценки качества алгоритма используется логарифмическая функция потерь.

Также, для каждого теннисиста, был определен один из 8 видов стилей игры.

Схема работы программы: 1. Первичная загрузка базы данных.

Решение многокритериальных задач линейного программирования...

Вопрос — ответ.

%Настройка функции linprog на решение симплекс-методом.

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

Равномерное приближение таблично-заданных значений гладкой...

Если же последняя последовательность содержит лишь три точки , то на ней произвести параболическую интерполяцию функции ; если лишь

- 2) Выдача результатов вычислений и переход к модулю С. Модуль С. 1) Для каждого z-го стыка , где строится сочленяющий полином .

Оценки явных формул многомерной интерполяции в зависимости...

Интерполяционная формула строилась в виде линейной комбинации чебышевской системы функций, т. е. в виде. , (3).

.(6). Здесь - разделённые разности. Мы рассмотрим обобщения одномерных формул интерполяции Ньютона и Лагранжа.

Решения нелинейных волновых уравнений методом вариационных...

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

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Явные формулы многомерной интерполяции | Статья в журнале...

Задача интерполяции для функций многих переменных формулируется следующим образом.

Сплайны являются оптимальными в классе интерполяционных формул, например, , где -некоторый квадратичный функционал [5,6,7].

Многомерная интерполяция сеточной вектор-функции

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

Методы приближения функций параболическими сплайнами

Вопрос — ответ.

Теория интерполяции функций полиномами целых неотрицательных степеней.

Они ведут к тому, что отсутствует сходимость интерполирующих полиномов к функции.

Восстановление простых линейных и итерационных функций...

MATLAB позволяет сохранить откомпилированные М-функции в виде p-кода [1]. В

Описанный в данной работе метод основан на анализе данных, получаемых в результате работы с

Если не указать номер строки кода для точки останова, функция остановится на второй строке.

Модель оценивания пар игроков в теннис | Статья в журнале...

Результатом работы алгоритма является вектор . Для оценки качества алгоритма используется логарифмическая функция потерь.

Также, для каждого теннисиста, был определен один из 8 видов стилей игры.

Схема работы программы: 1. Первичная загрузка базы данных.

Решение многокритериальных задач линейного программирования...

Вопрос — ответ.

%Настройка функции linprog на решение симплекс-методом.

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

Равномерное приближение таблично-заданных значений гладкой...

Если же последняя последовательность содержит лишь три точки , то на ней произвести параболическую интерполяцию функции ; если лишь

- 2) Выдача результатов вычислений и переход к модулю С. Модуль С. 1) Для каждого z-го стыка , где строится сочленяющий полином .

Оценки явных формул многомерной интерполяции в зависимости...

Интерполяционная формула строилась в виде линейной комбинации чебышевской системы функций, т. е. в виде. , (3).

.(6). Здесь - разделённые разности. Мы рассмотрим обобщения одномерных формул интерполяции Ньютона и Лагранжа.

Решения нелинейных волновых уравнений методом вариационных...

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

Задать вопрос