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

Computing tight bounds via piecewise linear functions through the example of circle cutting problems

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2016年第1期84卷 3-57页

作者： Rebennack, Steffen Colorado Sch Mines Div Econ & Business Golden CO 80401 USA

This paper discusses approximations of continuous and mixed-integer nonlinear optimization problems via piecewise linear functions. Various variants of circle cutting problems are considered, where the non-overlap of circles impose a non-convex feasible region. While the paper is written in an "easy-to-understand" and "hands-on" style which should be accessible to graduate students, also new ideas are presented. Specifically, piecewise linear functions are employed to yield mixed-integer linear programming problems which provide lower and upper bounds on the original problem, the circle cutting problem. The piecewise linear functions are modeled by five different formulations, containing the incremental and logarithmic formulations. Another variant of the cutting problem involves the assignment of circles to pre-defined rectangles. We introduce a new global optimization algorithm, based on piecewise linear function approximations, which converges in finitely many iterations to a globally optimal solution. The discussed formulations are implemented in GAMS. All GAMS-files are available for download in the Electronic supplementary material. Extensive computational results are presented with various illustrations.

关键词： piecewise linear functions Circle cutting Non-convex optimization Global optimization Non-linear programming (NLP) Quadratically constrained programming (QCP) Mixed-integer linear programming (MILP) Outer approximation Inner approximation Incremental formulation Logarithmic formulation

来源：评论

学校读者我要写书评

暂无评论

A new topological entropy-based approach for measuring similarities among piecewise linear functions

引用

SIGNAL PROCESSING 2017年 134卷 130-138页

作者： Rucco, Matteo Gonzalez-Diaz, Rocio Jimenez, Maria-Jose Atienza, Nieves Cristalli, Cristina Concettoni, Enrico Ferrante, Andrea Merelli, Emanuela Univ Camerino Sch Sci & Technol Div Comp Sci Camerino Italy Univ Seville Sch Comp Engn Dept Appl Math Seville Spain Res Innovat Grp Loccioni Grp Angeli Di Rosora AN Italy

In this paper we present a novel methodology based on a topological entropy, the so-called persistent entropy, for addressing the comparison between discrete piecewise linear functions. The comparison is certified by the stability theorem for persistent entropy that is presented here. The theorem is used in the implementation of a new algorithm. The algorithm transforms a discrete piecewise linear function into a filtered simplicial complex that is analyzed via persistent homology and persistent entropy. Persistent entropy is used as a discriminant feature for solving the supervised classification problem of real long-length noisy signals of DC electrical motors. The quality of classification is stated in terms of the area under receiver operating characteristic curve (AUC=93.87%).

关键词： piecewise linear functions Noisy signals Persistent homology Persistent entropy Supervised classification

来源：评论

学校读者我要写书评

暂无评论

A successive relaxation algorithm to solve a MILP involving piecewise linear functions with application to road design

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2022年第3期81卷 741-767页

作者： MonnetnAff, Dominique Hare, Warren Lucet, Yves Polytech Montreal Montreal PQ Canada Univ British Columbia Okanagan Kelowna BC Canada

This paper presents a new algorithm to build feasible solutions to a MILP formulation of the vertical alignment problem in road design. This MILP involves a large number of special ordered set of type 2 variables used to describe piecewise linear functions. The principle of the algorithm is to successively solve LPs adapted from the MILP by replacing the special ordered set of type 2 constraints by linear constraints. Proof that the solutions to the successive linear relaxations of the MILP converge to a feasible solution to the MILP is provided. Numerical results emphasize that the algorithm performs better than CPLEX for large scale vertical alignment problems.

关键词： Mixed integer linear program piecewise linear functions Road design Vertical alignment proble

来源：评论

学校读者我要写书评

暂无评论

Efficient representation of piecewise linear functions into Lukasiewicz logic modulo satisfiability

引用

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE 2022年第9期32卷 1119-1144页

作者： Preto, Sandro Finger, Marcelo Univ Sao Paulo Inst Math & Stat Sao Paulo Brazil

This work concerns the representation of a class of continuous functions into Logic, so that one may automatically reason about properties of these functions using logical tools. Rational McNaughton functions may be implicitly represented by logical formulas in Lukasiewicz Infinitely-valued Logic by constraining the set of allowed valuations;such a restriction contemplates only those valuations that satisfy specific formulas. This work investigates two approaches to such depiction, called representation modulo satisfiability. Furthermore, a polynomial-time algorithm that builds this representation is presented, producing a pair of formulas consisting of the representative formula and the constraining one, given as input a rational McNaughton function in a suitable encoding. An implementation of the algorithm is discussed.

关键词： Function representation Lukasiewicz Infinitely-valued Logic rational McNaughton functions piecewise linear functions

来源：评论

学校读者我要写书评

暂无评论

Second-Order Analysis of piecewise linear functions with Applications to Optimization and Stability

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2016年第2期171卷 504-526页

作者： Mordukhovich, B. S. Sarabi, M. E. Wayne State Univ Detroit MI 48202 USA

This paper is devoted to second-order variational analysis of a rather broad class of extended-real-valued piecewise liner functions and their applications to various issues of optimization and stability. Based on our recent explicit calculations of the second-order subdifferential for such functions, we establish relationships between nondegeneracy and second-order qualification for fully amenable compositions involving piecewise linear functions. We then provide a second-order characterization of full stable local minimizers in composite optimization and constrained minimax problems.

关键词： Variational analysis and optimization piecewise linear functions Second-order subdifferentials Nondegeneracy Full stability of local minimizers

来源：评论

学校读者我要写书评

暂无评论

A comparison of piecewise cubic Hermite interpolating polynomials, cubic splines and piecewise linear functions for the approximation of projectile aerodynamics 31

A comparison of piecewise cubic Hermite interpolating polyno...

引用

31st International Symposium on Ballistics

作者： Rabbath, C. A. Corriveau, D. Def R&D Canada Valcartier Res Ctr 2459 Bravoure Rd Quebec City PQ G3J 1X5 Canada

ISBN: (纸本)9781605956107

Modelling and simulation of projectile flight is at the core of ballistic computer software and is essential to the study of performance of rifles and projectiles in various engagement conditions. An effective and representative numerical model of projectile flight requires a relatively good approximation of the aerodynamics. The aerodynamic coefficients of the projectile model should be described as a series of piecewise polynomial functions of the Mach number that ideally meet the following conditions: they are continuous, differentiable at least once, and have a relatively low degree. The paper provides the steps needed to generate such piecewise polynomial functions using readily available tools, and then compares piecewise Cubic Hermite Interpolating Polynomial (PCHIP), cubic splines, and piecewise linear functions, and their variant, as potential curve fitting methods to approximate the aerodynamics of a generic small arms projectile. A key contribution of the paper is the application of PCHIP to the approximation of projectile aerodynamics, and its evaluation against a set of criteria. Finally, the paper provides a baseline assessment of the impact of the polynomial functions on flight trajectory predictions obtained with 6-degree-of-freedom simulations of a generic projectile. Crown Copyright (C) 2019 Production and hosting by Elsevier B.V.

关键词： Aerodynamic coefficients piecewise polynomial functions Cubic splines Curve fitting piecewise linear functions piecewise cubic Hermite interpolating polynomial Projectile modelling and simulation Fire control inputs Precision Ballistic computer software

来源：评论

学校读者我要写书评

暂无评论

Least Squares Approximation to Lognormal Sum Distribution via piecewise linear functions

Least Squares Approximation to Lognormal Sum Distribution vi...

引用

4th IEEE Conference on Industrial Electronics and Applications

作者： Zhao, Lian Ding, Jiu Ryerson Univ Dept Elect & Comp Engn Toronto ON M5B 2K3 Canada Univ Southern Mississippi Dept Math Hattiesburg MS 39406 USA

ISBN: (纸本)9781424427994

In this paper, the least squares approximation via a piecewise linear function approach is applied to solve the approximation problem of a sum of lognormal random variables. A number of linear basis functions are applied and the corresponding coefficients are specified to form a piecewise linear approximation to the sum lognormal cumulative distribution function. By using the proposed approach, arbitrary precision of the approximation can be achieved by increasing the number of basis functions. The computation complexity shows no significant increase with the increase of the number of basis functions. Simulation results exhibit a desirable performance by using the proposed approximation method through piecewise linear basis functions.

关键词： Lognormal random variables L-2-norm least squares piecewise linear functions basis functions cumulative distribution functions (CDF)

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Representing piecewise linear functions into Logic 15

An Efficient Algorithm for Representing Piecewise Linear Fun...

引用

15th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA)

作者： Preto, Sandro Finger, Marcelo Univ Sao Paulo Inst Math & Stat Sao Paulo Brazil

Rational McNaughton functions may be implicitly represented by logical formulas in Lukasiewicz Infinitely-valued Logic by constraining the set of valuations to the ones that satisfy some specific formulas. This work investigates this implicit representation called representation modulo satisfiability and describes a polynomial algorithm that builds it - the representative formula and the constraining ones - for a given rational McNaughton function.

关键词： Lukasiewicz Infinitely-valued Logic Rational McNaughton functions piecewise linear functions

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Representing piecewise linear functions into Logic

引用

Electronic Notes in Theoretical Computer Science 2020年 351卷 167-186页

作者： Sandro Preto Marcelo Finger Institute of Mathematics and Statistics University of São Paulo São Paulo Brazil

Rational McNaughton functions may be implicitly represented by logical formulas in Łukasiewicz Infinitely-valued Logic by constraining the set of valuations to the ones that satisfy some specific formulas. This work investigates this implicit representation called representation modulo satisfiability and describes a polynomial algorithm that builds it — the representative formula and the constraining ones — for a given rational McNaughton function.

关键词： Łukasiewicz Infinitely-valued Logic Rational McNaughton functions piecewise linear functions

来源：评论

学校读者我要写书评

暂无评论

piecewise linear bounding functions in univariate global optimization

引用

SOFT COMPUTING 2020年第23期24卷 17631-17647页

作者： Posypkin, Mikhail Usov, Alexander Khamisov, Oleg Russian Acad Sci Fed Res Ctr Comp Sci & Control Vavilova 40 Moscow Russia Russian Acad Sci Melentiev Energy Syst Inst Siberian Branch Lermontov St 130 Irkutsk 664033 Russia

The paper addresses the problem of constructing lower and upper estimators for univariate functions. This problem is of crucial importance in global optimization, where such bounds are used to reduce the search area. We propose to use piecewise linear estimators for bounding univariate functions and show how such estimators can be derived from the function's algebraic expression. The basic properties of such estimators are formulated and proved. We implemented the algorithms for the automated construction of lower and upper piecewise linear estimators and experimentally compared the proposed approach with the first-order interval bounds, Pijavskij method, and slope arithmetic. Numerical examples demonstrate that the piecewise linear estimators are more accurate with respect to the mentioned approaches. We also show that global optimization algorithms can significantly benefit from using piecewise linear estimators. Another advantage of the proposed approach is that the objective function does not have to be differentiable. This feature can favorably distinguish this method from other methods where the first and second derivatives are used.

关键词： Univariate global optimization piecewise linear functions Estimators Deterministic methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：