约束序列极大极小问题的部分凝聚动约束组合同伦方法

1、约束序列极大极小问题的部分凝聚动约束组合同伦方法* 刘庆怀*基金项目：国家自然科学基金资助项目（10771020）；吉林省教育厅“十一五”科学技术研究资助项目 *通讯作者：刘庆怀（1961） 男 教授 博士 吉林长春人 主要从事最优化理论与算法研究，Email：Liuqh6195. 王秀玉1 谭佳伟1(1 长春工业大学基础科学学院,长春 130012).摘要:为解决约束序列极大极小问题(CSMMP)，首先构造凝聚动约束函数族并给出其相关性质,然后构造组合同伦方程,给出同伦路径收敛性证明,所用初始点既可以是内点 也可以是外点,最后,给出数值算例,并用matlab7.0编程进行计算,数值结果表明:

2、此算法是可行和有效的.关键词: 序列极大极小问题,同伦方法,凝聚函数,动约束 1991 MR subject classification:90C47,65K05,65H10,90C51中图分类号:O221.21 预备知识约束序列极大极小优化问题是一类重要的优化问题。它在工程设计、电子线路设计、热交换设计、化学反应设计等诸多领域有广泛的应用（1 8）.此外，多目标规划、随机规划的一些特殊情形可转化为约束序列极大极小优化问题9.约束序列极大极小优化问题相应算法的主要困难是问题本身的非光滑性及非凸性，至今尚缺少有效的算法，处理这类问题有割平面法、捆集信赖域法及采用分解的策略等.文10以引入若干额外

3、变量为代价讨论了此类问题转化为一种光滑约束规划问题.文11利用凝聚同伦方法讨论了可行域的边界满足弱法锥条件下约束序列极大极小优化问题.但当可行域不满足弱法锥条件时, 使用凝聚同伦方法解决约束序列极大极小优化问题的算法尚未见到,本文在这方面做一些尝试性工作,并得到了较好的结果. 本文考虑如下的序列极大极小问题(CSMMP):记 ,.引理1 .(证明参考11)假设1 和均为至少三次连续可微的函数;2 对任意是正独立的;其中,3 有界连通, 非空.定理 111 若 and 均为充分光滑的函数且假设2,3的条件成立.如为 CSMMP问题的局部极小点,则存在 使得其中 .上述方程的解成为序列极大极小问题

4、(CSMMP)的点.为解决CSMMP问题我们构造如下动约束函数族:,其中, 为一族充分光滑的函数.记 .2 主要结论引理2 若假设1和 3的条件成立, 则 有:,其中,且有: ,证明: 略.引理3 若假设1,2,3的条件成立,则存在 ,对,是正独立的.证明:(反证)假如上述结论不成立,则存在,且 不全为零,满足:且 因为, 必存在收敛子列,仍记为,及, , 则 矛盾(因假设3,及, 固有对任意,是正独立的.选取即可. 在计算过程中保证所选取的满足:假设 4 满足法锥条件12:,其中是空集.因,只要取得足够小就能保证非空,对,记,构造同伦方程如下: (1)其中,当, 式(1)变为 显然有唯一解.

5、由引理2得: 当, 式(1)变为 ,where, .且显然成立.记引理 4 若假设1,2,3的条件成立,则对于几乎所有的 ,0是映射 的正则值,同伦方程 (1) 产生一条起始于点的光滑曲线,记为证明:用 表示的矩阵 (看作变量)=,对几乎所有的 ,有 , 为单位矩阵, 对任意的,因 ,则 行满秩.由参数化定理,得0是映射 的正则值,再由逆映象定理及,含有一条起始于点的光滑曲线 .引理5 若假设1,2,3的条件成立,则对任意给定的 , 0是映射 的正则值,则有 是中的有界曲线.证明: 由同伦方程(1)易知 .若 是无界曲线,那么必存在点列,使得,由同伦方程(1)的第二个方程得: :, (2)由(

6、2)得, 及 , 有界,即有界,必存在收敛子列,仍记为,设,其中,由 (2) 得到:, ,i.e.,.由同伦方程(1)的第一个方程得: : (3)(3)式重写为: (1) 若 (3)式两边取极限得: ,由引理3, 存在,记 (3)式为: ,此与假设4矛盾.(2) 若当时, 式左边的第二项趋于无限,而其他各项均趋于有限,又产生了矛盾.综上所述, 有界. 定理2 若假设1,2,3的条件成立,同伦映射由(1)式给出,则对几乎所有的 ,同伦方程(1)的零点集包含一条起始于的光滑曲线.当时, 的极限点存在,记为, 为序列极大极小问题的K-K-T 点. 证明: 由引理4 和5得的存在性及连续性.又由一维光

7、滑流形的分类定理知:或微分同胚于单位圆周,或微分同胚于单位区间.注意到:是非奇异矩阵,不能微分同胚于单位圆周,只能微分同胚于单位区间.设为的极限点.则只有下列五种情况可能出现:(1) 存在一个;(4) ;.证明:由引理5知:情形(1)不可能出现;又由同伦方程在有唯一解知,情形 (3)不可能出现;由(2)式,若有某及,必有,这是不可能的, 情形 (2)也不可能出现; 由(2)式,如果,则有某,(4)也不可能出现;因而,只有情形(5)是唯一可以成立的结论.其余显然可证.从定理2可以得到,对几乎所有的,同伦方程(1)生成一条光滑曲线 ,称之为同伦路径.设s 表示的弧长,参数化这条解曲线,即存在连续可

8、微函数使得: (4)关于微分(4)式的第一个等式,得到如下结论:定理3 同伦方程所确定的解曲线满足如下微分方程的初值问题:并且,若有使得,则是序列极大极小问题的点. 3 数值算例例1 其中 , ;, ;, ;, ;,.,满足法锥条件(法锥条件见12). 用7.0编程计算结果如下：表1 例1计算结果1/72.611.11110.00061.61720.06930.01940.02420.06870.0094其中 ,.参考文献1 Limin，H. E. and Polak, E., Effective diagonalization strategies for the solution of a

9、 class of optimal design problems, 35 (1990) 258-267.2 Bandler，J. W., Liu, P. C. and Tromp, H., A nonlinear programming approach to optimal design centering, tolerancing, tuning, CAS-23, 1976, 155-165. 3 Liu, P. C., Chung, V. M. and Li, K. C., Circuit design with post-fabrication tuning, in Proc. Wa

10、shington, DC. IEEE, NY, 1992,344-3474 Muller, G., On computer-aided tuning of microwave filters, In IEEE Proc. international Symposium on Cirtuits and Systems, Munich, IEEE Computer Society Press Los Alamitos, CA, 1976, 722-725.5 Polak, E., Sangiovanni, A. and Vincentelli, A. S., Theoretical and com

11、putational aspects of the optimal design centering, tolerancing and tuning prblom, CAS-26, 1976, 795-813.6 Gilbert,E. G. and Johnson, D. W., Distance functions and their application to robot path pianning in the presence of obstacles, RA-1, 1985,21-30.7 Halemane, K. P. and Grossman, I. E., Optimal p

12、rocess design under uncertainty, 29 (1983),425-433.8 Ostrivsky, G. M., Volin, Y. M., Barit, E. I. and Senyavin, M. M., Flexibility analysis and optimization of chemical plants with uncertain parameters,18 (1991),755-7679 Scholtes, S., Combinatorial structures in nonlinear programming, Judge Institut

13、e of management, Department of Engineerng, University of Cambridge CB21AG, 2002.10 Kirjner-Neto, C. and Polak, E., On the conversion of optimization problems with max-min constraints to standard optimization problems. 8 (1998), 887-915.11 LIU Guo-xin. Aggregaye Homotopy Methods for Solving Sequential Max-Min Problems,Complementarity Problems and Variational lnequalities D：Ph D ThesisChangchun Jilin University, 2003. in Chinese12 Xu Qing，Yu Bo，Homotopy Methods for Non-convex Programming in Unbo