六、 约束优化

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

   集合 内的点 称作可行解。集合 也称作可行域。

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

   如果使用线性搜索：则每次只搜索那些使得新的 位于集合 中的那些 。

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

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

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

   

   可行域由等式和不等式确定： 。

6.1 原始问题

1. 引入拉格朗日函数：

   

   这里 是拉格朗日乘子， 。

   是 的多元非线性函数。

2. 定义函数：

   

   其中下标 表示原始问题。则有：

   

   • 若 满足原问题的约束，则很容易证明 ，等号在 时取到。

   • 若 不满足原问题的约束：

     • 若不满足 ：设违反的为 ，则令 ，有： 。
     • 若不满足 ： 设违反的为 ，则令 ，有： 。

3. 考虑极小化问题：

   

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

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

6.2 对偶问题

1. 定义 ，考虑极大化 ，即：

   

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

   

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

   为了方便讨论，定义对偶问题的最优值为： 。

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

   

   • 推论一：设 为原始问题的可行解，且 的值为 ； 为对偶问题的可行解， 值为 。

     如果有 ，则 分别为原始问题和对偶问题的最优解。

3. 定理二：假设函数 和 为凸函数， 是仿射函数；并且假设不等式约束 是严格可行的，即存在 ，对于所有 有 。则存在 ，使得： 是原始问题 的解， 是对偶问题 的解，并且 。

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

   

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

   一般形式为 。这里： 是一个 矩阵， 是一个 维列向量， 是一个 维列向量。

   它实际上反映了一种从 维到 维的空间线性映射关系。

6. 凸函数：设 为定义在区间 上的函数，若对 上的任意两点 和任意的实数 ，总有 ，则 称为 上的凸函数 。