首页 > 其他分享 >2023-07-08 《数值优化方法》-庞丽萍,肖现涛-无约束最优化(五).md

2023-07-08 《数值优化方法》-庞丽萍,肖现涛-无约束最优化(五).md

时间:2023-07-08 17:56:01浏览次数:42  
标签:md end 07 epsilon 08 alpha diff x0 最速

2023-07-08 《数值优化方法》-庞丽萍,肖现涛-无约束最优化(五)

数值优化方法Matlab最速下降法

考虑无约束最优化问题


其中是一阶连续可微的 (记作), 也就具有连续的一阶偏导数. 最速下降法的基本思想正如其名字一样,就是在当前迭代点处寻找一个使目标函数下降最快的方向. 这样的方向由下述问题(下降量)

的解给出,因此为函数处的最速下降方向。

最速下降法
Step 1. 选取初始点, 给定精度, 置.

Step 2. 计算, 若, 则停止,置最优解为, 否则转下步.

Step 3. 取, 作精确线搜索


得解, 令, , 转 Step 1.

下面给出最速下降法的收敛性证明:

定理1 设函数二阶连续可微有下界,存在满足, 若最速下降法产生无穷点列, 则.#673AB7

证明:由算法和定义可知序列单调有界,即收敛. 对任意, 存在, 使得


由假设和可得

考虑合并,得到

, 由精确线搜索可知


由于收敛,因此.

最速下降法迭代路径呈锯齿状的原因: 由于采用的是精确线搜索方法,在当前下降方向已经充分下降了。从这也可以知道如果是一维优化问题,最速下降法一步即可达到最优 (精确线搜索).

下面的程序可求解多维优化问题,使用的是成功-失败法搜索

  1. % 最速下降法 
  2. function [x xlog] = SteepestDes(f, x0, epsilon) 
  3. % f 目标函数,函数句柄 
  4. % g 梯度函数 函数句柄 
  5. % epsilon 精度要求 
  6. % method 线搜索方法 
  7. k = 0; 
  8. while k <= 1e4 
  9. diff_x = -My_Gradient(f, x0); 
  10. if norm(diff_x) < epsilon 
  11. x = x0; 
  12. xlog(k+1) = norm(diff_x); 
  13. break 
  14. end 
  15. [alpha tx] = SuccFa(f, 1, x0, diff_x, 1, epsilon, 1e4); 
  16. x0 = x0 + alpha * diff_x; 
  17. k = k + 1; 
  18. xlog(k) = norm(diff_x); 
  19. end 
  20.  
  21. end 
  22.  
  23. function [alphak xlog] = SuccFa(fun, alpha, x0, diff_x, h, epsil, maxIt) 
  24. k = 0; 
  25. xlog = alpha; 
  26. while k <= maxIt 
  27. alphak = alpha + h; 
  28. if fun(x0 + alphak * diff_x) < fun(x0 + alpha * diff_x) 
  29. h = 2 * h; 
  30. alpha = alphak; 
  31. else 
  32. h = - h / 4; 
  33. end 
  34. k = k + 1; 
  35. xlog(k) = alphak; 
  36. if abs(h) < epsil 
  37. break 
  38. end 
  39. end 
  40. end 
  41.  
  42. function [x] = F_alpha(alpha) 
  43. x = f(x0 + alpha * diff_x); 
  44. end 
  45.  
  46.  
  47. function [gd] = My_Gradient(f, x) 
  48. gd = x; 
  49. epsil = 1e-5; 
  50. d = [-2* epsil, -epsil 0 epsil 2*epsil]; 
  51. tx = [x x x x x]; 
  52. fx = [0,0,0,0,0]; 
  53. for i = 1:length(x) 
  54. tx(i,:) = tx(i,:) + d; 
  55. for h = 1:5 
  56. fx(h) = f(tx(:,h)); 
  57. end 
  58. gf = gradient(fx); 
  59. gd(i) = gf(3); 
  60. end 
  61. end 

测试程序

  1. f = @(x) sin(x(1)) + cos(x(2)); 
  2. x0 = [1 ,2]'; 
  3. epsilon = 1e-8; 
  4. [x xlog] = SteepestDes(f, x0, epsilon) 
  5.  
  6. f = @(x) sin(x); 
  7. x0 = 1; 
  8. epsilon = 1e-8; 
  9. [x xlog] = SteepestDes(f, x0, epsilon) 

标签:md,end,07,epsilon,08,alpha,diff,x0,最速
From: https://www.cnblogs.com/NEFPHYS/p/17537578.html

相关文章

  • 2023/7/08
    今天主要学习了字符串的创建与连接字符串的创建方法有多种:Strings=newString(字符数组名);Strings=newString(字符数组名,开始的位置,长度);Strings="";等在这里只能用字符数组名做参数,不能用字符做参数但是可以用第三种方法将字符转为字符串charc='@';//注意,单个字......
  • 2023-07-08 《数值优化方法》-庞丽萍,肖现涛-无约束最优化(四).md
    2023-07-08《数值优化方法》-庞丽萍,肖现涛-无约束最优化(四)数值优化方法Matlab一维线搜索非精确线搜索ArmijoGoldsteinWolfe多维搜索前面我们学习的二分法、成功-失败法、牛顿法、抛物线法都是精确求解一维问题,其中.回到我们一开始的线搜索方法的目标是求解,如果我们不求解当......
  • vscode makedown md代码片段不生效
    1.创建markdoen代码片段文件。注意文件名:markdown.json2.写代码片段:"多行注释":{ "prefix":"notebash", "body":[ "", "```bash", "", "```", "" ], "description":......
  • 20230708练习总结
    CF1785DWoodenSpoon为了方便,将题目中的大小关系反转一下。这是一个\(n+1\)层的满二叉树,第\(i\)层每个点都是\(2^{n-i+1}\)个人中的胜者。如果从下往上dp,需要记录胜利者编号和得到木勺者编号,会爆掉。那么从上往下dp。设\(dp_{i,j}\)表示第\(i\)层\(j\)胜利随即......
  • 【题解】 [APIO2007] 动物园
    目录题目链接原题描述题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示题意概括思路历程1.与环相关2.设计状态代码实现题目链接原题描述[APIO2007]动物园题目描述新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个......
  • 成语积累 20230708
    皓首穷经:皓:白;穷经:专心研究经书和古籍。指一直到年老头白之时还在深入钻研经书和古籍。含褒义。在句中一般作谓语,定语。例句:百尺楼台,~,在这段时光里,他绞尽脑汁,努力学习,只为追求更高的目标。单书白马:单书:古代帝王赐功臣享有世袭爵位和免罪等特权的证件时(如单书铁券),宰白马歃其血,以示......
  • 20230707-NOIP模拟赛(多校联训)
    20230707T1.信号传输(signal)考场思路先把这\(n+k+1\)个点都转化到平面直角坐标系上面又是没有想清楚就开始打代码(但至少比昨天好,懂得放弃)本来想的是按照x轴从左到右扫一遍每一次处理这一列上的每个点复杂度是\(O(n)\)但是后面想到有可能信号是从后面的点传送过来的所以我......
  • 2023-07-07:给出两个字符串 str1 和 str2。 返回同时以 str1 和 str2 作为子序列的最短
    2023-07-07:给出两个字符串str1和str2。返回同时以str1和str2作为子序列的最短字符串。如果答案不止一个,则可以返回满足条件的任意一个答案。输入:str1="abac",str2="cab"。输出:"cabac"。答案2023-07-07:大体步骤如下:1.初始化字符串str1和str2分别为"abac"......
  • 2023-07-07:给出两个字符串 str1 和 str2。 返回同时以 str1 和 str2 作为子序列的最短
    2023-07-07:给出两个字符串str1和str2。返回同时以str1和str2作为子序列的最短字符串。如果答案不止一个,则可以返回满足条件的任意一个答案。输入:str1="abac",str2="cab"。输出:"cabac"。答案2023-07-07:大体步骤如下:1.初始化字符串str1和str2分别为"abac"和"cab"......
  • [oeasy]python0071_字符串类型_str_string_下标运算符_中括号
    回忆上次内容上次分辨了静态类型语言动态类型语言 python属于对类型要求没有那么严格的动态类型语言 对初学者很友好不过很多时候也容易弄不清变量类型 直接修改代码增强程序的可读性把变量的类型明确标......