一般的线性规划具有以下形式：
其中，线性规划标准形是线性规划的一种特殊情况，近年来已经被广泛、深入地研究。在求解线性规划问题时，可以将上述的一般形式通过某种变化（如引入松弛变量等）转换成标准形式：
其中
本文主要讨论利用内点法求解线性规划标准形的过程。
内点法求解线性等式和不等式约束的优化问题，是通过将其简化成一系列线性等式约束问题求解。
首先，重新表述标准形问题，把不等式约束隐含在目标函数中：
其中Indicator函数
不可微，因此需要查找一个替代函数来近似Indicator函数。
障碍法（Barrier Method）
障碍法的基本思想是用以下的函数近似Indicator函数：
t越大越逼近Indicator函数。
代入可得（为了方便，我们用t乘目标函数考虑等价问题）
在上述目标中引入Lagrange乘子构建对偶问题有：
对应的KKT条件为
利用Newton Step可以有
整理可得
其中
.
通常通过消去
来求解方程，从第一个等式可得
带入第二个方程得
综上，使用barrier method求解标准形的线性规划问题的步骤可以整理如下：
step1: 初始化
和可行点
step2: 根据
求解
step3: 根据
求解
step4: 更新
step5: 判断
是否成立，若成立，则退出循环，输出
，否则执行step6
step6: 更新
，执行step2
原对偶内点法（Primal-dual interior-point method）
原对偶内点法对应的KKT条件与Barrier method方法类似：
稍微整理一下可得
利用Newton Step可得
代入
可得
进一步代入可得
依次计算
的值。
综上，使用primal dual求解标准形的线性规划问题的步骤可以整理如下：
step1: 初始化
，定义
，定义参数
step2: 定义
，计算
step3: 确定步长s，更新
step4: 计算
，判断
且
,退出循环，同时输出
，否则重复step2
齐次内点法（Homogeneous interior-point method）
这里主要介绍Mosek方法。
原问题的对偶问题可以表示为
原问题的最优性条件表示为
原问题和对偶问题的对偶间隔为
引入两个非负变量
，化简齐次模型得到HLF模型
显然，0解是一个合理但是没什么用的解。
如果我们通过HLF模型得到一组解
，那么原问题和对偶问题的解为
对偶间隔为
。
求解HLF模型需要满足以下5个条件：
对应残差为
搜索更新方向为
写成方程组形式
代入
和
得
定义
通过求解
和
来计算
综上，使用mosek求解标准形的线性规划问题的步骤可以整理如下：
step1: 初始化
for k = 1,2, ...
step2: 计算
，如果
则输出
，如果
且
，则表示该线性规划无解，退出循环。
step3: 初始化
，计算
step4: 更新
，再次计算
step5: 更新
，回step2
注：其中step4中的
为搜索方向。
