优化理论
优化理论是寻找最优解的方法！理解优化理论，能帮助我们解决许多实际问题。
什么是优化？
优化（Optimization）是在约束条件下寻找目标函数的最优值（最大值或最小值）。
简单理解
优化就像"找最好的方案"：
- 有一个目标（如成本最小、利润最大）
- 有约束条件（如资源限制）
- 寻找最优解
数学形式
优化问题的一般形式：
约束优化问题：
\min_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0 \quad (i = 1, 2, \ldots, m) \\ & h_j(x) = 0 \quad (j = 1, 2, \ldots, p) \end{aligned}$$ 其中： - $f(x)$ 是**目标函数** - $g_i(x) \le 0$ 是**不等式约束** - $h_j(x) = 0$ 是**等式约束** ## 无约束优化 ### 一维优化 #### 黄金分割法 **黄金分割法**（Golden Section Search）是求解一维优化问题的方法。 **算法**： 1. 选择初始区间 $[a, b]$ 2. 计算两个内点：$x_1 = a + (1 - \phi)(b - a)$，$x_2 = a + \phi(b - a)$ 其中 $\phi = \frac{\sqrt{5} - 1}{2} \approx 0.618$（黄金比例） 3. 比较 $f(x_1)$ 和 $f(x_2)$，缩小区间 4. 重复步骤 2-3，直到满足精度要求 #### 牛顿法 **牛顿法**用于求解 $f'(x) = 0$： $$x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}$$ ### 多维优化 #### 梯度下降法 **梯度下降法**（Gradient Descent）是求解无约束优化问题的迭代方法。 **迭代公式**： $$x_{n+1} = x_n - \alpha \nabla f(x_n)$$ 其中 $\alpha$ 是**学习率**（步长）。 **几何意义**：沿着梯度的反方向（下降最快的方向）移动。 #### 牛顿法 **牛顿法**（Newton's Method）： $$x_{n+1} = x_n - [H_f(x_n)]^{-1} \nabla f(x_n)$$ 其中 $H_f(x_n)$ 是**海塞矩阵**（Hessian Matrix）。 ## 约束优化 ### 拉格朗日乘数法 **拉格朗日乘数法**（Lagrange Multiplier Method）用于求解等式约束优化问题。 **拉格朗日函数**： $$L(x, \lambda) = f(x) + \sum_{j=1}^{p} \lambda_j h_j(x)$$ **最优性条件**： $$\frac{\partial L}{\partial x_i} = 0, \quad \frac{\partial L}{\partial \lambda_j} = 0$$ ### KKT 条件 **KKT 条件**（Karush-Kuhn-Tucker Conditions）是约束优化问题的必要条件。 对于问题： $$\begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0 \quad (i = 1, 2, \ldots, m) \\ & h_j(x) = 0 \quad (j = 1, 2, \ldots, p) \end{aligned}$$ **KKT 条件**： 1. **可行性**：$g_i(x^*) \le 0$，$h_j(x^*) = 0$ 2. **对偶可行性**：$\lambda_i \ge 0$ 3. **互补松弛性**：$\lambda_i g_i(x^*) = 0$ 4. **梯度条件**：$\nabla f(x^*) + \sum \lambda_i \nabla g_i(x^*) + \sum \mu_j \nabla h_j(x^*) = 0$ ## 线性规划 ### 定义 **线性规划**（Linear Programming）是目标函数和约束都是线性的优化问题。 **标准形式**： $$\begin{aligned} \min_{x} \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \ge 0 \end{aligned}$$ ### 单纯形法 **单纯形法**（Simplex Method）是求解线性规划问题的经典方法。 **步骤**： 1. 将问题转化为标准形式 2. 找到初始可行解 3. 迭代改进，直到找到最优解 ## 非线性规划 ### 定义 **非线性规划**（Nonlinear Programming）是目标函数或约束至少有一个是非线性的优化问题。 ### 方法 - **梯度法**：使用梯度信息 - **拟牛顿法**：近似海塞矩阵 - **内点法**：处理约束 ## 优化应用 ### 工程优化 - 🏗️ **结构设计**：优化结构设计 - ⚙️ **系统优化**：优化系统性能 ### 经济优化 - 💰 **资源配置**：优化资源配置 - 📈 **投资组合**：优化投资组合 ### 机器学习 - 🤖 **参数优化**：优化模型参数 - 📊 **特征选择**：选择最优特征 ## 常见错误 ### 错误 1：局部最优和全局最优混淆 要注意区分局部最优和全局最优。 ### 错误 2：约束处理错误 要正确处理约束条件。 ### 错误 3：算法选择不当 要根据问题特点选择合适的优化算法。 ## 小练习 1. 用梯度下降法求 $f(x, y) = x^2 + y^2$ 的最小值 2. 用拉格朗日乘数法求解：$\min x^2 + y^2$，s.t. $x + y = 1$ 3. 说明 KKT 条件的意义 4. 应用题：在机器学习中，如何用优化方法训练模型？ --- > 💡 **小贴士**：优化理论是寻找最优解的方法。记住：梯度下降法沿着梯度反方向移动，拉格朗日乘数法处理等式约束，KKT 条件处理不等式约束。掌握优化理论，你就能解决许多优化问题！