两类二阶锥线性互补问题的低阶罚函数算法研究

发布时间：2018-02-03 12:40

本文关键词： 二阶锥规划二阶锥互补问题低阶罚函数算法指数收敛速度　出处：《北方民族大学》2016年硕士论文　论文类型：学位论文

【摘要】：二阶锥规划隶属于凸优化,它的目标函数是线性函数的极小化或极大化问题,而约束域为一个仿射空间和若干个二阶锥的笛卡尔乘积的交集.线性规划、凸二次规划、凸二次约束二次规划等问题都可统一转化为二阶锥规划问题,且它们又都是半定规划的特例.二阶锥规划已经成为数学规划领域一个重要的研究方向.二阶锥互补问题是一类均衡优化问题,是指在二阶锥约束条件下,两组决策变量之间满足一种互补关系,它隶属于对称锥互补问题.近几年来,人们在欧几里得约当代数的基础上,对二阶锥互补问题的研究已取得许多成果,并且使之逐渐受到了重视.由于二阶锥规划的KKT条件是二阶锥互补问题的一种特殊情况,因此可以运用求解二阶锥互补问题的算法来解决二阶锥规划问题.低阶罚函数算法是求解对称锥互补问题的有效方法,其主要思路即将互补问题转化为低阶罚函数方程组,此算法的突出之处在于低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥互补问题的解.由于低阶罚函数算法有很多良好的性质,比如解的精确性等,所以将低阶罚函数算法扩展到求解二阶锥互补问题上是一个非常有意义的研究工作.本文主要研究求解二阶锥线性互补问题的低阶罚函数算法.其主要内容如下:1.针对二阶锥线性互补问题,利用低阶罚函数算法的思想及二阶锥投影的幂的表达式将二阶锥线性互补问题转化为低阶罚函数方程组.证明了矩阵正定(不一定对称)的条件下低阶罚函数方程组的解序列以指数速度收敛于二阶锥线性互补问题的最优解.数值实验的结果进一步验证了有关理论的结果.并将低阶罚函数算法的数值结果与著名的光滑Fischer-Burmeister(F-B)函数算法进行比较,结果表明提出的算法是有效的,并且占有一定优势.2.针对一类广义的二阶锥线性互补问题,利用低阶罚函数算法的思想也将其转化为低阶罚函数方程组.在矩阵正定(不一定对称)的前提下,证明了在罚参数趋向于正无穷时,低阶罚函数方程组的解序列以指数速度收敛于原广义二阶线性锥互补问题的解.最后,对本文的工作作了总结,并提出了有待进一步研究的工作.
[Abstract]:The second order cone programming belongs to convex optimization. Its objective function is the minimization or maximization of linear function, while the constraint domain is the intersection of the Cartesian product of an affine space and several second order cones. Problems such as convex quadratic programming and convex quadratic constrained quadratic programming can be unified into second-order cone programming problems. And they are special cases of semidefinite programming. Second order cone programming has become an important research direction in the field of mathematical programming. Second order cone complementarity problem is a kind of equilibrium optimization problem, which refers to the second order cone constraint problem. The two sets of decision variables satisfy a kind of complementary relation, which belongs to the symmetric cone complementarity problem. In recent years, on the basis of Euclidean approximate contemporary numbers, many achievements have been made in the study of the second-order cone complementarity problem. The KKT condition of the second-order cone programming is a special case of the second-order cone complementarity problem. Therefore, we can use the algorithm to solve the second-order cone complementarity problem, and the low-order penalty function algorithm is an effective method to solve the symmetric cone complementarity problem. The main idea is to transform the complementarity problem into a system of low-order penalty function equations. The outstanding point of this algorithm is that the sequence of solutions of the system of low-order penalty function converges to the solution of the second-order cone complementarity problem at exponential speed under certain conditions, because the low-order penalty function algorithm has many good properties. Such as the accuracy of the solution. Therefore, it is very meaningful to extend the low order penalty function algorithm to solve the second order cone complementarity problem. In this paper, we mainly study the low order penalty function algorithm for solving the second order cone linear complementarity problem. The main contents of this paper are as follows. :. 1. For the second order conical linear complementarity problem. By using the idea of the low-order penalty function algorithm and the expression of the power of the second-order cone projection, the linear complementarity problem of the second-order cone is transformed into the low-order penalty function equations. It is proved that the matrix is positive definite (not necessarily symmetric). The sequence of solutions of the system of penalty function of low order converges to the optimal solution of the linear complementarity problem of second order cone at exponential speed. The results of numerical experiments further verify the results of the theory. The number of the algorithm of low order penalty function is also given. Value results and the famous smooth Fischer-Burmeister (. F-B) function algorithm is compared. The results show that the proposed algorithm is effective and has a certain advantage .2. for a class of generalized second-order conical linear complementarity problems. By using the idea of low-order penalty function algorithm, it is also transformed into a set of low-order penalty function equations. On the premise of positive definite matrix (not necessarily symmetric), it is proved that the penalty parameters tend to be positive infinity when the penalty parameters tend to be positive infinity. The sequence of solutions of the system of penalty functions of low order converges to the solution of the original generalized second order linear cone complementarity problem at exponential speed. Finally, the work of this paper is summarized, and the work to be further studied is put forward.
【学位授予单位】：北方民族大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O221

【相似文献】