在线性规划的过程中，往往我们会确定一个方程，求其的最值。而在这个过程当中，往往会进行一些多余的，不必要的计算增加了事件复杂度，对这一类问题的优化解决，被称为斜率优化。
在求最值得问题当中，我们一般会进行平面上有限个数的有序数对的枚举： ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) , . . . , ( x n , y n ) (x_1, y_1), (x_2, y_2), (x_3, y_3), ...,(x_n, y_n) (x1,y1),(x2,y2),(x3,y3),...,(xn,yn) 现引入一个一般形式的方程，设这个方程为我们要计算的方程： f ( i ) = min 0 ≤ j < i { − K i X j + Y j } f(i) = \min_{0 \leq j < i}\{ -K_iX_j + Y_j \} f(i)=0≤j<imin{−KiXj+Yj} 其中 ( X j , Y j ) (X_j, Y_j) (Xj,Yj)为平面上的点，且这个方程需要满足两个条件： K i K_i Ki与 X j X_j Xj是递增的。此时我们会将（1）当中的所有i所对应的j代入（2）求值，求其最小值。
设一线性函数过两点， ( X j , Y j ) (X_j, Y_j) (Xj,Yj)， ( 0 , − K i X j + Y j ) (0, -K_iX_j + Y_j) (0,−KiXj+Yj)，则设其解析式为 y = k x + b y = kx+b y=kx+b，分别代入，可得以下关系： 0 + b = − K i X j + Y j k X j + b = Y j 0+b=-K_iX_j+Y_j \\ kX_j + b = Y_j 0+b=−KiXj+YjkXj+b=Yj 联立上述两式，可得： Y j − k X j = − K i Y j + Y j Y_j-kX_j = -K_iY_j+Y_j Yj−kXj=−KiYj+Yj 即 k = K i k=K_i k=Ki。也就是说， y = k x + b y=kx+b y=kx+b这个线性方程的斜率与 f ( i ) f(i) f(i)在 0 ≤ j < i 0\leq j < i 0≤j<i情况下的斜率相同，同样地，可以将这条直线代入表达出来，即： y = K i x + ( − K i X j + Y j ) y = K_ix + (-K_iX_j+Y_j) y=Kix+(−KiXj+Yj) 问题所需求解的函数值 f ( i ) f(i) f(i)即为方才所求直线在y轴上的截距。
也就是说，对于固定的 i i i，斜率 K i K_i Ki已经确定，所以直线 y = K i x + b y=K_ix +b y=Kix+b在不断靠近所对应的确定点集： ( X 1 , Y 1 ) , ( X 2 , Y 2 ) , . . . , ( X n , Y n ) (X_1, Y_1), (X_2, Y_2), ...,(X_n, Y_n) (X1,Y1),(X2,Y2),...,(Xn,Yn) 的过程当中，这条直线所最先撞到的点，所对应的在 y y y轴上的截距 − K i X j + Y j -K_iX_j+Y_j −KiXj+Yj在点集内所有值当中最小，即此时的 ( X j , Y j ) (X_j,Y_j) (Xj,Yj)对应了 min 0 ≤ j < i { − K i X j + Y j } \min_{0\leq j < i} \{-K_iX_j+Y_j\} min0≤j<i{−KiXj+Yj}，即求得此时 j j j所对应的 f ( i ) f(i) f(i)。
所以说为了确定每个 ( X j , Y j ) (X_j,Y_j) (Xj,Yj)所分别对应的 min 0 ≤ j < i { − K i X j + Y j } \min_{0\leq j < i} \{-K_iX_j+Y_j\} min0≤j<i{−KiXj+Yj}，通常会进行遍历，随后去最小值。但是这种做法确实非常不高效的，会重复计算。此时我们尝试构建一个模型，减少所需尝试的点，使得算法最优。由于是求最小的截距，所以可以形象地理解为将直线： y = K i x + b y=K_ix + b y=Kix+b 从负无穷远处向上不断移动，直至直线遇到点集中的任意一点，而对于最先遇到的点，必定是点集中部分点构成的下凸曲线，将所有的点处于此下图曲线线上或其上方（如下图） 由此，引入了凸包的概念，并将求最小值问题转换为对凸包的维护：
凸包的概念：点集Q的凸包（Convex Hull）是指一个最小的凸多边形，满足Q中的点在多边形上或在其内。引入凸包后可以发现需要判断的点都处在凸包上，处理量大大减少。在图中，凸包即为部分的下图曲线上的点集，同时，凸包满足斜率不断增加的条件，换而言之，其各个部分导数不断增加，若使用光滑的曲线连接各点使其连续且可导，则其二阶导数始终大于 0 0 0（函数下凸）。
对凸包的维护：
（1）对于一个凸包，每当 i i i增加时，会有一个新的点，而由于 X j X_j Xj递增，所以新点 ( X i + 1 , Y i + 1 ) (X_{i+1}, Y_{i+1}) (Xi+1,Yi+1)必定在最右侧，一定在凸包上，需将此点加入凸包，但是加入的同时必须要使其符合斜率不断增加的定义，即 y i + 1 − y i x i + 1 − x i \frac {y_{i+1}-y_i}{x_{i+1}-x_i} xi+1−xiyi+1−yi是递增的，所以可能会需要删除部分点，使其满足条件。进行判断：当 y t − y t − 1 x t − x t − 1 ≥ y i − y t x i − x t \frac {y_t-y_{t-1}}{x_t-x_{t-1}} \geq \frac {y_i - y_t}{x_i-x_t} xt−xt−1yt−yt−1≥xi−xtyi−yt 时，舍去第 t t t个数对（点）， t t t为每次点集的最后一项。重复上述过程直至（9）的条件不再成立。如下图： （2）首先进行以下推导：
由于对于凸包的队首而言，如果两点 ( X 1 , Y 1 ) , ( X 2 , Y 2 ) (X_1,Y_1), (X_2,Y_2) (X1,Y1),(X2,Y2)，过前者的直线与过后者的平行直线（ k = K i k=K_i k=Ki）前者截 y y y轴的截距大于后者截 y y y轴的截距，即： − K i × X 1 + Y 1 > − K i × X 2 + Y 2 -K_i \times X_1 + Y_1 > -K_i \times X_2 + Y_2 −Ki×X1+Y1>−Ki×X2+Y2 若（10）式成立，则可以推导出下式： K i > Y 2 − Y 1 X 2 − X 1 K_i > \frac {Y_2-Y_1}{X_2-X_1} Ki>X2−X1Y2−Y1 由于 X j X_j Xj始终递增，所以分母不为 0 0 0，又因为 K i K_i Ki是递增的（开头提到）所以有： K i + 1 > K i > Y 2 − Y 1 X 2 − X 1 ⇒ − K i + 1 × X 1 + Y 1 > − K i + 1 × X 2 + Y 2 K_{i+1} > K_i > \frac {Y_2 - Y_1}{X_2 - X_1} \\ \Rightarrow-K_{i+1} \times X_1 + Y_1 > -K_{i+1} \times X_2 + Y_2 Ki+1>Ki>X2−X1Y2−Y1⇒−Ki+1×X1+Y1>−Ki+1×X2+Y2 可以发现由（10）式可以推出（13）式，即（10）为（13）的充分条件，即如果对于 i = k i=k i=k， ( X j , Y j ) (X_j, Y_j) (Xj,Yj)所对应的函数值大于 ( X j + 1 , Y j + 1 ) (X_{j+1}, Y_{j+1}) (Xj+1,Yj+1)所对应的函数值，即后者更优时，在所有 i ≥ k i \geq k i≥k， ( X j , Y j ) (X_j, Y_j) (Xj,Yj)所对应的函数值都大于 ( X j + 1 , Y j + 1 ) (X_{j+1}, Y_{j+1}) (Xj+1,Yj+1)所对应的函数值，即后者都更优。所以通过这个结论，每当计算开始之前，就对凸包的前部进行维护，可以直接通过判断（10）式，确定对凸包的第一个元素的取舍，并重复上述过程直至（10）不再成立。
从上述两点，可以发现维护这个凸包，基本相当于维护一个队列。并且上述的两个过程是针对固定的 i i i中的过程，对于不同的 i i i值，进行同样地循环。而对于方程 f ( i ) f(i) f(i)的计算，则在单个循环的两次维护之间进行。
