fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <functional>
  6. //#include <fstream>
  7. //#include <ostream>
  8.  
  9. #define METHOD (4)
  10. //выбор метода определения длины шага
  11. //1 - метод градиентного спуска с постоянным шагом
  12. //2 - Градиентный метод с дроблением шага
  13. //3 - Метод наискорейшего спуска
  14.  
  15. //константа для метода градиентного спуска с постоянным шагом
  16. //начальное значение eps для метода с дроблением шага
  17. #define LAMBDA_CONSTANT (0.01)
  18.  
  19. //параметры для метода с дроблением шага
  20. #define DELTA_FOR_METHOD2 (0.95)
  21. #define EPS_FOR_METHOD2 (0.0001)
  22.  
  23. //максимально возможное число итераций
  24. #define NUMBER_OF_ITERATIONS (100000)
  25.  
  26. //eps для критерия останова
  27. #define EPS (0.6) //0.9 0.07 0.6
  28.  
  29. //критерий останова
  30. #define OSTANOV (2)
  31.  
  32. using namespace std;
  33.  
  34. vector<double> goldensectionoptimize(vector<double> x,double a, double b, int n);
  35. double f(vector<double> x);
  36. vector<double> GradientDescent(int N,vector<double> x0,int&Iterations);
  37. //ofstream o;
  38.  
  39.  
  40.  
  41. double f(vector<double> x)
  42. //функция минимум которой ищут
  43. {
  44. 	return (pow(x[0],2)+20*sin(x[0])+20*pow(x[1],2));;
  45. }
  46.  
  47. vector<double> GradientF(vector<double> x)
  48. //градиент исследуемой функции
  49. {
  50. 	vector<double> tmp;
  51. 	tmp.push_back(2*x[0]+cos(x[0]));
  52. 	tmp.push_back(40*x[1]);
  53. 	return tmp;
  54. }
  55.  
  56.  
  57. vector<double> GradientDescent(int N,vector<double> x0,int&Iterations)
  58. //minimizes N-dimensional function f; x0 - start point
  59. {
  60. 	vector <double> old,cur_x=x0,gr;
  61. 	double s,Lambda;
  62. 	int j,i;
  63.  
  64. 	Lambda=LAMBDA_CONSTANT;
  65.  
  66. 	for (Iterations=1;Iterations<=NUMBER_OF_ITERATIONS;Iterations++)
  67. 	{
  68.  
  69. 		//save old value
  70. 		old=cur_x;
  71. 		//compute gradient
  72.         gr=GradientF(cur_x);
  73.  
  74.  
  75. 		if (METHOD==1)
  76. 		{
  77.  
  78. 			Lambda=LAMBDA_CONSTANT;
  79. 			//вычисляем новое значение
  80. 			for(j=0;j<old.size();j++)
  81. 				cur_x[j]=cur_x[j]-Lambda*gr[j];
  82. 		}
  83.  
  84. 		if (METHOD==2)
  85. 		{
  86. 			//вычисляем новое значение
  87. 			for(j=0;j<old.size();j++)
  88. 				cur_x[j]=cur_x[j]-Lambda*gr[j];
  89.  
  90. 			//вычисляем квадрат нормы градиента
  91. 			s=0;
  92. 			for(j=0;j<old.size();j++)
  93. 				s+=gr[j]*gr[j];
  94.  
  95.  
  96. 			while (f(cur_x)>f(old)-EPS_FOR_METHOD2*Lambda*s)
  97. 			{
  98. 				Lambda=Lambda*DELTA_FOR_METHOD2;
  99. 				//пересчет значения Лямда
  100. 				cur_x=old;
  101. 				for(j=0;j<old.size();j++)
  102. 					cur_x[j]=cur_x[j]-Lambda*gr[j];
  103. 			}
  104.  
  105. 		}
  106.  
  107. 		if (METHOD==3)
  108. 		{
  109. 			cur_x=goldensectionoptimize(cur_x,-10,10,100);
  110. 		}
  111.  
  112. 		if (METHOD==4)
  113.         {
  114.             Lambda=(double)1/Iterations;
  115. 			//вычисляем новое значение
  116. 			for(j=0;j<old.size();j++)
  117. 				cur_x[j]=cur_x[j]-Lambda*gr[j];
  118.         }
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.         //o<<cur_x[0]<<","<<cur_x[1]<<","<<f(cur_x)<<"\n";
  127. 		if(OSTANOV==1)
  128. 		{
  129. 			//условие останова 1
  130. 			s=0;
  131. 			for(j=0;j<old.size();j++)
  132. 				s+=(old[j]-cur_x[j])*(old[j]-cur_x[j]);
  133. 			s=sqrt(s);
  134. 			if (s<EPS)
  135. 				return cur_x;
  136. 		}
  137.  
  138. 		if(OSTANOV==2)
  139. 		{
  140. 			//условие останова 2
  141. 			s=fabs(f(cur_x)-f(old));
  142. 			if (s<EPS)
  143. 				return	cur_x;
  144. 		}
  145.  
  146. 	}
  147.  
  148. 	return cur_x;
  149. }
  150.  
  151. int main()
  152. {
  153. 	vector<double> x;
  154. 	x.push_back(0.9);
  155. 	x.push_back(0.7);
  156. 	int i,Iteration;
  157.       // o.open("grad.txt");
  158. 	vector<double> ans=GradientDescent(2,x,Iteration);
  159. 	cout<<"Value: "<<f(ans)<<endl;
  160. 	cout<<"Point: ";
  161. 	for(i=0;i<ans.size();i++)
  162. 		cout<<ans[i]<<' ';
  163. 	cout<<endl<<"Number of iterations:"<<Iteration<<endl;
  164.     //o.close();
  165. 	return 0;
  166. }
  167.  
  168. vector<double> goldensectionoptimize(vector<double> x,double a, double b, int n)
  169. //метод золотого сечения одномерной оптимизации функции f
  170. //вектор переменных x на отрезке [a,b], n итераций
  171. //взят с сайта http://a...content-available-to-author-only...s.ru/
  172. {
  173. 	vector<double> tmp=x;
  174. 	int i,j;
  175.     double s1;
  176.     double s2;
  177.     double u1;
  178.     double u2;
  179.     double fu1;
  180.     double fu2;
  181. 	vector<double> GF=GradientF(x);
  182.  
  183.     s1 = (3-sqrt(double(5)))/2;
  184.     s2 = (sqrt(double(5))-1)/2;
  185.     u1 = a+s1*(b-a);
  186.     u2 = a+s2*(b-a);
  187.  
  188. 	for(j=0;j<x.size();j++)
  189. 		tmp[j]=x[j]+u1*GF[j];
  190. 	fu1 = f(tmp);
  191.  
  192. 	for(j=0;j<x.size();j++)
  193. 		tmp[j]=x[j]+u2*GF[j];
  194. 	fu2 = f(tmp);
  195.  
  196.     for(i = 1; i <= n; i++)
  197.     {
  198.         if( fu1<=fu2 )
  199.         {
  200.             b = u2;
  201.             u2 = u1;
  202.             fu2 = fu1;
  203.             u1 = a+s1*(b-a);
  204. 			for(j=0;j<x.size();j++)
  205. 				tmp[j]=x[j]+u1*GF[j];
  206. 	        fu1 = f(tmp);
  207.         }
  208.         else
  209.         {
  210.             a = u1;
  211.             u1 = u2;
  212.             fu1 = fu2;
  213.             u2 = a+s2*(b-a);
  214. 			for(j=0;j<x.size();j++)
  215. 				tmp[j]=x[j]+u2*GF[j];
  216. 			fu2 = f(tmp);
  217.         }
  218.     }
  219. 	for(j=0;j<x.size();j++)
  220. 		tmp[j]=x[j]+u1*GF[j];
  221. 	fu1 = f(tmp);
  222.     for(j=0;j<x.size();j++)
  223. 		tmp[j]=x[j]+u2*GF[j];
  224. 	fu2 = f(tmp);
  225.  
  226. 	if (fu1<fu2)
  227. 		for(j=0;j<x.size();j++)
  228. 			tmp[j]=x[j]+u1*GF[j];
  229. 	else
  230. 		for(j=0;j<x.size();j++)
  231. 			tmp[j]=x[j]+u2*GF[j];
  232.  
  233. 	return tmp;
  234. }
  235.  
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Value: 4.65541e+22
Point: -0.449614 4.82463e+10 
Number of iterations:20
https://ideone.com/JH7Jgd
language:
C++14 (gcc 8.3)
created:
327 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!