【作者】 房亮；

【导师】 贺国平；

【作者基本信息】 上海交通大学 ， 应用数学， 2010， 博士

【摘要】 二阶锥规划是在一个仿射空间和有限个二阶锥的笛卡尔积的交集上极小化或者极大化一个线性函数问题.其约束是非线性的,但却是凸的,因此二阶锥规划属于凸规划.二阶锥规划是半定规划的特例,而线性规划、凸二次规划和二次约束的凸二次优化等可作为它的特例.由于其宽广的应用范围、特殊的锥结构和计算上的方便性,所以它有其独立的研究价值.由于它的广泛应用和原始-对偶内点法的迅速发展,二阶锥规划已经成为数学规划领域的一个重要研究方向.二阶锥互补问题是一类均衡优化问题.近几年,人们借助欧几里得约当代数技术,在对称锥互补问题的研究方面取得了突破性进展并使之逐渐受到重视.二阶锥互补问题是二阶锥规划的推广,它包括线性二阶锥互补问题和非线性二阶锥互补问题.近几年来,人们对它的研究呈上升趋势,主要研究内容包括：解的存在性与特征,势函数和误差界,各种光滑化方法和优化方法,以及各种实际应用.关于非线性二阶锥规划及其互补问题的理论和算法,其研究方兴未艾,是当今人们关注的热点课题之一.本文主要研究二阶锥规划及其互补问题的算法.论文共分八个部分：第一部分,介绍二阶锥规划和二阶锥互补问题的模型,研究背景、意义和现状,并对现有算法加以总结,从而引出需要进一步解决的问题及本文所作的主要工作.第二部分,简要介绍有关预备知识.主要介绍欧几里得约当代数、二阶锥规划的最优性条件、中心路径条件、互补条件和原始-对偶内点算法.第三部分,定义了中心路径的一个宽邻域,并给出二阶锥规划问题的一个宽邻域原始-对偶路径跟踪内点算法,使得所有迭代点都跟踪这个宽领域,得到目前为止宽邻域路径跟踪内点算法最好的迭代复杂性界.第四部分,给出一个与二阶锥关联的光滑函数,并研究该光滑函数的性质.基于此光滑函数,给出二阶锥规划问题的一个光滑牛顿类型算法.该算法把扰动最优性条件重新表述成一个线性方程组进行求解,得到比相应的内点法更强的结果.它可以始于任意初始点；每步迭代只需求解一个线性方程组,执行一次线搜索；在较弱的假设下,算法所产生的序列全局收敛,并且在无严格互补条件的情况下Q二次收敛于问题的最优解.第五部分,受求解变分不等式问题的交替方向法的启发,给出二阶锥规划的一个带完全牛顿步的非内点全局收敛算法.该算法的主要思想是把原始-对偶最优性条件中的互补条件重新表述成一个投影方程.所给算法对初始点的可行性不作任何要求；每步迭代只需求解一个系数矩阵固定的线性方程组,执行两次简单的投影运算；无需执行任何线搜索；不要求约束系数矩阵的行向量组线性独立；算法所产生的序列全局收敛到问题的最优解,无需严格互补条件,这一结果强于相应的内点法和光滑算法.第六部分,研究一类特殊的二阶锥规划问题带有P0函数的非线性互补问题.基于一个新的带有惩罚项的光滑函数,把问题近似成参数化的光滑方程组,并且给出一个新的非内部连续化方法.所给算法在每步迭代只需求解一个线性方程组,执行一次Armijo类型的线搜索.在不需要严格互补条件的情况下,证明了该算法是全局收敛和超线性收敛的.并且,在一个较弱的条件下该算法具有局部二阶收敛性.通过数值实验证实了算法的可行性和有效性.第七部分,我们给出一类新的含有单参数的光滑二阶锥互补函数,在适当的条件下证明该类光滑函数是强制的.基于所给的单参数类二阶锥互补函数,给出求解单调二阶锥互补问题的一个光滑牛顿算法,在一定条件下证明了算法的全局收敛性和局部超线性收敛性.最后,在第八部分,针对现有的二阶锥规划及其互补问题算法存在的问题,提出了有待进一步研究的课题.更多还原

【Abstract】 Second-order cone programming is a kind of problem which minimizes or max-imizes a linear function over the intersection of an affine space with the Cartesian product of a finite number of second-order cones. The constraints of second-order cone programming are nonlinear, but they are convex, so it belongs to convex programming. Second-order cone programming is a special case of semidefinite programming, but it covers linear programming, convex quadratic programming, quadratically constraint convex quadratic optimization as well as other problems. The study of second-order cone programming has its independent value due to its wide range of applications, special cone constructer and computational convenience. Second-order cone program-ming has already become one of the important research direction in the mathematical programming fields.Second-order cone complementarity problems are a class of equilibrium problems. In recent years, based on the technique of Euclidean Jordan Algebra, many researchers have achieved a breakthrough in the study of symmetric cone complementarity prob-lems, and made them attract a lot of attention. Second-order cone complementarity problems are generalizations of the second-order cone programming. They contains both linear and nonlinear second-order cone complementarity problems. In the recent years, the study of second-order cone complementarity problems is increasing. The study contains:the existence and properties of the solution, potential function and error bound, many smoothing method and optimization method, and many real appli-cations. However, the study of nonlinear second-order cone programming and nonlinear second-order cone complementarity problems is just in its initial state, and it is one of the current hot fields that researchers pay attention to.The thesis mainly on the study of algorithms for second-order cone programming and second-order cone complementarity problems. It consists of the following eight parts:(1) In the first chapter, we introduce the modeling, research background, signif-icance and the recent situations of second-order cone programming and second-order cone complementarity problems. The existing methods is discussed and summarized, which drops the problems need to be further solved and the main results of the paper.(2) In the second part, we briefly introduce the preliminary knowledge. We mainly focus on Euclidean Jordan algebra, and optimality conditions, central path conditions, complementarity condition and interior-point method for second-order cone program-ming.(3) We define a wide neighborhood of the central path, and present a large-update primal-dual path-following interior-point algorithm for second-order cone programming in the third chapter. Each iterate is always following the wide neighborhood. We show that the method has the best iteration complexity bound of the wide neighborhood algorithms for solving second-order cone programming.(4) In the fourth chapter, a smoothing function corresponding to second-order cone is given, and its properties are studied. Based on the smoothing function, a smooth-ing Newton-type method is proposed for solving second-order cone programming. The method reformulates the perturbed optimality conditions into a system of linear equa-tions to solve. Its results are stronger than corresponding interior-point methods, and its initial point is arbitrary. At each iteration, the proposed algorithm need only to solve one system of linear equations and perform one line search. The sequence gen-erated by the method converges globally and Q-quadratically to the solution of the SOCP under a mild assumption, without strict complementarity condition.(5) A globally convergent non-interior point algorithm with full Newton step for second-order cone programming is proposed in the fifth part. The main idea of the algorithm is that we cast the complementary equation of the primal-dual optimality conditions as a projection equation. This algorithm can start from an arbitrary point. Without performing any line search, we only need to solve a system of linear equa-tions with the same coefficient matrix and compute two simple projections at each iteration. It does not require the row vectors of coefficient matrix of constraints to be linearly independent. The proposed algorithm is globally convergent without strict complementarity conditions.(6) In the sixth part, we study the special second-order cone programming-nonlinear complementarity problem with P0-function. Based on a new smoothing func-tion with penalty, the problem is approximated by a family of parameterized smooth equations and a new non-interior-point continuation method is presented. At each it-eration, the proposed algorithm only need to solve one system of linear equations and perform one Armijo-type line search. The algorithm is proved to be globally and locally superlinearly convergent without strict complementarity. Moreover, the quadratic con-vergence rate is achieved under mild conditions. Numerical experiments demonstrate the feasibility and efficiency of the proposed algorithm.(7) In chapter seven, we introduce a class of one-parametric smoothing second-order cone complementarity functions. Under suitable assumptions, we prove that these functions are coercive. Based on this class of one-parametric smoothing functions, a smoothing Newton method is proposed to solve the monotone second-order cone complementarity problems. It is proved that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Preliminary numerical results for randomly generated second-order cone programs are reported, which confirm the favorable theoretical properties of the method.Finally, based on the problems of the existing methods, including the methods proposed in the thesis, the last chapter is concerned with some future research work.更多还原