本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(11)

2020-08(42)

最优化方法---一维搜索的经典方法(成功失败法、牛顿法、0.618法python实现)

发布于2021-06-12 11:52     阅读(827)     评论(0)     点赞(25)     收藏(5)



上学期学习了最优化方法这门课,但是到了现在该忘的忘得差不多了,所以想写个文章来总结记录一下,以后需要用到的话再过来看。这次主要总结3个经典的算法:成功-失败法、牛顿法和0.618法

一.成功-失败法

成功失败法的计算步骤如下:
(1)给定初始点x0∈R,搜索步长h>0及精度e>0.
(2)计算x1=x0+h,f(x1)。
(3)若f(x1)<f(x0),则搜索成功,下一次搜索就大步前进,用x1代替x0, 2h代替h,继续进行搜索;若f(x1)>=f(x0),则搜索失败,下一次搜索就小步后退。首先看是否有|h|<=e,若是,则取x*≈x0,计算结束;否则,用-h/4代替h,返回第(2)步,继续进行搜索。

计算框图如下:
在这里插入图片描述
例题:
在这里插入图片描述
参考Python代码实现:

'''
成功失败法
题目:利用“成功-失败”法求函数 f(x)=x**3-2x+1 的搜索区间,取初始点-0.5,步长h=0.5
'''
def fun(x):
    return x ** 3 - 2 * x + 1

def run(x,h,e):
    count = 0
    left = x
    right = x + h
    while abs(h)>e:
        count += 1
        print("---------第{}次搜索----------".format(count))
        if fun(left) > fun(right):
            print("搜索成功,步长加倍")
            left = x + h
            h = 2 * h
            right = right + h
            print("得到的搜索区间为:[%d,%d]" % (left, right))
        else:
            print("搜索失败,减小步长")
            left = x + h
            h = -0.25 * h
            right = right + h
            print("得到的搜索区间为:[%d,%d]" % (left, right))
    return left,right

run(x=-0.5,h=0.5,e=0.2)

在这里插入图片描述

二.牛顿法

在这里插入图片描述
在这里插入图片描述
总结:
牛顿法的优点: 收敛速度快
牛顿法的缺点: 需要计算二阶导数,且要求选好初始点,不然有可能不收敛。

例题:
在这里插入图片描述

'''2020.12.02
牛顿法:试用Newton 法求函数f(x)= x ** 4 - 4*x ** 3-6*x**2-16*x+4 的最优解
'''
from sympy import *

x = symbols("x")  # 符号x,自变量
f_x = x ** 4 - 4*x ** 3-6*x**2-16*x+4 #公式
x0 = 6
e = 0.01
# 求一阶导数
count = 1

# 求一阶导数
first_grad = diff(f_x,x)
print("one_grad=",first_grad)  # one_grad= 4*x**3 - 12*x**2 - 12*x - 16
# 求二阶导数
second_grad = diff(first_grad,x)
print("second_grad=",second_grad)  # second_grad= 12*x**2 - 24*x - 12
print("-------第{}次迭代------".format(count))
# 更新x
x_old = x0
x_new = x0-(first_grad.subs({x:x0}))/(second_grad.subs({x:x0}))
print("x1=",float(x_new))  # x1= 4.753623188405797
fx1 = first_grad.subs({x:x_new})  # 一阶导数值
print("fx1=",float(fx1))  # fx1= 85.46254744923274
x_old = x_new
while first_grad.subs({x:float(x_new)})>e:  # 当一阶导数值大于e时继续循环
    count+=1
    print("-------第{}次迭代------".format(count))
    x_new = x_old-(first_grad.subs({x:x_old}))/(second_grad.subs({x:x_old}))
    print("x"+str(count)+"={}".format(float(x_new)))
    print("f("+str(float(x_new))+")的一阶导数函数值为:",first_grad.subs({x:float(x_new)}))
    x_old = x_new

print("因为f("+str(float(x_new))+")的一阶导数函数值<精度0.01,所以停止迭代。")

在这里插入图片描述

三.0.618法

0.618法又称为黄金分割法,基本思想是:
通过试探点函数值的比较,使包含极小点的搜索区间不断缩小。
优点:该方法仅需要计算函数值,适用范围广,使用方便。
在这里插入图片描述
例题:
在这里插入图片描述

'''
黄金分割法
题目:试用0.618法求目标函数f(x)=x**3-2x+1的最优解。给定初始区间[0,2],收敛精度e=0.002
-----第16次迭代---------
x1=0.816534 x2=0.816905 f(x1)=-0.088662  f(x2)=-0.088662 [0.816002,0.817463] |b-a|=0.001461
'''

# 声明目标函数
# fx = x**3-2*x+1
def fun(x):
    return x ** 3 - 2 * x + 1

a, b = 0, 2  # 初始区间[0,2]
e = 0.002  # 收敛精度0.002
count = 1  # 计算迭代次数

print("-----第1次迭代---------")
x1 = a + 0.382 * (b - a)
fx1 = fun(x1)

x2 = a + 0.618 * (b - a)
fx2 = fun(x2)
print("x1=%f x2=%f f(x1)=%f  f(x2)=%f [%f,%f] |b-a|=%f" % (x1, x2, fx1, fx2,a,b,abs(b-a)))

# 结束条件为:|b-a|<e
while abs(b - a) > e:
    count += 1
    print("-----第{}次迭代---------".format(count))

    if (fx1 < fx2):  # 先定x2,再更新x1
        b = x2
        x2 = x1
        x1 = a + 0.382 * (b - a)
        fx1 = fun(x1)
        fx2 = fun(x2)
        print("x1=%f x2=%f f(x1)=%f  f(x2)=%f [%f,%f] |b-a|=%f" % (x1, x2, fx1, fx2,a,b,abs(b-a)))

    else:  # fx1 > fx2   先定x1,再更新x2
        a = x1
        x1 = x2
        x2 = a + 0.618 * (b - a)
        fx1 = fun(x1)
        fx2 = fun(x2)
        print("x1=%f x2=%f f(x1)=%f  f(x2)=%f [%f,%f] |b-a|=%f" % (x1, x2, fx1, fx2,a,b,abs(b-a)))

在这里插入图片描述
在这里插入图片描述
所有代码均为自己实现,仅供参考。

参考资料:
《最优化方法及其MATLAB实现》—许国根、赵后随等人编著

原文链接:https://blog.csdn.net/Aiden_yan/article/details/117528828






所属网站分类: 技术文章 > 博客

作者:python好学吗

链接:https://www.pythonheidong.com/blog/article/984101/8d512112ea2190a3f8c7/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

25 0
收藏该文
已收藏

评论内容:(最多支持255个字符)