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

linear programming with a feasible direction interior point technique for smooth optimization

RAIRO-OPERATIONS RESEARCH 2022年第5期56卷 3643-3658页

作者： Victorio Celis, Angelica Miluzca Norman, Jose Herskovits Univ Fed Rio de Janeiro COPPE Syst Engn & Comp Sci POB 68511 BR-21945970 Rio De Janeiro RJ Brazil Univ Fed Rio de Janeiro COPPE Mech Engn Program POB 68503Cidade Univ BR-21945970 Rio De Janeiro RJ Brazil

We propose an adaptation of the Feasible Direction interior points Algorithm (FDIPA) of J. Herskovits, for solving large-scale linear programs. At each step, the solution of two linear systems with the same coefficient matrix is determined. This step involves a significant computational effort. Reducing the solution time of linear systems is, therefore, a way to improve the performance of the method. The linear systems to be solved are associated with definite positive symmetric matrices. Therefore, we use Split Preconditioned Conjugate Gradient (SPCG) method to solve them, together with an Incomplete Cholesky preconditioner using Matlab's ICHOL function. We also propose to use the first iteration of the conjugate gradient, and to presolve before applying the algorithm, in order to reduce the computational cost. Following, we then provide mathematica proof that show that the iterations approach Karush-Kuhn-Tucker points of the problem under reasonable assumptions. Finally, numerical evidence show that the method not only works in theory but is also competitive with more advanced methods.

关键词： interior point feasible direction linear programming

来源：评论

学校读者我要写书评

暂无评论

Solving Saddle point Formulations of linear Programs with Frank-Wolfe

Solving Saddle Point Formulations of Linear Programs with Fr...

引用

作者： Hough, Matthew University of Waterloo

学位级别：硕士

The problem of solving a linear program (LP) is ubiquitous in industry, yet in recent years the size of linear programming problems has grown and continues to do so. State-of-the-art LP solvers make use of the Simplex method and primal-dual interior-point methods which are able to provide accurate solutions in a reasonable amount of time for most problems. However, both the Simplex method and interior-point methods require solving a system of linear equations at each iteration, an operation that does not scale well with the size of the problem. In response to the growing size of linear programs and poor scalability of existing algorithms, researchers have started to consider first-order methods for solving large scale linear programs. The best known first-order method for general linear programming problems is PDLP. First-order methods for linear programming are characterized by having a matrix-vector product as their primary computational cost. We present a first-order primal-dual algorithm for solving saddle point formulations of linear programs, named FWLP (Frank-Wolfe linear programming). We provide some theoretical results regarding the behavior of our algorithm, however no convergence guarantees are provided. Numerical investigations suggest that our algorithm has error O(1/sqrt(k)) after k iterations, worse than that of PDLP, however we show that our algorithm has advantages for solving very large LPs in practice such as only needing part of the matrix A at each iteration.

关键词：

来源：评论

学校读者我要写书评

暂无评论

No Self-Concordant Barrier interior point Method Is Strongly Polynomial 2022

No Self-Concordant Barrier Interior Point Method Is Strongly...

引用

54th Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Allamigeon, Xavier Gaubert, Stephane Vandame, Nicolas INRIA Villeneuve Dascq France Ecole Polytech CMAP IP Paris CNRS Palaiseau France

ISBN: (纸本)9781450392648

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 for the simplex method, i.e., in which the feasible region is a combinatorial cube and the number of iterations is O(2(n)).

关键词： interior point methods self-concordant barriers linear programming convex programming tropical geometry

来源：评论

学校读者我要写书评

暂无评论

Convergence of a Weighted Barrier Algorithm for Stochastic Convex Quadratic Semidefinite Optimization

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2023年第2期196卷 490-515页

作者： Alzalg, Baha Gafour, Asma Univ Jordan Dept Math Amman 11942 Jordan Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Univ Djillali Liabes Sidi Bel Abbes Dept Math Sidi Bel Abbes 22038 Algeria

Mehrotra and ozevin (SIAM J Optim 19:1846-1880, 2009) computationally found that a weighted barrier decomposition algorithm for two-stage stochastic conic programs achieves significantly superior performance when compared to standard barrier decomposition algorithms existing in the literature. Inspired by this motivation, Mehrotra and ozevin (SIAM J Optim 20:2474-2486, 2010) theoretically analyzed the iteration complexity for a decomposition algorithm based on the weighted logarithmic barrier function for two-stage stochastic linear optimization with discrete support. In this paper, we extend the aforementioned theoretical paper and its self-concordance analysis from the polyhedral case to the semidefinite case and analyze the iteration complexity for a weighted logarithmic barrier decomposition algorithm for two-stage stochastic convex quadratic SDP with discrete support.

关键词： Quadratic semidefinite programming Two-stage stochastic programming Large-scale optimization interior-point methods Decomposition

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Preprocessing for segment routing optimization

引用

NETWORKS 2023年第4期82卷 459-478页

作者： Callebaut, Hugo De Boeck, Jerome Fortz, Bernard Univ libre Bruxelles Dept Informat Brussels Belgium INRIA INOCS Villeneuve Dascq France Univ Liege HEC Management Sch Liege Belgium Univ Fribourg Decis Support & Operat Res Fribourg Switzerland Univ Liege HEC Management Sch Rue Louvrex14 B-4000 Liege Belgium

In this article we introduce a preprocessing technique to solve the Segment Routing Traffic Engineering Problem optimally using significantly fewer computational resources than previously introduced methods. Segment routing is a recently developed interior gateway routing protocol to be used on top of existing protocols that introduces more flexibility in traffic engineering. In practice, segment routing allows to deviate traffic from its original path by specifying a list of intermediate nodes or links, called segments, to visit before going to its destination. The issue we tackle in this article is that the number of segment paths scales exponentially with the maximum number of segments allowed leading to scalability issues in mathematical formulations. This article introduces the notion of dominated segment paths, these are paths that can be eliminated from the solution space when searching for an optimal solution. We propose a dynamic programming algorithm eliminating dominated paths for any number of segments. Numerical results show that respectively 50%, 90%, and 97% of paths are dominated when considering up to 2, 3, and 4 segments on benchmark network topologies.

关键词： graph theory mixed integer linear programming network flows network optimization routing algorithms segment routing telecommunication networks traffic engineering

来源：评论

学校读者我要写书评

暂无评论

Loraine - an interior-point solver for low-rank semidefinite programming

引用

OPTIMIZATION methods & SOFTWARE 2024年第6期39卷 1185-1215页

作者： Habibi, Soodeh Kocvara, Michal Stingl, Michael Univ Birmingham Sch Math Birmingham England Inst Informat Theory & Automat Prague Czech Republic Friedrich Alexander Univ Erlangen Nurnberg Appl Math Continuous Optimizat Nurnberg Germany

The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.

关键词： Semidefinite optimization interior-point methods preconditioned conjugate gradients truss topology optimization MAXCUT problem Lasserre relaxations sensor network localization

来源：评论

学校读者我要写书评

暂无评论

An interior-point Algorithm for linear programming with Optimal Selection of Centering Parameter and Step Size

引用

Journal of the Operations Research Society of China 2021年第3期9卷 659-671页

作者： Ya-Guang Yang Nuclear Regulatory Commission Office of ResearchRockville 20850USA

For interior-point algorithms in linear programming,it is well known that the selection of the centering parameter is crucial for proving polynomiality in theory and for efficiency in ***,the selection of the centering parameter is usually by heuristics and separated from the selection of the line-search step *** heuristics are quite different while developing practically efficient algorithms,such as Mehrotra’s predictor–corrector(MPC)algorithm,and theoretically efficient algorithms,such as short-step path-following *** introduces a dilemma that some algorithms with the best-known polynomial bound are least efficient in practice,and some most efficient algorithms may not be convergent in polynomial ***,in this paper,we propose a systematic way to optimally select the centering parameter and linesearch step size at the same time,and we show that the algorithm based on this strategy has the best-known polynomial bound and may be very efficient in computation for real problems.

关键词： interior-point method Convergence Polynomial algorithm linear programming

来源：评论

学校读者我要写书评

暂无评论

Optimization for Learning and Control 1

引用

2023年

作者： Martin Andersen Anders Hansson

ISBN: (数字)9781119809173;9781119809142

ISBN: (纸本)9781119809135

Optimization for Learning and Control Comprehensive resource providing a masters’ level introduction to optimization theory and algorithms for learning and control Optimization for Learning and Control describes how optimization is used in these domains, giving a thorough introduction to both unsupervised learning, supervised learning, and reinforcement learning, with an emphasis on optimization methods for large-scale learning and control problems. Several applications areas are also discussed, including signal processing, system identification, optimal control, and machine learning. Today, most of the material on the optimization aspects of deep learning that is accessible for students at a Masters’ level is focused on surface-level computer programming; deeper knowledge about the optimization methods and the trade-offs that are behind these methods is not provided. The objective of this book is to make this scattered knowledge, currently mainly available in publications in academic journals, accessible for Masters’ students in a coherent way. The focus is on basic algorithmic principles and trade-offs. Optimization for Learning and Control covers sample topics such as:

Optimization theory and optimization methods, covering classes of optimization problems like least squares problems, quadratic problems, conic optimization problems and rank optimization.
First-order methods, second-order methods, variable metric methods, and methods for nonlinear least squares problems.
Stochastic optimization methods, augmented Lagrangian methods, interior-point methods, and conic optimization methods.
Dynamic programming for solving optimal control problems and its generalization to reinforcement learning.
How optimization theory is used to develop theory and tools of statistics and learning, e.g., the maximum likelihood method, expectation maximization, k-means clustering, and support vector machines.
How calculus of variatio

关键词： Optimization machine learning statistics linear algebra artificial neural networks entropy probability theory signal processing system identification mathematical programming k-means clustering algorithm support vector machine reinforcement learning optimal control dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Volt/VAR Optimization: A Survey of Classical and Heuristic Optimization methods

引用

IEEE ACCESS 2022年 10卷 13379-13399页

作者： Mataifa, H. Krishnamurthy, S. Kriger, C. Cape Peninsula Univ Technol Dept Elect Elect & Comp Engn ZA-7535 Cape Town South Africa

Reactive power optimization and voltage control is one of the most critical components of power system operation, impacting both the economy and security of system operation. It is also one of the most complex optimization problems, being highly nonlinear, and comprising both continuous and discrete decision variables. This paper presents the problem formulation, and a thorough literature review and detailed discussion of the various solution methods that have been applied to the Volt/VAR optimization problem. Each optimization method is described in detail, and its strengths and shortcomings are outlined. The review provides detailed information on classical and heuristic methods that have been applied to the Volt/VAR optimization problem. The classical methods reviewed include (i) first- and second-order gradient-based methods, (ii) Quadratic programming, (iii) linear programming, (iv) interior-point methods, (iv) and mixed-integer programming and decomposition methods. The heuristic methods covered include (i) Genetic Algorithm, (ii) Evolutionary programming, (iii) Particle Swarm Optimization, (iv) Fuzzy Set theory, and (v) Expert Systems. A comparative analysis of the key characteristics of the classical and heuristic optimization methods is also presented along with the review.

关键词： Reactive power Voltage control Power systems Power system stability Transformers Planning Optimization methods Volt VAR optimization reactive power voltage control classical numerical optimization heuristic methods artificial intelligence techniques

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：