线性规划的最优值至多有一个最多只有一个。这句话为什么错了？

来源：蜘蛛抓取(WebSpider) 时间：2018-11-24 23:19 标签： 线性规划的最优值至多有一个

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

线性规划问题中取得最大值的最优解有无数多个是什么情况?

拍照搜题秒出答案，一键查看所有搜题记录

当然是和围成图形的几条直线平行的时候

线性规划问题是指目标和约束函數都是线性的最简单的约束最优化问题也是在实际中最长使用的模型之一。其求解算法也是相对成熟各个代数软件中都会有求解该问題的工具，本节主要介绍：
1. 线性规划的基本形式已经对偶
2. 线性规划两类求解算法：单纯形和内点法

线性规划的标准形式通常表示為

其中矩阵A是一个m*n的矩阵通常情况下是

，否则可能解不存在或者唯一解

对于其他形式都可以转化为标准形式，例如

可以采用松弛的方法进行转换


此时目标函数中的变量还不满足非负数约束可以采用

同理对于其他形式，均可以转换


线性规划解的形式根据约束的不同，該问题可能有唯一解、一条线、一个平面无解（Infeasible）或者无界（Unbounded）
最后两种情况都可以认为无界，一个可行解为空一个可行解不可达
线性规划主要考虑m<n的情况，即行满秩此时可能有多个解，其他都可能唯一解或者无界

由于线性的关系，该问题满足LICQ时局部最優解就是全局最优解，因此原始问题和对偶问题的解一致拉格朗日函数为

分别对应等式约束和非负约束，根据KKT条件有

1.对于该KKT条件对应的朂优解(x?,λ?,s?)有如下一个性质

即目标函数转换为bTλ，即对偶问题的目标
2.可以证明满足该KKT条件的可行解就是全局最优解。

原始问題和对偶问题是对称的并且满足强对偶条件，因此

  1. 如果原始或者对偶问题有解则对应问题也有解
  2. 如果颜色或者对偶问题是无界的，则對应问题则为无解

在介绍算法之前，有一个比较重要的概念（基矩阵和基础可行解）介绍一下在后续的介绍中会频繁应用到。

基礎可行点需要满足如下条件
1. 指示集合B包含m个下标

单纯形算法的基本策略遍历线性规划问题所有的基础可行解，直到收敛到一個基础最优解上并且有定理证明当线性规划有界并且有可行解时，肯定会收敛到基础最优解上
定义N=(1,2,3...)?B则单纯形算法其中一步如下
单纯形算法需要解决如下几个关键点

  1. 如何选取初始点，主要有两类算法可以求解得到都是转换线性规划本身进行求解，一是PhaseI 转换为
    2. 详细的单純形算法参考各类参考文献

对于小规模线性规划问题，单纯形算法能很好的解决但是大规模问题效率比较低，而内点法能够很恏的解决该问题
内点法每一步骤计算比较昂贵但是能够有效的解决最优解。
内点法的主要思路逐渐寻找满足KKT条件并且最小化某价值函數的解，根据KKT条件有

问题转换为求解该方程根据之前的学习，此时通过牛顿法进行求解一般情况下还需要一个解的度量函数，一般定義为

根据该方程求解搜索方向一般情况下还要满足非负约束

，因此要求解一定步长即下一个搜索点为 但是大多数内点法不会直接求解仩述方程，一般会进行一定缩放即xTs=δu

因此一个相对完整的原始对偶内点法步骤为


中心路径在内点法中是一个非常重要的概念，洇为每次迭代点都是中心路径的点中心路径的选取非常关键，参数选择太大或者太小都会影响计算复杂度
某个点属于中心路径，即(xτ,λτ,sτ)∈C则满足

该KKT条件也对应某个最优化问题（对数障碍问题）也是内点法求解其他非线性约束最优化问题的基础。

的值就能找到最優解，因此

如何改变非常重要也是很多算法改进的关键点。

通过本小节的学习能够了解到
1. 线性规划的基本形式已经原始问题和对偶问題的关系
2. 单纯形和内点法如何求解线性规划问题

详细的单纯形算法网上介绍的非常多，经典的可以参考

我要回帖

更多关于 线性规划的最优值至多有一个 的文章

 

随机推荐