Размещено на http://www.allbest.ru/

4

- 3 -

Размещено на http://www.allbest.ru/

Курсовой проект

Функциональный и выпуклый анализ

Ялта - 2011

ВВЕДЕНИЕ

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

В курсовой работе рассмотрен итерационный метод наискорейшего спуска решения функций нескольких переменных. Приложение будет создано для метода наискорейшего спуска на языке C++ в программной среде Microsoft Visual C++. С использованием библиотек <iostream.h>, <math.h>,<time.h>.

1. ПОСТАНОВКА ЗАДАЧ

наискорейший спуск программная среда

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

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

формула 1

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

формула 2 …,

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

Существуют специальные методы поиска минимума функции многих переменных, основанные на целенаправленном поиске. Их называют методами спуска.

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

Решается задача минимизации функции на всем пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности Х⁰. В качестве начального приближения выбирается любая точка Х⁰ E_n. Последовательные приближения Х¹, Х²,… строятся по следующей схеме:

1) в точке Хⁱ выбирают направление спуска - Sⁱ

2) находят (i+1) приближение по формуле 3

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

Число pⁱ определяет расстояние от точки Хⁱ до точки Хⁱ⁺¹. Это число называется длиной шага или просто шагом. Основная задача при выборе величины pⁱ - это обеспечить выполнение неравенства

Одним из наиболее простых способов определения направления спуска является выбор в качестве направления спуска Sⁱ одного из координатных векторов e₁, e₂, …, e_n, вследствие чего у Хⁱ на каждой итерации изменяется лишь одна из компонент. Методы спуска, основанные на выборе пути оптимизации вдоль координатных векторов, называются методами покоординатного спуска.

Итерация - поэтапный процесс, в котором результаты выполнения группы операций в рамках каждого этапа используются следующим этапом (кроме последнего, потому что он предоставляет конечный результат)

Другим способом определения направления спуска является выбор в качестве направления спуска Sⁱ направления наибольшего убывания функции. Известно, что направление наибольшего возрастания функции характеризуется ее градиентом. Следовательно направление противоположное градиентному, укажет путь, ведущий к минимуму функции.

Градиент - вектор, показывающий направление наискорейшего возрастания некоторой величины, значение которой меняется от одной точки пространства к другой (скалярного поля).

Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными. К ним относится и метод наискорейшего спуска.

1.1 Теоретические основы. Методы спуска

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

Решается задача минимизации функции (x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности {x_k}. В качестве начального приближения выбирается любая точка x_0En. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

в точке x_k выбирают направление спуска - S_k;

находят (k+1)-е приближение по формуле .

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

Число hk определяет расстояние от точки x_k до точки х_k+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины hk - это обеспечить выполнение неравенства по формуле 1.1 (x_k+1)<(x_k).

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

Формула 1.2,где =

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

Наибольшее распространение получили следующие алгоритмы:

1. (без коррекции);

2. если ; если

3. , если ; , если ; ,если ,

где -угол между градиентами на предыдущем и текущем шаге;

и - заданные пороговые значения выбираются субъективно

(например, ).

[4, с. 308-310]

Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).

1.1.1Метод покоординатного спуска

Пусть нужно найти наименьшее значение целевой функции u=f(M)=f(x₁, x₂, . . . ,x_n). Здесь через М обозначена точка n-мерного пространства с координатами x₁, x₂, . . . ,xn: M=(x₁, x₂, . . . ,x_n). Выберем какую-нибудь начальную точку М0=(x₁⁰, x₂⁰, . . . ,x_n⁰) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x₁, x₂⁰,x₃⁰, . . . ,x_n⁰ ). Тогда она превратится в функцию одной переменной x1 . Изменяя эту переменную, будем двигаться от начальной точки x₁=x₁⁰ в сторону убывания функции, пока не дойдем до ее минимума при x₁=x₁¹, после которого она начинает возрастать. Точку с координатами ( x₁¹, x₂⁰,x₃⁰, . . . ,x_n⁰) обозначим через М₁, при этом f(M₀) >= f(M₁).

Фиксируем теперь переменные: и рассмотрим функцию f как функцию одной переменной . Изменяя x₂ , будем опять двигаться от начального значения x²=x₂⁰ в сторону убывания функции, пока не дойдем до минимума при x₂=x₂¹ .Точку с координатами обозначим через М₂, при этом

формула 2.1

Проведем такую же минимизацию целевой функции по переменным x₃, x₄, . . . ,x_n. Дойдя до переменной x_n, снова вернемся к x₁ и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М₀,М₁,М₂, . . . , которой соответствует монотонная последовательность значений функции Обрывая ее на некотором шаге k можно приближенно принять значение функции f(M_k) за ее наименьшее значение в рассматриваемой области.



Рис. 2.1 Поиск наименьшего значения функции методом покоординатного спуска[2,с. 223-226]

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

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

На рис. изображены линии уровня некоторой функции двух переменных u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода. Когда мы приступаем к решению реальной задачи оптимизации, такого рисунка, содержащего в себе готовый ответ, у нас, конечно, нет. Пусть требуется решить задачу :

формула 2.2

В двумерном пространтсве R². Решение задачи методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.

Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями (3):

формула 2.3

где вектор направления спуска s^(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S^(k) параллелен х1, то S^(k)= {1,0,0,...,0}, если он параллелен x₂, то S^(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t^(k) является решением задачи одномерной минимизации:

формула 2.4

и может определяться, в частности, методом сканирования.

Детальная реализация общей схемы в двумерном случае R² дает траекторий приближения к точке х^* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х^(k), х~ ^(k) , x^(k+1) (k=0, 1, 2,) (рис). При k=0, исходя из начальной точки х⁽⁰⁾=(x₁⁽⁰⁾,x₂⁽⁰⁾), находят точку х~⁽⁰⁾= (x₁~ ⁽⁰⁾ ,x₂ ⁽⁰⁾), минимума функции одной переменной f(x₁,x₂⁽⁰⁾); при этом f(x~⁽⁰⁾)<=f(x⁽⁰⁾).Затем находят точку минимума x⁽¹⁾ функции f (x₁~⁽⁰⁾,x₂) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х(1). Фиксируя вторую координату точки х⁽¹⁾, находят точку минимума х~(1)= (x₁~^(1),x₂⁽¹⁾), функции f(x₁,x₂⁽¹⁾) одной переменной x⁽¹⁾; при этом f(x~⁽¹⁾)<=f(x⁽¹⁾)<=f(x⁽⁰⁾). Точку х⁽²⁾ получают, минимизируя целевую функцию f(x₁~⁽¹⁾,x₂), вновь по коорданате х₂, фиксируя координату x₁~⁽¹⁾ ,точки x⁽¹⁾ , и т.д.

Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство

формула 2.4

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

1.1.2 Метод градиентного спуска

Рассмотрим функцию f, считая для определенности, что она зависит от трех переменных x,y,z. Вычислим ее частные производные df/dх, df/dу, df/dz и образуем с их помощью вектор, который называют градиентом функции:

формула 11

Здесь i, j, k - единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции f по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (х, у,z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента

формула 1.2

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

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

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

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

1.1.3 Метод наискорейшего спуска

Одним из самых распространенных методов минимизации функции нескольких переменных является метод градиентного спуска. В этом методе в качестве направления поиска минимума заданной функции выбирается вектор, направление которого противоположно направлению вектора градиента функции F(X), где X=x₁, x_2, x₃, … x_n. Координаты этого вектора :

Формула 3.1

В математическом анализе доказывается, что вектор gradF(X) характеризует направление наиболее быстрого возрастания функции. Поэтому вектор - gradF(X) (антиградиента) является направлением наиболее быстрого ее убывания. Каждое последующее приближение получается из предыдущего смещением в направлении антиградиента функции F(X) (смотри рис.2) [3, с. 207-209]



Рис. 3.1 смещением в направлении антиградиента функции F(X) [5, с. 308-310]

Задавшись начальным приближением X⁰ ищется следующее приближение с помощью реккурентного соотношения вида:

, i=0,1,2…

Приведенное соотношение не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра _i. Например его можно определять из условия минимума величины:

В этом случае рассматриваемый метод называют методом наискорейшего градиентного спуска, или просто методом наискорейшего спуска.

Рассматриваемая функция является функцией одного параметра и ее минимум находится или методами одномерной минимизации или решением уравнения, которое имеет вид:

,

минимальный неотрицательный корень этого уравнения и является искомым значением _i.

Поиск прекращается при выполнении условия , так как градиент в точке минимума функции = 0, а при приближенных вычислениях .[2, с. 52-56]

1.2 Используемые средства языка и среды программирования

Программа написана на языке программирования С++, в

среде Visual C++, с использованием библиотек <iostream.h>

<math.h>,<time.h>.

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

Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума.

2. РАЗРАБОТКА ПРОГРАММЫ

2.2 Структура программы

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

Множество X называется выпуклым, если оно содержит всякий отрезок, концы которого принадлежат X , т.е. Функция f(x), определенная на выпуклом множестве X, называется выпуклой, если

Алгоритм

1. Задаются: x? -- начальное приближение, е1 > 0, е2> 0, M - предельное число итераций;

2. Количество итераций n = 0 ;

3. Вычисляется: ;

4. Вычисляется ;

4.1. если , то x*= x? ;

4.2. если , то к 5);

5. n < M

5.1. если выполняется, то к 6) ;

5.2. если нет, то x*= x? ;

6. задается t_n ;

7. ;

8. Проверяется условие f(x? ? ) -- f(x?) < 0

8.1. если выполняется, то к 9) ;

8.2. если нет, то t_n= t_n / 2 и к 7) ;

9. Проверяется условие

9.1. если оба условия выполняются, то x*= x? ? ;

9.2. если хотя бы одно не выполняется , то n = n+1 и к 3). [7]

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

Рис 4.1 Блок схема алгоритма: Метода наискорейшего спуска

2.3 Программный код

В процессе реализации задачи, были разработаны следующие функции:

1. Функция f, возвращающая значение функции



double f (double x1,double x2)

{

return x1*x1+2*x1*x2+4*x2*x2-2*x1-3*x2;

}

2. Функция grad для нахождения производной i-той переменной

double grad(double x1[2],int i)

{

double h=0.00000001,ly,lx[2];

lx[0]=x1[0];

lx[1]=x1[1];

ly=f(x1[0],x1[1]);

lx[i]=lx[i]-h;

ly=(ly-f(lx[0],lx[1]))/(h);

return ly;

}

Функция opt находит оптимальное tk

double opt(double pk[2], double x[2]) {

double a, b, xp, ll, delta,xk,yk;

double e=0.00001,l=0.0001,t = 1.0, tk = 0.0, kk = 1.0;

int p = 0;

Алгоритмом Свена находим отрезок локации

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) >=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1]) >=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])))

{

a=tk-t;

b=tk+t;

p=1;

}

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) <=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1]) <=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])))

{

cout<<"Funkziya ne unimodal'na "<<endl ;

p=1.0;

}

xp=tk;

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) >f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1]) >f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1])))

{

delta=t;

a=tk ;

tk=tk+t;

}

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) < f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1]) < f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1])))

{

delta=-t;

b=tk ;

tk=tk-t;

}

while (p!=1)

{

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])< f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t >0))

a=xp;

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])< f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t <0))

b=xp;

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])> f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t >0))

{

b=tk;

p=1;

}

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])> f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t<0))

{

a=tk;

p=1;

};

kk++;

xp=tk;

tk=xp+pow(2.0,kk)*delta;

}

do{

// методом дихотомия находим tk

Метод дихотомии используется для нахождения безусловного минимума унимодальных функций f(x)

xk = (a + b) / 2.0-e;

yk = (a + b)/2.0+e;

if (f(x[0]-(yk)*pk[0],x[1]-(yk)*pk[1])>=f(x[0]-(xk)*pk[0],x[1]-(xk)*pk[1])){

b = yk;}

if (f(x[0]-yk*pk[0],x[1]-yk*pk[1])<f(x[0]-xk*pk[0],x[1]-xk*pk[1])){

a = xk;}

ll = b-a;

}while(l<ll);

return tk = (a + b) / 2.0;

}

3. РЕЗУЛЬТАТЫ ТЕСТОВЫХ ЗАПУСКОВ

Проведем тестирование приложения при различных входных данных.

При X₀₁=1.5, X₀₂=1.1(X0 приближенное), eps1 =0.2 b esp2 =0.3, M=5(максимальное количество итераций) использовался алгоритм метода наискорейшего спуска и завершил свою работу за время:56, что представлено на рис. 5.1

Рис. 5.1 первый тестовый запуск программы при значении перменных X₀₁=2.5, X₀₂=2.01, eps1=1.2 b eps2=1.5, M=5

При X₀₁=2.5, X₀₂=2.01(X0 приближенное), eps₁=1.2 b eps₂=1.5, M=5(максимальное количество итераций) использовался алгоритм метода наискорейшего спуска и завершил свою работу за время:32, что представлено на рис. 5.2



Рис. 5.2 второй тестовый запуск программы при значении перменных X₀₁=2.5, X₀₂=2.01, eps1=1.2 b eps2=1.5, M=5

Следовательно, время работы алгоритма зависит от сложности алгоритма и от количества входных данных, и количества итераций.

Заключение

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

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

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

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

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

Список используемых источников

1. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Учебник. Воронеж, Воронежский госуниверситет, 1997. --416с.

2. Банди Б. Методы оптимизации. Вводный курс / Б. Банди. - М.: Радио и связь, 1988. --64c.

3. Корнеенко, В.П. Методы оптимизации : учебник/ В.П. Корнеенко . - М. : Высшая школа, 2007 . - 664 с.

4. Пантелеев, А.В. Методы оптимизации в примерах и задачах: Учеб. пособие/А.В. Пантелеев, Т.А. Летова. -- 2-е изд., исправл. -- М.: Высш. шк., 2005. -- 544 с.

5. Реклейтис Г. Оптимизация в технике том№1: учеб пособие. / Г. Реклейтис, А. Рейвиндран. - М.: Мир, 1986, -- 349с.

6. Свободная общедоступная мультиязычная универсальная Интернет-энциклопедия [Электронный ресурс ] - Режим доступа: http://ru.wikipedia.org/

7. Сайт для студентов по числовым методам[Электронный ресурс ] - Режим доступа:http://www.matmetod.ru/

ПРИЛОЖЕНИе

Листинг программы:

#include <iostream>

#include <cmath>

#include <time.h>

using namespace std;

double f(double x1,double x2);

double grad(double x1[2],int i);

double opt(double pk[2], double x[2]);

int main()

{clock_t start, end;

start = clock();

double eps1,eps2,M,k=0,tk;

double grx[2],x[2],xx[2];

double xpr[2]; //начальное приближение

int q=0;

for(int i=0;i<2;i++){

cout<<"enter x"<<i+1<<":\n";

cin>>xpr[i];

}

cout<<"enter eps1"<<endl;

cin>>eps1;

cout<<"enter eps2"<<endl;

cin>>eps2;

cout<<"enter M"<<endl;//Придельное число итераций

cin>>M;

x[0]=xpr[0];

x[1]=xpr[1];

do

{

grx[0]=grad(x,0);

grx[1]=grad(x,1);

if ((sqrt((grx[0]*grx[0]+grx[1]*grx[1]))<eps1))

{

xx[0]=x[0];

xx[1]=x[1];

cout<<"||f'(x)||<eps1"<<endl;

q=1;

}

if(k>=M)

{

xx[0]=x[0];

xx[1]=x[1];

cout<<"k=M"<<endl;

q=1;

}

if(q==0)

{

tk = opt(grx,x);

x[0]=x[0]-tk*grad(xpr,0);

x[1]=x[1]-tk*grad(xpr,1);

if(((sqrt(((x[0]-xpr[0])*(x[0]-xpr[0])+(x[1]-xpr[1])*(x[1]-xpr[1]))))<eps2)&&(abs(f(x[0],x[1])-f(xpr[0],xpr[1])))<eps2)

{ xx[0]=x[0];

xx[1]=x[1];

cout<<"||xk-x||<eps2 && |f(xk)-f(x)|<eps2"<<endl;

q=1;

}

xpr[0]=x[0];

xpr[1]=x[1];

}

++k;

}

while(q==0);

cout<<xx[0]<<" "<<xx[1]<<" k="<<k;

end = clock();

cout<<endl<<"The time was: \n";

cout<<(end - start)/CLK_TCK<<endl;

return 0;

}

double f(double x1,double x2)

{

return

x1*x1+2*x1*x2+4*x2*x2-2*x1-3*x2;

}

//производная по i-ой переменной

double grad(double x1[2],int i)

{

double h=0.00000001,ly,lx[2];

lx[0]=x1[0];

lx[1]=x1[1];

ly=f(x1[0],x1[1]);

lx[i]=lx[i]-h;

ly=(ly-f(lx[0],lx[1]))/(h);

return ly;

}

//находим оптимальное tk

double opt(double pk[2], double x[2]){

double a, b, xp, ll, delta,xk,yk;

double e=0.00001,l=0.0001,t = 1.0, tk = 0.0, kk = 1.0;

int p = 0;

//Алгоритмом Свена находим отрезок локации

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) >=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1]) >=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1]))){

a=tk-t;

b=tk+t;

p=1;

}

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) <=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1]) <=f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])))

{

cout<<"Funkziya ne unimodal'na "<<endl ;

p=1.0;

}

xp=tk;

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) >f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1]) >f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1])))

{

delta=t;

a=tk ;

tk=tk+t;

}

if ((f(x[0]-(tk-t)*pk[0],x[1]-(tk-t)*pk[1]) < f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])) &&

(f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1]) < f(x[0]-(tk+t)*pk[0],x[1]-(tk+t)*pk[1])))

{

delta=-t;

b=tk ;

tk=tk-t;

}

while (p!=1)

{

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])< f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t >0))

a=xp;

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])< f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t <0))

b=xp;

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])> f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t >0))

{

b=tk;

p=1;

}

if ((f(x[0]-(tk)*pk[0],x[1]-(tk)*pk[1])> f(x[0]-(xp)*pk[0],x[1]-(xp)*pk[1])) && (delta*t<0))

{

a=tk;

p=1;

};

kk++;

xp=tk;

tk=xp+pow(2.0,kk)*delta;

}

do{

// методом дихотомия находим tk

xk = (a + b) / 2.0-e;

yk = (a + b)/2.0+e;

if (f(x[0]-(yk)*pk[0],x[1]-(yk)*pk[1])>=f(x[0]-(xk)*pk[0],x[1]-(xk)*pk[1])){

b = yk;}

if (f(x[0]-yk*pk[0],x[1]-yk*pk[1])<f(x[0]-xk*pk[0],x[1]-xk*pk[1])){

a = xk;}

ll = b-a;

}while(l<ll);

return tk = (a + b) / 2.0;

}

Размещено на Allbest