Home 计算机 最优化

# 最优化

最优化问题 (Optimization Problem)「最適化問題」，是指在一系列约束条件，或者无约束下寻找目标函数的最值
最值虽然可以分为最大值和最小值两个，但是由于

max⁡x∈Rnf(x)=−min⁡x∈Rn(−f(x))\max_{\boldsymbol x \in \mathbb R^n} f(\boldsymbol x) = -\min_{\boldsymbol x \in \mathbb R^n} (-f(\boldsymbol x))

等价，所以优化问题中我们默认寻找最小值

当条件个数有限时，称为 数理规划问题 (Mathematical Programming Problem)「数理計画問題」，当条件个数无限时，称为 变分问题 (Variational Problem)「変分問題」。

给出一系列约束函数 gi,hj:Rn→Rg_i,h_j:\mathbb R^n \to \mathbb R，使用向量计法分别写为 g,h\boldsymbol g,\boldsymbol h

  • 等式约束条件写为 g(x)=0\boldsymbol g(\boldsymbol x) = \boldsymbol 0
  • 不等式约束条件写为 h(x)≤0\boldsymbol h(\boldsymbol x) \leq \boldsymbol 0

对于 f:Rn→Rf:\mathbb R^n \to \mathbb R，优化问题可以写为

Findmin⁡x∈Rnf(x)\text{Find} \min_{\boldsymbol x \in \mathbb R^n} f(\boldsymbol x)

约束条件下的优化问题可以写为

Findmin⁡x∈Rnf(x) subject to g(x)=0,h(x)≤0\text{Find} \min_{\boldsymbol x \in \mathbb R^n} f(\boldsymbol x) \text{ subject to } \boldsymbol g(\boldsymbol x) = \boldsymbol 0, \boldsymbol h(\boldsymbol x) \leq \boldsymbol 0

一般来说，ff 称为 目标函数 (Objective Function)「目的関数」，gig_i 和 hjh_j 称为 约束函数 (Constraint Function)「制約関数」

如果目标函数与约束函数均是线性，那么称该类问题为 线性规划问题 (Linear Programming Problem)「線形計画問題」，简称为 LP
否则被称为 非线性规划问题 (Nonlinear Programming Problem)「非線形計画問題」，简称为 NLP
NLP 问题中最广泛的是 二次规划问题 (Quadratic Programming Problem)「二次計画問題」，简称为 QP，即目标函数是二次函数，约束函数是线性函数的 NLP 问题，例如最小二乘问题就是一个典型的二次规划问题