定义
当目标函数和约束函数都是仿射函数时，问题称为线性规划（Linear Program, LP）。线性规划问题的定义如下：
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}x+d \\ \mathrm{subject\ to} \quad & Gx \preceq h \\ \quad & Ax=b \end{aligned} $$其中 $G \in \mathbf{R}^{m \times n}$ 并且 $A \in \mathbf{R}^{p \times n}$。显然，线性规划问题是凸优化问题。
几何意义
可行域 $\mathcal{P}$ 是一个多面体（图中蓝色六边形），目标函数 $c^{\top}x$ 是线性的，所以其等位曲线是与 $c$ 正交的超平面（如虚线所示）。点 $x^{\star}$ 是最优的，它是 $\mathcal{P}$ 中在方向 $-c$ 上最远的点。
线性规划的标准形式和不等式形式
在标准形式线性规划中仅有的不等式都是分量的非负约束 $x \succeq 0$
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}x \\ \mathrm{subject\ to} \quad & Ax=b \\ \quad & x \succeq 0 \end{aligned} $$如果线性规划问题没有等式约束，则成为不等式形式线性规划
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}x \\ \mathrm{subject\ to} \quad & Ax \leqslant b \end{aligned} $$将线性规划转化为标准形式
有时我们需要将一般的线性规划转化为标准形式。第一步是为不等式引入松弛变量 $s_i$，得到
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}x+d \\ \mathrm{subject\ to} \quad & Gx+s=h \\ \quad & Ax=b \\ \quad & s \succeq 0 \end{aligned} $$第二步是将变量 $x$ 表示为两个非负变量 $x^+$ 和 $x^-$ 的差，即 $x=x^+-x^-$，$x^+,x^- \succeq 0$，从而得到问题
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}x^+-c^{\top}x^-+d \\ \mathrm{subject\ to} \quad & Gx^+-Gx^-+s=h \\ \quad & Ax^+-Ax^-=b \\ \quad & x^+ \succeq 0, x^- \succeq 0, s \succeq 0 \end{aligned} $$这是标准形式的线性规划，其优化变量是 $x^+$、$x^-$ 和 $s$。
线性分式规划
在多面体上极小化仿射函数纸币的问题称为线性分式规划
$$ \begin{aligned} \mathrm{minimize} \quad & \frac{c^{\top}x+d}{e^{\top}x+f} \\ \mathrm{subject\ to} \quad & Gx \preceq h \\ \quad & Ax = b \end{aligned} $$这个函数是拟凸的（事实上是拟线性的），因此线性分式规划是一个拟凸优化问题。
转化为线性规划
如果可行集
$$ \{ x \mid Gx \preceq h, Ax=b, e^{\top}x+f > 0 \} $$非空，则线性分式规划可以转换为等价的线性规划
$$ \begin{aligned} \mathrm{minimize} \quad & c^{\top}y+dz \\ \mathrm{subject\ to} \quad & Gy-hz \preceq 0 \\ \quad & Ay-bz=0 \\ \quad & e^{\top}y + fz = 1 \\ \quad & z \geqslant 0 \end{aligned} $$其优化变量为 $y$ 和 $z$。