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

The minimum area spanning tree problem: Formulations, Benders decomposition and branch-and-cut algorithms

COMPUTATIONAL GEOMETRY-theory AND APPLICATIONS 2021年 97卷 101771-101771页

作者： Guimaraes, Dilson Almeida da Cunha, Alexandre Salles Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil

The Minimum Area Spanning Tree Problem (MASTP) is defined in terms of a complete undirected graph G, where every vertex represents a point in the two dimensional Euclidean plane. Associated to each edge, there is a disk placed right at its midpoint, with diameter matching the length of the edge. MASTP seeks a spanning tree of Gthat minimizes the area in the union of the disks associated to its edges. This paper presents Integer programming (IP) approaches for MASTP, introduces pre-processing techniques to reduce the size of the formulations, and characterizes valid inequalities for reinforcing its linear programming Relaxation bounds. Several Branch-and-cut (BC) algorithms exploiting such ideas are introduced. Additionally, we also apply Benders Decomposition to one of these formulations. An accompanying BC method, that separates Benders optimality cuts, is also introduced. Aiming to save linear programming re-optimization times, that algorithm makes use of an early branching strategy. Given the set of valid inequalities used in the polyhedral representation of the problem and the best available upper bound for the optimal cost, it detects if the node cannot be pruned by bounds and then stops the cutting plane generation, in order to branch. Our algorithms manage to solve instances with up to only 15 vertices, suggesting thus that MASTP is hard to solve in practice, at least with the currently available methods. Thanks to the early branching strategy, the Benders based BC method obtained the best computational results, by far. It solved more instances to proven optimality than the other algorithms (31 out of 45 cases) and it is about three times faster than the second best performing algorithm. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Integer programming Spanning trees Discrete geometry Arrangements

来源：评论

学校读者我要写书评

暂无评论

Barrier and penalty methods for low-rank semidefinite programming with application to truss topology design

arXiv

引用

arXiv 2021年

作者： Habibi, Soodeh Kavand, Arefeh Kočvara, Michal Stingl, Michael School of Mathematics University of Birmingham United Kingdom Friedrich-Alexander-Universität Erlangen-Nürnberg Germany Institute of Information Theory and Automation Prague Czech Republic

The aim of this paper is to solve large-and-sparse linear Semidefinite Programs (SDPs) with low-rank solutions. We propose to use a preconditioned conjugate gradient method within second-order SDP algorithms and introduce a new efficient preconditioner fully utilizing the low-rank information. We demonstrate that the preconditioner is universal, in the sense that it can be efficiently used within a standard interior-point algorithm, as well as a newly developed primal-dual penalty method. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems of growing *** Codes 90C22, 90C51, 65F08, 74P05 Copyright © 2021, The Authors. All rights reserved.

关键词： Constrained optimization

来源：评论

学校读者我要写书评

暂无评论

Basis Preconditioning In interior point methods

Basis Preconditioning In Interior Point Methods

引用

作者： Lukas Marius Schork University of Edinburgh

学位级别：博士

Solving normal equations AAáµx = b, where A is an m x n matrix, is a common task in numerical optimization. For the efficient use of iterative methods, this thesis studies the class of preconditioners of the form BBáµ , where B is a nonsingular "basis" matrix composed of m columns of A. It is known that for any matrix A of full row rank B can be chosen so that the entries in [Bâ»Â¹A] are bounded by 1. Such a basis is said to have "maximum volume" and its preconditioner bounds the spectrum of the transformed normal matrix in the interval [1, 1+mn]. The theory is extended to (numerically) rank deficient matrices, yielding a rank revealing variant of Gaussian elimination and a method for computing the minimum norm solution for x from a reduced normal system and a low-rank update. Algorithms for finding a maximum volume basis are discussed. In the linear programming interior point method a sequence of normal equations needs to be solved, in which A changes by a column scaling from one system to the next. A heuristical algorithm is proposed for maintaining a basis of approximate maximum volume by update operations as those in the revised simplex method. Empirical results demonstrate that the approximation means no loss in the effectiveness of the preconditioner, but makes basis selection much more efficient. The implementation of an interior point solver based on the new linear algebra is described. Features of the code include the elimination of free variables during preconditioning and the removal of degenerate variables from the optimization process once sufficiently close to a bound. A crossover method recovers a vertex solution to the linear program, starting from the basis at the end of the interior point solve. A computational study shows that the implementation is robust and of general applicability, and that its average performance is comparable to that of state-of-the-art solvers.

关键词： preconditioners nonsingular basis matrix rank deficient matrices linear programming interior point interior point solver

来源：评论

学校读者我要写书评

暂无评论

Faster randomized infeasible interior point methods for tall/wide linear programs 20

Faster randomized infeasible interior point methods for tall...

引用

Proceedings of the 34th International Conference on Neural Information Processing Systems

作者： Agniva Chowdhury Palma London Haim Avron Petros Drineas Department of Statistics Purdue University West Lafayette IN ORIE Department Cornell University Ithaca NY School of Mathematical Sciences Tel Aviv University Tel Aviv Israel Department of Computer Science Purdue University West Lafayette IN

ISBN: (纸本)9781713829546

linear programming (LP) is 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 infeasible IPMs for the special case where the number of variables is much larger than the number of constraints (i.e., wide), or vice-versa (i.e., tall) by taking the dual. Using tools from Randomized linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, prov-ably guarantees that infeasible 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 and synthetic data.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Data-Driven Robust and Sparse Solutions for Large-scale Fuzzy Portfolio Optimization

Data-Driven Robust and Sparse Solutions for Large-scale Fuzz...

引用

IEEE Symposium Series on Computational Intelligence (SSCI)

作者： Na Yu You Liang A. Thavaneswaran Ryerson University Toronto Canada University of Manitoba Winnipeg Canada

ISBN: (纸本)9781728190495

There has been a growing interest in combining randomness and fuzziness to solve portfolio optimization problems in finance. However, many proposed fuzzy methods remain difficult to use in practice and hence, there is a need for efficient and robust approaches to obtain the optimal weights of the fuzzy models for real data. This paper focuses on the large-scale no short-selling fuzzy portfolio selection by modelling the returns of assets as nonlinear adaptive fuzzy numbers including trapezoidal fuzzy numbers. Moreover, the data-driven algorithmic approach proposed in this paper provides optimal portfolio weights by focusing on the robustness and sparsity of the solution. The proposed algorithms include interior-point (IP) with global search, pattern search (PS) with multiple starts, genetic algorithm (GA), ordered random weights algorithm (ORWA), and particle swarm optimization (PSO). Using 150 most traded stock prices downloaded from Yahoo finance, experiments are carried out and the results are described. The main findings are that out of the five proposed algorithms the PS (PSO) algorithm outperforms the rest in terms of robustness and sparsity to construct the optimal fuzzy minimum variance (tangency) portfolios respectively.

关键词： Adaptation models Finance linear programming Robustness Stability analysis IP networks Particle swarm optimization

来源：评论

学校读者我要写书评

暂无评论

Proximal Distance Algorithms: theory and practice

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2019年第1期20卷 2384-2421页

作者： Keys, Kevin L. Zhou, Hua Lange, Kenneth Univ Calif San Francisco Dept Med San Francisco CA 94158 USA Univ Calif Los Angeles Dept Biostat Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Biomath Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Human Genet Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Stat Los Angeles CA 90095 USA

Proximal distance algorithms combine the classical penalty method of constrained minimization with distance majorization. If f(x) is the loss function, and C is the constraint set in a constrained minimization problem, then the proximal distance principle mandates minimizing the penalized loss f (x) + rho/2 dist(x, C)(2) and following the solution x(rho) to its limit as rho tends to infinity. At each iteration the squared Euclidean distance dist(x,C)(2) is majorized by the spherical quadratic parallel to x-P-c(x(k))parallel to(2), where P-c(x(k)) denotes the projection of the current iterate x(k) onto C. The minimum of the surrogate function f (x) + rho/2 parallel to x-P-c(x(k))parallel to(2) is given by the proximal map prox(rho-1) (f)[P-c(x(k))]. The next iterate x(k+1) automatically decreases the original penalized loss for fixed rho. Since many explicit projections and proximal maps are known, it is straightforward to derive and implement novel optimization algorithms in this setting. These algorithms can take hundreds if not thousands of iterations to converge, but the simple nature of each iteration makes proximal distance algorithms competitive with traditional algorithms. For convex problems, proximal distance algorithms reduce to proximal gradient algorithms and therefore enjoy well understood convergence properties. For nonconvex problems, one can attack convergence by invoking Zangwill's theorem. Our numerical examples demonstrate the utility of proximal distance algorithms in various high-dimensional settings, including a) linear programming, b) constrained least squares, c) projection to the closest kinship matrix, d) projection onto a second-order cone constraint, e) calculation of Horn's copositive matrix index, f) linear complementarity programming, and g) sparse principal components analysis. The proximal distance algorithm in each case is competitive or superior in speed to traditional methods such as the interior point method and the alternating d

关键词： constrained optimization EM algorithm majorization projection proximal operator

来源：评论

学校读者我要写书评

暂无评论

Speeding up linear programming using randomized linear algebra

arXiv

引用

arXiv 2020年

作者： Chowdhury, Agniva London, Palma Avron, Haim Drineas, Petros Department of Statistics Purdue University West LafayetteIN United States Department of Computer Science California Institute of Technology PasadenaCA United States School of Mathematical Sciences Tel Aviv University Tel Aviv Israel Department of Computer Science Purdue University West LafayetteIN United States

linear programming (LP) is an extremely useful tool and 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 pointmethods (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 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 Conjugate Gradient iterative solver, provably guarantees that infeasible 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. Copyright © 2020, The Authors. All rights reserved.

关键词： linear programming

来源：评论

学校读者我要写书评

暂无评论

Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2018年第3期26卷 551-563页

作者： Darvay, Zsolt Takacs, Petra Renata Babes Bolyai Univ Fac Math & Comp Sci 1 Mihail Kogalniceanu St Cluj Napoca 400084 Romania Budapest Univ Technol & Econ Inst Math Muegyet Rkp 3 H-1111 Budapest Hungary

The interior-point algorithms can be classified in multiple ways. One of these takes into consideration the length of the step. In this way, we can speak about large-step and short-step methods, that work in different neighbourhoods of the central path. The large-step algorithms work in a wide neighbourhood, while the short-step ones determine the new iterates that are in a smaller neighbourhood. In spite of the fact that the large-step algorithms are more efficient in practice, the theoretical complexity of the short-step ones is generally better. Ai and Zhang introduced a large-step interior-point method for linear complementarity problems using a wide neighbourhood of the central path, which has the same complexity as the best short-step methods. We present a new wide neighbourhood of the central path. We prove that the obtained large-step primal-dual interior-point method for linear programming has the same complexity as the best short-step algorithms.

关键词： linear programming Large-step algorithm Wide neighbourhood Polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

Preconditioned Krylov iterations and condensing in interior point MPC method

引用

IFAC-PapersOnLine 2018年第20期51卷 388-393页

作者： Malyshev, Alexander Quirynen, Rien Knyazev, Andrew University of Bergen Department of Mathematics BergenPostbox 8700 5020 Norway Mitsubishi Electric Research Laboratories 201 Broadway 8th floor CambridgeMA02139 United States

We investigate using Krylov subspace iterative methods in model predictive control (MPC), where the prediction model is given by linear or linearized systems with linear inequality constraints on the state and the input, and the performance index is quadratic. The inequality constraints are treated by the primal-dual interior point method. We indicate condition numbers of several linear systems, which determine the search direction in the Newton method, and propose a new preconditioner for one of the systems. Numerical results illustrate convergence of Krylov methods with and without preconditioning and demonstrate that our preconditioning reduces the number of Krylov iterations 2–10 times. © 2018

关键词： Model predictive control Constraint theory Convergence of numerical methods Large scale systems linear programming linear systems Newton Raphson method Number theory Predictive control systems Inequality constraint Krylov subspace iterative methods linear inequality constraints linearized systems Numerical algorithms Performance indices Preconditioning Primal dual interior point methods

来源：评论

学校读者我要写书评

暂无评论

Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming

引用

NUMERICAL ALGORITHMS 2018年第3期79卷 957-992页

作者： Yang, Y. US NRC Off Res Two White Flint North 11545 Rockville Pike Rockville MD 20852 USA

Since the beginning of the development of interior-point methods, there exists a puzzling gap between the results in theory and the observations in numerical experience, i.e., algorithms with good polynomial bounds are not computationally efficient and algorithms demonstrated efficiency in computation do not have a good or any polynomial bound. Todd raised a question in 2002: Can we find a theoretically and practically efficient way to reoptimize? This paper is an effort to close the gap. We propose two arc-search infeasible interior-point algorithms with infeasible central path neighborhood wider than all existing infeasible interior-point algorithms that are proved to be convergent. We show that the first algorithm is polynomial and its simplified version has a complexity bound equal to the best known complexity bound for all (feasible or infeasible) interior-point algorithms. We demonstrate the computational efficiency of the proposed algorithms by testing all Netlib linear programming problems in standard form and comparing the numerical results to those obtained by Mehrotra's predictor-corrector algorithm and a recently developed more efficient arc-search algorithm (the convergence of these two algorithms is unknown). We conclude that the newly proposed algorithms are not only polynomial but also computationally competitive compared to both Mehrotra's predictor-corrector algorithm and the efficient arc-search algorithm.

关键词： Polynomial algorithm Arc-search Infeasible interior-point method linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：