二阶锥规划的内点算法研究

发布时间：2018-05-24 02:55

本文选题：二阶锥规划 + 核函数　；参考：《内蒙古大学》2017年硕士论文

【摘要】：二阶锥规划(SOCP)是一类基于仿射集和有限个二阶锥的笛卡尔乘积的交集上极大化或极小化一个线性函数的凸优化问题.它作为线性规划(LP)的推广及半正定规划(SDP)的特例,有着广泛的应用.为此,许多数学规划问题都通过转化成二阶锥规划进行求解.本文主要讨论二阶锥规划的数值解法—原始-对偶内点算法,具体包括以下几部分内容:第一章:二阶锥规划简介及研究进展.第二章:提出一个新的二次核函数,并分析该函数的性质,进而基于该函数给出二阶锥规划的原始-对偶内点算法.通过探讨算法的复杂性,求出基于该二次核函数的大步校正法的理论迭代界为O(O(r3/4logr/ε),此迭代界略好于基于对数障碍函数的理论迭代界O(rlogr/ε).此外,我们通过数值实验表明了本章算法是可行有效的.第三章:用对数核函数φ(t)=(t2-1)/2-log(t)及核函数φ(t)=1/2(t-1/t)~2的凸组合,构造了另一个新核函数.在证明了该核函数的性质的基础上给出了二阶锥规划的原始-对偶内点算法.通过研究算法的复杂性,求出了基于该凸组合核函数的大步校正算法的理论迭代界为O(r2/3logr/ε),该界与基于核函数φ(t)=1/2(t-1/t)2的理论迭代界一致.第四章:对本文的总结.
[Abstract]:Second order cone programming (SOCP) is a convex optimization problem in which a linear function is maximized or minimized on the intersection of affine sets and finite second order cones. It is widely used as a special case of linear programming (LP) and positive semidefinite programming (SDP). For this reason, many mathematical programming problems are solved by transforming them into second-order cone programming. In this paper, we mainly discuss the numerical solution of second-order cone programming, primal-dual interior point algorithm, including the following parts: chapter 1: introduction and research progress of second-order cone programming. Chapter 2: a new quadratic kernel function is proposed, and the properties of the function are analyzed. Based on this function, a primal-dual interior point algorithm for second-order cone programming is presented. By discussing the complexity of the algorithm, the theoretical iteration bound of the giant step correction method based on the quadratic kernel function is found to be O(O(r3/4logr/ 蔚, which is slightly better than the theoretical iteration bound O(rlogr/ 蔚 n based on logarithmic barrier function. In addition, numerical experiments show that the algorithm is feasible and effective. In Chapter 3, another new kernel function is constructed by using the convex combination of the logarithmic kernel function 蠁 t ~ (2) ~ (1 / 2) and the kernel function 蠁 ~ (t) ~ (1 / 2) / t ~ (1 / 1) ~ (2). On the basis of proving the properties of the kernel function, the primal-dual interior point algorithm for second-order cone programming is given. By studying the complexity of the algorithm, the theoretical iteration bound of the giant step correction algorithm based on the convex combined kernel function is obtained, which is consistent with the theoretical iteration bound based on the kernel function 蠁 / t / 2 / t ~ (-1) / t ~ (2). Chapter four: summary of this paper.
【学位授予单位】：内蒙古大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221

【相似文献】