约束最优化方法 (一) 最优性条件

  之前讨论的是无约束最优化方法，这一节主要介绍的是带有约束的非线性规划问题，所谓的非线性规划，就是约束项含有平方这种。解这类问题有两种方法，一个是 容许方向法 、它是一种直接处理约束的方法；另一个是 罚函数法 ，它是将约束问题转变成一系列无约束问题，用无约束的极小点去逐渐逼近约束问题的极小点。但是在介绍这两种方法之前，要先介绍一些概念。

  本节主要讨论一般约束问题的最优性条件。我们将先从仅含等式约束或不等式约束的问题入手，然后自然过渡到一般约束问题。所以这一节主要介绍各种约束下的最优性条件，也就是各种约束下，什么样的条件能够推出这个点是最优点、另外一种，已知各种约束下的最优点，能够推出什么条件。整体目录结构如下：

  考虑仅含等式约束的 问题1 ：

  这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是Lagrange定理和Lagrange乘子法。

定理1 ：假设

  这个定理的意义还在于，它把对等式约束问题的求解转化为对无约束问题的求解。

   上式是最优性一阶必要条件 。

定理2 ：在约束问题1中，假设：

  的任意非零向量 ，都有：

  这个定理的几何意义是，在Lagrange函数的驻点 处，如果Lagrange函数关于 的Hesse矩阵在 个约束(超)曲面的切平面的交集上正定(注意，并不需要在原来的空间中正定)，那么 就是严格局部极小点。

  这里就是直接给出两个定理，没办法，理解记忆吧。第一个定理相对来说比较重要一点。

  下面将给出约束 问题2 ：

  的最优性条件。

定义1 ：对于约束问题，设 ， 若使得某个不等式约束有 ，则该不等式约束 称为是关于容许点 的 起作用约束 ；否者，若 ，则该不等式约束称为是关于容许点的 不起作用约束 。

定义2 ：设 是 中的非空集，且 。对于 ，若当 时，对于 ，必有 ，则集合 称为 以 为顶点的锥 。若锥 是凸集，则称为 凸锥 。

定义3 ：设 是 中的非空集，且 。对于非零向量 ，若存在 ，当 时，必有 ，则 称为点 的 容许方向向量 ，其方向称为点 的 容许方向 。由点 的全部容许方向向量构成的集合称为点 的 容许方向集 ，或者说 容许方向锥 。

  约束曲面 把整个空间分成两部分，梯度 总是指向包含容许集的那一侧。

  把由点 的所有下降方向向量构成的集合称为点 的 下降方向锥 。

定理：设 在点 可微，则点 处的下降方向向量 必满足：

  记 ，则 是点 处的下降方向集。显然 是 中的半空间。

  接下来就是 几何最优性条件 的定义：(因为这个条件是仅借助点集的概念给出的，所以称为 几何最优性条件 )：

定理： 在约束问题2中，若 是局部最优点，则点 处的 容许方向锥 和 下降方向锥 的交集是空集。

  上面这个定理仅仅是必要的，而不是充分的。也就是说知道这个点是最优点能够推断出容许方向锥和下降方向锥的交集是空集，但由容许方向锥和下降方向锥的交集是空集并不能推断出其是最优点。

  这里要介绍：引理(Farkas)、引理(Gordan)、定理：Fritz John

引理(Farkas) ：设 ， ， ， 和 是 维向量，则满足：

  的向量 也满足

  的充要条件是，存在 非负数 ， ， ， ，使得：

  这个依旧不需要证明，相信它就完事了，因为直观上感觉就是非常正确的。可以看课本图4-6。或者下面这张图理解( 理解为 )：

定理：Fritz John： 在问题2中，设 是局部最优解， ， ， ， ， 在点 处可微，那么，存在不全为零的实数 ， ， ， 使得：

  上面这个式子我们来理解一下，因为这个 是最优点，所以这个容许集和下降方向集是空集。所以不存在向量 ，使得：

   称为 互补松弛条件 。它表明：若 ，即 ，则必有 ；若 ，则必有 ，即 。

  这个定理给你了问题2的一个 最优性必要条件 。上式称为Fritz John条件，满足Fritz-John条件的点称为 Fritz-John点 。 ， ， ， 也称为Lagrange乘子。

  Fritz-John条件仅是判别某一容许点是否为 最优点的必要条件 ，而不是充分条件。

  如果Fritz-John条件中 时，Fritz-John条件失去实用价值。为了使得其大于0，就有了Kuhn-Tucker条件。

定理：Kuhn-Tucker：

在问题2中，假设

i） 是局部最优点；

ii) 在点 处可微；

iii) 点 处的全部起作用约束的梯度线性无关。那么存在实数 使得：

  Kuhn-Tucker条件是Fritz John条件的特殊情况。

  Kuhn-Tucker条件有明显的几何意义。在Kuhn-Tucker定理的公式中，删去不起作用约束项（注意，它们的系数是 ，当 ，Kuhn-Tucker条件可简写成：存在 （ ）使得：

  此式在几何上表示：若 是问题地最优解，根据Farkas引理可知，在此点处地目标函数地梯度必处在由起作用约束函数地梯度张成地凸锥之中。

  之前是不等式约束，现在考虑一般约束问题地最优性条件，既有等式约束还有不等式约束的情况。我们这节就介绍一般约束问题下的 Fritz-John定理 和 Kuhn-Tucker定理 ：

Fritz-John定理 ：

  考虑问题：

  在上述问题中设 是局部最优点 ， 在点 处可微。那么，存在不全为零的实数 ，使得：

  这个定理可以看成是Lagrange定理的结论与Fritz-John定理的结论的合并。相当于多了 个等式约束。

Kuhn-Tucker定理 ：

  考虑问题：

  假设：

  i) 是局部最优解；

  ii） 在点 处可微；

  iii）点 处的全部起作用约束的梯度线性无关。

那么存在实数 使得：

定理：

  在以下 凸规划 问题中：

  假设 是可微 凸函数 ， 是可微凹函数， 是线性函数。若 是上述问题的Kuhn-Tucker点，则 就是上述问题的全局最优点。(用Hesson矩阵即可证明是不是凸优化问题)。

找出问题所在了.

你看一下你的dd

由于你的Dd是一个三次方程,有三个解.也就是说dd有三个值.才出现上述问题.

想办法看一下怎么弄吧。

我记得梯度法求d是有公式，不要我们人工去求导的。

找找书看看吧。

另外

if(double(sqrt((a(k)-a(k-1))^2+(b(k)-b(k-1))^2))<=0.001&&double(abs((f(k)-f(k-1))/f(k-1)))<=0.001)

如果k=1的话，a(k-1)会有问题的。

约束优化问题的目标是在满足一组线性或非线性约束的条件下，找到使得适应值函数最优的解。对于约束优化问题，需要对原始PSO算法进行改进来处理约束。

一种简单的方法是，所有的微粒初始化时都从可行解开始，在更新过程中，仅需记住在可行空间中的位置，抛弃那些不可行解即可。该方法的缺点是对于某些问题，初始的可行解集很难找到。或者，当微粒位置超出可行范围时，可将微粒位置重置为之前找到的最好位置，这种简单的修正就能成功找到一系列Benchmark问题的最优解。Paquet让微粒在运动过程中保持线性约束，从而得到一种可以解决线性约束优化问题的PSO算法。Pulido引入扰动算子和约束处理机制来处理约束优化问题。Park提出一种改进的PSO算法来处理等式约束和不等式约束。

另一种简单的方法是使用惩罚函数将约束优化问题转变为无约束优化问题，之后再使用PSO算法来进行求解。Shi将约束优化问题转化为最小—最大问题，并使用两个共同进化的微粒群来对其求解。谭瑛提出一种双微粒群的PSO算法，通过在微粒群间引入目标信息与约束信息项来解决在满足约束条件下求解目标函数的最优化问题。Zavala在PSO算法中引入两个扰动算子，用来解决单目标约束优化问题。

第三种方法是采用修复策略，将微粒发现的违反约束的解修复为满足约束的解。

约束满足

PSO算法设计的初衷是用来求解连续问题，，对微粒的位置和速度计算公式进行了重新定义，使用变量和它的关联变量存在的冲突数作为微粒的适应度函数，并指出该算法在求解约束满足问题上具有一定优势。Lin在Schoofs工作的基础上研究了使用PSO算法来求解通用的n元约束满足问题。杨轻云在Schoofs工作的基础上对适应度函数进行了改进，把最大度静态变量序列引入到适应度函数的计算中。

---