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

Зарипова А. А. Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php // Молодой ученый. — 2014. — №4. — С. 13-20.

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

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

Обсуждение

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