一维搜索算法
成功-失败法 求搜索区间黄金分割法 求最小值点二次插值法 求最小值点一维搜索函数 多维直接搜索算法
坐标轮换法 基础运算
多元函数任意一点求导
此文章为《机器学习》西瓜书 算法代码 python实现 的基础
一维搜索算法一维搜索算法传入一个凸函数，返回其最小值点
一维搜索算法需要由两部分组成
确定搜索区间在搜索区间内寻找最小值点
以下代码均经过本人在 python3.7 下测试成功，测试代码就不放了
成功-失败法 求搜索区间此处代码有一个不完善的地方，就是当传入的函数定义域不为R时，需自行调整 x0
实际上我们可以重新设计该算法，传入函数的左范围点或右范围点，不传入默认为无穷
h 的调整需加入参数 xl 和 xr 以防止越界
但本人较为懒惰，有需要请评论或私聊讨论
def success_failure_method(f,x0=0,h=5,maxiters=1000):
'''
成功-失败法求搜索区间
必须传入有最小值的严格凸函数
有可能搜索区间长度为0 代表输入的x0即为最优解
'''
y0 = f(x0)
y1 = f(x0+h)
while maxiters:
if y0 > y1:
y2 = f(x0+3*h)
if y1 > y2:
x0 = x0 + h
y0 = y1
y1 = y2
h = 2*h
maxiters -= 1
continue
else:
if h > 0:
return x0,x0+3*h
else:
return x0+3*h,x0
elif y0 == y1:
if h > 0:
return x0,x0+h
else:
return x0+h,x0
else:
h = -h/4
y1 = f(x0+h)
maxiters -= 1
continue
print('成功失败法传入了非凸函数')
return 0,0
黄金分割法 求最小值点
def golden_section_method(f,a,b,acy=0.001,maxiters=1000):
'''
黄金分割法求最小值点
传入函数f 搜索区间[a, b]
'''
alpha = 0.381966
beta = 1 - alpha
x1 = a + alpha*(b-a)
x2 = a + b - x1
y1 = f(x1)
y2 = f(x2)
while maxiters:
if y1 > y2:
a = x1
if b - a < acy:
break
else:
x1 = x2
y1 = y2
x2 = alpha*a + beta*b
y2 = f(x2)
maxiters -= 1
continue
else:
b = x2
if b - a < acy:
break
else:
x2 = x1
y2 = y1
x1 = beta*a + alpha*b
y1 = f(x1)
maxiters -= 1
continue
else:
print('黄金分割法未收敛到精度')
return (a+b)/2
二次插值法 求最小值点
def quadratic_interpolation_method(f,x1,x3,acy=0.001,maxiters=1000,simplify=False):
'''
二次插值法求最小值点
传入函数f 搜索区间[x1, x3]
simplify 传入True时 使用化简后的二次插值法 但迭代次数更多
'''
x2 = (x1+x3)/2
if abs(x1-x3) < acy:
return x2
if not simplify:
while maxiters:
y1 = f(x1);y2 = f(x2);y3 = f(x3)
k1 = (y1-y3)/(x1-x3)
k2 = ((y2-y1)/(x2-x1)-k1)/(x2-x3)
xt = (x1+x3-k1/k2)/2
# 这个地方绝对不能抄书上的 有误
if abs(xt-x2) < acy:
break
elif xt < x2:
if f(xt) < y2:
x3 = x2
x2 = xt
else:
x1 = xt
maxiters -= 1
continue
else:
if f(xt) < y2:
x1 = x2
x2 = xt
else:
x3 = xt
maxiters -= 1
continue
else:
print('二次插值法未收敛到精度')
return xt
else:
while maxiters:
y1 = f(x1);y2 = f(x2);y3 = f(x3)
delta = (x3-x1)/2
xt = x2 + (y1-y3)*delta/2/(y1-2*y2+y3)
if abs(xt-x2) < acy:
break
elif xt < x2:
if f(xt) < y2:
x3 = x2
else:
x1 = xt
x2 = (x1+x3)/2
maxiters -= 1
continue
else:
if f(xt) < y2:
x1 = x2
else:
x3 = xt
x2 = (x1+x3)/2
maxiters -= 1
continue
else:
print('二次插值法未收敛到精度')
return xt
一维搜索函数
def one_dimensional_search(f,x0=0,method='golden_section',acy=0.001,maxiters=1000,h=5):
'''
一维搜素算法
method可选择如下:
golden_section
quadratic_interpolation
simplified_quadratic_interpolation
'''
a,b = success_failure_method(f,x0=x0,h=h,maxiters=maxiters)
if method == 'golden_section':
ans = golden_section_method(f,a,b,acy=acy,maxiters=maxiters)
elif method == 'quadratic_interpolation':
ans = quadratic_interpolation_method(f,a,b,acy=acy,maxiters=maxiters)
elif method == 'simplified_quadratic_interpolation':
ans = quadratic_interpolation_method(f,a,b,acy=acy,maxiters=maxiters,simplify=True)
else:
print('Input method does not exist!')
return None
return ans
多维直接搜索算法
坐标轮换法
def univarite_search_technique(f,d,ini_point=None,acy=0.01,maxiters=1000):
'''
坐标轮换法
传入函数 维度 初始点
'''
if ini_point is None:
point = [0 for i in range(d)]
else:
point = list(ini_point)
difference = 1000
old = f(*point)
while abs(difference) > acy and maxiters:
for i in range(d):
part1 = point[:i]
part2 = point[i+1:]
fun = lambda x:f(*part1,x,*part2)
t = one_dimensional_search(fun,point[i])
point[i] = t
new = f(*point)
difference = new - old
old = new
maxiters -= 1
return point
基础运算
多元函数任意一点求导
def diff(f,x,acy=0.01,maxiters=1000):
ans = []
y0 = f(*x)
for i in range(len(x)):
delta = 1
part1 = x[:i]
part2 = x[i+1:]
old = f(*part1,x[i]+delta,*part2) - y0
oldd = old/delta
while maxiters:
delta /= 10
new = f(*part1,x[i]+delta,*part2) - y0
newd = new/delta
if abs(new-old) < acy and abs(newd-oldd) < acy:
break
else:
old = new
oldd = newd
maxiters -= 1
ans.append(newd)
return ans
