线性搜索的计算方法

‘壹’ C语言编程：输入一个整数，输出这几个数的和，例如1987，1+9+8+7=25

第一题：
#include<stdio.h>
void
main()
{
int
a;
int
sum=0;
scanf("%d",&a);
while(a!=0)
{
sum=sum+a%10;
a=a/10;
}
printf("%d\n",sum);
}
第二题：
#include<stdio.h>
void
main()
{
int
a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
if(a[i]%3==0&&a[i]%5!=0)
printf("%d\t",a[i]);
}
第三题：
方法一：线性查找法是最简单的查找方法。若在一个一维数组中查找给定的值x，过程是：先从第一个元素查起，看它是否等于x，若等于x，即找到了，否则，接着查第二个元素……线配旅饥性查找法不要求被操作的数组已排序。
#include<stdio.h>
void
main()
{
int
a[10]={12,4,23,56,34,2,15,68,56,1};
int
x,i,flag=0;
scanf("%d",&x);
for(i=0;i<10;i++)
if(a[i]==x)
{
flag=1;
break;
}
if(flag==0)printf("not
found.\n");
else
printf("a[%d]=%d\n",i,a[i]);
}
方法二：.二分法：­
当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。­
基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找­，直到找到为止。­
假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界镇旅，mid=（front+end）/2.­
1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。­
2.另新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。­
3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。­
如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。­
例：在有序的有N个元素的数组中查找用户输进去的数据x。­
算法如下：­
1.确定查找范围front=0，end=N-1，计算中项培返mid（front+end）/2。­
2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。­
3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给front，并重新计算mid，转去执行步骤2。­
#include<stdio.h>
#define
N
8
void
main()
{
int
a[N];
int
front,end,mid,x,i;
printf("请输入已排好序的a数组元素\n");
for(i=0;i<N;i++)
scanf("%d",&a[
i
]);
printf("请输入待查找的数x\n");
scanf("%d",&x);
front=0;end=N-1;
mid=(front+end)/2;
while(front<end&&a[mid]!=x)
{
if(a[mid]<x)front=mid+1;
if(a[mid]>x)end=mid-1;
mid=(front+end)/2;
}
if(a[mid]!=x)printf("没找到。\n");
else
printf("找到了，在第%d项里。\n",mid+1);
}

‘贰’ 梯度下降中的线性搜索计算学习率是怎么理解

梯度下降法是一个最优化算法，通常也称为最速下降法。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。
梯度下降法可以用于求解非线性方程组。
顾名思义，梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。

表示梯度方向上的中首槐搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标看做是ak+1的函数，然后求满足f(ak+1)的最小值即可。
因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅芹笑值接近0即可，可以设置个非常小卖友的常数阈值。

‘叁’ 线性搜索的算法步骤

procerelinearsearch(x:整数,a1,a2,...,an:不罩贺猛同整数)
i:=1
while(i<=n&&x=/(不等于)ai)
i:=i+1
ifi<=nthenlocation:=i
elselocation:=0
{location是等于拍戚x的下标,或是0(找不到)}
最物桥坏情况下使用O(n)次比较,2分搜索算法最坏情形复杂度O(logn)次比较,2分搜索算法比之线性搜索最坏情况下要好.

‘肆’ 数学优化问题(最优化问题)

  数学优化（Mathematical Optimization）问题，也叫最优化问题，是指在一定约束条件下，求解一个目标函数的最大值（或最小值）问题。
  数学优化问题的定义为：给定一个目标函数（也叫代价函数） f : A → R ，寻找一个变量（也叫参数） x ^∗ ∈ D ，使得对于所有 D 中的 x ， f(x ^∗ ) ≤ f(x) （最小化）；或者 f(x ^∗ ) ≥ f(x) （最大化），其中 D 为变量 x 的约束集，也叫可行域； D 中的变量被称为是可行解。

  根据输入变量 x 的值域是否为实数域，数学优化问题可以分为离散优化问题和连续优化问题。

  离散优化（Discrete Optimization）问题是目标函数的输入变量为离散变量，比如为整数或有限集合中的元素。连续优化（Continuous Optimization）问题是目标函数的输入变量为连续变量 x ∈ R ^d ，即目标函数为实函数。离散优化问题主要有两个分支：

  离散优化问题的求解一般都比较困难，优化算法的复杂度都比较高。后面的内容主要以连续优化为主。

  在连续优化问题中，根据是否有变量的约束条件，可以将优化问题分为无约束优化问题和约束优化问题。
   无约束优化问题（Unconstrained Optimization） 的可行域为整个实数域 D = R ^d ，可以写为
其中 x ∈ R ^d 为输入变量， f : R ^d → R 为目标函数。
   约束优化问题（Constrained Optimization） 中变量 x 需要满足一些等式或不等式的约束。约束优化问题通常使用拉格朗日乘数法来进行求解。

  如果目标函数和所有的约束函数都为线性函数，则该问题为 线性规划问题（Linear Programming） 。相反，如果目标函数或任何一个约束函数为非线性函数，则该问题为 非线性规划问题（Nonlinear Programming） 。
  在非线性优化问题中，有一类比较特殊的问题是 凸优化问题（Convex Programming） 。在凸优化问题中，变量 x 的可行域为凸集，即对于集合中任意两点，它们的连线全部位于在集合内部。目标函数 f 也必须为凸函数，即满足
  凸优化问题是一种特殊的约束优化问题，需满足目标函数为凸函数，并且等式约束函数为线性函数，不等式约束函数为凹函数。

   优化问题 一般都是通过 迭代 的方式来求解：通过猜测一个初始的估计 x ₀ ，然后不断迭代产生新的估计 x ₁ , x ₂ , · · · x _t ，希望 x _t 最终收敛到期望的最优解 x ^∗旅散纳 。一个好的优化算法应该是在 一定的时间或空间复杂度下能够快速准确地找到最优解。同时，好的优化算法受初始掘培猜测点的影响较小，通过迭代能稳定地找到最优解 x ^∗ 的邻域，然后迅速收敛于 x ^∗ 。
  优化算法中常用的迭代方法有 线性搜索和置信域方法 等。线性搜索的策略是寻找方向和步长，具体算法有梯度下降法、牛顿拆没法、共轭梯度法等。

  对于很多非线性优化问题，会存在若干个局部的极小值。局部最小值，或局部最优解 x ^∗ 定义为：存在一个δ > 0，对于所有的满足|| x − x∗|| ≤ δ 的 x ，公式 f(x ^∗ ) ≤ f(x) 成立。也就是说，在 x ^∗ 的附近区域内，所有的函数值都大于或者等于 f(x ^∗ ) 。对于所有的 x ∈ A ，都有 f(x∗) ≤ f(x) 成立，则 x ^∗ 为全局最小值，或全局最优解。一般的，求局部最优解是容易的，但很难保证其为全局最优解。 对于线性规划或凸优化问题，局部最优解就是全局最优解 。

‘伍’ 牛顿法、黄金分割法、二次插值法实验（最优化1）

在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，，所以最优化理论和方法日益受到重视。

无约束最优化计算方法是数隐森值计算领域中十分活跃的研究课题之一，快速的求解无约束最优化问题，除了自身的重要性以外，还体现在它也构成一些约束最优化问题的子问题。因此，对于无约束最优化问题，如何快速高精度的求解一直是优化工作者十分关心的事。本文验证求解 一维无约束最优化问题 的三种线性搜索方法，分别是牛顿法、黄金分割法，二次插值法。

min ⁡f(x)=3x ⁴ - 4x ³ -12x ²

牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊方法（Newton-Raphson method）,它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法,其基本思想是利用目标函数的二次Taylor展开，并将其极小化。牛顿法使用函数 f(x)的泰勒级数的前面几项来寻找方程 "f(x)=0" 的根。牛顿法是求方程根的重要方法之一，其困改最大优点是在方程 "f(x)=0" 的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。

方程 f(x)=0 的根 x ^* 可解释为曲线y=f(x)轴的焦点的横坐标。如下图：

设 x[k]是根 x ^* 的某个近似值，过曲线 y=f(x)上横坐标为 x[k]的点P[k]引切线，并将该切线与 x轴的交点 的横坐标 x_{k+1}_作为 x ^* 的新的近似值。鉴于这种几何背景，牛顿法亦称为切线法。

将f(x ^k+1 )在x=x ^k 处一阶泰勒展开：

公式不打了
令函数趋于0，求与x轴交点：

分别取-1.5,0.4,1.0,1.6,2.8

在凸函数很初始点选取好的情况下，收敛快。

Ø 计算二阶导数，计算量大

Ø 要求函数二阶可微

Ø 收敛性与初始点选取有关

黄金分割法适用于[a,b]区间上的任何单股函数求极小值问题，对函数除要求“单峰”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间 ？内适当插入两点 ？，并计算其函数值。 ？将区间分成三段，应用函数的单峰性汪携判质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。

一 维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。如图所示

黄金分割法是用于一元函数 ？在给定初始区间 ？内搜索极小点？的一种方法。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。

具体步骤是：在区间 ？内取点： ？分为三段。如果 ？,令？；如果 ？，令 <？,如果 ？都大于收敛精度？重新开始。因为 ？为单峰区间，这样每次可将搜索区间缩小0.618倍或0.382倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区 ？逐步缩小，满足预先给定的精度时，即获得一维优化问题的近似最优解。

[-2,0],[1,3]

很巧妙地使每次分割点都为上次的黄金分割点，可以复用上次运算的结果，简化计算。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而着称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。

在求解一元函数?的极小点时，在搜索区间中用低次（通常不超过三次）插值多项式?来近似目标函数，后求该多项式的极小点（比较容易计算），并以此作为目标函数?的近似极小点。如果其近似的程度尚未达到所要求的精度时，反复使用此法，逐次拟合，直到满足给定的精度时为止。

考虑二次多项式

则

令 ，得 。这意味着我们要求a，b。
今考虑在包含 的极小点 的搜索区间 中，给定三个点 ， ， ，满足
< <
> <
利用三点处的函数值 ， ， 构造二次函数，并要求插值条件满足

令 ，i=1,2,3。解上述方程组得

于是，二次函数 的极小点为

设 。求得 和 以后，如果
≤ ，当 > 时，
或者如果
≤ ，当 < 时。
则我们认为收敛准则满足。如果 < ,则极小点估计为 ，否则为 。
若终止准则不满足，则利用 提供的信息，从 ， ， 和 中选出相邻的三个点，将原来的搜索区间缩小，然后重复上述过程，直到终止准则满足为止。

初始步 给出?，?，?，满足上述设计步骤。
步1 由上述设计步骤计算?。
步2 比较?和?的大小，如果?>?，则转步3；否则转步4。
步3 如果?≤?，则
?，?，?，?，
转步5；否则?，?，转步5。
步4 若?，则
?，?，?，?，
转步5；否则?，?，转步5。
步5 如果收敛准则满足，停止迭代；否则转步1，在新的搜索区间[?,?]上按公式计算二次插值函数的极小点?。

-2.5,-1.4,-0.3
-0.3,1.5,3.3.

插值法仅需计算函数值，不涉及导数、Hesse矩阵等的计算，计算起来相对比较简单，能够适用于非光滑和导数表达式复杂或表达式写不出等种种情形。

当迭代步数较多时，计算过程比较复杂，计算量较大，计算起来比较麻烦。当迭代点离目标函数的最优解较远时，追求线性搜索的精度反而会降低整个算法的效率。

用符号推导画图

picture.py

Gold_ratio.py

Newton.py

Polynomial_interpolation.py