约束最优化问题的求解算法

fdsgsg

约束最优化问题的求解算法

求解约束优化问题要比求解无约束优化问题复杂困难, 在每次迭代时, 不仅要使方针函数值有所下降, 而且要使迭代点要落在可行域内. 因而求解方式也就多种多样. 归纳起来, 大致可以分为两类:
1. 间接方式
将约束优化问题进行某种措置(转换或近似)得到一个或多个新问题，然后通过求解新问题得到原优化问题的最优解，如罚函数方式、Lagrange-Newton方式、SQP方式和对偶类方式等。
(1) 转换成无约束优化问题(如变量消去法)，只适用于特殊问题。
(2) 用一系列无约束优化问题近似，例如罚函数方式(外罚函数、内罚函数、ALM)
(3) 用一系列简单约束的优化问题近似，例如序列二次规划法(SQP)
(4) 每个优化问题都有对应的对偶问题．出格是凸的情形，当原始问题斗劲难解的时候，其对偶问题可能很容易求解．通过求解对偶问题或者同时求解原始问题和对偶问题，可以简化原始问题的求解，从而设计更有效的算法．
这类优化方式可以用于任意的约束优化问题。
2. 直接方式
操作约束优化问题本身的性质,在可行域内直接求解，极小化方针函数。该方式大多从无约束优化问题的下降方式衍生而来，其迭代过程一般通过两种策略实现：
(1) 从问题的可行点出发，在该点的可行标的目的中，寻找使方针函数下降的标的目的, 然后沿可行下降标的目的进行线搜索发生新的可行迭代点，如此进行下去，算法发生一个点列，该点列中的所有的点均为问题的可行点．但愿该点列终止于问题的解，或其极限点是问题的解．这类方式称为可行标的目的法，如Zoutendijk可行标的目的法。
(2) 搜索标的目的为当前点的下降标的目的在可行标的目的集中的投影，称相应的算法为投影法．借助投影技术由当前迭代点沿可行域的边界进行曲线搜索，如GLP投影算法．
这类优化方式斗劲适合可行域布局简单的凸约束优化问题或线性约束问题，而且由于搜索标的目的多基于负梯度标的目的，收敛速度至多是线性的。