数学期望极小值的几种求法

大家好，欢迎来到IT知识分享网。

前言：

其中一维搜索方法这种思想，在图像二值化里面有应用。像二维码算法里面的条形码二值化，就是这种算法的进阶版。

缺点是只能按照一个方向进行搜索，且步伐需要调整。

目录：

数学期望例子
一维搜索方法求极值
黄金分隔法求极值

一数学期望例子

普查某种疾病，为此要抽验N个人血，有两种方法：

方案1：每个人分别去检验，这需要检验N次

方案2: k个人混合在一起检验，如果检验出来呈阳性，就全部检测一次，需要K+1一次，否则只检验一次。

假设每个人呈阳性概率为p,阴性概率为q(q=1-p).

求：如果按照第二种方案，可以减少检验次数，且k取什么值最合适

解：

X	$\frac{1}{k}$	$\frac{k+1}{k}$
		–

X的数学期望为

$E(x)=\frac{1}{k}q^k+(1+\frac{1}{k})(1-q^k)$

$=1-q^k+\frac{1}{k}$

N个人平均化验次数为

$N(1-q^k+\frac{1}{k})<N$

则，只要选择合适的k,使得

$L=1-q^k+\frac{1}{k}<1$ ，二阶导数小于0，有极小值

""" Created on Fri Oct 16 14:41:02 2020 @author: chengxf2 """ import numpy as np import matplotlib.pyplot as plt def Draw(): q = 0.9 k = np.arange(2,20,1) L =1-np.power(q,k)+1/k plt.plot(k,L) plt.show() Draw()

要取合适的k,使得L最小. $k \in [2,N]$

除了牛顿迭代法，这里介绍两种方法，一维搜索区间法，黄金分割法，求解极小值

二一维搜索的搜索区间

迭代公式：

$X_{k+1}=x_k+\alpha s_k$

其中：

x_k : 当前点

$x_{k+1}$ : 下一个点

$\alpha$ : 步长因子

s_k : 当前搜索的步伐大小，以及方向

如上图，极小值点具有如下特征：

$f(x_{k+1})\leq f(x_{k+2})\leq f(x_{k+3})$

思想：

从一点出发，找到大，小，大特征的三个点，如果一个方向不成功，就反过来寻找

算法流程：

初始化：

0,\alpha>0″>,其中h 为步伐

x_1=x_0

$x_2=x_1+\alpha h$

if f_2<f_1

前进计算Forward

else(两点换位)

h=-h;

后退计算Backward

Forward( 前进计算）

$x_3=x_2+\alpha h$

if $f_2\leq f_3$ :

return [a, b] =[ x_1,x_3 ]

else

h = 2h

return Forward

Backward( 反向计算）

$x_3=x_2+\alpha h$ ;

if $f_3\geq f_2$

return

else

return Backward

# -*- coding: utf-8 -*- """ Created on Wed Oct 21 15:32:43 2020 @author: chengxf2 """ import numpy as np class Find(): """ 计算f值 args k return f """ def Calc(self,k): #f= np.power(a,2)-7*a+10 q = 0.9 #k = np.arange(2,20,1) f =1-np.power(q,k)+1/k return f def __init__(self): self.h = 1.0 #搜索步伐 self.alpha = 1.0 #alpha self.iterNum = 0 self.x0 = 2.0 """ 前进运算 args x1: 左边点 x2: 中间点 a3: 右边点 """ def Forward(self,x1,x2,f1,f2,h): #print("\n Forward :",a1,a2,a3,f1,f2,f3,h) self.iterNum = self.iterNum+1 x3 = x2+h*self.alpha f3 = self.Calc(x3) #调到step1 if f2<=f3: #大 小 大 找到了 a = x1 #左边点 b = x2 #中间点 c = x3 #右边点 return a,b,c else: #f2>f3 大 小 小 h = 2*h x1 = x2 #这个点是大的 f1 = f2 x2 = x3 f2 =f3 return self.Forward(x1,x2,f1,f2,h) #再做前进运算 """ 反向运算 args a1: 左边点 a2: 中间点 a3: 右边点 """ def Backward(self,x1,x2,f1,f2,h): #移动x1,x2 指针，保持x2为最小点位置 x3 = x2+h*self.alpha f3 = self.Calc(x3) if f3>=f2: #大 小 大 找到了 a = x1 #左边点 b = x2 #右边点 c = x3 #极小点 return a,b,c else: #f3<f2 大 小 小 h = 2*h x1 = x2 #这个点是大的 f1 = f2 x2 = x3 f2 =f3 return self.Forward(x1,x2,f1,f2,h) #再做前进运算 def Run(self): print("\n =======一维搜索===") a= 0 b =0 c = 0 x1 = self.x0 f1 = self.Calc(x1) x2 = x1+self.h*self.alpha f2 = self.Calc(x2) if f2<f1: # 前进运算 h = self.h a,b,c=self.Forward(x1,x2,f1,f2,h) print("\n 左区间 : ",a,"\t 极小点 : ",b,"\t 右区间 ",c,"\t 迭代次数 ",self.iterNum) else: #后退算法 h = -self.h m = x1 #a3 只是中间值，保存f1 n = f1 x1= x2 f1= f2 x2 = m f2 = n a,b,c = self.Backward(x1,x2,f1,f2,h) print("\n 反向 a: ",a,"\t b: ",b,"\c ",c) fd = Find() fd.Run()

运算结果

=======一维搜索===

左区间 : 3.0 极小点 : 4.0 右区间 6.0 迭代次数 2

三黄金分隔法

缺点：当区间有全局极小值，但是多个极小值的时候，无法找到全局极小值

算法流程

x_1,x_2 始终落在极小值区间[a,b]的黄金分割点上

算法流程：

L=b-a

迭代 (step1)

a-b<tol 终止

if f_2″ />

跳转到step1

else

跳转到step1

# -*- coding: utf-8 -*- """ Created on Mon Oct 26 10:51:21 2020 @author: chengxf2 """ import numpy as np class Golden(): """ 一维函数 Args f: 概率值 """ def Calc(self,x): q = 0.9 f =1-np.power(q,x)+1/x return f def __init__(self): self.tol = 0.5 #精度要去 self.T = 0.618 #黄金分割系数 self.k = 1 #迭代次数 self.N = 100 #总人数 self.a = 0 self.b = 10 """ 迭代 args a: 区间左 b: 区间右 """ def Loop(self): a = 2 b = self.N for k in range(self.N): x1 = a +(1.0-self.T)*(b-a) #x1 x2 = a +self.T*(b-a) #x2点 if (b-a)<self.tol : c = int((a+b)/2.0+0.5) #四舍五入取整数 print("\n 极小值点 ",c) return c f1 = self.Calc(x1) f2 = self.Calc(x2) if f1>f2: #截取左边的 # 重新切换黄金分割点 a = x1 x1 = x2 x2 = x1+ self.T*(b-a) else: # print("\n 右边 截取 ") b = x2 #截取右边的 x2 = x1 x1 = a + (1-self.T)*(b-a) gd = Golden() gd.Loop()

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/139053.html

数学期望 极小值的几种求法

相关推荐

发表回复

数学期望极小值的几种求法