• 带约束优化问题 (Constrained Optimization)
  • 1. 问题概述
    • 1.1 问题形式
    • 1.2 问题分类
  • 2. 等式约束优化问题
    • 2.1 问题形式
    • 2.2 拉格朗日乘子法 (Lagrange Multiplier Method)
      • 2.2.1 求解步骤
      • 2.2.2 几何解释
      • 2.2.3 简单示例
  • 3. 线性等式约束二次目标函数优化问题
    • 3.1 问题形式
    • 3.2 求解方法
  • 4. 一般不等式约束优化问题
    • 4.1 问题形式
    • 4.2 KKT条件
      • 4.2.1 求解步骤
      • 4.2.2 简单示例
    • 4.3 对偶问题方法
      • 4.3.1 基本概念
      • 4.3.2 简单示例
    • 4.4 内点法 (Interior Point Method)
      • 4.4.1 基本概念
      • 4.4.2 障碍函数的理解
      • 4.4.3 简单示例
    • 4.5 序列二次规划法 (Sequential Quadratic Programming, SQP)
      • 4.5.1 基本思想
    • 4.6 方法比较
      • 4.6.1 方法比较总结表
      • 4.6.2 方法选择决策树
  • 5. 线性不等式约束线性目标函数优化问题 LP
    • 5.1 问题形式
    • 5.2 求解方法
      • 5.2.1 单纯形法 (Simplex Method)
      • 5.2.2 内点法 (Interior Point Method)
      • 5.2.3 对偶单纯形法 (Dual Simplex Method)
      • 5.2.4 分支定界法 (Branch and Bound)
      • 5.2.5 切割平面法 (Cutting Plane Method)
    • 5.3 方法比较
    • 5.4 方法选择建议
  • 6. 线性不等式约束二次目标函数优化问题 QP
    • 6.1 问题形式
    • 6.2 最优性条件
      • 6.2.1 KKT条件
      • 6.2.2 最优性判别
    • 6.3 对偶问题
    • 6.4 内点法
    • 6.5 ADMM算法
      • 6.5.1 基本思想
      • 6.5.2 标准形式
      • 6.5.3 算法步骤
      • 6.5.4 收敛条件
      • 6.5.5 在QP问题中的应用
      • 6.5.6 算法优势
      • 6.5.7 算法缺点
      • 6.5.8 实际应用建议
    • 6.6 有效集法（Active Set Method）
    • 6.7 梯度投影法（Gradient Projection Method）
    • 6.8 求解方法的选择
    • 6.9 数值稳定性
      • 6.9.1 条件数
      • 6.9.2 预处理
      • 6.9.3 收敛性分析
    • 6.10 求解工具
  • 7. 带约束最小二乘问题 SLSQP
    • 7.1 问题形式
    • 7.2 SLSQP的QP子问题
    • 7.3 QP子问题的构造原理
    • 7.4 算法实现细节
      • 7.4.1 拉格朗日函数
      • 7.4.2 迭代更新
      • 7.4.3 收敛条件
      • 7.4.4 Hessian矩阵更新
      • 7.4.5 线搜索条件
      • 7.4.6 算法复杂度
      • 7.4.7 收敛性分析
    • 7.5 示例
    • 7.6 与其他优化方法的比较
      • 7.6.1 SLSQP与SQP的比较
        • 主要区别
        • 选择建议
      • 7.6.2 SLSQP与牛顿法的比较
      • 7.6.3 SLSQP与拟牛顿法的比较

---

Created 2021.03.22 by Cong Yu; Last modified: 2024.06.22-v4.3.2

Contact: windmillyucong@163.com

Copyleft! 2024 Cong Yu. Some rights reserved.

---

带约束优化问题 (Constrained Optimization)

[TOC]

1. 问题概述

1.1 问题形式

带约束优化问题的一般形式为：

\[\begin{align} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad g_i(x) \leq 0, \quad i = 1,2,\ldots,m \\ &\quad h_j(x) = 0, \quad j = 1,2,\ldots,p \end{align}\]

其中：

• $f(x): \mathbb{R}^n \to \mathbb{R}$ 是目标函数
• $g_i(x)$ 是不等式约束
• $h_j(x)$ 是等式约束
• $x \in \mathbb{R}^n$ 是决策变量

1.2 问题分类

根据目标函数和约束条件的性质，带约束优化问题可以分为以下几类：

1. 等式约束优化问题
2. 线性等式约束二次目标函数优化问题
3. 线性不等式约束线性目标函数 - 线性规划问题(LP)
4. 线性不等式约束二次目标函数 - 二次规划问题(QP)
5. 一般不等式约束最小二乘目标函数 - 带约束最小二乘问题(SLSQP)
6. 一般不等式约束优化问题

2. 等式约束优化问题

2.1 问题形式

\[\begin{align} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad h_j(x) = 0, \quad j = 1,2,\ldots,p \end{align}\]

2.2 拉格朗日乘子法 (Lagrange Multiplier Method)

2.2.1 求解步骤

1. 构造拉格朗日函数： \(\mathcal{L}(x,\lambda) = f(x) + \sum_{j=1}^p \lambda_j h_j(x)\) 其中 $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_p)^T$ 是拉格朗日乘子向量。

2. 求一阶必要条件（驻点条件）： \(\begin{align} \frac{\partial \mathcal{L}}{\partial x_i} &= 0, \quad i = 1,2,\ldots,n \\ \frac{\partial \mathcal{L}}{\partial \lambda_j} &= 0, \quad j = 1,2,\ldots,p \end{align}\)

   这等价于： \(\begin{align} \nabla_x \mathcal{L}(x,\lambda) &= \nabla f(x) + \sum_{j=1}^p \lambda_j \nabla h_j(x) = 0 \\ \nabla_\lambda \mathcal{L}(x,\lambda) &= h(x) = 0 \end{align}\)

   其中 $h(x) = (h_1(x), h_2(x), \ldots, h_p(x))^T$。

3. 验证二阶充分条件： 构造海森矩阵（Hessian matrix）： \(H = \begin{bmatrix} \frac{\partial^2 \mathcal{L}}{\partial x_1^2} & \frac{\partial^2 \mathcal{L}}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 \mathcal{L}}{\partial x_1 \partial x_n} \\ \frac{\partial^2 \mathcal{L}}{\partial x_2 \partial x_1} & \frac{\partial^2 \mathcal{L}}{\partial x_2^2} & \cdots & \frac{\partial^2 \mathcal{L}}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 \mathcal{L}}{\partial x_n \partial x_1} & \frac{\partial^2 \mathcal{L}}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 \mathcal{L}}{\partial x_n^2} \end{bmatrix}\)

   对于所有满足约束的向量 $d \in \mathbb{R}^n$（即 $\nabla h_j(x)^T d = 0, \forall j$），如果： \(d^T H d > 0\) 则当前点是局部最小值点。

4. 选择最优解： 比较所有满足一阶和二阶条件的点，选择使目标函数值最小的点作为全局最优解： \(x^* = \arg\min_{x \in S} f(x)\) 其中 $S$ 是所有满足条件的点的集合。

2.2.2 几何解释

在最优解处，目标函数的梯度与约束函数的梯度平行

\[\nabla f(x^*) = \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*)\]

2.2.3 简单示例

\[\begin{align} \min_{x,y} &\quad f(x,y) = x^2 + y^2 \\ \text{s.t.} &\quad h(x,y) = x + y - 1 = 0 \end{align}\]

求解步骤：

1. 构造拉格朗日函数： \(\mathcal{L}(x,y,\lambda) = x^2 + y^2 + \lambda(x + y - 1)\)

2. 求一阶必要条件（驻点条件）： \(\begin{align} \frac{\partial \mathcal{L}}{\partial x} &= 2x + \lambda = 0 \quad (1) \\ \frac{\partial \mathcal{L}}{\partial y} &= 2y + \lambda = 0 \quad (2) \\ \frac{\partial \mathcal{L}}{\partial \lambda} &= x + y - 1 = 0 \quad (3) \end{align}\)

3. 求解方程组，得
   • $\lambda = -1$
   • $x = y = \frac{1}{2}$
4. 验证二阶充分条件：
   • 计算二阶偏导数： \(\begin{align} \frac{\partial^2 \mathcal{L}}{\partial x^2} &= 2 \\ \frac{\partial^2 \mathcal{L}}{\partial y^2} &= 2 \\ \frac{\partial^2 \mathcal{L}}{\partial x \partial y} &= 0 \end{align}\)
   • 构造海森矩阵： \(H = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)
   • 对于满足约束的向量 $d = (d_1, d_2)^T$，有： \(\nabla h(x,y)^T d = (1,1) \begin{pmatrix} d_1 \\ d_2 \end{pmatrix} = d_1 + d_2 = 0\)
   • 因此 $d_2 = -d_1$
   • 计算二次型： \(d^T H d = 2d_1^2 + 2d_2^2 = 2d_1^2 + 2(-d_1)^2 = 4d_1^2 > 0\)
   • 由于二次型恒为正，说明当前点是局部最小值点
5. 计算最优值：
   • 将 $x = y = \frac{1}{2}$ 代入目标函数： \(f(\frac{1}{2}, \frac{1}{2}) = (\frac{1}{2})^2 + (\frac{1}{2})^2 = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}\)
6. 几何解释：
   • 目标函数 $f(x,y) = x^2 + y^2$ 表示到原点的距离的平方
   • 约束 $x + y = 1$ 表示一条直线
   • 最优解 $(\frac{1}{2}, \frac{1}{2})$ 是直线上距离原点最近的点
   • 这个点也是直线与以原点为中心的圆的切点

因此，该优化问题的最优解为：

• 最优解：$x^* = y^* = \frac{1}{2}$
• 最优值：$f(x^,y^) = \frac{1}{2}$
• 对应的拉格朗日乘子：$\lambda^* = -1$

3. 线性等式约束二次目标函数优化问题

3.1 问题形式

\(\begin{align}\min_{x} &\quad\frac{1}{2}x^T Q x + p^T x\\ s.t. &\quad Ax = b \end{align}\)

其中 $Q \in \mathbb{R}^{n \times n}$ 是对称正定矩阵，$A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$

3.2 求解方法

构造拉格朗日函数： \(\mathcal{L}(x,\lambda) = \frac{1}{2}x^T Q x + p^T x + \lambda^T(Ax-b)\)

KKT条件：

1. $\nabla_x \mathcal{L} = Qx + p + A^T\lambda = 0$
2. $Ax = b$

整理得到线性方程组，直接求解即可 \(\begin{bmatrix} Q & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} -p \\ b \end{bmatrix}\)

4. 一般不等式约束优化问题

4.1 问题形式

\[\begin{align} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad g_i(x) \leq 0, \quad i = 1,2,\ldots,m \\ &\quad h_j(x) = 0, \quad j = 1,2,\ldots,p \end{align}\]

也就是本文最开始的通用的带约束的问题形式

4.2 KKT条件

4.2.1 求解步骤

当问题同时包含等式约束和不等式约束时，我们需要使用更一般的 KKT 条件。KKT 条件是对拉格朗日乘子法的推广，它能够处理不等式约束。

1. 构造拉格朗日函数： \(\mathcal{L}(x,\lambda,\mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)\) 其中：
   • $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_m)^T$ 是不等式约束的拉格朗日乘子
   • $\mu = (\mu_1, \mu_2, \ldots, \mu_p)^T$ 是等式约束的拉格朗日乘子
2. KKT条件提供了最优解的必要条件，写出KKT方程组：
   • 梯度条件： \(\nabla_x \mathcal{L}(x,\lambda,\mu) = \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) + \sum_{j=1}^p \mu_j \nabla h_j(x) = 0\)
   • 原始可行性条件： \(g_i(x) \leq 0, \quad i = 1,2,\ldots,m\) \(h_j(x) = 0, \quad j = 1,2,\ldots,p\)
   • 对偶可行性条件： \(\lambda_i \geq 0, \quad i = 1,2,\ldots,m\)
   • 互补松弛条件： \(\lambda_i g_i(x) = 0, \quad i = 1,2,\ldots,m\)
3. 求解KKT方程组：
   • 对于每个不等式约束，考虑两种情况：
     • 情况1：$\lambda_i = 0$ 且 $g_i(x) \leq 0$
     • 情况2：$\lambda_i > 0$ 且 $g_i(x) = 0$
   • 对于每个等式约束，直接使用 $h_j(x) = 0$
   • 结合梯度条件，求解所有可能的组合
4. 验证解的可行性：
   • 检查所有约束是否满足
   • 验证拉格朗日乘子的符号条件
   • 确认互补松弛条件成立
5. 选择最优解：
   • 比较所有满足KKT条件的点
   • 选择使目标函数值最小的点作为最优解
6. 验证二阶条件（可选）：
   • 如果问题满足某些正则性条件（如LICQ），可以验证二阶充分条件
   • 检查拉格朗日函数的Hessian矩阵在约束切空间上的正定性

注意事项：

• KKT条件只是必要条件，不是充分条件
• 对于凸优化问题，KKT条件是充分必要条件
• 在实际应用中，可能需要考虑数值计算的稳定性
• 对于大规模问题，可能需要使用数值优化方法求解KKT方程组

4.2.2 简单示例

考虑以下优化问题：

\[\begin{align} \min_{x,y} &\quad f(x,y) = x^2 + y^2 \\ \text{s.t.} &\quad g_1(x,y) = x + y - 1 \leq 0 \\ &\quad g_2(x,y) = -x \leq 0 \\ &\quad g_3(x,y) = -y \leq 0 \end{align}\]

这是一个带不等式约束的优化问题，我们可以使用KKT条件求解。

求解步骤：

1. 构造拉格朗日函数： \(\mathcal{L}(x,y,\lambda) = x^2 + y^2 + \lambda_1(x + y - 1) + \lambda_2(-x) + \lambda_3(-y)\) 其中 $\lambda_1, \lambda_2, \lambda_3$ 是拉格朗日乘子。

2. 写出KKT条件：
   • 梯度条件： \(\begin{align} \frac{\partial \mathcal{L}}{\partial x} &= 2x + \lambda_1 - \lambda_2 = 0 \quad (1) \\ \frac{\partial \mathcal{L}}{\partial y} &= 2y + \lambda_1 - \lambda_3 = 0 \quad (2) \end{align}\)
   • 原始可行性条件： \(\begin{align} x + y - 1 &\leq 0 \quad (3) \\ -x &\leq 0 \quad (4) \\ -y &\leq 0 \quad (5) \end{align}\)
   • 对偶可行性条件： \(\lambda_1, \lambda_2, \lambda_3 \geq 0 \quad (6)\)
   • 互补松弛条件： \(\begin{align} \lambda_1(x + y - 1) &= 0 \quad (7) \\ \lambda_2(-x) &= 0 \quad (8) \\ \lambda_3(-y) &= 0 \quad (9) \end{align}\)

3. 分析可能的解： 由于有3个不等式约束，需要考虑 $2^3 = 8$ 种情况。我们分析几种主要情况：

   情况1：所有约束都是活跃的（即等号成立）

   • $x + y = 1$
   • $x = 0$
   • $y = 0$ 但这与 $x + y = 1$ 矛盾，所以这种情况无解。

   情况2：只有 $g_1$ 是活跃的

   • $x + y = 1$
   • $x > 0$
   • $y > 0$
   • 由互补松弛条件：$\lambda_2 = \lambda_3 = 0$
   • 代入梯度条件： \(\begin{align} 2x + \lambda_1 &= 0 \\ 2y + \lambda_1 &= 0 \end{align}\)
   • 解得：$x = y = \frac{1}{2}, \lambda_1 = -1$
   • 但 $\lambda_1 < 0$ 违反对偶可行性，所以这种情况无解。

   情况3：只有 $g_2$ 和 $g_3$ 是活跃的

   • $x = 0$
   • $y = 0$
   • 由互补松弛条件：$\lambda_1 = 0$
   • 代入梯度条件： \(\begin{align} -\lambda_2 &= 0 \\ -\lambda_3 &= 0 \end{align}\)
   • 解得：$\lambda_2 = \lambda_3 = 0$
   • 这个解满足所有KKT条件
4. 验证二阶充分条件：
   • 计算二阶偏导数： \(\begin{align} \frac{\partial^2 \mathcal{L}}{\partial x^2} &= 2 \\ \frac{\partial^2 \mathcal{L}}{\partial y^2} &= 2 \\ \frac{\partial^2 \mathcal{L}}{\partial x \partial y} &= 0 \end{align}\)
   • 海森矩阵： \(H = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)
   • 对于满足约束的向量 $d = (d_1, d_2)^T$，有： \(\nabla g_2^T d = -d_1 = 0\) \(\nabla g_3^T d = -d_2 = 0\)
   • 因此 $d_1 = d_2 = 0$，二次型 $d^T H d = 0$
   • 由于问题为凸优化问题，且满足KKT条件，所以当前点是全局最优解
5. 几何解释：
   • 目标函数 $f(x,y) = x^2 + y^2$ 表示到原点的距离的平方
   • 约束 $g_1$ 表示直线 $x + y = 1$ 下方的区域
   • 约束 $g_2$ 和 $g_3$ 表示第一象限
   • 最优解 $(0,0)$ 是可行域中距离原点最近的点

因此，该优化问题的最优解为：

• 最优解：$x^* = y^* = 0$
• 最优值：$f(x^,y^) = 0$
• 对应的拉格朗日乘子：$\lambda_1^* = 0, \lambda_2^* = 0, \lambda_3^* = 0$

4.3 对偶问题方法

4.3.1 基本概念

对偶问题方法通过将原问题转化为对偶问题来求解。

1. 对偶函数： \(g(\lambda,\mu) = \inf_{x \in \mathcal{D}} \mathcal{L}(x,\lambda,\mu)\)

2. 对偶问题： \(\begin{align} \max_{\lambda,\mu} &\quad g(\lambda,\mu) \\ \text{s.t.} &\quad \lambda_i \geq 0, \quad i = 1,2,\ldots,m \end{align}\)

3. 重要性质：

   • 弱对偶性：$g(\lambda,\mu) \leq f(x^*)$
   • 强对偶性：在凸优化问题中，$\max_{\lambda \geq 0, \mu} g(\lambda,\mu) = \min_{x} f(x)$

4.3.2 简单示例

\[\begin{align} \min_{x_1,x_2} &\quad f(x_1,x_2) = 2x_1 + 3x_2 \\ \text{s.t.} &\quad x_1 + x_2 \geq 1 \\ &\quad x_1 \geq 0, x_2 \geq 0 \end{align}\]

解：

• 构造拉格朗日函数：$\mathcal{L}(x_1,x_2,\lambda) = 2x_1 + 3x_2 + \lambda(1 - x_1 - x_2)$
• 对偶函数：$g(\lambda) = \inf_{x_1,x_2 \geq 0} [2x_1 + 3x_2 + \lambda(1 - x_1 - x_2)]$
• 对偶问题：$\max_{\lambda} \lambda$ s.t. $\lambda \leq 2, \lambda \leq 3, \lambda \geq 0$
• 对偶最优解：$\lambda^* = 2, g(\lambda^*) = 2$

4.4 内点法 (Interior Point Method)

4.4.1 基本概念

内点法主要用于求解凸优化问题，特别是：

1. 线性规划问题 (LP)
2. 二次规划问题 (QP)
3. 半定规划问题 (SDP)
4. 锥规划问题

内点法的基本思想是：

1. 通过引入障碍函数将约束优化问题转化为无约束问题： \(\min_{x} f(x) - \mu \sum_{i=1}^m \ln(-g_i(x))\) 其中 $\mu > 0$ 是障碍参数。

2. 从可行域内部开始，通过迭代逐渐接近最优解
3. 随着迭代进行，障碍参数 $\mu$ 逐渐减小，使得解越来越接近原问题的最优解

4.4.2 障碍函数的理解

障碍函数（Barrier Function）是内点法中的核心概念，它的主要作用是：

1. 基本形式：
   • 对于不等式约束 $g_i(x) \leq 0$，障碍函数通常取为： \(B(x) = -\sum_{i=1}^m \ln(-g_i(x))\)
   • 完整的障碍问题形式为： \(\min_{x} f(x) - \mu B(x)\) 其中 $\mu > 0$ 是障碍参数
2. 工作原理：
   • 当 $x$ 接近约束边界时（即 $g_i(x) \to 0$），$-\ln(-g_i(x)) \to +\infty$
   • 这会在约束边界处形成一个”障碍”，阻止解越过约束边界
   • 当 $x$ 在可行域内部时，障碍函数的值是有限的
   • 随着 $\mu$ 的减小，障碍的影响逐渐减弱
3. 几何意义：
   • 障碍函数在约束边界处形成一个”墙”
   • 这面”墙”的高度由 $\mu$ 控制
   • 当 $\mu$ 较大时，”墙”很高，解会被限制在可行域内部
   • 当 $\mu$ 减小时，”墙”变矮，解可以更接近约束边界
   • 当 $\mu \to 0$ 时，”墙”消失，解可以到达约束边界
4. 数学性质：
   • 连续性：障碍函数在可行域内部是连续的
   • 可导性：障碍函数在可行域内部是可导的
   • 凸性：如果原问题是凸的，障碍问题也是凸的
   • 单调性：随着 $\mu$ 的减小，障碍问题的解逐渐接近原问题的最优解
5. 实际应用中的考虑：
   • 初始点选择：必须选择严格可行的初始点
   • 步长控制：需要确保迭代点始终在可行域内部
   • 参数更新：$\mu$ 的减小速度影响算法的收敛性
   • 数值稳定性：需要处理接近边界时的数值问题
6. 示例说明： 考虑简单约束 $x \geq 0$：
   • 障碍函数为 $-\ln(x)$
   • 当 $x \to 0$ 时，$-\ln(x) \to +\infty$
   • 当 $x$ 较大时，$-\ln(x)$ 的影响较小
   • 随着 $\mu$ 的减小，解可以更接近 $x = 0$
7. 优势：
   • 保证解始终在可行域内部
   • 不需要处理约束违反的情况
   • 可以处理大量约束
   • 收敛性好
8. 局限性：
   • 需要严格可行的初始点
   • 在约束边界处可能数值不稳定
   • 计算障碍函数及其导数可能计算量大

4.4.3 简单示例

考虑以下优化问题：

\[\begin{align} \min_{x,y} &\quad f(x,y) = x^2 + y^2 \\ \text{s.t.} &\quad g_1(x,y) = x + y - 1 \leq 0 \\ &\quad g_2(x,y) = -x \leq 0 \\ &\quad g_3(x,y) = -y \leq 0 \end{align}\]

使用内点法求解的步骤：

1. 构造障碍函数： \(\begin{align} \phi_\mu(x,y) &= f(x,y) - \mu \sum_{i=1}^3 \ln(-g_i(x,y)) \\ &= x^2 + y^2 - \mu [\ln(1-x-y) + \ln(x) + \ln(y)] \end{align}\)

2. 计算梯度： \(\begin{align} \frac{\partial \phi_\mu}{\partial x} &= 2x + \mu \left(\frac{1}{1-x-y} - \frac{1}{x}\right) \\ \frac{\partial \phi_\mu}{\partial y} &= 2y + \mu \left(\frac{1}{1-x-y} - \frac{1}{y}\right) \end{align}\)

3. 迭代过程： 从初始点 $(x_0, y_0) = (0.5, 0.5)$ 开始，设置 $\mu_0 = 1$，迭代步骤如下：

   第1次迭代（$\mu = 1$）：

   • 求解方程组： \(\begin{align} 2x + \left(\frac{1}{1-x-y} - \frac{1}{x}\right) &= 0 \\ 2y + \left(\frac{1}{1-x-y} - \frac{1}{y}\right) &= 0 \end{align}\)
   • 使用牛顿法求解，得到： \(x_1 \approx 0.333, y_1 \approx 0.333\)

   第2次迭代（$\mu = 0.1$）：

   • 求解方程组： \(\begin{align} 2x + 0.1\left(\frac{1}{1-x-y} - \frac{1}{x}\right) &= 0 \\ 2y + 0.1\left(\frac{1}{1-x-y} - \frac{1}{y}\right) &= 0 \end{align}\)
   • 得到： \(x_2 \approx 0.167, y_2 \approx 0.167\)

   第3次迭代（$\mu = 0.01$）：

   • 求解方程组： \(\begin{align} 2x + 0.01\left(\frac{1}{1-x-y} - \frac{1}{x}\right) &= 0 \\ 2y + 0.01\left(\frac{1}{1-x-y} - \frac{1}{y}\right) &= 0 \end{align}\)
   • 得到： \(x_3 \approx 0.033, y_3 \approx 0.033\)
4. 收敛性分析：
   • 随着 $\mu$ 的减小，解逐渐接近最优解 $(0,0)$
   • 每次迭代后，目标函数值的变化： \(\begin{align} f(x_0,y_0) &= 0.5 \\ f(x_1,y_1) &\approx 0.222 \\ f(x_2,y_2) &\approx 0.056 \\ f(x_3,y_3) &\approx 0.002 \end{align}\)
5. 几何解释：
   • 障碍函数在约束边界处趋向于无穷大
   • 随着 $\mu$ 的减小，障碍函数的影响逐渐减弱
   • 迭代路径始终保持在可行域内部
   • 最终收敛到最优解 $(0,0)$
6. 算法特点：
   • 每次迭代都需要求解一个无约束优化问题
   • 可以使用牛顿法等高效方法求解
   • 收敛速度与 $\mu$ 的减小策略有关
   • 需要选择合适的初始点和 $\mu$ 值
7. 实际应用中的注意事项：
   • 选择合适的 $\mu$ 更新策略（如 $\mu_{k+1} = 0.1\mu_k$）
   • 设置合适的收敛准则
   • 处理数值计算中的稳定性问题
   • 考虑问题的特殊结构以加速求解

4.5 序列二次规划法 (Sequential Quadratic Programming, SQP)

SQP方法适用于求解一般的非线性规划问题：

1. 目标函数和约束函数都是非线性的
2. 约束可以是等式或不等式
3. 问题不要求是凸的

4.5.1 基本思想

1. 在每次迭代中，在点 $x_k$ 处对目标函数和约束进行二阶泰勒展开：

\[f(x) \approx f(x_k) + \nabla f(x_k)^T(x-x_k) + \frac{1}{2}(x-x_k)^T \nabla^2 f(x_k)(x-x_k)\] \[g_i(x) \approx g_i(x_k) + \nabla g_i(x_k)^T(x-x_k) + \frac{1}{2}(x-x_k)^T \nabla^2 g_i(x_k)(x-x_k)\] \[h_i(x) \approx h_i(x_k) + \nabla h_i(x_k)^T(x-x_k) + \frac{1}{2}(x-x_k)^T \nabla^2 h_i(x_k)(x-x_k)\]

1. 构造一个二次规划QP子问题： \(\min_{\Delta x} \frac{1}{2}\Delta x^T H_k \Delta x + \nabla f(x_k)^T \Delta x\) s.t. \(\begin{align}g_i(x_k) + \nabla g_i(x_k)^T \Delta x \leq 0 \\ h_j(x_k) + \nabla h_j(x_k)^T \Delta x = 0 \end{align}\) \(\)

2. 求解这个二次规划子问题，得到搜索方向
3. 沿着搜索方向进行线搜索，确定步长
4. 更新当前点，继续迭代

SQP的优势：

• 可以处理非凸问题
• 收敛速度快（二阶收敛）
• 可以处理等式和不等式约束
• 对初始点要求不高

QP的具体求解方法详见下文QP问题章节

4.6 方法比较

4.6.1 方法比较总结表

方法	适用问题	优势	局限性	计算复杂度	实现难度
拉格朗日乘子法	• 等式约束问题 • 小规模问题	• 理论基础清晰 • 计算简单 • 可得到解析解	• 只适用于等式约束 • 要求约束线性独立 • 不适用于大规模问题	低	低
对偶问题方法	• 凸优化问题 • 原问题难解的问题	• 可能比原问题易解 • 提供最优值下界 • 可处理大规模问题	• 需要强对偶性 • 对偶问题可能复杂 • 恢复原问题解可能困难	中-高	中
内点法	• 凸优化问题 • 大规模问题 • 多约束问题	• 多项式时间复杂度 • 可处理大量约束 • 收敛性好	• 需要问题凸性 • 对初始点要求高 • 实现复杂	中	高
SQP方法	• 一般非线性问题 • 非凸问题 • 中小规模问题	• 可处理非凸问题 • 收敛速度快 • 精度高	• 计算成本高 • 大规模问题效率低 • 需要二阶导数	高	高

4.6.2 方法选择决策树

1. 问题类型：
   • 等式约束 → 拉格朗日乘子法
   • 不等式约束：
     • 凸优化问题：
       • 大规模问题 → 内点法
       • 小规模问题 → 对偶方法
     • 非凸问题 → SQP方法
2. 问题规模：
   • 大规模问题 → 内点法
   • 中小规模问题：
     • 高精度要求 → SQP方法
     • 一般精度要求 → 对偶方法
3. 计算资源：
   • 资源有限 → 拉格朗日乘子法
   • 资源充足：
     • 需要快速求解 → 内点法
     • 需要高精度 → SQP方法

5. 线性不等式约束线性目标函数优化问题 LP

5.1 问题形式

线性规划(Linear Programming, LP)是一种特殊的优化问题，其目标函数和约束条件都是线性的。标准形式如下：

\[\begin{aligned} \min_{x} \quad &c^T x \\ \text{s.t.} \quad &Ax = b \\ &Gx \leq h \end{aligned}\]

其中：

• $x \in \mathbb{R}^n$ 是优化变量
• $c \in \mathbb{R}^n$ 是目标函数系数向量
• $A \in \mathbb{R}^{m_e \times n}$ 是等式约束矩阵
• $b \in \mathbb{R}^{m_e}$ 是等式约束向量
• $G \in \mathbb{R}^{m_i \times n}$ 是不等式约束矩阵
• $h \in \mathbb{R}^{m_i}$ 是不等式约束向量
• $m_e$ 是等式约束的数量
• $m_i$ 是不等式约束的数量

5.2 求解方法

5.2.1 单纯形法 (Simplex Method)

单纯形法是最经典的LP求解方法，其基本思想是：

1. 在可行域的顶点之间移动
2. 每次移动到使目标函数值更优的相邻顶点
3. 直到找到最优解或确定问题无界

算法步骤：

1. 将问题转化为标准形式
2. 找到初始基本可行解
3. 计算检验数（reduced costs）
4. 选择入基变量和出基变量
5. 更新基本可行解
6. 重复步骤3-5直到收敛

优点：

• 理论基础完善
• 实现相对简单
• 可以处理大规模问题

缺点：

• 最坏情况下是指数时间复杂度
• 对数值误差敏感

5.2.2 内点法 (Interior Point Method)

内点法通过从可行域内部开始，通过迭代逐渐接近最优解。

算法步骤：

1. 构造障碍函数： \(\phi(x) = -\sum_{i=1}^m \log(h_i - g_i^T x)\)

2. 求解中心路径问题： \(\min_x c^T x - \mu \sum_{i=1}^m \log(h_i - g_i^T x)\) 其中 $\mu > 0$ 是中心参数

3. 迭代更新：

   • 计算搜索方向
   • 确定步长
   • 更新当前点
   • 减小中心参数

优点：

• 多项式时间复杂度
• 数值稳定性好
• 适合大规模问题

缺点：

• 实现复杂
• 对初始点要求高

5.2.3 对偶单纯形法 (Dual Simplex Method)

对偶单纯形法在保持对偶可行性的同时，通过迭代使原始问题可行。

算法步骤：

1. 找到对偶可行解
2. 检查原始可行性
3. 选择出基变量
4. 选择入基变量
5. 更新基本解
6. 重复步骤2-5直到收敛

优点：

• 适合处理约束条件变化的问题
• 可以处理大规模问题

缺点：

• 收敛速度可能较慢
• 实现相对复杂

5.2.4 分支定界法 (Branch and Bound)

分支定界法主要用于求解整数线性规划问题。

算法步骤：

1. 求解LP松弛问题
2. 如果解是整数，则停止
3. 否则，选择非整数变量进行分支
4. 对每个分支求解子问题
5. 更新上下界
6. 剪枝
7. 重复步骤2-6直到找到最优解

优点：

• 可以处理整数规划问题
• 保证找到全局最优解

缺点：

• 计算量大
• 内存消耗大

5.2.5 切割平面法 (Cutting Plane Method)

切割平面法通过添加新的约束条件来逼近可行域。

算法步骤：

1. 求解当前LP问题
2. 生成切割平面
3. 添加新的约束
4. 重复步骤1-3直到收敛

优点：

• 可以处理复杂的约束条件
• 适合处理大规模问题

缺点：

• 收敛速度可能较慢
• 需要有效的切割平面生成策略

5.3 方法比较

方法	适用问题	优势	局限性	计算复杂度	实现难度
单纯形法	一般LP问题	理论基础清晰，实现简单	最坏情况指数时间	中	低
内点法	大规模LP问题	多项式时间复杂度，数值稳定	对初始点要求高	中	高
对偶单纯形法	约束变化的问题	适合处理约束变化	收敛可能较慢	中	中
分支定界法	整数规划问题	保证全局最优	计算量大	高	高
切割平面法	复杂约束问题	可处理复杂约束	收敛可能较慢	中	中

5.4 方法选择建议

1. 问题规模考虑：
   • 小规模问题：可以使用单纯形法
   • 大规模问题：建议使用内点法
   • 整数规划问题：使用分支定界法
2. 数值稳定性：
   • 如果问题条件数较大，建议使用内点法
   • 如果问题结构简单，可以使用单纯形法
3. 约束特点：
   • 约束经常变化：考虑对偶单纯形法
   • 约束复杂：考虑切割平面法
4. 计算资源：
   • 资源有限：选择单纯形法
   • 资源充足：可以选择内点法
5. 精度要求：
   • 高精度要求：使用内点法
   • 一般精度要求：可以使用单纯形法

6. 线性不等式约束二次目标函数优化问题 QP

6.1 问题形式

二次规划(Quadratic Programming, QP)是一种特殊的优化问题，其目标函数是二次型，约束条件为线性不等式。标准形式如下：

\[\begin{aligned} \min_{x} \quad &\frac{1}{2}x^T P x + q^T x \\ \text{s.t.} \quad &Ax = b \\ &Gx \leq h \end{aligned}\]

其中：

• $x \in \mathbb{R}^n$ 是优化变量
• $P \in \mathbb{R}^{n \times n}$ 是半正定矩阵（确保问题是凸的）
• $q \in \mathbb{R}^n$ 是线性项系数向量
• $A \in \mathbb{R}^{m_e \times n}$ 是等式约束矩阵
• $b \in \mathbb{R}^{m_e}$ 是等式约束向量
• $G \in \mathbb{R}^{m_i \times n}$ 是不等式约束矩阵
• $h \in \mathbb{R}^{m_i}$ 是不等式约束向量
• $m_e$ 是等式约束的数量
• $m_i$ 是不等式约束的数量

其中：

1. $Ax = b$ 表示等式约束
2. $Gx \leq h$ 表示不等式约束
3. 上述约束形式也可变化为 $l \leq Ax \leq u$

6.2 最优性条件

6.2.1 KKT条件

对于QP问题，其最优解满足以下KKT条件：

1. 原始可行性： \(Ax^* = b\) \(Gx^* \leq h\)

2. 对偶可行性： \(\lambda^* \geq 0\)

3. 互补松弛性： \(\lambda_i^*(Gx^* - h)_i = 0, \quad \forall i\)

4. 梯度条件： \(Px^* + q + A^T\nu^* + G^T\lambda^* = 0\)

其中：

• $\lambda^*$ 是对偶变量
• $\nu^*$ 是等式约束的拉格朗日乘子

6.2.2 最优性判别

对于凸QP问题：

1. 如果存在满足KKT条件的点，则该点是全局最优解
2. 如果目标函数是严格凸的（P正定），则最优解唯一

6.3 对偶问题

拉格朗日函数 \(\mathcal{L}(x,\lambda,\nu) = \frac{1}{2}x^T P x + q^T x + \lambda^T(Gx - h) + \nu^T(Ax - b)\)

对偶函数 \(g(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu)\)

对偶问题 \(\max_{\lambda \geq 0, \nu} g(\lambda,\nu)\)

强对偶性 对于凸QP问题，在满足Slater条件的情况下，强对偶性成立：

• 原问题和对偶问题的最优值相等
• 对偶间隙为零

6.4 内点法

内点法通过引入障碍函数将约束问题转化为无约束问题：

• 将约束问题转化为无约束问题
• 使用障碍函数处理不等式约束
• 通过中心路径追踪求解
• 优点：全局收敛性好
• 缺点：计算量较大

数学形式：

1. 障碍函数： \(\phi(x) = -\sum_{i=1}^m \log(h_i - g_i^T x)\)

2. 中心路径问题： \(\min_x \frac{1}{2}x^T P x + q^T x - \mu \sum_{i=1}^m \log(h_i - g_i^T x)\)

   • 其中 $\mu > 0$ 是中心参数
   • 迭代更新：$x_{k+1} = x_k + \alpha_k \Delta x_k$
   • 搜索方向：$(P + \mu \nabla^2 \phi(x_k)) \Delta x_k = -(Px_k + q + \mu \nabla \phi(x_k))$

6.5 ADMM算法

OSQP库（详见另一篇2022-01-21-OSQP ）使用ADMM算法求解QP问题，主要步骤包括：

1. 将原问题转化为标准形式
2. 引入辅助变量和拉格朗日乘子
3. 交替优化原始变量和辅助变量
4. 更新拉格朗日乘子

数学形式：

• 增广拉格朗日函数：$\mathcal{L}_\rho(x,z,\lambda) = f(x) + g(z) + \lambda^T(Ax + Bz - c) + \frac{\rho}{2}|Ax + Bz - c|^2$
• 原始变量更新：$x^{k+1} = \arg\min_x \mathcal{L}_\rho(x,z^k,\lambda^k)$
• 对偶变量更新：$z^{k+1} = \arg\min_z \mathcal{L}_\rho(x^{k+1},z,\lambda^k)$
• 拉格朗日乘子更新：$\lambda^{k+1} = \lambda^k + \rho(Ax^{k+1} + Bz^{k+1} - c)$
• 其中 $\rho > 0$ 是惩罚参数

6.5.1 基本思想

ADMM是一种将问题分解为多个子问题并交替求解的方法。它结合了：

• 对偶分解的优点（分解问题）
• 增广拉格朗日方法的优点（收敛性）
• 将问题分解为多个子问题
• 交替优化原始变量和对偶变量
• 使用增广拉格朗日函数
• 优点：易于并行化
• 缺点：收敛速度可能较慢

6.5.2 标准形式

ADMM用于求解如下形式的优化问题： \(\min_{x,z} f(x) + g(z)\) 约束条件：$Ax + Bz = c$

其中：

• $x \in \mathbb{R}^n$ 和 $z \in \mathbb{R}^m$ 是优化变量
• $f(x)$ 和 $g(z)$ 是目标函数
• $A \in \mathbb{R}^{p \times n}$ 和 $B \in \mathbb{R}^{p \times m}$ 是约束矩阵
• $c \in \mathbb{R}^p$ 是约束向量

6.5.3 算法步骤

a) 增广拉格朗日函数： \(\mathcal{L}_\rho(x,z,\lambda) = f(x) + g(z) + \lambda^T(Ax + Bz - c) + \frac{\rho}{2}\|Ax + Bz - c\|^2\)

其中：

• $\lambda$ 是拉格朗日乘子
• $\rho > 0$ 是惩罚参数

b) 迭代更新：

1. 更新原始变量 $x$： \(x^{k+1} = \arg\min_x \mathcal{L}_\rho(x,z^k,\lambda^k)\)

2. 更新原始变量 $z$： \(z^{k+1} = \arg\min_z \mathcal{L}_\rho(x^{k+1},z,\lambda^k)\)

3. 更新对偶变量 $\lambda$： \(\lambda^{k+1} = \lambda^k + \rho(Ax^{k+1} + Bz^{k+1} - c)\)

6.5.4 收敛条件

算法在满足以下条件时停止： \(\|r^k\| \leq \epsilon_{abs} + \epsilon_{rel} \max\{\|Ax^k\|, \|z^k\|, \|c\|\}\)

其中：

• $r^k$ 是残差
• $\epsilon_{abs}$ 是绝对容差
• $\epsilon_{rel}$ 是相对容差

6.5.5 在QP问题中的应用

对于QP问题：

\[\begin{aligned} \min_{x} \quad &\frac{1}{2}x^T P x + q^T x \\ \text{s.t.} \quad &l \leq Ax \leq u \\ \end{aligned}\]

ADMM的求解过程：

a) 问题转换：

• 引入辅助变量 $z$：$z = Ax$
• 原问题转化为： \(\min_{x,z} \frac{1}{2}x^T P x + q^T x + I_C(z)\) 约束条件：$z = Ax$

其中 $I_C(z)$ 是指示函数： \(I_C(z) = \begin{cases} 0, & \text{if } l \leq z \leq u \\ \infty, & \text{otherwise} \end{cases}\)

b) 迭代步骤：

1. 更新 $x$： \(x^{k+1} = (P + \rho A^T A)^{-1}(-q + \rho A^T(z^k - \lambda^k/\rho))\)

2. 更新 $z$： \(z^{k+1} = \Pi_C(Ax^{k+1} + \lambda^k/\rho)\) 其中 $\Pi_C$ 是到集合 $C = {z \mid l \leq z \leq u}$ 的投影

3. 更新 $\lambda$： \(\lambda^{k+1} = \lambda^k + \rho(Ax^{k+1} - z^{k+1})\)

6.5.6 算法优势

• 分解问题，降低求解难度
• 易于并行化
• 收敛性保证
• 对大规模问题效果好

6.5.7 算法缺点

• 收敛速度可能较慢
• 对惩罚参数 $\rho$ 的选择敏感
• 需要多次迭代

6.5.8 实际应用建议

• 选择合适的惩罚参数 $\rho$
• 使用适当的预处理方法
• 根据问题特点调整收敛条件
• 考虑使用加速技术（如Nesterov加速）

6.6 有效集法（Active Set Method）

• 识别活跃约束集
• 在活跃约束的边界上求解
• 动态更新活跃集
• 优点：迭代次数少
• 缺点：对初始点敏感

数学形式：

• 活跃集：$\mathcal{A}(x) = {i \mid g_i(x) = 0}$
• 子问题：$\min_d \frac{1}{2}d^T P d + (Px + q)^T d$
• 约束：$\nabla g_i(x)^T d = 0, \quad i \in \mathcal{A}(x)$
• 拉格朗日乘子：$\lambda_i = -\frac{\partial f}{\partial g_i}, \quad i \in \mathcal{A}(x)$
• 更新规则：如果 $\lambda_i < 0$，从活跃集中移除约束 $i$

6.7 梯度投影法（Gradient Projection Method）

• 计算无约束问题的梯度
• 将梯度投影到可行域
• 使用线搜索确定步长
• 优点：实现简单
• 缺点：收敛速度慢

数学形式：

• 投影算子：$P_\mathcal{X}(x) = \min_{y \in \mathcal{X}} |y - x|$
• 搜索方向：$d_k = P_\mathcal{X}(x_k - \alpha \nabla f(x_k)) - x_k$
• 步长选择：$\alpha_k = \min_{\alpha > 0} f(x_k + \alpha d_k)$
• 迭代更新：$x_{k+1} = x_k + \alpha_k d_k$
• 收敛条件：$|P_\mathcal{X}(x_k - \nabla f(x_k)) - x_k| \leq \epsilon$

6.8 求解方法的选择

• 问题规模：大规模问题选择ADMM
• 约束类型：等式约束多用有效集法
• 实时性要求：高实时性选择梯度投影
• 精度要求：高精度选择内点法

选择标准：

• 问题维度 $n$ 与约束数量 $m$ 的关系
• 约束矩阵 $A$ 的稀疏性
• 目标函数 $f(x)$ 的凸性
• 计算资源限制

6.9 数值稳定性

• 条件数：$\kappa(P) = \frac{\lambda_{max}(P)}{\lambda_{min}(P)}$
• 正则化：$P_{reg} = P + \delta I$
• 预处理：$M^{-1}Ax = M^{-1}b$
• 其中 $M$ 是预处理矩阵，$\delta > 0$ 是正则化参数

6.9.1 条件数

问题的条件数定义为： \(\kappa(P) = \frac{\lambda_{max}(P)}{\lambda_{min}(P)}\)

其中 $\lambda_{max}$ 和 $\lambda_{min}$ 分别是P的最大和最小特征值。

6.9.2 预处理

为提高数值稳定性，常采用以下预处理方法：

1. 尺度变换
2. 正则化
3. 矩阵分解

6.9.3 收敛性分析

1. 线性收敛率
2. 超线性收敛
3. 二次收敛（在特定条件下）

6.10 求解工具

OSQP 详见2022-01-21-OSQP

7. 带约束最小二乘问题 SLSQP

7.1 问题形式

SLSQP用于求解如下形式的优化问题：

\[\min_{x} \|f(x)\|^2\]

约束条件： \(\begin{align} & g_i(x) = 0, \quad i = 1,...,m_e \\ & g_i(x) \geq 0, \quad i = m_e+1,...,m \\ & x_l \leq x \leq x_u \end{align}\)

其中：

• 目标函数是最小二乘形式
• $g_i(x)$ 是约束函数
• $x_l$ 和 $x_u$ 是变量的上下界

7.2 SLSQP的QP子问题

在每次迭代点 $x_k$ 处，构造如下二次规划子问题：

\[\min_{d} \frac{1}{2} d^T H_k d + \nabla f(x_k)^T d\]

约束条件： \(\nabla g_i(x_k)^T d + g_i(x_k) = 0, \quad i = 1,...,m_e\) \(\nabla g_i(x_k)^T d + g_i(x_k) \geq 0, \quad i = m_e+1,...,m\)

其中：

• $d$ 是搜索方向
• $H_k$ 是拉格朗日函数的Hessian矩阵的近似
• $\nabla f(x_k)$ 是目标函数的梯度
• $\nabla g_i(x_k)$ 是约束函数的梯度

7.3 QP子问题的构造原理

SLSQP构造QP子问题的过程基于以下原理：

1. 泰勒展开近似
   • 对于目标函数 $f(x)$，在迭代点 $x_k$ 处进行二阶泰勒展开： \(f(x_k + d) \approx f(x_k) + \nabla f(x_k)^T d + \frac{1}{2}d^T \nabla^2 f(x_k) d\)
   • 其中 $d$ 是搜索方向
2. 约束线性化
   • 对于约束函数 $g_i(x)$，在 $x_k$ 处进行一阶泰勒展开： \(g_i(x_k + d) \approx g_i(x_k) + \nabla g_i(x_k)^T d\)
   • 对于等式约束，要求 $g_i(x_k + d) = 0$，因此： \(\nabla g_i(x_k)^T d + g_i(x_k) = 0\)
   • 对于不等式约束，要求 $g_i(x_k + d) \geq 0$，因此： \(\nabla g_i(x_k)^T d + g_i(x_k) \geq 0\)
3. QP子问题构造
   • 将上述近似代入原问题，得到QP子问题： \(\min_{d} \frac{1}{2} d^T H_k d + \nabla f(x_k)^T d\)
   • 约束条件： \(\nabla g_i(x_k)^T d + g_i(x_k) = 0, \quad i = 1,...,m_e\) \(\nabla g_i(x_k)^T d + g_i(x_k) \geq 0, \quad i = m_e+1,...,m\)
4. Hessian矩阵近似
   • 使用BFGS方法更新Hessian矩阵的近似 $H_k$
   • 更新公式： \(H_{k+1} = H_k - \frac{H_k s_k s_k^T H_k}{s_k^T H_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}\)
   • 其中： \(s_k = x_{k+1} - x_k\) \(y_k = \nabla_x \mathcal{L}(x_{k+1},\lambda_{k+1}) - \nabla_x \mathcal{L}(x_k,\lambda_k)\)
5. 迭代过程
   • 求解QP子问题得到搜索方向 $d_k$
   • 使用线搜索确定步长 $\alpha_k$
   • 更新迭代点：$x_{k+1} = x_k + \alpha_k d_k$

这种构造方法的优势在于：

1. 将复杂的非线性优化问题转化为一系列QP子问题
2. 每个QP子问题都是凸的，可以高效求解
3. 通过迭代求解，逐步逼近原问题的最优解
4. 保持了原问题的约束结构，同时简化了求解难度

7.4 算法实现细节

7.4.1 拉格朗日函数

拉格朗日函数定义为：

\[\mathcal{L}(x,\lambda) = f(x) - \sum_{i=1}^m \lambda_i g_i(x)\]

其中 $\lambda_i$ 是拉格朗日乘子。

7.4.2 迭代更新

1. 求解二次规划子问题得到搜索方向 $d_k$
2. 使用线搜索确定步长 $\alpha_k$
3. 更新迭代点： \(x_{k+1} = x_k + \alpha_k d_k\)

7.4.3 收敛条件

算法在满足以下条件时停止：

\(\|\nabla_x \mathcal{L}(x_k,\lambda_k)\| \leq \epsilon_1\) \(\|g_i(x_k)\| \leq \epsilon_2, \quad i = 1,...,m_e\) \(g_i(x_k) \geq -\epsilon_2, \quad i = m_e+1,...,m\)

其中 $\epsilon_1$ 和 $\epsilon_2$ 是预设的收敛容差。

7.4.4 Hessian矩阵更新

使用BFGS方法更新Hessian矩阵的近似：

\[H_{k+1} = H_k - \frac{H_k s_k s_k^T H_k}{s_k^T H_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}\]

其中： \(s_k = x_{k+1} - x_k\) \(y_k = \nabla_x \mathcal{L}(x_{k+1},\lambda_{k+1}) - \nabla_x \mathcal{L}(x_k,\lambda_k)\)

7.4.5 线搜索条件

步长 $\alpha_k$ 需要满足Armijo条件：

\[f(x_k + \alpha_k d_k) \leq f(x_k) + c_1 \alpha_k \nabla f(x_k)^T d_k\]

其中 $c_1 \in (0,1)$ 是预设参数。

7.4.6 算法复杂度

• 每次迭代的主要计算成本：
  • 计算梯度：$O(n)$
  • 求解二次规划子问题：$O(n^3)$
  • 更新Hessian矩阵：$O(n^2)$

其中 $n$ 是决策变量的维度。

7.4.7 收敛性分析

在适当的条件下，算法具有以下性质：

• 局部收敛性：$|x_k - x^| = O(|x_{k-1} - x^|^2)$
• 全局收敛性：$\lim_{k \to \infty} |\nabla f(x_k)| = 0$

其中 $x^*$ 是局部最优解。

7.5 示例

考虑一个带有非线性约束的优化问题，这是一个简化的机器人路径规划问题：

\[\min_{x} f(x) = \sum_{i=1}^3 (x_i^2 + 2x_i x_{i+1} + x_{i+1}^2) + \sum_{i=1}^4 x_i^4\]

约束条件： \(g_1(x) = \sum_{i=1}^4 x_i - 2 = 0\) \(g_2(x) = \prod_{i=1}^4 x_i - 0.5 \geq 0\) \(g_3(x) = \sum_{i=1}^3 (x_i - x_{i+1})^2 - 1 \leq 0\) \(x_i \geq 0, \quad i = 1,...,4\)

1. 初始点选择
   • 选择初始点 $x_0 = [0.5, 0.5, 0.5, 0.5]^T$
   • 计算目标函数和约束函数的值： \(f(x_0) = 4.0\) \(g_1(x_0) = 0\) \(g_2(x_0) = -0.4375\) \(g_3(x_0) = 0\)
2. 构造QP子问题

   • 计算梯度： \(\nabla f(x_0) = [2x_1 + 2x_2 + 4x_1^3, 2x_1 + 2x_2 + 2x_3 + 4x_2^3, 2x_2 + 2x_3 + 2x_4 + 4x_3^3, 2x_3 + 4x_4^3]^T = [3.5, 4.5, 4.5, 3.5]^T\) \(\nabla g_1(x_0) = [1, 1, 1, 1]^T\) \(\nabla g_2(x_0) = [0.125, 0.125, 0.125, 0.125]^T\) \(\nabla g_3(x_0) = [1, -2, 1, 0]^T\)

   • 初始Hessian矩阵（单位矩阵）： \(H_0 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

   • 构造QP子问题： \(\min_{d} \frac{1}{2} d^T H_0 d + [3.5, 4.5, 4.5, 3.5]^T d\)

     约束条件： \([1, 1, 1, 1]^T d = 0\) \([0.125, 0.125, 0.125, 0.125]^T d \geq 0.4375\) \([1, -2, 1, 0]^T d \leq 0\) \(d_i \geq -0.5, \quad i = 1,...,4\)

3. 求解QP子问题
   • 求解得到搜索方向 $d_0 = [-0.2, 0.1, 0.1, 0.0]^T$
   • 使用线搜索确定步长 $\alpha_0 = 0.5$
   • 更新迭代点： \(x_1 = x_0 + \alpha_0 d_0 = [0.4, 0.55, 0.55, 0.5]^T\)
4. 更新Hessian矩阵

   • 计算： \(s_0 = x_1 - x_0 = [-0.1, 0.05, 0.05, 0.0]^T\) \(y_0 = \nabla f(x_1) - \nabla f(x_0) = [3.2, 4.3, 4.3, 3.5]^T - [3.5, 4.5, 4.5, 3.5]^T\) \(= [-0.3, -0.2, -0.2, 0.0]^T\)

   • 使用BFGS公式更新Hessian矩阵： \(H_1 = H_0 - \frac{H_0 s_0 s_0^T H_0}{s_0^T H_0 s_0} + \frac{y_0 y_0^T}{y_0^T s_0}\)

5. 迭代过程
   • 重复上述步骤，直到满足收敛条件
   • 最终收敛到最优解 $x^* \approx [0.4, 0.6, 0.6, 0.4]^T$
   • 此时： \(f(x^*) \approx 3.2\) \(g_1(x^*) = 0\) \(g_2(x^*) \approx 0.0576\) \(g_3(x^*) \approx -0.04\)

这个例子展示了SLSQP如何：

1. 处理高维非线性优化问题
2. 同时满足多个非线性约束
3. 在迭代过程中保持约束的可行性
4. 通过QP子问题逐步改进解的质量

7.6 与其他优化方法的比较

7.6.1 SLSQP与SQP的比较

SLSQP (Sequential Least Squares Quadratic Programming) 是SQP的一个变种，主要用于处理带约束的最小二乘问题。

主要区别

1. 问题类型：
   • SQP：适用于一般的非线性规划问题
   • SLSQP：专门针对最小二乘问题优化，目标函数形如 $\min_x \frac{1}{2}|F(x)|^2$
2. 子问题构造：
   • SQP：使用完整的二阶泰勒展开
   • SLSQP：使用最小二乘形式，可以更好地处理目标函数的特殊结构
3. 收敛性质：
   • SQP：通常具有二阶收敛性
   • SLSQP：在最小二乘问题上可能具有更好的收敛性
4. 实现复杂度：
   • SQP：需要计算完整的Hessian矩阵
   • SLSQP：可以利用最小二乘问题的特殊结构，计算更简单
5. 应用场景：
   • SQP：适用于一般的非线性优化问题
   • SLSQP：特别适合：
     • 参数估计问题
     • 曲线拟合问题
     • 数据拟合问题
     • 其他最小二乘问题

选择建议

1. 使用SQP的情况：
   • 一般的非线性优化问题
   • 需要处理复杂的约束条件
   • 问题规模较大
   • 需要二阶收敛性
2. 使用SLSQP的情况：
   • 最小二乘类型的问题
   • 目标函数可以表示为残差平方和
   • 需要快速收敛
   • 问题具有特殊的结构
3. 实际应用考虑：
   • 如果问题可以转化为最小二乘形式，优先考虑SLSQP
   • 如果是一般非线性问题，使用标准SQP
   • 如果问题规模很大，可以考虑使用SQP的简化版本

7.6.2 SLSQP与牛顿法的比较

SLSQP和牛顿法都是求解优化问题的迭代方法，但它们有以下主要区别：

1. 问题类型
   • 牛顿法：主要用于无约束优化问题
   • SLSQP：可以处理带约束的优化问题，包括等式约束和不等式约束
2. 搜索方向计算
   • 牛顿法：
     • 直接使用目标函数的Hessian矩阵
     • 搜索方向：$d_k = -H_k^{-1}\nabla f(x_k)$
     • 需要计算和存储完整的Hessian矩阵
   • SLSQP：
     • 构造QP子问题求解搜索方向
     • 使用BFGS等方法近似Hessian矩阵
     • 可以处理约束条件
3. 收敛性质
   • 牛顿法：
     • 在最优解附近具有二次收敛性
     • 对初始点要求较高
     • 可能不收敛或收敛到局部最优
   • SLSQP：
     • 具有全局收敛性
     • 通过线搜索保证目标函数下降
     • 可以处理非凸问题
4. 计算复杂度
   • 牛顿法：
     • 每次迭代需要计算完整的Hessian矩阵
     • 需要求解线性方程组
     • 计算成本较高
   • SLSQP：
     • 使用拟牛顿法近似Hessian矩阵
     • 需要求解QP子问题
     • 计算成本相对较低
5. 应用场景
   • 牛顿法：
     • 适用于无约束优化问题
     • 目标函数二阶可导
     • 计算资源充足
   • SLSQP：
     • 适用于带约束的优化问题
     • 可以处理非光滑问题
     • 计算资源有限
6. 数值稳定性
   • 牛顿法：
     • 对Hessian矩阵的条件数敏感
     • 需要额外的正则化
     • 可能数值不稳定
   • SLSQP：
     • 通过QP子问题保证数值稳定性
     • 可以处理病态问题
     • 具有更好的鲁棒性
7. 实现难度
   • 牛顿法：
     • 实现相对简单
     • 主要关注目标函数的计算
     • 调试相对容易
   • SLSQP：
     • 实现较为复杂
     • 需要处理约束条件
     • 调试难度较大

总的来说，SLSQP是牛顿法的一个扩展，它通过构造QP子问题来处理约束条件，同时使用拟牛顿法来避免计算完整的Hessian矩阵。这使得SLSQP能够处理更广泛的问题，但计算成本也相应增加。

7.6.3 SLSQP与拟牛顿法的比较

SLSQP和拟牛顿法虽然都使用近似Hessian矩阵，但它们有以下主要区别：

1. 问题类型
   • 拟牛顿法：
     • 主要用于无约束优化问题
     • 目标函数需要连续可导
     • 不直接处理约束条件
   • SLSQP：
     • 可以处理带约束的优化问题
     • 通过QP子问题处理约束
     • 可以处理非光滑问题
2. Hessian矩阵近似
   • 拟牛顿法：
     • 直接近似目标函数的Hessian矩阵
     • 使用BFGS、DFP等公式更新
     • 更新公式只依赖于梯度信息
   • SLSQP：
     • 近似拉格朗日函数的Hessian矩阵
     • 需要考虑约束的影响
     • 更新公式包含约束信息
3. 搜索方向计算
   • 拟牛顿法：
     • 直接计算搜索方向：$d_k = -H_k^{-1}\nabla f(x_k)$
     • 不需要求解子问题
     • 计算成本较低
   • SLSQP：
     • 通过求解QP子问题得到搜索方向
     • 需要考虑约束的可行性
     • 计算成本较高
4. 收敛性质
   • 拟牛顿法：
     • 超线性收敛
     • 对初始点要求较高
     • 可能不收敛到全局最优
   • SLSQP：
     • 全局收敛性
     • 通过线搜索保证下降
     • 可以处理非凸问题
5. 实现复杂度
   • 拟牛顿法：
     • 实现相对简单
     • 主要关注Hessian矩阵的更新
     • 调试相对容易
   • SLSQP：
     • 实现较为复杂
     • 需要处理约束条件
     • 需要求解QP子问题
     • 调试难度较大
6. 内存需求
   • 拟牛顿法：
     • 需要存储Hessian矩阵的近似
     • 内存需求与问题维度平方成正比
     • 可以使用有限内存版本（L-BFGS）
   • SLSQP：
     • 需要存储Hessian矩阵的近似
     • 需要存储约束相关的信息
     • 内存需求更大
7. 应用场景
   • 拟牛顿法：
     • 适用于大规模无约束问题
     • 目标函数计算成本高
     • 内存受限时可用L-BFGS
   • SLSQP：
     • 适用于带约束的中小规模问题
     • 约束条件复杂
     • 需要保证解的可行性
8. 数值稳定性
   • 拟牛顿法：
     • 对Hessian矩阵的条件数敏感
     • 需要额外的正则化
     • 可能数值不稳定
   • SLSQP：
     • 通过QP子问题保证数值稳定性
     • 可以处理病态问题
     • 具有更好的鲁棒性

总的来说，SLSQP是拟牛顿法的一个扩展，它通过构造QP子问题来处理约束条件，同时保留了拟牛顿法在Hessian矩阵近似方面的优势。这使得SLSQP能够处理更广泛的问题，但计算成本和实现复杂度也相应增加。在实际应用中，如果问题是无约束的，使用拟牛顿法可能更简单高效；如果问题带有约束，SLSQP则是一个更好的选择。

---

• Previous
  凸优化
• Next
  最小二乘优化

---