检索结果-内蒙古大学图书馆

A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization

OPTIMIZATION 2019年第12期68卷 2243-2263页

作者： Kheirfam, B. Azarbaijan Shahid Madani Univ Dept Appl Math Tabriz Iran

In this paper, we present a wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization. We define a new wide neighbourhood , which is an extension of the Darvay-Takacs's wide neighbourhood for linear optimization to semidefinite optimization. We use an algebraic reformulation of the centering equation along with Zhang's symmetrization operator to create symmetric search directions. After applying Newton's method to the resulting system, we recommend using the square root function for simplicity. We consider the Newton direction as the sum of two other directions, corresponding to the negative and positive parts of the right-hand side of the centring equation. Starting with a feasible point , we prove that our algorithm has complexity the same as small neighbourhood path-following algorithms for semidefinite optimization that use the Nesterov-Todd directions. To the best of our knowledge, this is the first large neighbourhood path-following interior-point algorithm that uses a different neighbourhood from those available for semidefinite optimization.

关键词： Semidefinite optimization wide neighbourhood interior-point method iteration complexity bound

来源：评论

学校读者我要写书评

暂无评论

A Wide Neighborhood Second-order Predictor-corrector Interior-point Algorithm for Semidefinite Optimization with Modified Corrector Directions

引用

FUNDAMENTA INFORMATICAE 2017年第4期153卷 327-346页

作者： Kheirfam, Behrouz Mohamadi-Sangachin, Mohaddeseh Azarbaijan Shahid Madani Univ Dept Appl Math Tabriz Iran

In this paper, we present a new second-order predictor-corrector interior-point method for semidefinite optimization. The algorithm is based on the wide neighborhood of the central path and modified corrector directions. In the corrector step, we derive the step size and corrector directions which guarantee that new iterate lies in the wide neighborhood. The iteration complexity bound is O (root nlog X-0 center dot S-0/is an element of) for the Nesterov-Todd direction, which coincides with the best known complexity results for semidefinite optimization. Some numerical results are provided as well.

关键词： Semidefinite optimization predictor-corrector interior-point method wide neighborhood second-order methods iteration complexity bound

来源：评论

学校读者我要写书评

暂无评论

PRIMAL-DUAL INTERIOR-POINT ALGORITHM FOR LO BASED ON A NEW KERNEL FUNCTION

ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS

引用

ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2016年第36期36卷 319-334页

作者： Li, Xin Zhang, Mingwang Ji, Ping China Three Gorges Univ Coll Sci Yi Chang 443002 Peoples R China

Based on a new kernel function, a large-update primal-dual interior-point algorithm for solving linear optimization is proposed. The kernel function is used both for determining the search directions and for measuring the distance between the given iterate and the mu-center for the algorithm. By using several new technical lemmas, the iteration complexity bound as O(root n log n log n/epsilon) is obtained, which coincides with the currently best iteration complexity bounds for large-update methods. In addition, we present some preliminary numerical results.

关键词： linear optimization kernel function primal-dual interior-point algorithm large-update methods iteration complexity bound

来源：评论

学校读者我要写书评

暂无评论

A new O(√nL)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2014年 256卷 65-76页

作者： Feng, Zengzhe Fang, Liang Beijing Jiaotong Univ Sch Traff & Transportat Beijing 100044 Peoples R China Taishan Med Univ Coll Informat Engn Tai An 271016 Shandong Peoples R China Taishan Univ Coll Math & Stat Tai An 271021 Shandong Peoples R China

In this paper, we extend the Ai-Zhang predictor-corrector method to the class of semidefinite programming. First, we define a new wide neighborhood N(tau, beta). Another key ingredient of our method is that we treat the classical Newton direction as the sum of two other directions, corresponding to respectively the negative part and the positive part of the right-hand-side. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of 1 - 1/O(root nL). Then the method enjoys the low iteration bound of O(root nL), which is better than that of usual wide neighborhood algorithm O(nL), where n is the dimension of the problem and L = (x(0))(T).S-0/epsilon with E the required precision and (X-0, y(0), S-0) the initial interior solution. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Semidefinite programming Predictor-corrector algorithm iteration complexity bound Wide neighborhood

来源：评论

学校读者我要写书评

暂无评论

An [...] iteration primal-dual path-following method, based on wide neighbourhood and large update, for second-order cone programming

引用

Optimization 2014年第5期63卷 679页

作者： Feng, Zeng Zhe Fang, Liang He, Guoping [a] College of Information Engineering Taishan Medical University 271016 Tai'an China [b] Department of Mathematics and System Science Taishan University 271021 Tai'an China [c] College of Information Science and Engineering Shandong University of Science and Technology 266510 Qingdao China

This article proposes a new primal-dual path-following interior point algorithm for second-order cone programming. Each iterate always follows the usual wide neighborhood ..., it does not necessarily stay within it, but must stay within the wider neighbourhood ...(t, β). This paper shows that the algorithm has ... iteration complexity bound which is better than that of usual wide neighbourhood algorithm O(n log ...), where n is the dimension of the problem, ... with ... the required precision, α ... [0, 1] the given constant number and (x ..., s ...) the initial interior solution. It is the best result in regard to the iteration complexity bound in the context of path-following method for second-order cone programming. (ProQuest: ... denotes formulae/symbols omitted.)

关键词： second-order cone programming path-following interior-point method wide neighbourhood iteration complexity bound 65K05 90C22 90C51

来源：评论

学校读者我要写书评

暂无评论

A NEW O(√nL) iteration LARGE-UPDATE PRIMAL-DUAL INTERIOR-POINT METHOD FOR SECOND-ORDER CONE PROGRAMMING

引用

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION 2012年第4期33卷 397-414页

作者： Feng, Zengzhe Taishan Med Univ Coll Informat & Engn Tai An 271016 Shandong Peoples R China

In this article, we extend the Ai-Zhang direction for solving LCP to the class of second-order cone programming. Each iterate always follows the usual wide neighborhood N-infinity(-), not necessarily staying within it, but must stay within the wider neighborhood N (beta, tau). In addition, we decompose the classical Newton direction into two separate parts according to the positive and negative parts. We show that the algorithm has O(root nL) iteration complexity bound, where n is the dimension of the problem and L = (X-0)(T) S-0/epsilon with epsilon the required precision and (X-0, S-0) the initial interior solution. To the best of our knowledge, this is the first large-neighborhood path-following interior point method (IPMs) with the same complexity as small neighborhood path-following IPMs for second-order cone programming. It is the best result in regard to the iteration complexity bound in the context of the large-update path-following method for second-order cone programming.

关键词： Interior-point method iteration complexity bound Primal-dual path following method Second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

A New iteration Large-Update Primal-Dual Interior-Point Method for Second-Order Cone Programming

引用

Numerical Functional Analysis & Optimization 2012年第4期33卷 397-414页

作者： Feng, Zengzhe fengzengzhe@*** College of Information and Engineering Taishan Medical University P. R. China

In this article, we extend the Ai-Zhang direction for solving LCP to the class of second-order cone programming. Each iterate always follows the usual wide neighborhood , not necessarily staying within it, but must stay within the wider neighborhood 𝒩(β, τ). In addition, we decompose the classical Newton direction into two separate parts according to the positive and negative parts. We show that the algorithm has iteration complexity bound, where n is the dimension of the problem and with ϵ the required precision and (X 0, S 0) the initial interior solution. To the best of our knowledge, this is the first large-neighborhood path-following interior point method (IPMs) with the same complexity as small neighborhood path-following IPMs for second-order cone programming. It is the best result in regard to the iteration complexity bound in the context of the large-update path-following method for second-order cone programming. [ABSTRACT FROM AUTHOR]

关键词： Interior-point method iteration complexity bound Primal-dual path following method Second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：