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

arXiv 2024年

作者： Chiu, Hong-Ming Zhang, Richard Y. University of Illinois Urbana-Champaign United States

We describe how the low-rank structure in an SDP can be exploited to reduce the per-iteration cost of a convex primal-dual interior-point method down to O(n3) time and O(n2) memory, even at very high accuracies. A traditional difficulty is the dense Newton subproblem at each iteration, which becomes progressively ill-conditioned as progress is made towards the solution. Preconditioners have been proposed to improve conditioning, but these can be expensive to set up, and fundamentally become ineffective at high accuracies, as the preconditioner itself becomes increasingly ill-conditioned. Instead, we present a well-conditioned reformulation of the Newton subproblem that is cheap to set up, and whose condition number is guaranteed to remain bounded over all iterations of the interior-point method. In theory, applying an inner iterative method to the reformulation reduces the per-iteration cost of the outer interior-point method to O(n3) time and O(n2) memory. We also present a well-conditioned preconditioner that theoretically increases the outer per-iteration cost to O(n3r3) time and O(n2r2) memory, where r is an upper-bound on the solution rank, but in practice greatly improves the convergence of the inner iterations. Copyright © 2024, The Authors. All rights reserved.

关键词： Iterative methods

来源：评论

学校读者我要写书评

暂无评论

2-norm Flow Diffusion in Near-linear Time 62

2-norm Flow Diffusion in Near-Linear Time

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chen, Li Peng, Richard Wang, Di Georgia Tech Atlanta GA 30332 USA Google Res Mountain View CA USA

ISBN: (纸本)9781665420556

Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an near-linear time randomized algorithm for the 2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.

关键词： graph algorithm flow diffusion near linear time nonnegative quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Primal-Dual interior-point methods for Domain-Driven Formulations

引用

MATHEMATICS OF OPERATIONS RESEARCH 2020年第2期45卷 591-621页

作者： Karimi, Mehdi Tuncel, Levent Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We study infeasible-start, primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as domain-driven formulations. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to domain-driven formulations. The complexity results are new for the infeasible-start setup used even in the case of linear programming. In addition to complexity results, our algorithms aim for expanding the applications of and software for interior-point methods to wider classes of problems beyond optimization over symmetric cones.

关键词： convex optimization interior-point methods primal-dual algorithms duality theory

来源：评论

学校读者我要写书评

暂无评论

Sums of Squares and Symmetric Polynomials

Sums of Squares and Symmetric Polynomials

引用

作者： Shankar, Isabelle University of California Berkeley

学位级别：Ph.D., Doctor of Philosophy

Real algebraic geometry has a long and beautiful history going back to the 1800s. It is the study of real polynomials using algebraic techniques. Convex optimization plays a key role in applied mathematics and engineering, studying the geometric structure of convex sets that arise in optimization problems. Representation theory allows us to understand, study, and exploit the symmetries that naturally arise in many mathematical problems. The work in this thesis lies in the intersection of these fields, studying the symmetries of geometric objects coming from convex algebraic geometry and optimization. In particular, we study the spectrahedra that arise in the theory of symmetric polynomials and sums of squares (SOS) polynomials. Much of this thesis is motivated by polynomial optimization. It is through this lens that we arrive at the study of semidefinite programming, the feasible region of which is called a spectrahedron. A common method for solving a semidefinite program (SDP) is via interior-point methods. interior-point algorithms cut out a path towards the optimal solution and taking the Zariski closure of this defines the central curve. In this thesis, we discuss the central curve in semidefinite programming, linear programming and quadratic programming. As our first contribution, we prove the degree of the central curve for a generic SDP is equal to the maximum likelihood (ML) degree of a statistical model formulated and discussed in [75]. As such the degree of the central curve of a generic SDP can be computed using complete quadrics [50, 53]. The study of sums of squares and invariant polynomials inevitably leads to the study of invariant semidefinite programs [32]. Such an SDP can be greatly simplified using symmetry reduction techniques. We explore the geometry of the spectrahedra that arise from the invariant SDPs when considering sums of squares and symmetric polynomials. The first spectrahedron we study is the symmetry-adapted PSD cone, denoted PSDNSn,

关键词： Polynomial optimization Semidefinite programming Symmetric functions Sums of Squares Spectrahedron Algebraic geometry Control theory

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT IMPLEMENTATION OF interior-point methods FOR QUANTUM RELATIVE ENTROPY

arXiv

引用

arXiv 2023年

作者： Karimi, Mehdi Tunçel, Levent Department of Mathematics Illinois State University NormalIL61761 United States Department of Combinatorics and Optimization Faculty of Mathematics University of Waterloo WaterlooONN2L 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 (SQRE). 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 DDS. In addition to handling QRE constraints, DDS accepts any combination of several other conic and non-conic 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. Copyright © 2023, The Authors. All rights reserved.

关键词： Quantum computers

来源：评论

学校读者我要写书评

暂无评论

Isogeometric form finding of membrane shells by optimised Airy stress function

引用

COMPUTER methods IN APPLIED MECHANICS AND ENGINEERING 2024年 426卷

作者： Chianese, Claudia Rosati, Luciano Marmo, Francesco Univ Naples Federico II Dept Struct Engn & Architecture Via Claudio 21 I-80125 Naples Italy

A two -stage form -finding procedure, based on Isogeometric Analysis (IgA), is proposed to determine the configuration of shells having a prescribed planar footprint so as to carry applied loads in a state of purely membrane stresses. The boundary -value problem of a membrane shell is described by Pucher's equation in terms of Airy stress function, external loads and shell mid -plane elevation. Within the IgA framework, the weak form of the problem is derived and the resulting integral equation is discretised by approximating the relevant fields as a linear combination of control point values and B -Spline basis functions. Taking external loads as input, control point values of the Airy potential are computed via a nonlinear programming (NLP) routine aimed at minimising the thrusts at edge supports while ensuring no -traction membrane stresses fulfilling the relevant boundary conditions. The corresponding shell form is then obtained in terms of control point heights based on the stress field computed at the previous stage. Compared to the traditional practice of manually prescribing the Airy stress function, incorporation of the proposed NLP routine into the present IgA-based form -finding procedure proves to be an effective and versatile tool to assist the designer in computing a suitable Airy stress field able to account for usual static as well as user -defined functional constraints, regardless of the domain geometry complexity. Two numerical examples substantiate the presented approach.

关键词： Form finding Isogeometric analysis Membrane shells Pucher's theory Single-objective optimisation

来源：评论

学校读者我要写书评

暂无评论

Trust-Region Solver of a Nonlinear Magnetometer Disturbance Estimation Problem

引用

IEEE SENSORS JOURNAL 2021年第20期21卷 22569-22577页

作者： Wu, Jin Li, Chong Zhang, Chengxi Jiang, Yi Huang, Yulong Wang, Lujia Liu, Ming Hong Kong Univ Sci & Technol Dept Elect & Comp Engn Hong Kong Peoples R China Ocean Univ China Dept Automat & Measurement Qingdao 266071 Peoples R China Harbin Inst Technol Sch Elect & Informat Engn Shenzhen 518055 Peoples R China City Univ Hong Kong Dept Mech & Biomed Engn Coll Sci & Engn Hong Kong Peoples R China Harbin Engn Univ Dept Automat Harbin 150001 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Guangdong Peoples R China

Earth geomagnetic field provides very important information for autonomous navigation. However, in practice, magnetometer measurements are easily distorted by outer disturbances, as shown in the right diagram. In a recent study, the real-time magnetometer disturbance estimation problem has been solved via a constrained nonlinear programming for better underwater navigation accuracy. However, the employed interior-point optimizer will require considerable computational resources and cannot always guarantee optimality during optimization updates. This paper further investigates this problem and refines the solution by introducing the trust-region method. The challenge of the designed approach mainly falls into finding out the feasible regions of the possible solutions. Geometric analysis and algebraic elimination methods are taken into account to give globally optimal solutions to the trust-region solver. Experimentations are conducted to verify the correctness of the proposed method. Moreover, it is also confirmed that the trust-region technique can continuously and accurately propagate so that high-frequency dynamic magnetic disturbances can be efficiently estimated.

关键词： Magnetometers Optimization Sensors linear programming Estimation Real-time systems Magnetic sensors Magnetometer disturbance estimation trust-region method computational efficiency navigation

来源：评论

学校读者我要写书评

暂无评论

Faster Randomized interior point methods for Tall/Wide linear Programs

arXiv

引用

arXiv 2022年

作者： Chowdhury, Agniva Dexter, Gregory London, Palma Avron, Haim Drineas, Petros Computer Science and Mathematics Division Oak Ridge National Laboratory TN United States Department of Computer Science Purdue University West LafayetteIN United States Operations Research and Information Engineering Cornell University IthacaNY United States School of Mathematical Sciences Tel Aviv University 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, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as 1-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 iterative solvers such as Conjugate Gradient or Chebyshev Iteration, provably guarantees that IPM algorithms (suitably modified to account for the error incurred by the approximate 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. © 2022, CC BY.

关键词： Operations research

来源：评论

学校读者我要写书评

暂无评论

No self-concordant barrier interior point method is strongly polynomial

arXiv

引用

arXiv 2022年

作者： Allamigeon, Xavier Gaubert, Stéphane Vandame, Nicolas Inria France CMAP CNRS Ecole Polytechnique IP Paris France

It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this paper, we show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, on parametric families of convex optimization problems, the log-limit of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. We provide an explicit linear program that falls in the same class as the Klee–Minty counterexample, i.e., in dimension n with 2n constraints, in which the number of iterations is Ω(2n). Copyright © 2022, The Authors. All rights reserved.

关键词： Piecewise linear techniques

来源：评论

学校读者我要写书评

暂无评论

An efficient twice parameterized trigonometric kernel function for linear optimization

引用

OPTIMIZATION AND ENGINEERING 2020年第2期21卷 651-672页

作者： Bouafia, Mousaab Yassine, Adnan Univ 8 May 1945 Guelma BP 401 Guelma 24000 Algeria Normandie Univ ISCN LMAH UNIHAVREFR CNRS 3335 F-76600 Le Havre France

Recently, Bouafia et al. (J Optim theory Appl 170:528-545, 2016) investigated a new efficient kernel function that differs from self-regular kernel functions. The kernel function has a trigonometric barrier term. This paper introduces a new efficient twice parametric kernel function that combines the parametric classic function with the parametric kernel function trigonometric barrier term given by Bouafia et al. (J Optim theory Appl 170:528-545, 2016) to develop primal-dual interior-point algorithms for solving linear programming problems. In addition, we obtain the best complexity bound for large and small-update primal-dual interior point methods. This complexity estimate improves results obtained in Li and Zhang (Oper Res Lett 43(5):471-475, 2015), Peyghami and Hafshejani (Numer Algorithms 67:33-48, 2014) and matches the best bound obtained in Bai et al. (J Glob Optim 54:353-366) and Peng et al. (J Comput Technol 6:61-80, 2001). Finally, our numerical experiments on some test problems confirm that the new kernel function has promising applications compared to the kernel function given by Fathi-Hafshejani (Optimization 67(10):1605-1630, 2018).

关键词： linear optimization Kernel function interior point methods Complexity bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：