一维搜索算法
① 请问MUSIC算法和LMS算法到底是怎么回事,都是用来干吗的啊
这是两种不同的算法,MUSIC算法是多重信号分类算法,是经典的空间谱估计算法,通过将接受信号分成噪声子空间和信号子空间(这两子空间正交)达到超分辨谱估计.MUSIC算法可以完成DOA(波达方向)估计和频率估计.其实质是基于一维搜索的噪声子空间算法.
LMS算法是最小均方算法，是自适应技术的基础．LMS算法是达到输入信号与期望信号有最小的均方误差的一种算法．
② music算法的理论发展及应用
MUSIC（Multiple Signal Classification多信号分类）算法是1979年由美国人R.O.Schmidt提出的，它标志着空间谱估计测向进入了繁荣发展的阶段。它将“向量空间”的概念引入了空间谱估计领域，经过三十年的发展，可以说其理论已经比较成熟。
自80年代以来，人们对基于特征分解的超分辨率空间谱估计算法进行了广泛深入的研究，并提出了一系列高效的处理方法，其中最经典的是多信号分类（MUSIC）算法，这种算法要经过一维搜索才能求出信源的来向，而相对最大似然（ML）和加权子空间拟合（WSF）等多维搜索算法的运算量已经减少了很多。以MUSIC为代表的算法存在一个缺点，即对相干信号处理的不理想。在针对相干信号源的一系列处理方案中，比较经典的是空间平滑技术，如空间平滑（SS）和修正的空间平滑（MSS）算法。然而，空间平滑技术是以损失阵列有效孔径为代价的，而且只适用于等距均匀线阵（ULA）。
事实上空间谱估计算法都是在已知信号源数目下计算的，而在实际应用中这是不可能的，只能根据观测数据对源数目进行估计。R.O.Schmidt在他的经典之作中提出了依据阵列协方差矩阵特征值的分布来估计信号源的方法。这种方法在理论上是完美的，至少对独立源和部分相关源是正确的，但实际上由于数据长度有限，很大程度上只能依靠主观判断来确定源数。
③ 最优化理论与算法的图书目录
第1章引言
1.1学科简述
1.2线性与非线性规划问题
*1.3几个数学概
1.4凸集和凸函数
习题
第2章线性规划的基本性质
2.1标准形式及图解法
2.2基本性质
习题
第3章单纯形方法
3.1单纯形方法原理
3.2两阶段法与大M法
3.3退化情形
3.4修正单纯形法
*3.5变量有界的情形
*3.6分解算法
习题
第4章对偶原理及灵敏度分析
4.1线性规划中的对偶理论
4.2对偶单纯形法
4.3原始对偶算法
4.4灵敏度分析
*4.5含参数线性规划
习题
第5章运输问题
5.1运输问题的数学模型与基本性
5.2表上作业法
5.3产销不平衡运输问题
习题
第6章线性规划的内点算法
*6.1Karmarkar算法
*6.2内点法
6.3路径跟踪法
第7章最优性条件
7.1无约束问题的极值条件
7.2约束极值问题的最优性条件
*7.3对偶及鞍点问题
习题
*第8章算法
8.1算法概念
8.2算法收敛问题
习题
第9章一维搜索
9.1一维搜索概念
9.2试探法
9.3函数逼近法
习题
第10章使用导数的最优化方法
10.1最速下降法
10.2牛顿法
10.3共轭梯度法
10.4拟牛顿法
10.5信赖域方法
10.6最小二乘
习题
第11章无约束最优化的直接方法
11.1模式搜索法
11.2Rosenbrock方法
11.3单纯形搜索法
11.4Powell方法
习题
第12章可行方向法
12.1Zoutendijk可行方向法
12.2Rosen梯度投影法
*12.3既约梯度法
12.4Frank?Wolfe方法
习题
第13章惩罚函数法
13.1外点罚函数法
13.2内点罚函数法
*13.3乘子法
习题
第14章二次规划
14.1Lagrange方法
14.2起作用集方法
14.3Lemke方法
14.4路径跟踪法
习题
*第15章整数规划简介
15.1分支定界法
15.2割平面法
15.301规划的隐数法
15.4指派问
习题
第16章动态规划简介
16.1动态规划的一些基本概念
16.2动态规划的基本定理和基本方程
16.3逆推解法和顺推解法
16.4动态规划与静态规划的关系
16.5函数迭代法
习题
参考文献
④ BP算法及其改进
传统的BP算法及其改进算法的一个很大缺点是：由于其误差目标函数对于待学习的连接权值来说非凸的，存在局部最小点，对网络进行训练时，这些算法的权值一旦落入权值空间的局部最小点就很难跳出，因而无法达到全局最小点(即最优点)而使得网络训练失败。针对这些缺陷，根据凸函数及其共轭的性质，利用Fenchel不等式，使用约束优化理论中的罚函数方法构造出了带有惩罚项的新误差目标函数。
用新的目标函数对前馈神经网络进行优化训练时，隐层输出也作为被优化变量。这个目标函数的主要特点有：
1.固定隐层输出，该目标函数对连接权值来说是凸的；固定连接权值，对隐层输出来说是凸的。这样在对连接权值和隐层输出进行交替优化时，它们所面对的目标函数都是凸函数，不存在局部最小的问题，算法对于初始权值的敏感性降低；
2.由于惩罚因子是逐渐增大的，使得权值的搜索空间变得比较大，从而对于大规模的网络也能够训练，在一定程度上降低了训练过程陷入局部最小的可能性。
这些特性能够在很大程度上有效地克服以往前馈网络的训练算法易于陷入局部最小而使网络训练失败的重大缺陷，也为利用凸优化理论研究前馈神经网络的学习算法开创了一个新思路。在网络训练时，可以对连接权值和隐层输出进行交替优化。把这种新算法应用到前馈神经网络训练学习中，在学习速度、泛化能力、网络训练成功率等多方面均优于传统训练算法，如经典的BP算法。数值试验也表明了这一新算法的有效性。
本文通过典型的BP算法与新算法的比较，得到了二者之间相互关系的初步结论。从理论上证明了当惩罚因子趋于正无穷大时新算法就是BP算法，并且用数值试验说明了惩罚因子在网络训练算法中的作用和意义。对于三层前馈神经网络来说，惩罚因子较小时，隐层神经元局部梯度的可变范围大，有利于连接权值的更新；惩罚因子较大时，隐层神经元局部梯度的可变范围小，不利于连接权值的更新，但能提高网络训练精度。这说明了在网络训练过程中惩罚因子为何从小到大变化的原因,也说明了新算法的可行性而BP算法则时有无法更新连接权值的重大缺陷。
矿体预测在矿床地质中占有重要地位，由于输入样本量大，用以往前馈网络算法进行矿体预测效果不佳。本文把前馈网络新算法应用到矿体预测中，取得了良好的预期效果。
本文最后指出了新算法的优点，并指出了有待改进的地方。
关键词：前馈神经网络，凸优化理论，训练算法，矿体预测，应用
Feed forward Neural Networks Training Algorithm Based on Convex Optimization and Its Application in Deposit Forcasting
JIA Wen-chen (Computer Application)
Directed by YE Shi-wei
Abstract
The paper studies primarily the application of convex optimization theory and algorithm for feed forward neural networks’ training and convergence performance.
It reviews the history of feed forward neural networks, points out that the training of feed forward neural networks is essentially a non-linear problem and introces BP algorithm, its advantages as well as disadvantages and previous improvements for it. One of the big disadvantages of BP algorithm and its improvement algorithms is: because its error target function is non-convex in the weight values between neurons in different layers and exists local minimum point, thus, if the weight values enter local minimum point in weight values space when network is trained, it is difficult to skip local minimum point and reach the global minimum point (i.e. the most optimal point).If this happening, the training of networks will be unsuccessful. To overcome these essential disadvantages, the paper constructs a new error target function including restriction item according to convex function, Fenchel inequality in the conjugate of convex function and punishment function method in restriction optimization theory.
When feed forward neural networks based on the new target function is being trained, hidden layers’ outputs are seen as optimization variables. The main characteristics of the new target function are as follows:
1.With fixed hidden layers’ outputs, the new target function is convex in connecting weight variables; with fixed connecting weight values, the new target function is convex in hidden layers’ outputs. Thus, when connecting weight values and hidden layers’ outputs are optimized alternately, the new target function is convex in them, doesn’t exist local minimum point, and the algorithm’s sensitiveness is reced for original weight values .
2.Because the punishment factor is increased graally, weight values ’ searching space gets much bigger, so big networks can be trained and the possibility of entering local minimum point can be reced to a certain extent in network training process.
Using these characteristics can overcome efficiently in the former feed forward neural networks’ training algorithms the big disadvantage that networks training enters local minimum point easily. This creats a new idea for feed forward neural networks’ learning algorithms by using convex optimization theory .In networks training, connecting weight variables and hidden layer outputs can be optimized alternately. The new algorithm is much better than traditional algorithms for feed forward neural networks. The numerical experiments show that the new algorithm is successful.
By comparing the new algorithm with the traditional ones, a primary conclusion of their relationship is reached. It is proved theoretically that when the punishment factor nears infinity, the new algorithm is BP algorithm yet. The meaning and function of the punishment factor are also explained by numerical experiments. For three-layer feed forward neural networks, when the punishment factor is smaller, hidden layer outputs’ variable range is bigger and this is in favor to updating of the connecting weights values, when the punishment factor is bigger, hidden layer outputs’ variable range is smaller and this is not in favor to updating of the connecting weights values but it can improve precision of networks. This explains the reason that the punishment factor should be increased graally in networks training process. It also explains feasibility of the new algorithm and BP algorithm’s disadvantage that connecting weigh values can not be updated sometimes.
Deposit forecasting is very important in deposit geology. The previous algorithms’ effect is not good in deposit forecasting because of much more input samples. The paper applies the new algorithm to deposit forecasting and expectant result is reached.
The paper points out the new algorithm’s strongpoint as well as to-be-improved places in the end.
Keywords: feed forward neural networks, convex optimization theory, training algorithm, deposit forecasting, application
传统的BP算法及其改进算法的一个很大缺点是：由于其误差目标函数对于待学习的连接权值来说非凸的，存在局部最小点，对网络进行训练时，这些算法的权值一旦落入权值空间的局部最小点就很难跳出，因而无法达到全局最小点(即最优点)而使得网络训练失败。针对这些缺陷，根据凸函数及其共轭的性质，利用Fenchel不等式，使用约束优化理论中的罚函数方法构造出了带有惩罚项的新误差目标函数。
用新的目标函数对前馈神经网络进行优化训练时，隐层输出也作为被优化变量。这个目标函数的主要特点有：
1.固定隐层输出，该目标函数对连接权值来说是凸的；固定连接权值，对隐层输出来说是凸的。这样在对连接权值和隐层输出进行交替优化时，它们所面对的目标函数都是凸函数，不存在局部最小的问题，算法对于初始权值的敏感性降低；
2.由于惩罚因子是逐渐增大的，使得权值的搜索空间变得比较大，从而对于大规模的网络也能够训练，在一定程度上降低了训练过程陷入局部最小的可能性。
这些特性能够在很大程度上有效地克服以往前馈网络的训练算法易于陷入局部最小而使网络训练失败的重大缺陷，也为利用凸优化理论研究前馈神经网络的学习算法开创了一个新思路。在网络训练时，可以对连接权值和隐层输出进行交替优化。把这种新算法应用到前馈神经网络训练学习中，在学习速度、泛化能力、网络训练成功率等多方面均优于传统训练算法，如经典的BP算法。数值试验也表明了这一新算法的有效性。
本文通过典型的BP算法与新算法的比较，得到了二者之间相互关系的初步结论。从理论上证明了当惩罚因子趋于正无穷大时新算法就是BP算法，并且用数值试验说明了惩罚因子在网络训练算法中的作用和意义。对于三层前馈神经网络来说，惩罚因子较小时，隐层神经元局部梯度的可变范围大，有利于连接权值的更新；惩罚因子较大时，隐层神经元局部梯度的可变范围小，不利于连接权值的更新，但能提高网络训练精度。这说明了在网络训练过程中惩罚因子为何从小到大变化的原因,也说明了新算法的可行性而BP算法则时有无法更新连接权值的重大缺陷。
矿体预测在矿床地质中占有重要地位，由于输入样本量大，用以往前馈网络算法进行矿体预测效果不佳。本文把前馈网络新算法应用到矿体预测中，取得了良好的预期效果。
本文最后指出了新算法的优点，并指出了有待改进的地方。
关键词：前馈神经网络，凸优化理论，训练算法，矿体预测，应用
Feed forward Neural Networks Training Algorithm Based on Convex Optimization and Its Application in Deposit Forcasting
JIA Wen-chen (Computer Application)
Directed by YE Shi-wei
Abstract
The paper studies primarily the application of convex optimization theory and algorithm for feed forward neural networks’ training and convergence performance.
It reviews the history of feed forward neural networks, points out that the training of feed forward neural networks is essentially a non-linear problem and introces BP algorithm, its advantages as well as disadvantages and previous improvements for it. One of the big disadvantages of BP algorithm and its improvement algorithms is: because its error target function is non-convex in the weight values between neurons in different layers and exists local minimum point, thus, if the weight values enter local minimum point in weight values space when network is trained, it is difficult to skip local minimum point and reach the global minimum point (i.e. the most optimal point).If this happening, the training of networks will be unsuccessful. To overcome these essential disadvantages, the paper constructs a new error target function including restriction item according to convex function, Fenchel inequality in the conjugate of convex function and punishment function method in restriction optimization theory.
When feed forward neural networks based on the new target function is being trained, hidden layers’ outputs are seen as optimization variables. The main characteristics of the new target function are as follows:
1.With fixed hidden layers’ outputs, the new target function is convex in connecting weight variables; with fixed connecting weight values, the new target function is convex in hidden layers’ outputs. Thus, when connecting weight values and hidden layers’ outputs are optimized alternately, the new target function is convex in them, doesn’t exist local minimum point, and the algorithm’s sensitiveness is reced for original weight values .
2.Because the punishment factor is increased graally, weight values ’ searching space gets much bigger, so big networks can be trained and the possibility of entering local minimum point can be reced to a certain extent in network training process.
Using these characteristics can overcome efficiently in the former feed forward neural networks’ training algorithms the big disadvantage that networks training enters local minimum point easily. This creats a new idea for feed forward neural networks’ learning algorithms by using convex optimization theory .In networks training, connecting weight variables and hidden layer outputs can be optimized alternately. The new algorithm is much better than traditional algorithms for feed forward neural networks. The numerical experiments show that the new algorithm is successful.
By comparing the new algorithm with the traditional ones, a primary conclusion of their relationship is reached. It is proved theoretically that when the punishment factor nears infinity, the new algorithm is BP algorithm yet. The meaning and function of the punishment factor are also explained by numerical experiments. For three-layer feed forward neural networks, when the punishment factor is smaller, hidden layer outputs’ variable range is bigger and this is in favor to updating of the connecting weights values, when the punishment factor is bigger, hidden layer outputs’ variable range is smaller and this is not in favor to updating of the connecting weights values but it can improve precision of networks. This explains the reason that the punishment factor should be increased graally in networks training process. It also explains feasibility of the new algorithm and BP algorithm’s disadvantage that connecting weigh values can not be updated sometimes.
Deposit forecasting is very important in deposit geology. The previous algorithms’ effect is not good in deposit forecasting because of much more input samples. The paper applies the new algorithm to deposit forecasting and expectant result is reached.
The paper points out the new algorithm’s strongpoint as well as to-be-improved places in the end.
Keywords: feed forward neural networks, convex optimization theory, training algorithm, deposit forecasting, application
BP算法及其改进
2.1 BP算法步骤
1°随机抽取初始权值ω0；
2°输入学习样本对（Xp,Yp），学习速率η，误差水平ε；
3°依次计算各层结点输出opi,opj,opk；
4°修正权值ωk+1=ωk+ηpk,其中pk=,ωk为第k次迭代权变量；
5°若误差E<ε停止，否则转3°。
2.2 最优步长ηk的确定
在上面的算法中，学习速率η实质上是一个沿负梯度方向的步长因子，在每一次迭代中如何确定一个最优步长ηk，使其误差值下降最快，则是典型的一维搜索问题，即E(ωk+ηkpk)=(ωk+ηpk)。令Φ(η)=E(ωk+ηpk)，则Φ′(η)=dE(ωk+ηpk)/dη=E(ωk+ηpk)Tpk。若ηk为(η)的极小值点，则Φ′(ηk)=0，即E(ωk+ηpk)Tpk=-pTk+1pk=0。确定ηk的算法步骤如下
1°给定η0=0,h=0.01,ε0=0.00001；
2°计算Φ′(η0),若Φ′(η0)=0,则令ηk=η0，停止计算；
3°令h=2h, η1=η0+h；
4°计算Φ′(η1)，若Φ′(η1)=0，则令ηk=η1，停止计算；
若Φ′(η1)>0，则令a=η0,b=η1；若Φ′(η1)<0，则令η0=η1，转3°；
5°计算Φ′(a)，若Φ′(a)=0，则ηk=a，停止计算；
6°计算Φ′(b)，若Φ′(b)=0，则ηk=b，停止计算；
7°计算Φ′(a+b/2),若Φ′(a+b/2)=0，则ηk=a+b/2，停止计算；
若Φ′(a+b/2)<0,则令a=a+b/2;若Φ′(a+b/2)>0，则令b=a+b/2
8°若｜a-b｜<ε0，则令，ηk=a+b/2,停止计算，否则转7°。
2.3 改进BP算法的特点分析
在上述改进的BP算法中，对学习速率η的选取不再由用户自己确定，而是在每次迭代过程中让计算机自动寻找最优步长ηk。而确定ηk的算法中，首先给定η0=0，由定义Φ(η)=E(ωk+ηpk)知，Φ′(η)=dE(ωk+ηpk)/dη=E(ωk+ηpk)Tpk，即Φ′(η0)=-pTkpk≤0。若Φ′(η0)=0，则表明此时下降方向pk为零向量，也即已达到局部极值点，否则必有Φ′(η0)<0，而对于一维函数Φ(η)的性质可知，Φ′(η0)<0则在η0=0的局部范围内函数为减函数。故在每一次迭代过程中给η0赋初值0是合理的。
改进后的BP算法与原BP算法相比有两处变化，即步骤2°中不需给定学习速率η的值；另外在每一次修正权值之前，即步骤4°前已计算出最优步长ηk。