Filter方法在不等式约束优化问题中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇Filter方法在不等式约束优化问题中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘 要】用filter方法取代罚函数进行线性搜索，又利用序列线性方程组获得搜索方向，使得迭代点能够保证目标函数或约束函数充分下降，在一定假设条件下可以收敛到原问题的最优解。

【关键词】序列线性方程组；罚函数；收敛性

The Application of A Filter Method in Solving Inequality Constrained Optimization Problem

ZHENG Xue-lian

（Shandong Institute of Business and Technology， Yantai Shandong 264005）

【Abstract】A filter method has been developed which advoids using a penalty parameter to perform linear search . The search direction has been got by Sequential Systems of Linear Equations. The aim is allows a step to be accepted if it reduces either the objective function or the constraint violation function.It proved to be converged to a KKT point under mild conditions.

【Key words】Sequential Systems of Linear Equations；Penalty function；Convergence

本文考虑这样的不等式约束优化问题：■ f（x）s.t. ci（x）≤0， i∈I，其中I={1，2，…，m}且f（x）和ci（x）均为二阶连续可微的实值函数。对于任意的x∈R■，定义I（x）={i∈I|ci（x）=Ψ（x）}，其中Ψ：R■R，Ψ（x）=max{ci（x），i∈I；0}。

为了求目标函数的极小值，并且使迭代点列收敛到原问题的可行域内，我们用filter方法代替传统的罚函数法，将不等式约束优化问题转化为这样的形式：■ f（x）■ h（c（x）），这里h（c（x））=，c+（x）其中c+（x）=（c1+（x），c2+（x），…cm+（x））T，ci+（x）=max（0，ci（x）），i∈I。

序列{xk}由xk+1=xk+αdk得到，搜索方向dk由如下线性方程组来计算，（LS1）Hkd+■？姿■？荦c■（x■）=-？荦f（x■）c■（x■）+？荦c■（x■）■d=0， i∈J■， J■=i-？着■c■（x■）-？追（x■）0，i∈I，。

本文我们在严格互补松弛条件和二阶充分条件（SOSC）的假设条件下，并且？荦2f，？荦2c■，i∈I在x*的某个邻域上都是局部Lipschitz连续的。对任意的x∈R■，向量组{？荦c■（x），i∈I（x）}是线性无关的，产生的迭代序列{xk}包含在紧致凸集中。

引理1 在假设条件下，若x■是一个可行点，则对充分大的k，有 ■？姿k，ic■（x■）≤-■ck，这里ck=■ 且■>0。

证明 因为xk是一个可行点，故有c■（x■）≤0，i∈I。再由严格互补松弛条件和二阶充分条件，■？姿k，ic■（x■）≤min{？姿k，i，i∈I（x*）}■c■（x■），对i∈I（x*），有？姿k，i？姿k*>0，因此，min{？姿k，i，i∈I（x*）}≥min{■，i∈I（x*）}=■>0，又对任意的z∈R■，z≤z1，故有■？姿k，ic■（x■）≤■■c■（x■）≤-■ck，这里ck=■。

引理2 若假设条件成立，对充分大的k，x■是一个可行点，则搜索方向d■满足？荦f（x■）■dk≤-adk2，a>0。

证明 由（LS1），对充分大的k，dk满足：？荦f（x■）+Hkdk+■？姿k，0i？荦c■（x■）=0

从而有？荦f（x■）■dk+dkTHkdk+■？姿k，0i？荦c■（x■）■dk=0，

所以？荦f（x■）■dk=-dkTHkdk-■？姿k，0i？荦c■（x■）■dk，

又由（LS1）， ？荦c■（x■）■dk=-c■（x■），于是，？荦f（x■）■dk=-dkTHkdk+■？姿k，0ic■（x■），

再由假设条件和引理1，即可得？荦f（x■）■dk≤-adk2。

命题 设s*是序列s■？奂R■的一个孤立聚点，如果对每个收敛到s*的子列s■，存在子集■？哿K，使得s■-s■■0，则s■整列收敛到s*。

若α=1搜索方向dk可由线性方程组 （LS2） （LS3） 来计算，

（LS2）Hkd+■？姿■？荦c■（x■）=-？荦f（x■）c■（x■）+？荦c■（x■）■d=vk，i， i∈J■，

（LS3）Hkd+■？姿■？荦c■（x■）=-？荦f（x■）c■（x■）+？荦c■（x■）■d=-c■（x■+dk）+dkv， i∈J■，

定理 在所有假设条件下，x■整列收敛到x*。

证明 由严格互补松弛条件和二阶充分条件，（x*，？姿*）是一个孤立的KKT点。

对任意收敛到x*的子序列x■k∈K，当k充分大时，有

x■-x■≤αkdk 若求解（LS2）αkdk+αk2■k-dk，若求解（LS3）≤2αkdk对充分大的k，dk0，因此存在子集■？哿K，使得当k∈■∞时，x■-x■0。于是，由命题，可得x■K整列收敛到x*。

【参考文献】

[1]R.Fletcher and S.Leyfer. Nonlinear programming without a penalty function [J]. Technical Report NA/171， Department of Mathematics， University of Dundee， Scotland， to appear in Mathematical Programming， 1997.

[2]C.M.Chin. A local convergence theory of a filter line search method for nonlinear programming [J].Numerical Optimization Report， Department of Statistics， University of Oxford， England，2002.

[3]L.T.Biegler and A.Wachter. Global and local convergence of line search filter methods for nonlinear programming [J].CAPD Technical Report B-01-09， Department of Chemical Engineering， Carnegie Mellon University， Pittsburgh， PA， 2001.

[4]高自友，贺国平，吴方.任意初始点下的序列线性方程组算法[J].中国科学（A辑），1997，27（1）：24-33.