二阶锥规划示例及其对偶 发表于 2025-04-11 更新于 2025-05-18 分类于 最优化 二阶锥规划(SOCP) 二阶锥规划(Second-order cone program)，是指目标函数为线性函数，约束条件中的决策变量在二阶锥中。 SOCP的原始和对偶问题 SOCP的原始问题为： minf⊤xs. t.∥Aix+bi∥2≤ci⊤x+di,i=1,…,m\begin{array}{ll} \min & \boldsymbol{f}^\top\boldsymbol{x}\\ \mathrm{s.~t.} & \|\boldsymbol{A}_i\boldsymbol{x} + \boldsymbol{b}_i\|_2 \leq \boldsymbol{c}_i^\top \boldsymbol{x} + d_i, \quad i=1,\ldots,m \end{array} mins. t.f⊤x∥Aix+bi∥2≤ci⊤x+di,i=1,…,m 其中Ai∈Rni×n,bi∈Rni,ci∈Rn,di∈R,x∈Rn,i=1,…,mA_i\in\mathbb{R}^{n_i\times n},\boldsymbol{b}_i\in\mathbb{R}^{n_i},\boldsymbol{c}_i\in\mathbb{R}^n,d_i\in\mathbb{R},\boldsymbol{x}\in\mathbb{R}^n, i=1,\ldots,mAi∈Rni×n,bi∈Rni,ci∈Rn,di∈R,x∈Rn,i=1,…,m。 阅读全文 »
Gradient descent method 发表于 2024-12-17 更新于 2025-05-18 分类于 最优化 梯度下降法 梯度下降法是一种用于优化函数的优化算法，它通过迭代地更新参数以找到函数的最小值。 阅读全文 »
列生成算法 发表于 2024-12-04 更新于 2025-05-18 分类于 运筹优化 列生成算法是在混合整数规划中一个经典的且强大的精确算法。 引例-下料问题 一家木材厂有一种长度为80英寸的木材原料。现在有3个顾客，他们分别需要46个10英寸，22个11英寸，43个19英寸的木材产品。 为了满足客户不同的需求并且使得切割的原料最少，问该公司最少需要的木材多少根，以及如何切割？ 阅读全文 »