【作者】 李慧；

【导师】 于波；

【作者基本信息】 大连理工大学 ， 计算数学， 2011， 硕士

【摘要】 2006年,于波、商玉凤提出了求解非凸规划问题的动边界组合同伦方法,在较弱条件下证明了同伦路径的存在性和收敛性.与已有的拟法锥条件、伪锥条件下的修正组合同伦方法相比,所需的条件更弱,同伦构造更容易,并且不要求初始点是可行集的内点,因此它更便于应用.在求解仅带有不等式约束的动边界组合同伦方法中,为了保证全局收敛性,需要构造一类具有下述两个性质的动约束函数：积极约束满足正独立性及初始约束集合满足法锥条件.本文针对特殊形式的二次约束非凸规划问题,给出了构造满足这两个性质的动约束函数的理论分析和一个形式上的算法.为了判断假设条件中向量组的正独立性,本文从代数角度出发,给出了一个等价的判断条件,并根据这个条件设计了相应的算法,通过具体算例验证了算法的可行性.在用Euler-Newton法数值跟踪同伦路径时,预估阶段需要计算切向量,以确定预估方向.本文对原有的列主元QR分解算法进行修改,得到了一种新的算法.此算法不需要对k1,k2…,kn按上升次序排列计算其最小交换数,而且算法执行到最后可以得到一个显式的上三角矩阵,容易存储和利用回代法求解.与原有的算法相比,更加便于编程实现,执行效率高,实用性更强.更多还原

【Abstract】 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.更多还原