等式约束优化问题

$\min f(x)$

$s.t.\quad Ax=b$

其中$f$为二次可微凸函数，假设等式约束少于变量数，并且等式约束互相独立。假定存在一个最优解$x^\star$，并用$p^\star$表示其最优值，即：

$p^\star = \inf \{f(x) | Ax = b\} = f(x^\star)$

由KKT条件，其最优解的重要条件是满足：

$Ax^\star = b \quad \triangledown f(x^\star) + A^Tv^\star = 0$

对于求解等式约束问题有两种方法：

1. 任何等式约束优化问题都可以通过消除等式约束转化为等价的无约束问题。
2. 使用对偶方法解决。

很多时候，直接处理等式约束比转化为无约束问题要好，这是因为转化之后可能会破坏问题的结构。

等式约束凸二次规划

$\min f(x) = (1/2)x^TPx+q^Tx+r$

$s.t. \quad Ax= b$

此问题的最优性条件为：

$Ax^\star =b \quad Px^\star+q+A^Tv^\star = 0$

可以将其写成矩阵形式：

因此，对偶问题为：

$\max -b^Tv - f^\star(-A^Tv)$

若Slater条件成立，则强对偶性成立，即$g(v^\star) = p^\star$

等式约束的Newton方法

讨论扩展的Newton方法，与之前无约束类似，但初始点必须可行（即满足$Ax=b$），并且需要保证Newton方向是可行的方向，即$A\Delta x_{nt} = 0$

Newton方向

基于二阶近似的定义

将目标函数换成在其$x$附近的二阶Taylor近似：

$\min \hat f(x+v) = f(x) +\triangledown f(x)^Tv + (1/2)v^T\triangledown ^2f(x) v$

$s.t.\quad A(x+v) =b$

根据之前对等式约束二次问题的分析，得到KKT矩阵：

线性化最优性条件的解

可以将Newton方向$\Delta x_{nt}$解释为最优性条件：

$Ax^\star =b \quad \triangledown f(x^\star)+A^Tv^\star = 0$

我们用$x+\Delta x_{nt}$替代$x^\star$，用$w$替代$v^\star$，将梯度换为二阶近似，得到：

Newton减量

等式约束的Newton方法

1. 给定初始点$x \in dom f$，误差阈值$\epsilon >0$
2. 计算Newton步径和减量
3. 停止准则：如果$\lambda^2/2\le \epsilon$，退出
4. 直线搜索，根据回溯直线搜索确定步长$t$
5. 改进：$x:=x + t\Delta x_{nt}$

不可行初始点的Newton方法

不可行点的Newton方向

和Newton方法一样，我们从等式约束优化的最优性条件开始：

$Ax^\star =b \quad \triangledown f(x^\star)+A^Tv^\star = 0$

用$x$表示当前点，不假设它是可行的，因此我们的目的是找到一个方向$\Delta x$使得$x+\Delta x$满足最优性条件，即$x + \Delta x\approx x^\star$。因此我们用$x + \Delta x$代替$x^\star$，并利用梯度的一阶近似：

$A(x+\Delta x) = b\quad x \triangledown f(x) +\triangledown ^2f(x)\Delta x+A^Tw = 0$

写成矩阵形式为：