摘要
2006年,于波、商玉凤提出了求解非凸规划问题的动边界组合同伦方法,在较弱条件下证明了同伦路径的存在性和收敛性.与已有的拟法锥条件、伪锥条件下的修正组合同伦方法相比,所需的条件更弱,同伦构造更容易,并且不要求初始点是可行集的内点,因此它更便于应用.
在求解仅带有不等式约束的动边界组合同伦方法中,为了保证全局收敛性,需要构造一类具有下述两个性质的动约束函数：积极约束满足正独立性及初始约束集合满足法锥条件.本文针对特殊形式的二次约束非凸规划问题,给出了构造满足这两个性质的动约束函数的理论分析和一个形式上的算法.为了判断假设条件中向量组的正独立性,本文从代数角度出发,给出了一个等价的判断条件,并根据这个条件设计了相应的算法,通过具体算例验证了算法的可行性.
在用Euler-Newton法数值跟踪同伦路径时,预估阶段需要计算切向量,以确定预估方向.本文对原有的列主元QR分解算法进行修改,得到了一种新的算法.此算法不需要对k1,k2…,kn按上升次序排列计算其最小交换数,而且算法执行到最后可以得到一个显式的上三角矩阵,容易存储和利用回代法求解.与原有的算法相比,更加便于编程实现,执行效率高,实用性更强.
In 2006, the boundary moving combined homotopy method for solving non-convex programming is given by Yu Bo and Shang Yu feng and the existence and convergence of the homotopy path is proved under some weak conditions. The conditions needed is weaker and the homotopy is easier to be constructed than the modified combined homotopy under quasi-normal cone condition and pseudo-cone condition. Moreover, it need not to choose the start point inside the interior part of the feasible set, so the method is more convenient to be implemented.
In boundary moving combined homotopy method for solving the problem with only inequality constraints, to ensure its global convergence, it is needed to construct a class of constraint shifting functions with the following two properties:a) Positive independence of active constraints; b) Starting feasible set satisfies normal cone condition. In this paper, We propose the theoretical analysis of constructing the constraint shifting functions and a formal algorithm. From the view of algorithm, this paper also gives a judgment condition, which is equivalent to the positive independence of vector groups, and an algorithm which is designed in order to judge the positive independence. Some specific examples are given to verify the feasibility of the algorithm.
It is needed to calculate the tangent vector in estimated phase so as to determine the estimate direction while numerically tracking homotopy path with Euler-Newton method. By modifying the original one in the book named the theory and method of nonlinear nu-merical analysis, we proposed a new column primary QR decomposition algorithm which is not required to calculate the minimum exchange number of k1, k2,…, kn according toits ascending order in this paper.moreover, algorithm implementation in the end, we can get an explicit which is easy to store and solve with back substitution method. Compared with the original algorithm, it is more convenient of the programming and of high efficiency and more practical application.
引文
[1]Linderoth J. A simplicial branch-and-bound algorithm for solving quadratically con-strained quadratic programs[J]. Mathematical Programming,2005,103(2):251-282.
[2]Raber U. A simplicial branch-and-bound method for solving nonconvex all quadratic programs[J]. Journal of Global optimization,1998,13(4):417-432.
[3]Liu G S, Zhang J Z. A new branch and bound algorithm for solving quadratic pro-grams with linear complementarity's constraints [J]. Journal of computational and Applied Mathematics,2002,146:77-87.
[4]Ye Y Y. Approximating global quadratic optimization with convex quadratic con-straints[J].1999,15:1-17.
[5]Brimberg J, Hansen P, Mladenovic N. A note on reduction of quadratic and Bilinear programs with equality constraints [J]. Journal of Global optimization,2002,22:39-47.
[6]Shen P P, Zhang K C. Global optimization of signomial geometric programming using linear relaxation [J]. Applied Mathematics and computation,2004,150:99-144.
[7]Gao Yuelin, Xue Honggang, Shen Peiping. A new rectangle branch and reduce ap-proach for solving nonconvex quadratic programming problems [J]. Applied Mathe-matics and Computation,2005,168(2):1409-1418.
[8]李会荣,高岳林.带有二次约束的非凸二次规划问题的一种全局优化方法[J].哈尔滨：黑龙江大学自然科学学报,2008,25(5)：696-700.
[9]高岳林,徐成贤.带有二次约束的一般二次规划问题的松弛分枝定界方法[J].西安：西安交通大学学报,2002,36(8)：871-874.
[10]Pardalos P M, Vavasis S A. Quadratic programming with one negative eigenvalue is NP-hard[J]. Journal of Global Optimization,1995,5:286-313.
[11]郑小金.基于最优D.C.分解的单二次约束非凸二次规划精确算法[[J].上海大学运筹学学报,2009,13(3)：111-118.
[12]Davidenko D. On a new method of numercial solution of systems of nonlinear equa-tions[J]. Doklady Akad. Nauk USSR.,1953,88:601-604.
[13]Gavurin M. Nonlinear function equations and continuous analogues of iterative method[J]. Russian, Izv. Vyss. Ucebn.Zaved,1958,6:18-31.
[14]Kellogg R B, Li T Y, Yorke J A. A constructive proof of the Brouwer fixed-point theorem and computational results [J]. SIAM J. Numer.Anal.,1976,13:473-483.
[15]Chow S N, Mallet-Paret J, Yorke J A. Finding zeros of maps:Homotopy methods that are constructive with probanility one[J]. Math. Comput.,1978,32:887-899.
[16]Garcia C B, Zangwill W I. Pathways to Solutions, FIxed Points and Equilibria[M]. Prentice-Hall, New Jersey,1981.
[17]Karmarkar N. A new polynomial-time algorithm for linear programming[J]. Combi-natirica,1984,14:373-395.
[18]Wrught S J. Primal-Dual Interior-Point Methods[M]. Philadelphia,Pa,SIAM,1997.
[19]于波,商玉凤.解非凸规划问题的动边界组合同伦方法[J].数学研究与评论,2006,26(4)：831-834.
[20]Feng Guo chen, Yu Bo. Combined homotopy interior pointmethod for nonolinear pro-gramming problems[J]. Advances in numerical mathematics; Proceedings of the Sec-ond Japan-China Seminar on Numerical Mathematics (Tokyo,1994), Lecture Notes in Num.Anal.,1995,14:9-16.
[21]Feng Guo chen, Lin Zheng hua, Yu Bo. Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem [J]. Nonlinear Analysis, 1998,32:761-768.
[22]Lin Zheng hua, Yu Bo, Feng Guo chen. Combined homotopy interior point method for convex nonlinear programming[J]. Apppl.Math.Comput.,1997,84:193-211.
[23]Yu Bo, Feng Guo chen, Zhang Shao liang. The aggregate constraint homotopy method for nonconvex nonlinear programming[J]. Nonlinear Analysis, TMA,2000,45:839-847.
[24]Liu Qing huai, Yu Bo, Feng Guo chen. An interior point path-following method for nonconvex programming with quasi normal cone condition[J]. Adv. Math., 2000,29:281-282.
[25]Yu Bo, Liu Qing huai, Feng Guo chen. A combined homotopy interior method for non-convex programming with pseudo cone condition[J]. Northeast. Math.,2000,16:383-386.
[26]Wstson L T. Theory of globally convergent probability-one homotopies for nonlinear programming[J]. SIAM J. OPtim.,2000,11:761-780.
[27]商玉凤.解非线性规划、均衡规划和变分不等式问题的动边界组合同伦方法[D].长春：吉林大学数学学院,2006.
[28]黄象鼎,曾中钢,马亚南.非线性数值分析的理论与方法[M].武汉：武汉大学出版社,2004.
[29]Nocedal Jorge, Wright Stephen J. Numerical Optimization[M]. New York:Springer, 2006.
[30]张春阳,张国霜,刘庆怀,等.正独立映射的判定及其在非凸优化中的应用[J].长春工业大学学报：自然科学版,2010,31(1)：111-114.
[31]Nemirovski Arkadi. Lectures on modern convex optimization[M]. SIAM, Philadelphia, PA,2001.
[32]卢开澄,卢华明.线性规划[M].北京：清华大学出版社,2009.
