Question

1. 在有的最优化问题中，希望输入 $ MathJax-Element-449 $ 位于特定的集合 $ MathJax-Element-385 $ 中，这称作约束优化问题。

   集合 $ MathJax-Element-385 $ 内的点 $ MathJax-Element-449 $ 称作可行解。集合 $ MathJax-Element-385 $ 也称作可行域。

2. 约束优化的一个简单方法是：对梯度下降法进行修改，每次迭代后，将得到的新的 $ MathJax-Element-449 $ 映射到集合 $ MathJax-Element-385 $ 中。

   如果使用线性搜索：则每次只搜索那些使得新的 $ MathJax-Element-449 $ 位于集合 $ MathJax-Element-385 $ 中的那些 $ MathJax-Element-383 $ 。

   • 另一个做法：将线性搜索得到的新的 $ MathJax-Element-449 $ 映射到集合 $ MathJax-Element-385 $ 中。
   • 或者：在线性搜索之前，将梯度投影到可行域的切空间内。

3. 在约束最优化问题中，常常利用拉格朗日对偶性将原始问题转换为对偶问题，通过求解对偶问题而得到原始问题的解。

4. 约束最优化问题的原始问题：假设 $ MathJax-Element-386 $ 是定义在 $ MathJax-Element-387 $ 上的连续可微函数。考虑约束最优化问题：

   $ \min_{\mathbf {\vec x} \in \mathbb R^{n}}f(\mathbf {\vec x})\\ s.t. \quad c_i(\mathbf {\vec x}) \le 0,i=1,2,\cdots,k \;;\quad h_j(\mathbf {\vec x})=0,j=1,2,\cdots,l $

   可行域由等式和不等式确定： $ MathJax-Element-388 $ 。

6.1 原始问题

1. 引入拉格朗日函数：

   $ L(\mathbf {\vec x},\vec \alpha,\vec\beta)=f(\mathbf {\vec x})+\sum_{i=1}^{k}\alpha_ic_i(\mathbf {\vec x})+\sum_{j=1}^{l}\beta_jh_j(\mathbf {\vec x}) $

   这里 $ MathJax-Element-389 $ 是拉格朗日乘子， $ MathJax-Element-390 $ 。

   $ MathJax-Element-391 $ 是 $ MathJax-Element-392 $ 的多元非线性函数。

2. 定义函数：

   $ \theta_P(\mathbf {\vec x})=\max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0}L(\mathbf {\vec x},\vec \alpha, \vec\beta) $

   其中下标 $ MathJax-Element-393 $ 表示原始问题。则有：

   $ \theta_P(\mathbf {\vec x})= \begin{cases} f(\mathbf {\vec x}), & \text{if $\mathbf {\vec x}$ statisfy original problem's constraint} \\ +\infty, & \text{or else.} \end{cases} $

   • 若 $ MathJax-Element-449 $ 满足原问题的约束，则很容易证明 $ MathJax-Element-395 $ ，等号在 $ MathJax-Element-396 $ 时取到。

   • 若 $ MathJax-Element-449 $ 不满足原问题的约束：

     • 若不满足 $ MathJax-Element-398 $ ：设违反的为 $ MathJax-Element-399 $ ，则令 $ MathJax-Element-400 $ ，有： $ MathJax-Element-401 $ 。
     • 若不满足 $ MathJax-Element-402 $ ： 设违反的为 $ MathJax-Element-403 $ ，则令 $ MathJax-Element-404 $ ，有： $ MathJax-Element-405 $ 。

3. 考虑极小化问题：

   $ \min_{\mathbf {\vec x}} \theta_P(\mathbf {\vec x})=\min_{\mathbf {\vec x}}\max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0}L(\mathbf {\vec x},\vec \alpha, \vec\beta) $

   则该问题是与原始最优化问题是等价的，即他们有相同的问题。

   • $ MathJax-Element-406 $ 称为广义拉格朗日函数的极大极小问题。
   • 为了方便讨论，定义原始问题的最优值为： $ MathJax-Element-407 $ 。

6.2 对偶问题

1. 定义 $ MathJax-Element-408 $ ，考虑极大化 $ MathJax-Element-409 $ ，即：

   $ \max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0}\theta_D(\vec \alpha,\vec\beta)=\max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0} \min_{\mathbf {\vec x}}L(\mathbf {\vec x},\vec \alpha, \vec\beta) $

   问题 $ MathJax-Element-410 $ 称为广义拉格朗日函数的极大极小问题。它可以表示为约束最优化问题：

   $ \max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0}\theta_D(\vec \alpha,\vec\beta)=\max_{\vec \alpha,\vec\beta\;:\;\alpha_i \ge 0} \min_{\mathbf {\vec x}}L(\mathbf {\vec x},\vec \alpha, \vec\beta)\\ s.t. \alpha_i \ge 0, i=1,2,\cdots,k $

   称为原始问题的对偶问题。

   为了方便讨论，定义对偶问题的最优值为： $ MathJax-Element-411 $ 。

2. 定理一：若原问题和对偶问题具有最优值，则：

   $ d^{*}=\max_{\vec \alpha,\vec\beta\;:\;\vec \alpha_i \ge 0}\min_{\mathbf {\vec x}}L(\mathbf {\vec x},\vec \alpha, \vec\beta) \le \min_{\mathbf {\vec x}}\max_{\vec \alpha,\vec\beta\;:\;\vec \alpha_i \ge 0}L(\mathbf {\vec x},\vec \alpha, \vec\beta)=p^{*} $

   • 推论一：设 $ MathJax-Element-441 $ 为原始问题的可行解，且 $ MathJax-Element-413 $ 的值为 $ MathJax-Element-414 $ ； $ MathJax-Element-443 $ 为对偶问题的可行解， $ MathJax-Element-416 $ 值为 $ MathJax-Element-417 $ 。

     如果有 $ MathJax-Element-418 $ ，则 $ MathJax-Element-445 $ 分别为原始问题和对偶问题的最优解。

3. 定理二：假设函数 $ MathJax-Element-433 $ 和 $ MathJax-Element-436 $ 为凸函数， $ MathJax-Element-435 $ 是仿射函数；并且假设不等式约束 $ MathJax-Element-436 $ 是严格可行的，即存在 $ MathJax-Element-449 $ ，对于所有 $ MathJax-Element-438 $ 有 $ MathJax-Element-439 $ 。则存在 $ MathJax-Element-445 $ ，使得： $ MathJax-Element-441 $ 是原始问题 $ MathJax-Element-442 $ 的解， $ MathJax-Element-443 $ 是对偶问题 $ MathJax-Element-444 $ 的解，并且 $ MathJax-Element-432 $ 。

4. 定理三：假设函数 $ MathJax-Element-433 $ 和 $ MathJax-Element-436 $ 为凸函数， $ MathJax-Element-435 $ 是仿射函数；并且假设不等式约束 $ MathJax-Element-436 $ 是严格可行的，即存在 $ MathJax-Element-449 $ ，对于所有 $ MathJax-Element-438 $ 有 $ MathJax-Element-439 $ 。则存在 $ MathJax-Element-445 $ ，使得 $ MathJax-Element-441 $ 是原始问题 $ MathJax-Element-442 $ 的解， $ MathJax-Element-443 $ 是对偶问题 $ MathJax-Element-444 $ 的解的充要条件是： $ MathJax-Element-445 $ 满足下面的 Karush-kuhn-Tucker(KKT) 条件：

   $ \nabla_\mathbf {\vec x}L(\mathbf {\vec x}^{*},\vec \alpha^{*},\vec\beta^{*})=0\\ \nabla_\vec \alpha L(\mathbf {\vec x}^{*},\vec \alpha^{*},\vec\beta^{*})=0\\ \nabla_\vec\beta L(\mathbf {\vec x}^{*},\vec \alpha^{*},\vec\beta^{*})=0\\ \vec \alpha^{*}_ic_i(\mathbf {\vec x}^{*})=0,i=1,2,\cdots,k\\ c_i(\mathbf {\vec x}^{*})\le 0,i=1,2,\cdots,k\\ \vec \alpha^{*}_i \ge 0,i=1,2,\cdots,k\\ h_j(\mathbf {\vec x}^{*})= 0,j=1,2,\cdots,l $

5. 仿射函数：仿射函数即由1阶多项式构成的函数。

   一般形式为 $ MathJax-Element-446 $ 。这里： $ MathJax-Element-447 $ 是一个 $ MathJax-Element-448 $ 矩阵， $ MathJax-Element-449 $ 是一个 $ MathJax-Element-453 $ 维列向量， $ MathJax-Element-451 $ 是一个 $ MathJax-Element-454 $ 维列向量。

   它实际上反映了一种从 $ MathJax-Element-453 $ 维到 $ MathJax-Element-454 $ 维的空间线性映射关系。

6. 凸函数：设 $ MathJax-Element-461 $ 为定义在区间 $ MathJax-Element-462 $ 上的函数，若对 $ MathJax-Element-462 $ 上的任意两点 $ MathJax-Element-458 $ 和任意的实数 $ MathJax-Element-459 $ ，总有 $ MathJax-Element-460 $ ，则 $ MathJax-Element-461 $ 称为 $ MathJax-Element-462 $ 上的凸函数 。