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

interior point methods in the year 2025

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2025年 13卷

作者： Gondzio, Jacek Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Scotland Univ Edinburgh Maxwell Inst Math Sci Peter Guthrie Tait Rd Edinburgh EH9 3FD Scotland

interior point methods (IPMs) have hugely influenced the field of optimization. Their fast development has been triggered by the seminal paper of Narendra Karmarkar published in 1984 which delivered a polynomial algorithm for linear programming and suggested that it might be implemented into a very efficient method in practice. Indeed, this has been demonstrated within a few years after 1984 and has gained IPMs a status of exceptionally powerful optimization tool. linear programming (LP) is at the centre of many operational research techniques including mixed-integer programming, network optimization and various decomposition techniques. Therefore, any progress in LP has far-reaching consequences. IPMs certainly did not disappoint in this context: they have become a heavily used methodology in modern optimization and operational research. Their accuracy, efficiency and reliability have been particularly appreciated when IPMs are applied to truly large scale problems which challenge any alternative approaches. In this survey we will discuss several issues related to interior point methods. We will recall techniques which provide the building blocks of IPMs, and observe that actually at least some of them have been developed before 1984. We will briefly comment on the worst-case complexity results for different variants of IPMs and then focus on key aspects of their implementation. We will also address some of the most spectacular features of IPMs and discuss their potential advantages when applied in decomposition algorithms, cutting planes scheme and column generation technique.

关键词： interior point methods linear programming Conic programming theory and computational perspective History and future developments

来源：评论

学校读者我要写书评

暂无评论

Efficient Implementation of interior-point methods for Quantum Relative Entropy

引用

INFORMS JOURNAL ON COMPUTING 2025年第1期37卷 1-196, C2页

作者： Karimi, Mehdi Tuncel, Levent Illinois State Univ Dept Math Normal IL 61761 USA Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Quantum relative entropy (QRE) programming is a recently popular and challenging class of convex optimization problems with significant applications in quantum computing and quantum information theory. We are interested in modern interior-point (IP) methods based on optimal self-concordant barriers for the QRE cone. A range of theoretical and numerical challenges associated with such barrier functions and the QRE cones have hindered the scalability of IP methods. To address these challenges, we propose a series of numerical and linear algebraic techniques and heuristics aimed at enhancing the efficiency of gradient and Hessian computations for the self-concordant barrier function, solving linear systems, and performing matrix-vector products. We also introduce and deliberate about some interesting concepts related to QRE such as symmetric quantum relative entropy. We design a two-phase method for performing facial reduction that can significantly improve the performance of QRE programming. Our new techniques have been implemented in the latest version (DDS 2.2) of the software package Domain-Driven Solver (DDS). In addition to handling QRE constraints, DDS accepts any combination of several other conic and nonconic convex constraints. Our comprehensive numerical experiments encompass several parts, including (1) a comparison of DDS 2.2 with Hypatia for the nearest correlation matrix problem, (2) using DDS 2.2 for combining QRE constraints with various other constraint types, and (3) calculating the key rate for quantum key distribution (QKD) channels and presenting results for several QKD protocols.

关键词： quantum computing quantum relative entropy convex optimization interior-point methods optimization software

来源：评论

学校读者我要写书评

暂无评论

A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2023年第3期31卷 691-711页

作者： E-Nagy, Marianna Varga, Anita Budapest Univ Technol & Econ Inst Math Dept Differential Equat Muegyet Rkp 3 H-1111 Budapest Hungary Corvinus Univ Budapest Corvinus Ctr Operat Res Fovam Ter 8 H-1093 Budapest Hungary

In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.

关键词： Mathematical programming linear optimization interior point algorithms Algebraic equivalent transformation technique

来源：评论

学校读者我要写书评

暂无评论

A New Ai-Zhang Type interior point Algorithm for Sufficient linear Complementarity Problems

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2024年第1期202卷 76-107页

作者： E-Nagy, Marianna Varga, Anita Corvinus Univ Budapest Corvinus Ctr Operat Res F spacing diaeresis ovam ter 8 Fovam Ter 8 H-1093 Budapest Hungary Budapest Univ Technol & Econ Dept Differential Equat Inst Math Muegyet Rkp 3 H-1111 Budapest Hungary

In this paper, we propose a new long-step interior point method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interior point algorithm introduced by Ai and Zhang and the algebraic equivalent transformation technique proposed by Darvay. Similar to the method of Ai and Zhang, our algorithm also works in a wide neighborhood of the central path and has the best known iteration complexity of short-step variants. However, due to the properties of the applied transforming function in Darvay's technique, the wide neighborhood definition in the analysis depends on the value of the handicap. We implemented not only the theoretical algorithm but a greedy variant of the new method (working in a neighborhood independent of the handicap) in MATLAB and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai-Zhang type methods.

关键词： Mathematical programming linear complementarity problems interior point algorithms Algebraic equivalent transformation technique

来源：评论

学校读者我要写书评

暂无评论

Proximal Stabilized interior point methods and Low-Frequency-Update Preconditioning Techniques

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2023年第3期197卷 1061-1103页

作者： Cipolla, Stefano Gondzio, Jacek Univ Edinburgh Sch Math Edinburgh Scotland

In this work, in the context of linear and convex Quadratic programming, we consider Primal Dual Regularized interior point methods (PDR-IPMs) in the framework of the Proximal point Method. The resulting Proximal Stabilized IPM (PS-IPM) is strongly supported by theoretical results concerning convergence and the rate of convergence, and can handle degenerate problems. Moreover, in the second part of this work, we analyse the interactions between the regularization parameters and the computational footprint of the linear algebra routines used to solve the Newton linear systems. In particular, when these systems are solved using an iterative Krylov method, we are able to show-using a new rearrangement of the Schur complement which exploits regularization-that general purposes preconditioners remain attractive for a series of subsequent IPM iterations. Indeed, if on the one hand a series of theoretical results underpin the fact that the approach here presented allows a better re-use of such computed preconditioners, on the other, we show experimentally that such (re)computations are needed only in a fraction of the total IPM iterations. The resulting regularized second order methods, for which low-frequency-update of the preconditioners are allowed, pave the path for an alternative class of second order methods characterized by reduced computational effort.

关键词： interior point methods Proximal point methods Regularized primal-dual methods Convex quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Faster Randomized interior point methods for Tall/Wide linear Programs*

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2022年第1期23卷 1-48页

作者： Chowdhury, Agniva Dexter, Gregory London, Palma Avron, Haim Drineas, Petros Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37830 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Cornell Univ Operat Res & Informat Engn Ithaca NY 14853 USA Tel Aviv Univ Sch Math Sci Tel Aviv Israel

linear programming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineer-ing, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as L1-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. interior point methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider both feasible and infeasible IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized linear Algebra, we present a preconditioning technique that, when combined with the it-erative solvers such as Conjugate Gradient or Chebyshev Iteration, provably guarantees that IPM algorithms (suitably modified to account for the error incurred by the approx-imate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data.

关键词： Randomized linear Algebra linear programming interior point methods

来源：评论

学校读者我要写书评

暂无评论

Accelerating Condensed interior-point methods on SIMD/GPU Architectures

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2024年第1期202卷 184-203页

作者： Pacaud, Francois Shin, Sungho Schanen, Michel Maldonado, Daniel Adrian Anitescu, Mihai Argonne Natl Lab Lemont IL 60439 USA

The interior-point method (IPM) has become the workhorse method for nonlinear programming. The performance of IPM is directly related to the linear solver employed to factorize the Karush-Kuhn-Tucker (KKT) system at each iteration of the algorithm. When solving large-scale nonlinear problems, state-of-the art IPM solvers rely on efficient sparse linear solvers to solve the KKT system. Instead, we propose a novel reduced-space IPM algorithm that condenses the KKT system into a dense matrix whose size is proportional to the number of degrees of freedom in the problem. Depending on where the reduction occurs, we derive two variants of the reduced-space method: linearize-then-reduce and reduce-then-linearize. We adapt their workflow so that the vast majority of computations are accelerated on GPUs. We provide extensive numerical results on the optimal power flow problem, comparing our GPU-accelerated reduced-space IPM with Knitro and a hybrid full-space IPM algorithm. By evaluating the derivatives on the GPU and solving the KKT system on the CPU, the hybrid solution is already significantly faster than the CPU-only solutions. The two reduced-space algorithms go one step further by solving the KKT system entirely on the GPU. As expected, the performance of the two reduction algorithms depends critically on the number of available degrees of freedom: They underperform the full-space method when the problem has many degrees of freedom, but the two algorithms are up to three times faster than Knitro as soon as the relative number of degrees of freedom becomes smaller.

关键词： Nonlinear programming

来源：评论

学校读者我要写书评

暂无评论

Domain-Driven Solver (DDS) Version 2.1: a MATLAB-based software package for convex optimization problems in domain-driven form

引用

MATHEMATICAL programming COMPUTATION 2024年第1期16卷 37-92页

作者： Karimi, Mehdi Tuncel, Levent Illinois State Univ Dept Math Normal IL 61761 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Domain-Driven Solver (DDS) is a MATLAB-based software package for convex optimization. The current version of DDS accepts every combination of the following function/set constraints: (1) symmetric cones (LP, SOCP, and SDP);(2) quadratic constraints that are SOCP representable;(3) direct sums of an arbitrary collection of 2-dimensional convex sets defined as the epigraphs of univariate convex functions (including as special cases geometric programming and entropy programming);(4) generalized Koecher (power) cone;(5) epigraphs of matrix norms (including as a special case minimization of nuclear norm over a linear subspace);(6) vector relative entropy;(7) epigraphs of quantum entropy and quantum relative entropy;and (8) constraints involving hyperbolic polynomials. The infeasible-start primal-dual algorithms used for DDS rely heavily on duality theory and properties of Legendre-Fenchel conjugate functions, and are designed to rigorously determine the status of a given problem. We discuss some important implementation details and techniques we used to improve the robustness and efficiency of the software. The appendix contains many examples.

关键词： Convex optimization Software package Self-concordant functions interior-point methods Primal-dual algorithms Duality theory

来源：评论

学校读者我要写书评

暂无评论

An interior point-Proximal Method of Multipliers for linear Positive Semi-Definite programming

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2022年第1期192卷 97-129页

作者： Pougkakiotis, Spyridon Gondzio, Jacek Univ Edinburgh Edinburgh Midlothian Scotland

In this paper we generalize the interior point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307-351, 2021. https://***/10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible interior point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.

关键词： Regularized interior point methods Semidefinite programming Proximal method of multipliers interior point Method Proximal point method

来源：评论

学校读者我要写书评

暂无评论

Hybrid Method for linear programming 15th

Hybrid Method for Linear Programming

引用

15th International Conference on Optimization and Applications, OPTIMA 2024

作者： Pirau, Vitali Hildebrand, Roland Institutskiy per. 9 Moscow Region Dolgoprudny141701 Russia Skolkovo Institute of Science and Technology Skolkovo Innovation Center Bolshoy Boulevard 30 P.1 Moscow121205 Russia

ISBN: (纸本)9783031791185

We propose a new approach to solving linear programs which combines the advantages of interior point methods and active set methods. methods of the first type, in particular the Nesterov-Todd interior-point method for self-concordant barriers [8] solve the problem in polynomial time, running Onlog1Ε iterations, however, it can be shown that it converges to accuracy ΕM when implemented on machines with ΕM accuracy, which is unacceptable for some practical problems, such as bank scheduling [14]. On the other hand, the simplex method [4] avoids the argument accuracy problem, since its trajectory traverses only the vertices of the feasible polyhedron. However, the simplex method is known to spend at worst exponential time to find the answer, and in practice the interior point method runs much faster and is preferred. The approach proposed in this paper is a hybrid algorithm which generates iterations as in an interior point method, but at some steps it additionally analytically solves an auxiliary minimization problem on a cone approximating the orthant with marginal additional cost. This allows us to find exactly-zero solution components and lower the dimensionality of the problem. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：