之前谈的都是无约束优化问题,这次转入约束优化方法。首先介绍一下什么是约束优化
其中, 是目标函数, 是等式约束的index, 是不等式约束的index。
可行集:所有满足约束的点组成的集合
有效集:激活集为可行集中满足等式约束的点
约束优化问题的求解比无约束优化要困难得多,这篇博客主要介绍一些特殊形式的约束优化以及非线性约束优化问题的常见解法。
参数变换化简约束
一些简单约束可以通过参数变换转化成无约束问题。
- 求 在 的最小值,可令 ,求得无约束问题的最小值 ,则 为 在 的最小值。
- 如果 约束在有限开区间 ,可以做变换
- 如果 约束在有限闭区间 ,可以做变换
最优性条件
等式约束优化
若仅考虑等式约束,则优化命题为
Kuhn-Tucker一阶必要条性条件为:
- 假设 是上述等式约束优化问题的局部极小点, 与 在 的某邻域内连续可微。若 线性无关,则存在一组实数 使得
我们称 为 Lagrange 乘子向量,
为等式约束问题的 Lagrange 函数,其中 ,计算 的梯度得
满足一阶必要条件和等式约束条件当且仅当 是 Lagrange 函数的驻点。
不等式约束优化
考虑不等式约束优化问题
对于可行域中某个点 ,有些约束为 ,而另一些约束 使得 ,则称不等式约束 为 的有效约束;若 为 的非有效约束。称所有在 处的有效约束的下标组成的集合为有效集
Kuhn-Tucker一阶必要条性条件为:
- 假设 为局部极小点,有效集 ,同时 及 在点 处可微。若 形成的向量组线性无关,则存在向量 使得
一般约束优化
一般约束问题既包含等式约束也包含不等式约束
把之前等式约束和不等式约束的结论结合起来,我们可以得到一般约束优化的Kuhn-Tucker一阶必要条性条件:
- 假设 为局部极小点, 为 与 的有效集的并,即
且 在 点可微。若 线性无关,则存在向量 使得
满足这一条件的 称为 KT 点,称 为 KT 对,其中 称为 Lagrange 乘子向量。
条件 称为互补松弛条件,表明它们不能同时为 0。极小点处的 Lagrange乘子 的分量是有区别的, 对应的 可以是任何实数, 对应的 ,即要满足非负性。
对于非线性规划,如果目标函数 为凸函数,等式约束 为线性函数,不等式约束 为凹函数,那么该约束优化为凸规划问题。凸规划问题的 KT 对为全局极小点。
评论(0)
您还未登录,请登录后发表或查看评论