約束最佳化問題的一階條件和二階條件

作者：由論文推土機發表于舞蹈時間：2022-03-16

因為我們在

論文推土機：引數最優控制與路徑規劃論文解析：Optimal Rough Terrain Trajectory Generation for Wheeled Mobile Robots

中講到了拉格朗日乘子法，使用了

$\begin{aligned} \frac{\partial}{\partial \boldsymbol{q}} H(\mathbf{q}, \boldsymbol{\lambda}) &=\frac{\partial}{\partial \boldsymbol{q}} J(\mathbf{q})+\lambda^{\mathrm{T}} \frac{\partial}{\partial \boldsymbol{q}} \mathbf{g}(\mathbf{q})=\mathbf{0}^{\mathrm{T}} \\ \frac{\partial}{\partial \lambda} H(\mathbf{q}) &=\mathbf{g}(\mathbf{q})=\mathbf{0} . \end{aligned}$

去求解最優解。

這其實是利用了最佳化問題的一階必要條件來解的，所謂必要條件，就是滿足這個等式的解不一定是最優解，但是最優解肯定滿足這個等式。而當問題是凸最佳化問題時則這個必要條件也是充分條件。在本文裡我使用Practical Optimization Algorithm and Engineering Applications 2nd Edition中的10。6和10。7節做一個整理。整理什麼事約束最佳化問題的一階必要條件，二階必要條件和充分條件。

接下來的所有條件，我們都考慮以下最佳化問題：

$\begin{align} minimize \quad f(\mathbf{x}) \\ subject\quad to: \quad a_{i}(\mathbf{x})=0 \quad for \quad i=1,2, \ldots, p \end{align}$

一階必要條件(等式約束)

$a_{i}\left(\mathbf{x}^{*}\right)=0 \text { for } i=1,2, \ldots, p$

存在拉格朗日乘子

$\lambda_i^*$

使得

$\nabla f\left(\mathbf{x}^{*}\right)+\sum_{i=1}^{p} \lambda_{i}^{*} \nabla a_{i}\left(\mathbf{x}^{*}\right)=\mathbf{0}$

一階必要條件（等式和不等式約束->推廣到更一般的情況）

接下來考慮更一般的情況，存在等式約束和不等式約束，在這裡定義那些有效不等式約束為active set。如有有K個active inequality constraints在

，並且他們組成一個集合：

$\mathcal{J}\left(\mathbf{x}^{*}\right)=\left\{j_{1}, j_{2}, \ldots, j_{K}\right\}$

則一階必要條件寫為：

$\begin{array}{c} \nabla f\left(\mathbf{x}^{*}\right)+\sum_{i=1}^{p} \lambda_{i}^{*} \nabla a_{i}\left(\mathbf{x}^{*}\right)+\sum_{k=1}^{K} \mu_{j k}^{*} \nabla c_{j_{k}}\left(\mathbf{x}^{*}\right)=\mathbf{0} a_{i}\left(\mathbf{x}^{*}\right)=0 \quad \text { for } \quad 1 \leq i \leq p \\ c_{j}\left(\mathbf{x}^{*}\right) \leq 0 \quad \text { for } \quad 1 \leq j \leq q\\ \lambda_{i}^{*} a_{i}\left(\mathbf{x}^{*}\right)=0 \quad \text { for } 1 \leq i \leq p \\ \mu_{j}^{*} c_{j}\left(\mathbf{x}^{*}\right)=0 \quad \text { for } 1 \leq j \leq q\\ \mu_{j}^{*} \geq 0 \text { for } 1 \leq j \leq q \end{array}$

由於這個定理由Karush Kuhn Tacker分別獨立提出，也被成為KT條件，或KKT條件。很多證明方法，各種知乎解釋。雖然KKT條件只是必要條件，但是如果問題是凸最佳化問題，則也是充要條件。我們開頭說的論文解的最佳化問題的確是凸最佳化問題，所以使用一階必要條件是存在充分性的，方程的解是最優解。

二階必要條件

$a_{i}\left(\mathbf{x}^{*}\right)=0 \quad \text { for } i=1,2, \ldots, p$

，

存在

$\lambda_i^*\ for \ i=1,2, \ldots, p$

使得：

$\nabla f\left(\mathbf{x}^{*}\right)+\sum_{i=1}^{p} \lambda_{i}^{*} \nabla a_{i}\left(\mathbf{x}^{*}\right)=\mathbf{0}$

並且

$\mathbf{N}^{T}\left(\mathbf{x}^{*}\right) \nabla_{x}^{2} L\left(\mathbf{x}^{*}, \lambda^{*}\right) \mathbf{N}\left(\mathbf{x}^{*}\right) \succeq \mathbf{0}$

，其中這個N是有效約束集的梯度的零空間（null space）。

二階充分條件

$a_{i}\left(\mathbf{x}^{*}\right)=0 \quad \text { for } i=1,2, \ldots, p$

，

存在

$\lambda_i^*\ for \ i=1,2, \ldots, p$

使得：

$\nabla f\left(\mathbf{x}^{*}\right)+\sum_{i=1}^{p} \lambda_{i}^{*} \nabla a_{i}\left(\mathbf{x}^{*}\right)=\mathbf{0}$

並且

$\mathbf{N}^{T}\left(\mathbf{x}^{*}\right) \nabla_{x}^{2} L\left(\mathbf{x}^{*}, \lambda^{*}\right) \mathbf{N}\left(\mathbf{x}^{*}\right) \succ \mathbf{0}$