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

Elliptic cone optimization and primal-dual path-following algorithms

OPTIMIZATION 2017年第12期66卷 2245-2274页

作者： Alzalg, Baha Pirhaji, Mohammad Univ Jordan Dept Math Amman Jordan Shahrekord Univ Dept Appl Math Shahrekord Iran

In elliptic cone optimization problems, we minimize a linear objective function over the intersection of an affine linearmanifoldwith the Cartesian product of the so-called elliptic cones. We present some general classes of optimization problems that can be cast as elliptic cone programmes such as second-order cone programmes and circular cone programmes. We also describe some real-world applications of this class of optimization problems. We study and analyse the Jordan algebraic structure of the elliptic cones. Then, we present a glimpse of the duality theory associated with elliptic cone optimization. A primal-dual path-following interior-point algorithm is derived for elliptic cone optimization problems. We prove the polynomial convergence of the proposed algorithms by showing that the logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are efficient.

关键词： Conic optimization elliptic cone optimization duality primal-dual path-following methods optimization models

来源：评论

学校读者我要写书评

暂无评论

An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners

引用

OPTIMIZATION methods & SOFTWARE 2009年第1期24卷 123-143页

作者： Lu, Zhaosong Monteiro, Renato D. C. O'Neal, Jerome W. Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

In this paper, we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors' previous paper [Z. Lu. R.D.C. Monteiro, and J.W. O'Neal, An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming. SIAM J. Optim. 17(1) (2006). pp. 287-310], we propose a new linear system, which we refer to as the hybrid augmented normal equation (HANE), to determine the primal-dual search directions. Since the iterative linear solver can only generate an approximate solution to the HANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a recipe to compute an inexact primal-dual search direction, based on a Suitable approximate solution to the HANE. The second difference between this paper and [Z. Lu, R.D.C. Monteiro. and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming. SIAM J. Optim. 17 (1)(2006), pp. 287-310] is that, instead of using the maximum weight basis (MWB) preconditioner in the aforesaid recipe for constructing the inexact search direction. this paper proposes the use of any member of a whole class of preconditioners. of which the MWB preconditioner is just a special case. The proposed recipe allows us to: (i) establish a polynomial bound on the number of iterations performed by our path-following algorithm and (ii) establish a uniform bound, depending on the quality of the preconditioner. on the number of iterations performed by the iterative solver.

关键词： convex quadratic programming iterative linear solver primal-dual path-following methods interior-point methods hybrid augmented normal equation inexact search directions polynomial convergence

来源：评论

学校读者我要写书评

暂无评论

An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming

引用

SIAM JOURNAL ON OPTIMIZATION 2006年第1期17卷 287-310页

作者： Lu, Zhaosong Monteiro, Renato D. C. O'Neal, Jerome W. Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Delta Technol Res Modelling & Design Grp Dept 709 Atlanta GA 30354 USA

In this paper we develop a long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. We propose a new linear system, which we refer to as the augmented normal equation (ANE), to determine the primal-dual search directions. Since the condition number of the ANE coefficient matrix may become large for degenerate CQP problems, we use a maximum weight basis preconditioner introduced in [ A. R. L. Oliveira and D. C. Sorensen, Linear Algebra Appl., 394 ( 2005), pp. 1 - 24;M. G. C. Resende and G. Veiga, SIAM J. Optim., 3 ( 1993), pp. 516 - 537;P. Vaida, Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners, Tech. report, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, 1990] to precondition this matrix. Using a result obtained in [ R. D. C. Monteiro, J. W. O'Neal, and T. Tsuchiya, SIAM J. Optim., 15 ( 2004), pp. 96 - 100], we establish a uniform bound, depending only on the CQP data, for the number of iterations needed by the iterative linear solver to obtain a sufficiently accurate solution to the ANE. Since the iterative linear solver can generate only an approximate solution to the ANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a way to compute an inexact primal-dual search direction so that the equation corresponding to the primal residual is satisfied exactly, while the one corresponding to the dual residual contains a manageable error which allows us to establish a polynomial bound on the number of iterations of our method.

关键词： convex quadratic programming iterative linear solver maximum weight basis preconditioner primal-dual path-following methods interior-point methods augmented normal equation inexact search directions polynomial convergence

来源：评论

学校读者我要写书评

暂无评论

A new primal-dual path-following method for convex quadratic programming

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2006年第1期25卷 97-110页

作者： Achache, Mohamed Univ Ferhat Abbas Dept Math Fac Sci Setif 19000 Algeria

In this paper, we describe a new primal-dual path-following method to solve a convex quadratic program (QP). The derived algorithm is based on new techniques for finding a new class of search directions similar to the ones developed in a recent paper by Darvay for linear programs. We prove that the short-update algorithm finds an epsilon-solution of (QP) in a polynomial time.

关键词： convex quadratic programming interior point methods primal-dual path-following methods convergence of algorithms

来源：评论

学校读者我要写书评

暂无评论

A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming

引用

OPTIMIZATION methods & SOFTWARE 1999年第1-4期11-2卷 141-182页

作者： Tsuchiya, T Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we study primal-dual path-following algorithms for second-order cone programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP and SDP to SOCP, and prove that the long-step algorithm using the NT direction and the HRVW/KSH/M direction have O(n log epsilon(-1)) iteration-complexity and O(n(3/2) log epsilon(-1)) iteration-complexity, respectively, to reduce the duality gap by a factor of 1/epsilon, where n is the number of the second-order cones. We also show that the short and semilong-step algorithms using the NT direction and the HRVW/KSH/M direction have O(root n log epsilon(-1)) and O(n log epsilon(-1)) iteration-complexities, respectively.

关键词： second-order cone programming interior-point methods polynomial-time algorithms primal-dual path-following methods Euclidean Jordan algebra homogeneous and self-dual cone programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：