一、概观
创新互联公司主要业务有网站营销策划、成都网站设计、成都网站制作、微信公众号开发、重庆小程序开发、HTML5建站、程序开发等业务。一次合作终身朋友,是我们奉行的宗旨;我们不仅仅把客户当客户,还把客户视为我们的合作伙伴,在开展业务的过程中,公司还积累了丰富的行业经验、成都全网营销推广资源和合作伙伴关系资源,并逐渐建立起规范的客户服务和保障体系。
scipy中的optimize子包中提供了常用的最优化算法函数实现。我们可以直接调用这些函数完成我们的优化问题。optimize中函数最典型的特点就是能够从函数名称上看出是使用了什么算法。下面optimize包中函数的概览:
1.非线性最优化
fmin -- 简单Nelder-Mead算法
fmin_powell -- 改进型Powell法
fmin_bfgs -- 拟Newton法
fmin_cg -- 非线性共轭梯度法
fmin_ncg -- 线性搜索Newton共轭梯度法
leastsq -- 最小二乘
2.有约束的多元函数问题
fmin_l_bfgs_b ---使用L-BFGS-B算法
fmin_tnc ---梯度信息
fmin_cobyla ---线性逼近
fmin_slsqp ---序列最小二乘法
nnls ---解|| Ax - b ||_2 for x=0
3.全局优化
anneal ---模拟退火算法
brute --强力法
4.标量函数
fminbound
brent
golden
bracket
5.拟合
curve_fit-- 使用非线性最小二乘法拟合
6.标量函数求根
brentq ---classic Brent (1973)
brenth ---A variation on the classic Brent(1980)ridder ---Ridder是提出这个算法的人名
bisect ---二分法
newton ---牛顿法
fixed_point
7.多维函数求根
fsolve ---通用
broyden1 ---Broyden’s first Jacobian approximation.
broyden2 ---Broyden’s second Jacobian approximationnewton_krylov ---Krylov approximation for inverse Jacobiananderson ---extended Anderson mixing
excitingmixing ---tuned diagonal Jacobian approximationlinearmixing ---scalar Jacobian approximationdiagbroyden ---diagonal Broyden Jacobian approximation8.实用函数
line_search ---找到满足强Wolfe的alpha值
check_grad ---通过和前向有限差分逼近比较检查梯度函数的正确性二、实战非线性最优化
fmin完整的调用形式是:
fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不过我们最常使用的就是前两个参数。一个描述优化问题的函数以及初值。后面的那些参数我们也很容易理解。如果您能用到,请自己研究。下面研究一个最简单的问题,来感受这个函数的使用方法:f(x)=x**2-4*x+8,我们知道,这个函数的最小值是4,在x=2的时候取到。
from scipy.optimize import fmin #引入优化包def myfunc(x):
return x**2-4*x+8 #定义函数
x0 = [1.3] #猜一个初值
xopt = fmin(myfunc, x0) #求解
print xopt #打印结果
运行之后,给出的结果是:
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 16
Function evaluations: 32
[ 2.00001953]
程序准确的计算得出了最小值,不过最小值点并不是严格的2,这应该是由二进制机器编码误差造成的。
除了fmin_ncg必须提供梯度信息外,其他几个函数的调用大同小异,完全类似。我们不妨做一个对比:
from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):
return x**2-4*x+8
x0 = [1.3]
xopt1 = fmin(myfunc, x0)
print xopt1
xopt2 = fmin_powell(myfunc, x0)
print xopt2
xopt3 = fmin_bfgs(myfunc, x0)
print xopt3
xopt4 = fmin_cg(myfunc,x0)
print xopt4
给出的结果是:
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 16
Function evaluations: 32
[ 2.00001953]
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 53
1.99999999997
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 12
Gradient evaluations: 4
[ 2.00000001]
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 15
Gradient evaluations: 5
[ 2.]
我们可以根据给出的消息直观的判断算法的执行情况。每一种算法数学上的问题,请自己看书学习。个人感觉,如果不是纯研究数学的工作,没必要搞清楚那些推导以及定理云云。不过,必须了解每一种算法的优劣以及能力所及。在使用的时候,不妨多种算法都使用一下,看看效果分别如何,同时,还可以互相印证算法失效的问题。
在from scipy.optimize import fmin之后,就可以使用help(fmin)来查看fmin的帮助信息了。帮助信息中没有例子,但是给出了每一个参数的含义说明,这是调用函数时候的最有价值参考。
有源码研究癖好的,或者当你需要改进这些已经实现的算法的时候,可能需要查看optimize中的每种算法的源代码。在这里:https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聪明的你肯定发现了,顺着这个链接往上一级、再往上一级,你会找到scipy的几乎所有源码!
题目:有一个升序的数组,数组中可能有正数、负数或者0,求数组中元素的绝对值最小的数。例如,数组[-10, -5, -2, 7, 15, 50],该数组中绝对值最小的数是-2。
分析:二分法。该题可分为以下三种情况:
(1)如果数组第一个元素为非负数,那么minNum = arr[0]
(2)如果数组最后一个值为负数,那么minNum = arr[-1]。
(3)如果数组中既有正数又有负数,首先找到正数与负数的分界点,如果分界点恰好为0,那么0为最小值。否则通过比较分界点左右的正数与负数的绝对值来确定最小数。
如何查找正数与负数的分界点呢?采用二分法,主要思路:取数组中间位置的值a[mid],并将它与0值比较,比较结果分为如下三种情况:
(1)如果a[mid] == 0,那么这个数就是绝对值最小的数。
(2)如果a[mid] 0,a[mid - 1] 0,那么通过比较a[mid]与a[mid - 1]的绝对值就可以找到数组中绝对值最小的数;如果a[mid - 1] == 0, 那么a[mid - 1]就是要找的数;否则接着在数组的左半部分查找。
(3)如果a[mid] 0,a[mid + 1] 0,那么通过比较a[mid]与a[mid +1]的绝对值就可以找到数组中绝对值最小的数;如果a[mid + 1] == 0, 那么a[mid + 1]就是要找的数;否则接着在数组的右半部分查找。
code:
def findMinNum(arr):
if arr is None or len(arr) = 0:
return
# [1] 数组中没有负数
if arr[0] = 0:
return arr[0]
# [2] 数组中没有正数
if arr[-1] = 0:
return arr[-1]
# [3] 数组中既有正数又又负数
mid = None
absMin = None
begin = 0
end = len(arr) - 1
while begin end:
mid = begin + (end - begin) 1
# 如果arr[mid] == 0,则是绝对值最小的数
if arr[mid] == 0:
return 0
# 如果大于0, 正负数的分界点在左侧
elif arr[mid] 0:
# 继续在数组的左半部分查找
if arr[mid - 1] 0:
end = mid - 1
elif arr[mid - 1] == 0:
return 0
# 找到正负数的分界点
else:
break # 如果小于0, 在数组右半部分查找
else:
# 在数组的右半部分继续查找
if arr[mid + 1] 0:
begin = mid + 1
elif arr[mid + 1] == 0:
return 0
else:
break
# 获取正负数分界点处绝对值最小的值
if (arr[mid] 0):
if arr[mid] abs(arr[mid - 1]):
absMin = arr[mid]
else:
absMin = arr[mid - 1]
else:
if abs(arr[mid]) abs(arr[mid + 1]):
absMin = arr[mid]
else:
absMin = arr[mid + 1]
return absMin
if __name__ == "__main__":
arr = [-10, -5, -2, 7, 15, 50]
print(findMinNum(arr))
代码有两个地方有问题
1:19行的return缩进有问题,19行的return不应该出现在一个非方法的地方
2: 代码有可能出现死循环,在我输入a:10, b:10, c:10, d:10的时候出现死循环,请检查代码逻辑
我已经调整好了
def f(x):
s=(a*x)**3+(b*x)**2+(c*x)+d
return s
a=int(input("a"))
b=int(input("b"))
c=int(input("c"))
d=int(input("d"))
mid = 0
for i in range(-100,100,1):
x1=int(i)
x2=int(i+1)
if f(x1)*f(x2)0:
lo,hi=x1,x2
while hi-lo0.01:
mid=(lo+hi)/2
if f(lo)*f(mid)0:
hi=mid
else:
lo=mid
else:
pass
print mid
import math
def erfenfa(function, a, b): #定义函数,利用二分法求方程的根,function为具体方程,a,b为根的取值范围
start = a
end = b
if function(a) == 0:
return a
elif function(b) == 0:
return b
elif function(a) * function(b) 0:
print("couldn't find root in [a,b]")
return
else:
mid = (start + end) / 2
while abs(start - mid) 0.0000001:
if function(mid) == 0:
return mid
elif function(mid) * function(start) 0:
end = mid
else:
start = mid
mid = (start + end) / 2
return mid
def f(x):#定义构造方程式函数
return math.pow(x, 5) -15*math.pow(x, 4) +85*math.pow(x, 3)-225*pow(x,2)+274*x - 121
print(round(erfenfa(f, 1.5, 2.4),6))
def erfen(low,high):
while low high:
mid=(low+high)/2
if f(low)*f(mid)0:
high=mid
elif f(mid)*f(high )0:
low=mid
return mid
这个函数没有结束 检查一下如何设置退出条件
首先二分法肯定需要一个“不断”二分的过程, 你的代码里面连一个循环都没有,肯定是不对的吧?
其次按照你的代码的思路,如果当前估算值guess的平法比x大,那就往0那边靠,否则就往1那边靠,这个好像也不对吧?
二分法的实现方法应该是,在区间[left, right]里面找x的开方,令估算值为guess等于区间的中点,如果guess比实际的大,那就把区间缩小一半,令到右端点移动到中点,如果guess比实际的小,也是将区间缩小一半,但是是令左端点移动到中点。这样每次缩小一半的区间,直到区间的长度非常非常小,那就认为区间的两个端点是相等的了,这个时候就得到了答案。
import math
def main():
x = input('x=')
n = 0
if x = 1 and x = 0:
left = 0.
right = 1.
while right - left = 0.0000001:
guess = (left + right) / 2.
if guess ** 2 - x = 0.0000001:
right = guess
else:
left = guess
#return guess
print 'sqrt(x) is', left
else:
print 'x should be in [0,1]'
if __name__ == '__main__':
main()
我按照你的思路又写了另外一种方法:
def second():
x = input('x=')
n = 0
if x = 1 and x = 0:
movelen = (1 + 0) / 4.
guess = (1 + 0) / 2.
while abs(guess ** 2 - x) = 0.0000001:
if (guess ** 2 - x) = 0.0000001:
guess = guess - movelen
else:
guess = guess + movelen
movelen = movelen / 2.
print 'sqrt(x) is', guess
else:
print 'x should be in [0,1]'