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

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

时间:2023-07-08 16:03:20浏览次数:46  
标签:md end 07 准则 08 Armijo fun alpha x0

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

数值优化方法Matlab一维线搜索非精确线搜索ArmijoGoldsteinWolfe多维搜索

前面我们学习的二分法、成功-失败法、牛顿法、抛物线法都是精确求解一维问题, 其中. 回到我们一开始的线搜索方法的目标是求解, 如果我们不求解当前的最优, 则称为非精确搜索法。

这里有个问题,牛顿法和抛物线法是近似求解了当前的最优, 但是二分法和成功-失败法只是给出了每步的下降方向和给定的步长。#F44336

非精确线搜索准则有Armijo准则,Goldstein准则和Wolfe 准则,下面逐一介绍。

1. Armijo准则

, 取步长, 其中是满足下式的最小非负整数


其中. 若上述不等式成立,则称步长满足Armijo准则.

这里给以下Armijo准则的解释:(1)首先因为下降方向必然和梯度方向相反, 因此, 否则. (2) 此外是因为当充分大时,上式即是一阶泰勒展开式,因此保证了不等式的成立.

注意如果目标函数可导,则必然存在满足Armijo准则的步长.

2. Goldstein准则

满足


其中, 则称满足Goldstein准则.

参考博文:https://www.cnblogs.com/pakchoy/p/13817126.html
参考博文:https://www.cnblogs.com/pakchoy/p/13817126.html

下面同样对Goldstein准则给出一些解释(应该会比书中清楚一些)
上图中由表示, 阴影部分表示的可行区间(实际上的部分也是可行的)
蓝色线表示第一个式子,即固定下的新的的可行域,红色线表示的最小值,最终在三条线的交点之间。

3. Wolfe准则(Armijo rule and curvature)


其中, 则称步长满足Wolfe准则。

参考博文:https://blog.csdn.net/weixin_46584887/article/details/122893222
参考博文:https://blog.csdn.net/weixin_46584887/article/details/122893222

第一个式子即Armijo准则,我们来看第二个式子,注意到, 则, 式子的右边即是处导数的倍. 现在第二个式子的含义就很明显了,首先显然必然小于0, 然后第二个式子保证了也是小于0, 则的点必然在第二个式子要求的右侧,结合第一个式子,可知Wolfe准则必然包含最优的.

其中并没有查到这样设置的原因,但是在Wiki中看到了它的经验设置: is usually chosen to be quite small while is much larger; Nocedal and Wright give example values of for Newton or quasi-Newton methods, and for nonlinear conjugate gradient method.#F44336

4. 强Wolfe准则(Strong Wolfe condition on curvature)


强Wolfe准则将的可行区间削减到了更小的范围 (与更接近).

四种非精确线搜索准则的总结
Armijo准则给处的搜索步长保证了迭代是单调下降的,但是由于没有限制最小步长,因此可能导致迭代不收敛到极小值.
为了解决Armijo步长过小的问题,Goldstein根据处的斜率生成了两条直线,将步长限制在两条直线与曲线的交点范围内.
由于Goldstein准则可能将最优的取值舍弃,因此Wolfe提出了曲率准则,始终保证了最优在取值范围内.
为了将取值范围进一步缩小,再改进了Wolfe准则,即得到强Wolfe准则.#3F51B5

5. 非精确线搜索的算法框架

前述非精确线搜索在优化算法中都扮演的确定最优步长的角色,而下降方向都假设已知。下面给出非精确线搜索Goldstein的算法框架:
Step 1. 在搜索区间中选择初始点, 给出可接受系数, 增大试探点系数, 令, .

Step 2. 计算, 若


成立,转Step 3; 否则令, 转Step 4.

Step 3. 若


成立,则停止,置, 否则令, 转 Step 4.

Step 4. , 转Step 2.

此算法和书中算法在Step 3 和 Step 4有些许不同,这里的算法感觉更清楚一些.

最后附上代码:
一维问题的非精确搜索算法

  1. function [alpha] = NonAccSearch(f, x0, method) 
  2. % 转为符号函数 
  3. if isa(f,'function_handle') 
  4. syms x; 
  5. fun(x) = f(x); 
  6. fun_h = f; 
  7. else 
  8. fun = f; 
  9. fun_h = matlabFunction(fun); 
  10. end 
  11. diff_fun1 = diff(fun); 
  12. diff_h = matlabFunction(diff_fun1); 
  13. if method == "Armijo" 
  14. beta = 2; 
  15. gamma = 0.5; 
  16. sigma = 0.5; 
  17. for i = 1:1e4 
  18. d = - diff_h(x0); 
  19. alpha = beta * gamma^i; 
  20. LF = fun_h(x0 + alpha * d); 
  21. RF = fun_h(x0) - sigma * alpha * d' * d; 
  22. if LF <= RF 
  23. break; 
  24. end 
  25. end 
  26. end 
  27.  
  28. if method == "Goldstein" 
  29. a = 0; 
  30. b = 100; 
  31. sigma = 0.01; 
  32. c = 2; 
  33. alpha = (a+b)/2; 
  34. for k = 1:1e4 
  35. d = - diff_h(x0); 
  36. alpha = min((a+b)/2, c * alpha) 
  37. LF = fun_h(x0 + alpha * d); 
  38. RF = fun_h(x0) - sigma * alpha * d' * d; 
  39. if LF <= RF 
  40. F = fun_h(x0) - (1-sigma) * alpha * d' * d; 
  41. if LF >= F 
  42. break; 
  43. end 
  44. a = alpha; 
  45. else 
  46. b = alpha; 
  47. end 
  48. end 
  49. end 
  50. end 
  51.  

特别的,这里给出一个多维情况下的Armijo搜索,基于符号运算

  1. function [alpha] = NonAccSearchVec(f, A, x0, method) 
  2. fun = f; 
  3. fun_h = f; 
  4. for i = 1:length(A) 
  5. diff_fun1(i,1) = diff(fun, A(i)); 
  6. end 
  7. diff_h = matlabFunction(diff_fun1); 
  8. x0 = num2cell(x0); 
  9. if method == "Armijo" 
  10. beta = 2; 
  11. gamma = 0.5; 
  12. sigma = 0.5; 
  13. for i = 1:1e4 
  14. d = - diff_h(x0{:}); 
  15. alpha = beta * gamma^i; 
  16. x1 = cell2mat(x0)' + alpha * d; 
  17. x1 = num2cell(x1); 
  18. LF = fun_h(x1{:}); 
  19. RF = fun_h(x0{:}) - sigma * alpha * d' * d; 
  20. if LF <= RF 
  21. break; 
  22. end 
  23. end 
  24. end 
  25. end 

测试代码

  1. n = 10; 
  2. A = sym('a', [n 1]); 
  3. f(A) = sum(A.^2 - A); 
  4. B = num2cell(1:n); 
  5. f(B{:}) 
  6. x0 = repelem(0,n) 
  7. [alpha] = NonAccSearchVec(f, A, x0, 'Armijo') 

这里特别注意符号运算和参数输入等情况,个人感觉是很有价值的.

标签:md,end,07,准则,08,Armijo,fun,alpha,x0
From: https://www.cnblogs.com/NEFPHYS/p/17537341.html

相关文章

  • 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属于对类型要求没有那么严格的动态类型语言 对初学者很友好不过很多时候也容易弄不清变量类型 直接修改代码增强程序的可读性把变量的类型明确标......
  • AtCoder Beginner Contest 308 题解
    https://atcoder.jp/contests/abc308/tasks_printA-NewScheme过水已隐藏。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>usingnamespacestd;u......
  • 20230706巴蜀暑期集训测试总结
    T1我是个大聪明!一眼矩乘。构造转移矩阵构造了3.5h!最开始以为只有\(15\times15\),直接手打。写到一半发现不一定四种颜色都有,是\(52\times52\)的,这时候狗被脑子吃了,还想手打,于是就打到了3h。差不多打了一大半,脑子终于把狗还回来了,意识到就算打完也不可能调得出来,就开始另辟蹊径,......