【作者】 曾友芳；

【导师】 简金宝；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2011， 博士

【摘要】 二阶锥规划是在有限个二阶锥的笛卡儿乘积与仿射子空间的交集上求一个线性目标函数的最小值问题二阶锥规划是锥规划的一个分支，它既是线性规划的推广，又是半定规划的特例，是一种具有优美结构的对称锥规划这类规划应用广泛，比如在设施选址、图论控制优化、天线阵列设计、投资组合问题等方面以及金融、工程设计、数字信号处理、声学、力学、民航、电气等领域都有所应用因此，研究二阶锥规划问题的理论和算法具有重要的理论意义和应用价值二阶锥规划问题的研究起源于17世纪，但直至最近十几年才进入活跃阶段，2fJfJ3年有了对其理论和算法研究的阶段性综述文章对二阶锥规划的算法研究主要分为内点法和非内点法两大类原始一对偶内点法是一类重要的内点法，包含“可行内点法”和"不可行内点法”两种，前者的初始点和迭代点均要求可行，后者的初始点和迭代点只需满足二阶锥约束可行内点法主要有原始一对偶路径跟踪算法，基于核函数的原始一对偶内点算法等不可行内点法常见的有不可行内点预估一校正算法，非精确不可行内点算法等非内点法主要有光滑牛顿法，非内点f内部)连续化方法，序列二次规划法等在较全面了解二阶锥规划研究背景和研究进展的基础上，本文对二阶锥规划的理论和算法进行了深入的研究，并取得如下主要成果：l在12完善了综述性文章中若当代数性质一个重要定理的证明(见定理l 2 3)，提出并证明了若当代数理论的三个新定理f见定理l 2 6一定理l 2 8)2详细分析了2维f每个二阶锥约束都是2维的情形)二阶锥规划转化为线性规划的过程，给出相关的重要性质，并提出了求解2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法，举例说明了算法的有效性并进行了灵敏度分析3基于不可行内点法的优点和预估一校正算法的思想，建立了两个新的求解二阶锥规划的预估一校正算法其预估方向分别是Newton方向和Euler方向，校正方向属于Alizadeh—Haeberly一0verton㈦H0)方向的范畴算法的优点是对于初始内点和迭代内点可行或不可行的情形都适用主要创新点是构造了一个更简单的中心路径的邻域，这不仅与最优性条件切合，而且由此构造的两个新算法能处理较大规模的问题在一些假设条件下，算法具有全局收敛性、线性和二次收敛速度，并获得了0(rln(s。e))的迭代复杂性界，其中r表示二阶锥规划问题所包含的二阶锥约束的个数数值实验结果表明提出的这两个算法是有效的4分别提出了非光滑向量值Fische r_BurmeisterfFB)函数和向量值最小函数的两个新光滑函数，并基于此建立了两个求解二阶锥规划的非内点连续化算法它们的共同优点是：初始点可任取；每次迭代只需求解一个线性方程组得到搜索方向，进行一次线搜索得到步长；在无严格互补假设下，得到算法的全局收敛性和强收敛性而且，证明了基于非光滑FB函数的光滑化算法还具有二次收敛性，并能很好地求解较大规模问题，同时证明了基于向量值最小函数的非内部连续化算法还获得超线性收敛性全文结构如下：第一章对国内外的研究主流和发展现状进行追踪和系统分类描述，并且建立了三个有关若当代数的新定理；第二章提出2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法并进行了灵敏度分析；第三章建立二阶锥规划两个新的预估一校正算法，它们对初始点和迭代点可行或不可行的情况都适用；第四章基于非光滑FB函数的一个新光滑函数建立了光滑化算法，并进行较大规模的数值实验；第五章提出向量值最小函数的一个新光滑函数并基于此建立了具有超线性收敛性的非内部连续化算法；第六章总结全文内容并展望进一步的研究工作更多还原

【Abstract】 Second-order cone programming (SOCP) problem minimizes a linear function overthe intersection of an a?ne linear manifold with the Cartesian product of second-ordercones. It is a branch of conic programming. SOCP , which has pretty framework, isthe generalized linear programming (LP), and also a special case of semi-definite pro-gramming (SDP). SOCP problems have broad application in real world, such as facilitylocation, grasping force optimization, antenna array design, portfolio investment, andin the areas of finance, engineering design, digital signal disposal, acoustics, mechan-ics, civil aviation, electrical engineering, and so on. Therefore, research on theory andalgorithms for SOCP has an important academic significance and applying value.The study of SOCP began from 17 century and has been active in ten years recently.There was a survey in 2003. The interior-point algorithms and the non-interior-pointalgorithms are the main methods for solving SOCP. The primal-dual interior-point al-gorithms are familiar interior-point algorithms, which include“feasible interior-pointmethod”and“infeasible interior-point method”. The initial point and the iterativepoints are required feasible in feasible interior-point methods. However, The initialpoint and the iterative points are only required feasible in second-order cones in in-feasible interior-point methods. The feasible interior-point methods own primal-dualpath-following algorithms, primal-dual interior-point algorithms based on a class of ker-nel functions, etc. There are some main infeasible interior-point methods, such as in-feasible interior-point predictor-corrector algorithms, inexact infeasible interior-pointalgorithms, and so forth. The non-interior-point algorithms have smoothing Newtonmethods, non-interior-point continuous algorithms, sequential quadratic programming(SQP) algorithms, etc.In this thesis, we study theory and algorithms for SOCP. The main results of thethesis are stated as follows.We improve the proof of one important theorem proposed by Alizadeh F. andGoldfarb D. in detail (see Theorem 1.2.3). Further, we present three new results ofJordan algebra (see Theorems 1.2.6-1.2.8).We study two-dimensional SOCP. Every second-order cone in this kind of SOCP is two-dimensional. We present a dual simplex method and a primal-dual simplex methodfor two-dimensional SOCP. First, two-dimensional SOCP can be reformulated as LP.And then, we prove some important conclusions in detail. Finally, we show the e?ec-tiveness of the proposed methods by several examples, and sensitivity analysis are madetoo.Based on the ideas of infeasible interior-point methods and predictor-correctoralgorithms, two predictor-corrector algorithms for SOCP are presented. We use theNewton direction and the Euler direction as the predictor directions, respectively. Thecorrector directions belong to the category of the Alizadeh-Haeberly-Overton (AHO)directions. These algorithms are suitable to the cases of feasible and infeasible interioriterative points. A simpler neighborhood of the central path for the SOCP is proposed,which is the pivotal di?erence from other interior-point predictor-corrector algorithms.Under some assumptions, the algorithms possess the global, linear, and quadratic con-vergence. The complexity bound O(rln(ε0/ε)) is obtained, where r denotes the numberof the second-order cones in the SOCP problem. The numerical results show that theproposed algorithms are e?ective.We give two di?erent new smoothing functions of the well-known nonsmoothFischer-Burmeister (FB) function and the vector-valued min-function, respectively. Bas-ing on the new smoothing functions, we present two non-interior-point continuous al-gorithms for SOCP problems. The features of the two algorithms are as follows: first,the starting point can be chosen arbitrarily; second, at each iteration, only one sys-tem of linear equations and one line search are performed; finally, global and strongconvergence are obtained without assumption of strict complementarity. Furthermore,we show the smoothing Newton-type method has quadratic convergent rate and pos-sesses e?ective numerical results. And the non-interior-point continuous algorithm getssuperlinear convergence.The thesis is organized as follows. In Chapter 1, we introduce the background,the preliminaries for SOCP problems and present three new results of Jordan algebra.Then, we propose a dual simplex method and a primal-dual simplex method for two-dimensional SOCP and make sensitivity analysis in Chapter 2. In Chapter 3, two newpredictor-corrector algorithms for SOCP are presented, which are suitable to the casesof feasible and infeasible initial point and iterative points. In Chapter 4, we propose a new smoothing algorithm for SOCP basing on a new smoothing function of non-smoothFB function. Some large-scale test problems have been done too. In Chapter 5, basedon a new smoothing function of the vector-valued min-function, a new non-interior-pointcontinuous algorithm with superlinear convergence is presented for SOCP. Finally, thesummary and prospect are listed in Chapter 6.更多还原