线性规划(LP)基本概念和搜索算法

标引

可以用一个符号描述一系列类似的数量值

线性方程

一个方程，如果他是关于决策变量的常熟加权求和形式，则该方程式线性方程(liner)，佛则该方程为非线性方程(non-linear)

线性规划

目标函数 $f$ 以及约束方程 $g_1,...,g_m$ 中均为关于决策变量的线性方程，则该优化模型为线性规划(linear program, LP)，其中目标函数可以为满足约束的任意整数或者分数

目标函数 $f$ 以及约束方程 $g_1,...,g_m$ 中存在关于决策变量的线性方程，则该优化模型为非线性规划(nonlinear program, LP)，其中目标函数可以为满足约束的任意整数或者分数

整数规划和混合整数规划

一个优化模型，如果他的决策变量中存在离散变量，则该优化模型位整数规划(integer program, IP)，如果整数规划的所有决策变量均为离散变量，则该整数规划为纯整数规划(pure integer program)；否则为混合整数规划(mixed integer program)。

搜索算法

搜索算法(improving search)通过检查邻域来寻找比当前更好地解，若有改进则替换当前解，继续迭代，直到邻域中没有更好的解为止。搜索算法又称为局部改进(local improvement)，爬山算法(hillclimbing)，局部搜索(local search)或邻域搜索(neighborhood search)

倘若一组可行解周围足够小的的邻域内没有优于该解的可行点，则称为局部最优解(local optimum)，最小化(最大化)问题存在局部最小(最大)解。

如果在全局范围内不存在目标值优于某可行解的其他可行点，则称为全局最优解(global optimum)，最小化(最大化)问题存在全局最小(最大)解

搜索算法沿 $x^{(t+1)}\leftarrow x^{(t)}+\lambda \Delta x$ 由当前点 $x^{(t)}$ 向下一个搜索点 $x^{(t+1)}$ 移动，其中 $\Delta x$ 是当前点 $x^{(t)}$ 处的搜索方向(move direction)， $\lambda$ 是沿该方向前进的步长， $\lambda >0$ 。