论坛 › 技术讨论 Technology Answers › 优化 | KKT条件学习笔记：理论介绍、详细计算案例 ...

量子计算9 发表于 2023-3-5 08:08

优化 | KKT条件学习笔记：理论介绍、详细计算案例 ...

作者：李心怡，清华大学，清华大学深圳国际研究生院，博士在读
作者：刘兴禄，清华大学，清华大学深圳国际研究生院，清华-伯克利深圳学院，博士在读
编辑：张瑞三，四川大学，硕士在读，E-mail:zrssum3@stu.scu.edu.cn，知乎ID：MunSum3
<hr/><hr/>前言

Karush–Kuhn–Tucker (KKT) 条件，或者叫Kuhn–Tucker (KT) 条件，是在满足约束正则条件下，一个非线性规划(Nonlinear programming, NLP)问题取得最优解的一阶必要条件(first derivative tests 或 first-order necessary conditions)。KKT条件最初以Harold W. Kuhn和Albert W. Tucker的名字命名，他们在1951年首次发表了这些条件。后来学者发现1939年William Karush已经在硕士论文中声明了必要条件。为了向三位科学家表示敬意，我们在此附上提出KKT条件的三位科学家的维基百科简介截图。



William Karush, 网址：https://en.wikipedia.org/wiki/William_Karush



Harold W. Kuhn, 网址：https://en.wikipedia.org/wiki/Harold_W._Kuhn



Albert W. Tucker, 网址：https://en.wikipedia.org/wiki/Albert_W._Tucker

本文首先对KKT条件的原理和具体内容加以介绍，然后提供一个具体的计算案例，帮助读者理解和练习。最后，我们提供了一些关于KKT条件的拓展内容，方便大家学习。
本次推送主要参考Winston, Wayne & Goldberg, Jeffrey的Operations research: applications and algorithms 第11章第9节。
KKT条件：原理和具体内容

KKT条件的具体内容

上文提到，KKT条件是非线性规划问题取得最优解的一阶必要条件。KKT条件有非常多的重要用途。
我们首先来看KKT条件的具体内容：



KKT条件的具体内容

KKT条件中的乘子 \overline{\lambda}_i 可视作NLP的第 i 条约束的影子价格 (shadow price) 或者对偶价格(dual price)。
不妨以最大化问题 (1) 为例，把每条约束理解为一种资源的使用约束，即资源 i 的可用量为 b_i 。若有解 \overline{\mathbf{x}}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) ，则对于第 i 个约束而言，使用的资源 i 的总量为 g_i(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 。
为什么会有KKT条件的第一个条件

如果将变量 x_j 的取值增加 \Delta （ \Delta 是一个小量），则目标函数值增加 \frac{\partial f(\overline{\mathbf{x}})}{\partial x_j}\Delta.
第 i 条约束相应地变成 g_i(\overline{\mathbf{x}})+\frac{\partial g_i(\overline{\mathbf{x}})}{\partial x_j}\Delta \leqslant b_i.
或者写成 g_i(\overline{\mathbf{x}}) \leqslant b_i-\frac{\partial g_i(\overline{\mathbf{x}})}{\partial x_j}\Delta.
即第i   条约的右侧项增加 -\frac{\partial g_i(\overline{\mathbf{x}})}{\partial x_j}\Delta.
这些右侧项的变化能将 z 值近似增加 -\Delta\sum_{i=1}^{m}\overline{\lambda}_i\frac{\partial g_i(\overline{\mathbf{x}})}{\partial x_j}.
综上，将 x_j 增加 \Delta ，NLP的目标函数 z 值约增加 \Delta\left[\frac{\partial f(\overline{x})}{\partial x_j}-\sum_{i=1}^{m}\overline{\lambda}_i\frac{\partial g_i(\overline{x})}{\partial x_j}\right] 如果括号中的值大于0，我们可以取 \Delta >0 以增加目标值；如果括号中的值小于0，我们可以取 \Delta <0 以增加目标值。因此，若要 \overline{\mathbf{x}} 最优，KKT条件中的 (2) 式必须成立。即 \\ \begin{eqnarray} \frac{\partial f(\overline{x})}{\partial x_j}{-}\sum\limits_{i=1}^{m}\overline{\lambda}_i\frac{\partial g_i(\overline{x})}{\partial x_j}=&0, \quad \forall j=1,\dots,n \end{eqnarray}\\ 为什么会有KKT条件的第二个条件

条件 (3) 是线性规划互补松弛条件的一般化表达，即
\begin{eqnarray} &&\text{If}~\overline{\lambda}_i >0,~&\text{then}~g_i(\overline{x})=b_i\label{binding} \\ &&\text{If}~g_i(\overline{x})< b_i,~&\text{then}~\overline{\lambda}_i=0\label{nonbinding} \end{eqnarray}

[*](7) 表明第 i 条约束有约束力（binding），即如果额外一单位资源是有价值的，则当前最优解一定用完了可用的 b_i 单位资源。
[*](8) 表明第 i 条约束无约束力（non-binding），即如果该约束对应的资源当前没有用完，则额外数量的该资源没有价值。
为什么会有KKT条件的第三个条件

取 \Delta >0 ，如果我们将第 i 条约束的右侧项从 b_i 增加到 b_i+\Delta ，则问题的可行域增大了，因此目标函数最优值要么增加、要么不变；而目标函数最优值增加 \Delta\overline{\lambda}_i ，因此 \overline{\lambda}_i\geqslant 0 ，KKT条件需包含式 (4) 。
非线性规划取得最优解的充分条件

Theorem 1给出了 \overline{\mathbf{x}}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 是问题 (1) 或问题 (5) 最优解的必要条件，充分条件由Theorem 2给出。
Theorem 2
对最大化NLP问题 (1) ，若 f(x) 为凹（concave）函数，且 g_1(x),\dots,g_m(x) 为凸（convex）函数，则任意满足Theorem 1条件的 \overline{x}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 都是 (1 ) 的最优解。
对最小化NLP问题 (2) ，若 f(x) 为凸函数，且 g_1(x),\dots,g_m(x) 为凸函数，则任意满足Theorem 1条件的 \overline{x}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 都是 (2) 的最优解。KKT条件的简单证明请参考A simple and elementary proof of the Karush–Kuhn–Tucker theorem for inequality-constrained optimization 或更易理解的The Kuhn-Tucker and Envelope Theorems 。
本节介绍的理论若要成立，要求函数 g_1,g_2,\dots,g_m 满足一定的正则条件(Regularity conditions 或者 constraint qualifications)，文末将简要介绍一种，深入讨论请参考Nonlinear Programming:Theory and Algorithms 第五章。实际上，当约束都是线性的，正则条件一定成立。下面我们就求解一个线性约束的NLP来练练手。
KKT条件计算示例及其Python+Gurobi求解

计算示例：手动推导和计算

求解如下NLP问题 \\ \begin{eqnarray*} \min z=&&e^{-x_1}+e^{-2x_2}\\ \mathbb{s.t.}\quad &&x_1+x_2\leqslant 1\\ &&x_1,x_2\geqslant 0 \end{eqnarray*} \\ 首先证明目标函数是凸函数： 记 \\ f(x_1,x_2)=e^{-x_1}+e^{-2x_2} \\ f(x_1,x_2) 的Hessian矩阵为 \\ H(x_1,x_2)=\left[\begin{matrix} e^{-x_1}& 0\quad\\ 0\quad &4e^{-2x_2} \end{matrix}\right] \\ 由于 e^{-x_1}>0, 4e^{-x_1-2x_2}>0 ，即所有顺序主子式非负，因此 H(x_1,x_2) 正定， f(x_1,x_2) 为凸函数。而该NLP的约束都是线性约束，为凸函数，因此任一满足KKT条件的解都是该问题的最优解。
\\ \begin{eqnarray*} \min z=e^{-x_1}+e^{-2x_2}\\ \mathbb{s.t.}\quad x_1+x_2\leqslant 1\\ -x_1\leqslant 0\\ -x_2\leqslant 0 \end{eqnarray*} \\ 将变量非负约束改写为如上的标准形式，记三条约束的乘子分别为 \lambda ， \mu_1 和 \mu_2 ，则该问题的KKT条件
\\ \begin{aligned} & -e^{-x_1}+\lambda-\mu_1=0   && (9)\\ &- 2e^{-2x_2}+\lambda-\mu_2=0,&& (10)\\&\lambda(1-x_1-x_2)=0   && (11)\\&\mu_1 x_1=0&& (12)\\ &\mu_2 x_2=0&& (13)\\ & \lambda,\mu_1,\mu_2 \ge0 &&(14) \\ \end{aligned}\\
可以看到，我们使用KKT条件，将一个带有目标函数的非线性规划，转化成了一个无目标函数的KKT方程组。一般情况下，该KKT方程组的解，就是原非线性规划的最优解。下面我们求解上述方程组。使用分情况讨论的方法：

[*] 若 \mu_1\neq 0,\mu_2\neq 0 ，从 (12),(13) 可得 x_1=0，x_2=0 ，带入 (11) 得 \lambda=0 ，然后由 (9),(10) 得 \mu_1=-1，\mu_2=-2 ，违反条件 (14) ;
[*] 若 \mu_1\neq 0,\mu_2= 0 ，从 (12) 可得 x_1=0 ，从 (10) 可知 \lambda=2e^{-2x_2}>0 ，又由于 11 ，可得 x_2=1 ，带入 (9) 得 \mu_1=2e^{-2}-1<0 ，违反条件 (14) ;
[*] 若 \mu_1= 0,\mu_2\neq 0 ，从 (13) 可得 x_2=0 ，从 (9) 可知 \lambda=2e^{-x_1}>0 ，又由于 (11) ，可得 x_1=1 ，带入 (10) 得 \mu_2=e^{-1}-2<0 ，违反条件 (14) ;
[*] 若 \mu_1= 0,\mu_2= 0 ，带入 (9),(10) 可得\\ \begin{aligned} &\lambda=e^{-x_1}   && (15)\\ &\lambda=2e^{-2x_2}&& (16)\\\end{aligned}\\ 都表明 \lambda>0 ，带入 (11) 得到 \\ \begin{aligned} &x_1+x_2=1&& (17)\\\end{aligned}\\则由 (15)-(17) 解得 x_1=\frac{2-\ln{2}}{3} ， x_2=\frac{1+\ln{2}}{3} ， \lambda=2^{\frac{1}{1}}e^{-\frac{2}{3}} ，所有KKT条件都满足。
因此，该问题最优解为 x_1=\frac{2-\ln{2}}{3} ， x_2=\frac{1+\ln{2}}{3} ，目标值 z=3\cdot(2e)^{-\frac{2}{3}} 。
计算示例：Python+Gurobi求解验证

下面我们使用Python调用Gurobi来验证上述推导和计算是否正确。
要用Gurobi求解上述非线性规划模型，需要引入辅助变量，且需要用到Gurobi的广义约束功能addGenConstrExp或者addGenConstrExpA。
运小筹公众号在往期推文中也多次涉及到了非线性规划的相关内容，感兴趣的读者可以前往下列推文学习。
本文例子的完整Gurobi代码如下。
from gurobipy import *
import math

model = Model()

x1 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='x1')
x2 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='x2')

xx1 = model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='xx1')
xx2 = model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='xx2')

y1 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='y1')
y2 = model.addVar(lb=0, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name='y2')

model.setObjective(y1 + y2, GRB.MINIMIZE)

model.addConstr(x1 + x2 <= 1)
model.addConstr(xx1 == -x1)
model.addConstr(xx2 == -2 * x2)
model.addGenConstrExpA(xx1, y1, math.e)
model.addGenConstrExpA(xx2, y2, math.e)

# model.addGenConstrExpA()

model.write('KKT.lp')
model.optimize()

print(" ======== Gurobi计算的结果 ======== ")
print('x1 = ', x1.x)
print('x2 = ', x2.x)
print('ObjVal = ', model.ObjVal)

print(" ======== 手动计算的结果 ======== ")
print('x1 = ', (2 - math.log(2, math.e))/3)
print('x2 = ', (1 + math.log(2, math.e))/3)
print('ObjVal = ', 3 * ((2 * math.e) ** (-2/3) ))

print('x1 + x2 =', (2 - math.log(2, math.e))/3 + (1 + math.log(2, math.e))/3)Gurobi导出的非线性模型如下：
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
y1 + y2
Subject To
R0: x1 + x2 <= 1
R1: x1 + xx1 = 0
R2: 2 x2 + xx2 = 0
Bounds
xx1 free
xx2 free
General Constraints
GC0: y1 = EXPA ( 2.718281828459045 ^ xx1 )
GC1: y2 = EXPA ( 2.718281828459045 ^ xx2 )
End上述代码的求解结果为
Root relaxation: objective 9.703110e-01, 95 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |   Objective Bounds      |   Work
Expl Unexpl |ObjDepth IntInf | Incumbent    BestBd   Gap | It/Node Time

   0   0    0.97031    0    2          -    0.97031      -   -    0s
H    0   0                     0.9719312    0.970310.17%   -    0s
   0   0    0.97031    0    2    0.97193    0.970310.17%   -    0s
H    0   0                     0.9703070    0.970310.00%   -    0s
   0   0    0.97031    0    2    0.97031    0.970310.00%   -    0s

Explored 1 nodes (95 simplex iterations) in 0.07 seconds (0.09 work units)
Thread count was 16 (of 16 available processors)

Solution count 2: 0.970307 0.971931

Optimal solution found (tolerance 1.00e-04)
Best objective 9.703069744688e-01, best bound 9.703069744688e-01, gap 0.0000%
======== Gurobi计算的结果 ========
x1 =0.4325
x2 =0.5675
ObjVal =0.9703069744688448
======== 手动计算的结果 ========
x1 =0.4356176064800182
x2 =0.5643823935199818
ObjVal =0.9702975534683167
x1 + x2 =   1.0可见，Gurobi的求解结果和手动计算的结果基本吻合。但是注意，由于Gurobi中的非线性约束的处理方法本质是分段线性近似, 因此会存在微小的数值误差。
若要提高Gurobi求解非线性规划的精度，可以修改FuncPieces, FuncPieceLength, FuncPieceError, FuncPieceRatio等参数。
Gurobi求解非线性规划的原理

上一节我们提供了Python调用Gurobi求解非线性规划的详细代码，其中用到了广义约束addGenConstrExpA。观察到，上述代码的求解日志如下：
Root relaxation: objective 9.703110e-01, 95 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |   Objective Bounds      |   Work
Expl Unexpl |ObjDepth IntInf | Incumbent    BestBd   Gap | It/Node Time

   0   0    0.97031    0    2          -    0.97031      -   -    0s
H    0   0                     0.9719312    0.970310.17%   -    0s
   0   0    0.97031    0    2    0.97193    0.970310.17%   -    0s
H    0   0                     0.9703070    0.970310.00%   -    0s
   0   0    0.97031    0    2    0.97031    0.970310.00%   -    0s

Explored 1 nodes (95 simplex iterations) in 0.07 seconds (0.09 work units)
Thread count was 16 (of 16 available processors)

Solution count 2: 0.970307 0.971931

Optimal solution found (tolerance 1.00e-04)
Best objective 9.703069744688e-01, best bound 9.703069744688e-01, gap 0.0000%我们发现，该日志和Gurobi求解MIP的日志很相似。
是的，实际上，Gurobi内部处理广义约束的方法，就是使用分段线性近似(Piecewise linear approximation)的方法，将非线性函数进行了线性近似，从而将非线性规划转化为近似的混合整数规划，然后调用求解混合整数规划的分支切割算法(Branch and cut)进行求解转化后的MIP。因此，Gurobi求解非线性规划的日志和求解MIP的日志形式是基本相同的。
但是，这种近似不可避免地会导致误差。所以用户在使用的时候一定要注意这个问题。
约束规范性条件

如果最优点 \overline{\mathbf{x}} 不满足约束规范（constraint qualification）或正则条件（regularity condition），KKT条件在 \overline{\mathbf{x}} 处可能不成立。下面介绍一种线性独立约束规范（Linear Independence Constraint Qualification, LICQ）：
记 \overline{\mathbf{x}} 为 NLP (1) 或 (5) 的最优解，如果所有$g_i$连续，点$\overline{x}$处所有binding约束（包括有约束力的变量非负性约束）的梯度构成一组线性独立向量，则KKT条件在$\overline{\mathbf{x}}$处一定成立。让我们求解下面这个NLP来理解约束规范的必要性。 \\ \begin{eqnarray*} &\min & z=x_1\\ &\mathbb{s.t.}\quad & x_2-(1-x_1)^3\leqslant 0    \quad   \quad   \quad (18) \\ && x_1\geqslant 0, x_2\geqslant 0 \end{eqnarray*} \\
若 x_1>1 ，则 x_2\leqslant (1-x_1)^3<0 ，违反变量非负性约束，因此目标函数最优值 z=x_1\leqslant 1 。而 x_1=1,x_2=0 时 z=1 且约束可行，因此 (1,0) 是问题 (18) 的最优解。
式 (19) 和 (20) 是问题 (18) 的两条KKT条件（乘子 \lambda 对应第一条约束， \mu_1 对应非负性约束 -x_1\leqslant 0 ）： \\ \begin{aligned} &1-3\lambda(1-x_1)^2+\mu_1=0   && (19)\\ & \mu_1\geqslant 0&& (20)\\\end{aligned}\\
将最优解 (1,0) 带入 （19） 可得 \mu_1=-1 ，与条件 （20） 矛盾，即KKT条件在点 (1,0) 处不成立。
观察点 (1,0) 处binding的两条约束 x_2-(1-x_1)^3\leqslant 0 和 -x_2\leqslant 0 的梯度： \\ \begin{gather*} \nabla\left(x_2-(1-x_1)^3\right)=\\ \nabla(-x_2)= \end{gather*} \\
+= ，梯度线性相关，不满足LICQ约束规范。
KKT条件可以用来干什么

1. 求解非线性规划

如本文中给出的例子。一般来讲，求解一个满足约束规范性条件（或者叫正则条件）的非线性规划的KKT方程组，可以获得该非线性规划的最优解。如本文中提供的例子。
2. 将双层规划(bilevel programming)转化为单层规划

由于KKT条件可以将带有目标函数的约束规划问题转化为一个无目标函数的方程组，因此KKT条件有消除目标函数的功能。所以对于形如下面的双层规划
\\\begin{aligned} \underset{x} \max\underset{y} \min \quad & cx+dy \\ s.t.\quad&Ax+By=b, \\ &x,y\geqslant 0. \end{aligned}\\ 转化为单层规划。
例如，求解两阶段鲁棒优化的列与约束生成(Column and constraint generation， C&CG)算法中，就涉及到了KKT条件的使用，详细介绍见往期推文：
3. 获得非线性规划中约束的对偶变量

KKT条件和拉格朗日松弛有紧密的联系。求解KKT方程组，可以同时获得非线性规划的最优解和非线性规划的约束的对偶变量，包括线性约束和非典型约束的。
使用Gurobi就可以很容易地获得非线性约束的对偶变量。Gurobi中，只需要访问二次约束(QuadExpr)的QCPi属性，即可得到二次约束的对偶变量。
在获取二次约束的对偶变量方面，我们退出过一期推文，感兴趣的读者可以前往查看：
文中求解的二次约束二次规划如下：
\\\begin{aligned} \min\quad &\frac{1}{2}x^2+y^2-xy-2x-6y \\ s.t. \quad&x\geqslant 2y, \\ &x^2+\frac{1}{2}y\leqslant 2, \\ &2x+y\leqslant 3, \\ &x,y\geqslant 0. \end{aligned}\\ 这里，我们直接将代码复制过来。
from gurobipy import *

# Create a new model
m = Model("QCQP")

# Create variables
x = m.addVar(lb = 0, vtype=GRB.CONTINUOUS , name="x")
y = m.addVar(lb = 0, vtype=GRB.CONTINUOUS , name="y")

# Set objective
m.setObjective (1/2 * x * x + y * y - x * y - 2 * x - 6 * y, GRB.MINIMIZE)

m.setParam('QCPDual', 1)

# Add constraints
m.addConstr(-x + 2 * y <= 2, "c0")
m.addConstr(x * x + 1/2 * y <= 2, "c1")
m.addConstr (2 * x + y <= 3, "c2")

# Write model to file
m.write("QCQP.lp")

# Solve the model
m.optimize ()

for con in m.getConstrs():
    print(con.ConstrName, '----', con.Pi)

for con in m.getQConstrs():
    print(con.QCName, '----', con.QCPi)求解结果如下
arrier statistics:
AA' NZ   : 2.100e+01
Factor NZ: 3.600e+01
Factor Ops : 2.040e+02 (less than 1 second per iteration)
Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual   Compl   Time
   0-1.49326539e+01 -4.35523979e+001.76e+00 3.70e+004.65e+00   0s
   1-6.12239820e+00 -1.12395144e+011.94e-06 1.22e-015.19e-01   0s
   2-8.53301014e+00 -8.99477729e+001.54e-07 1.02e-034.24e-02   0s
   3-8.82682363e+00 -8.85269793e+003.11e-13 5.50e-062.35e-03   0s
   4-8.83955816e+00 -8.84007974e+001.03e-13 4.22e-094.74e-05   0s
   5-8.83999672e+00 -8.84000230e+003.74e-12 5.43e-115.08e-07   0s

Barrier solved model in 5 iterations and 0.02 seconds
Optimal objective -8.83999672e+00

Solving KKT system to obtain QCP duals...


c0 ---- -1.0799994965216462
c2 ---- -1.8399999978917783
c1 ---- -1.1253017667406413e-10日志中清楚地显示着Solving KKT system to obtain QCP duals...。
小结

本文采用理论介绍+计算案例+代码实现+拓展用途的方式介绍了KKT条件的相关知识。如果读者想要继续深入了解KKT条件，欢迎阅读参考文献部分列出的资料。
参考文献

1. Winston, Wayne & Goldberg, Jeffrey. Operations research: applications and algorithms. (2004).

2. Brezhneva, O.A., Tret’yakov, A.A. & Wright, S.E. A simple and elementary proof of the Karush–Kuhn–Tucker theorem for inequality-constrained optimization. Optim Lett 3, 7–10 (2009).

3. The Kuhn-Tucker and Envelope Theorems

4. Bazaraa, M., H. Sherali, and C. Shetty. Nonlinear Programming: Theory and Algorithms. New York: John Wiley, 1993.<hr/>关注我们运小筹公众号
运小筹公众号致力于分享运筹优化(LP、MIP、NLP、随机规划、鲁棒优化)、凸优化、强化学习等研究领域的内容以及涉及到的算法的代码实现。编程语言和工具包括Java、Python、Matlab、CPLEX、Gurobi、SCIP 等。欢迎广大同行投稿！欢迎大家关注我们的公众号“运小筹”以及粉丝群！
如果群满加不进去，可以加本文作者微信，然后备注姓名+机构+专业，然后拉您入群。
<hr/>往期推文合集

第126篇：OR History (2) | 整数规划小时候
第125篇：OR History | 理查德·贝尔曼：动态规划是怎样的诞生的
第124篇：优化 | KKT条件学习笔记：理论介绍、详细计算案例、Python+Gurobi代码验证及拓展
第123篇：优化 | 组合优化问题的复杂度精讲(下): 案例(Cutting Stock Problem)与数值实验分析
第122篇：优化求解器 | 强大的Cutting Plane算法：Gurobi中Cuts的介绍及案例探究(Python+Gurobi)
第121篇：优化 | 组合优化问题的复杂度精讲(上): 概念、理论与案例详解
第120篇：优化问题|考虑多段运输过程的海外仓选址优化问题：优化模型及其编程求解(Python+Gurobi)
第119篇：主编新书强推 |《运筹优化常用模型、算法及案例实战：Python+Java实现》正式上线啦！！！
第118篇：重磅硬货！187页运小筹优化理论教程(Part 12)发布(2022年7月--2022年11月)！
第117篇：数学启发式算法 | 可行性泵 (Feasibility Pump)精讲：一份让您满意的【理论介绍+编程实现+数值实验】学习笔记
第116篇：优化 | 对偶理论那些事儿：一份让您满意的理论介绍+案例实践学习笔记 (Python+Gurobi)
第115篇：优化算法 | 强大的数学启发式算法：Gurobi求解器中启发式算法的参数设置与案例实践
第114篇：重磅硬货！280页运小筹优化理论教程发布(2022年3月--2022年6月)！
第113篇：优化 | 分支定界算法案例实战：Python调用COPT实现
第112篇：优化 | 分支定界算法案例实战：Python调用COPT实现
第111篇：优化 | 五个经典设施选址模型的详解及其实践：Python调用Gurobi实现
第110篇：始于初心，回馈教育：运筹与智能决策教学平台——杉数CORIDM全新升级上线！
第109篇：求解器COPT实践详解丨数学规划视角下的分货优化解题思路
第108篇：论文代码复现 | 考虑客户位置移动的车辆路径规划问题：MIP模型详解及Java调用CPLEX求解的完整代码
第107篇：求解器COPT实践丨地铁乘务排班问题如何优化求解
第106篇：优化求解器 | 求解器加速的高级技能包：MIP模型初始解设置相关操作的超详细解读
第105篇：OR Talk Pool：【8月26日-9月3日】近期讲座、课程和研讨会
第104篇：OR Talk Pool：【8月17日-8月31日】近期研讨会、论坛和培训
第103篇：进展 | 清华大学SIGS戚铭尧及其合作者在顶级期刊Operations Research上发表竞争性设施选址问题的最新研究进展
第102篇：启发式算法和优化算法设计及调试技巧 | AIRS in the AIR“运筹优化”系列讲座
第101篇：OR Talk Pool【8月9日-8月31号】：近期研讨会、论坛和培训
第100篇：理论算法与精确算法 | AIRS in the AIR”运筹优化“系列讲座
第99篇：OR Talk Pool【7月27日-8月】：近期研讨会、论坛和培训
第98篇：优化求解器|Solution Pool用法的超详细解读(Gurobi)：最优解与多个可行解的获取与分析(案例与代码实现)
第97篇：新书推荐《整数规划：模型、应用及求解》
第96篇：OR Talk Pool【7月6日-7月13日】：近期研讨会、论坛和培训
第95篇：从大规模的复杂应用，来解析杉数求解器的硬核能力
第94篇：优化 | 手把手教你用C++调用Gurobi求解CVRP：环境配置、数学模型及完整代码
第93篇：OR Talk Pool：近期研讨会、暑期学校和学术报告推荐
第92篇：优化求解器 | Gurobi的MVar类：矩阵建模利器、求解对偶问题的备选方案 (附详细案例+代码)
第91篇：【求解器】Gurobi中非线性约束的对偶值的获取：QCP、QCQP、SOCP | 以及求解器最优性理论证明
第90篇：优化 | 二部图最大匹配问题的精确算法详解(HK算法和匈牙利算法)：一份让您满意的【理论介绍+代码实现】学习笔记
第89篇：优化算法 | Benders Decomposition: 一份让你满意的【入门-编程实战-深入理解】的学习笔记
第88篇：优化 | 史上最【皮】数学题求解的新尝试：一种求解器的视角 (Python调用Gurobi实现)
第87篇：优化 | 寻找新的建模视角——从直观解释对偶问题入手：以Cutting Stock Problem的对偶问题为例
第86篇：ORers‘ Bling Chat【03】 | 【高光聊天记录集锦】：运小筹读者群里那些热烈的讨论
第85篇：非线性优化 | 非线性问题线性化以及求解的详细案例及Python+Gurobi求解
第84篇：ORers' Bling Chat | 【高光聊天记录集锦-02】：运小筹读者群里那些热烈的讨论
第83篇：Machine-Learning–Based Column Selection for Column Generation
第82篇：最新！205页运小筹优化理论学习笔记发布(2021年9月--2022年3月)！
第81篇：【鲁棒优化】| 补充证明:为什么最优解一定满足取值等于绝对值(论文笔记：The Price of Robustness)
第80篇：【鲁棒优化】| 论文笔记：The Price of Robustness - 列不确定性模型部分的推导和一些思考
第79篇：ORers' Bling Chat | 【高光聊天记录集锦-01】：运小筹读者群里那些热烈的讨论
第78篇：优化| 手把手教你学会杉数求解器(COPT)的安装、配置与测试
第77篇：【教学视频】优化 | 线性化(2)：连续变量 * 0-1变量的线性化
第76篇：【教学视频】优化 | 线性化：两个0-1变量相乘的线性化
第75篇：强化学习实战 | DQN和Double DQN保姆级教程：以Cart-Pole为例
第74篇：强化学习| 概念梳理：强化学习、马尔科夫决策过程与动态规划
第73篇：强化学习实战 | Q-learning求解最短路(SPP)问题
第72篇：鲁棒优化 | 以Coding入门鲁棒优化：以一个例子引入（二）
第71篇：鲁棒优化|基于ROME编程入门鲁棒优化：以一个例子引入(一)
第70篇：优化|含分式的非线性规划求解: 基于Outer Approximation的Branch-and-cut 算法及其Java实现
第69篇：科研工具 | 手把手教你玩转文献管理神器：Endnote
第68篇：相约深圳 | 2022 INFORMS 服务科学国际会议·征稿通知
第67篇：鲁棒优化｜ 利用rome求解鲁棒优化简单案例：以CVaR不确定性集为例
第66篇：机器学习 | 交通流特征工程小技巧和思考
第65篇：最新！145页运小筹优化理论学习笔记发布(2021年4月--9月)！
第64篇：优化 | 手把手教你用Python调用SCIP求解最优化模型
第63篇：优化 | 随机规划案例：The value of the stochastic solution
第62篇：工具 | draw.io: 科研流程示意图必备大杀器
第61篇：优化 | 开源求解器SCIP的安装与入门教程（Windows+Python）
第60篇：优化|Gurobi处理非线性目标函数和约束的详细案例
第59篇：让出租车更“懂”您的出行
第58篇：测试算例下载：《运筹优化常用模型、算法及案例实战：代码手册》
第57篇：鲁棒优化|分布式鲁棒优化转化为SOCP案例及代码实现(Python+RSOME)
第56篇：鲁棒优化 | 分布式鲁棒优化简单案例及实战(RSOME+Gurobi)
第55篇：【尾款+发货】|【代码手册】 《运筹优化常用模型、算法及案例实战：Python+Java
第54篇：深度强化学习之：PPO训练红白机1942
第53篇：简单装配线平衡问题
第52篇：【视频讲解】CPLEX的OPL语言：可视化的优化模型求解解决方案
第51篇：算法 | 基于英雄联盟寻路背景的A星算法及python实现
第50篇：【转发】清华大学深圳国际研究生院2021年物流工程与管理项目优秀大学生夏令营报名通知
第49篇：优化 | 精确算法之分支定界介绍和实现（附Python代码）
第48篇：【顶刊论文速递】综述：服务科学视角下的金融科技
第47篇：【重新发布】|《运筹优化常用模型、算法及案例实战：Python+Java实现》 【代码手册】 开始预购啦！！！
第46篇：智慧交通可视化：手把手教你用Python做出行数据可视化-osmnx 包入门教程
第45篇：优化 | Pick and delivery problem的介绍与建模实现（二）
第44篇：推一个知乎学弱猹的公众号
第43篇：元启发式算法 | 遗传算法(GA)解决TSP问题(Python实现)
第42篇：优化|视频详解Python调用Gurobi的应用案例：TSP
第41篇：最新！213页运小筹优化理论系列笔记发布！
第40篇：运小筹第四期月刊发布！
第39篇：开源交通仿真平台SimMobility的安装教程
第38篇：浅谈 | P问题、NP问题、NPC问题、NP-Hard问题
第37篇：一份掏心掏肺的信息素养笔记分享
第36篇：强化学习｜Q-learning (王者荣耀视角)
第35篇：优化｜高级建模方法（Gurobi）：线性化表达小技巧
第34篇：深度强化学习介绍 | Deep Q Network——理论与代码实现
第33篇：优化 | 列生成算法及Java调用cplex实现
第32篇：优化 | Pick and delivery problem的简介与建模实现（一）
第31篇：最新！运小筹月刊-1月份发布！
第30篇：“Learn to Improve”（L2I）：ICLR文章分享 | 运用RL解决VRP问题
第29篇：线性规划求解小程序 | 基于Python 的Cplex 求解器图形化界面
第28篇：运筹学与管理科学TOP期刊揭秘 —TR系列
第27篇：Julia安装与配置Jupyter Notebook
第26篇：期刊征文| IEEE TRANSACTIONS应对COVID-19的特刊征文消息速递
第25篇：两阶段随机规划(Two-stage Stochastic Programming)：一个详细的例子
第24篇：最新！运小筹月刊-12月份发布！
第23篇：Python调用Gurobi：Assignment Problem简单案例
第22篇：初识随机规划：一个小小例子
第21篇：机器学习运用到VRP的若干小知识
第20篇：运筹学与管理科学TOP期刊揭秘 —Service Science
第19篇：手把手教你用Python实现Dijkstra算法（伪代码+Python实现）
第18篇：运筹学与管理科学大揭秘—TOP期刊主编及研究方向一览
第17篇：优化 | 手把手教你用Python实现动态规划Labeling算法求解SPPRC问题
第16篇：代码 | 运小筹GitHub项目上线啦，快来标星收藏吧！！
第15篇：最新！运小筹月刊首次发布！
第14篇：优化| 手把手教你用Python实现Dijkstra算法（附Python代码和可视化）
第13篇：优化|手把手教你用Python调用Gurobi求解最短路问题
第12篇：优化| 手把手教你用Java实现单纯形法
第11篇：优化| 手把手教你用Python调用Gurobi求解VRPTW
第10篇：优化 | 两阶段启发式算法求解带时间窗车辆路径问题（附Java代码）
第9篇：Java调用cplex求解运输问题
第8篇：优化 | 如何优雅地写出大规模线性规划的对偶
第7篇：优化 | TSP中两种不同消除子环路的方法及Callback实现（Python调用Gurobi求解）
第6篇：元启发式算法 | 禁忌搜索(Tabu Search)解决TSP问题(Python代码实现)
第5篇：论文代码复现 | 无人机与卡车联合配送(Python+Gurobi)
第4篇：优化|Shortest Path Problem及其对偶问题的一些探讨(附Python调用Gurobi实现)
第3篇：可视化|Python+OpenStreetMap的交通数据可视化(二)：OpenStreetMap+Python画城市交通路网图
第2篇：优化|最速下降法：详细案例+Python实现
第1篇：Python+networkX+OpenStreetMap实现交通数据可视化(一)：用OpenStreetMap下载地图数据
<hr/>作者：李心怡，清华大学，清华大学深圳国际研究生院，博士在读
作者：刘兴禄，清华大学，清华大学深圳国际研究生院，清华-伯克利深圳学院，博士在读
编辑：张瑞三，四川大学，硕士在读，E-mail:zrssum3@stu.scu.edu.cn，知乎ID：MunSum3

查看完整版本: 优化 | KKT条件学习笔记：理论介绍、详细计算案例 ...