最优化方法4 - 约束最优化 (1)

《最优化方法4 - 约束最优化 (1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化–约束1最优化方法及应用OptimizationMethodsandTheirApplications约束最优化Constrainedoptimization2017年秋季提纲约束最优化问题的一般形式约束优化问题局部解的一阶必要条件Kuhn-Tucker条件典型的约束最优化方法罚函数法复合形法其可行域为：其可行域为：其可行域为：一般约束优化问题，其约束包含不等式约束和等式约束．起作用约束在可行点处，如果有，则该约束称可行点的起作用约束；不起作用约束如果有，则该约束称可行点的不起作用约束．对于等式约束，

2、显然在任意可行点处的等式约束都是起作用约束．在某个可行点处，起作用约束在的邻域内起到限制可行域范围的作用，而不起作用约束在处的邻域内就不产生影响．因此，应把注意力集中在起作用约束上．起作用约束和不起作用约束例：具有三个不等式约束的二维最优化问题（a）是最优点在可行域内部的一种情况．在此种情形下，点的全部约束函数值均大于零，所以这组约束条件对其最优点都不起作用．换句话说，如果除掉全部约束，其最优点也仍是同一个点．因此这种约束优化问题IP型约束问题的一阶必要条件与无约束优化问题是等价的．（b）约束最优点在的边界

3、曲线与目标函数等值线的切点处．此时，，，，所以是起作用约束，而其余的两个是不起作用约束．既然约束最优点是目标函数等值线与边界的切点，则在点处目标函数的梯度与约束函数梯度矢量必共线，而且方向一致．若取非负乘子，则在处存在如下关系（c）当前迭代点在两约束交点上，该点目标函数的梯度矢量夹于两约束函数的梯度矢量，之间．显然，在点邻近的可行域内部不存在目标函数值比更小的可行点．因此，点就是约束最优点，记作．由图可知，此时点目标函数的梯度可表达为约束函数梯度和的线性组合．若用代替即有成立，且式中的乘子和必为非负.总结以

4、上各种情况，最优解的一阶必要条件为IP型约束问题的一阶必要条件将以上分析推广至一般情况，并且把个约束全部考虑进去，取不起作用约束的相应乘子为零，则IP问题的最优解的一阶必要条件为其中是最优点。因为在实际求解过程中，并不能预先知道最优点位于哪一个或哪几个约束边界的汇交处．为此，把个约束全部考虑进去，并取不起作用约束的相应乘子为零。对于起作用约束，必有，因此式中的第四式成立；对于不起作用约束，虽然而必有IP型约束问题的一阶必要条件EP问题中，等式约束曲线是它的可行域，而且目标函数等值线与约束曲线的切点是该约束问

5、题的最优解．在点处，目标函数的梯度与约束函数的梯度共线．因此，在最优点处一定存在一个乘子，使得成立。对于一般的维等式约束优化问题，为其解的一阶必要条件为EP型约束问题的一阶必要条件由上述不等式约束优化与等式约束优化问题的一阶必要条件，可以推出一般约束优化问题的条件．为其解的一阶必要条件应为GP型约束问题的一阶必要条件函数称为关于GP型问题的广义拉格朗日函数，式中为拉格朗日乘子．由于引入拉格朗日函数，一阶必要条件中的第一式可写为GP型问题的广义拉格朗日函数在优化实用计算中，常常需要判断某可行迭代点是否可作为约

6、束最优点输出而结束迭代，或者对此输出的可行结果进行检查，观察它是否已满足约束最优解的必要条件，这种判断或检验通常借助于Kuhn—Tucker条件进行．Kuhn-Tucker条件如果是一个局部极小点，且各梯度矢量组成线性无关的矢量系，那么必存在一组非负乘子，使得成立。满足这一条件的（）称为一个K-T点.IP型问题的Kuhn-Tucker条件应用Kuhn-Tucker条件检验某迭代点是否为约束最优点的具体作法可按下述步骤进行：（1）检验是否为可行点．为此需要计算处的诸约束函数值，若是可行点，则（2）选出可行点处

7、的起作用约束．前面已求得个值，其中等于零或相当接近零的约束就是起作用约束．把这些起作用约束重新编排成序列，（3）计算点目标函数的梯度和个起作用约束函数的梯度（4）按K-T条件，点应满足IP型问题的Kuhn-Tucker条件检验算法将上式中的各梯度矢量用其分量表示，则可得到为变量的线性方程组由于矢量系是线性无关的，所以该方程组存在唯一解．通过解此线性方程组，求得一组乘子，若所有乘子均为非负，即，，则即为约束最优解．否则，点就不是约束最优点．IP型问题的Kuhn-Tucker条件检验算法例如果是一个局部极小点，

8、且各梯度矢量和组成线性无关的矢量系，那么必存在两组非负乘子和，使得成立。GP型问题的Kuhn-Tucker条件由处理约束条件的办法不同，约束优化方法也可分为直接法和间接法两大类．间接法的基本思想是将约束优化问题首先转换为一系列的无约束优化问题，然后利用无约束优化方法来求解，逐渐逼近约束问题的最优解．这些算法一般比较复杂，但由于它们可以采用计算效率高、稳定性好的无约束优化方法，故可用于求解高维的优化问题．直接法的基