Slope enclosures for functions given by two or more branches

In this paper, we consider the automatic computation of slope enclosures for continuous real functions given by two or more branches, such as piecewise defined nonsmooth functions. We show that a commonly used formula found in the literature does not always provide a slope enclosure for such functions. Furthermore, we prove a similar formula that always holds. AMS subject classification (2000)  65G20     

一类非光滑函数的区间扩张

本文指出了文献[1]中的一个错误,并给予修正,同时讨论了一类非光滑函数的区间扩张,它在数学规划有很多应用。所举的例子说明,我们给出的区间扩张函数优于文献[1]中的区间扩张函数。     

An interval iteration for multiple roots of transcendental equations

An iteration method for roots of algebraic functions with roots of multiplicity greater than one is established using tools and techniques from interval arithmetic. The method is based on an interval iteration functions for multiple roots and it retains the convergence order of the underlying iteration method while preserving global convergence over an initial interval. A number of simple examples are provided to show that the method is feasible and that it produces reasonable results.     

Differences of Convex Compact Sets in the Space of Directed Sets. Part I: The Space of Directed Sets

A normed and partially ordered vector space of so-called directed sets is constructed, in which the convex cone of all nonempty convex compact sets in R ⁿ is embedded by a positively linear, order preserving and isometric embedding (with respect to a new metric stronger than the Hausdorff metric and equivalent to the Demyanov one). This space is a Banach and a Riesz space for all dimensions and a Banach lattice for n=1. The directed sets in R ⁿ are parametrized by normal directions and defined recursively with respect to the dimension n by the help of a support function and directed supporting faces of lower dimension prescribing the boundary. The operations (addition, subtraction, scalar multiplication) are defined by acting separately on the support function and recursively on the directed supporting faces. Generalized intervals introduced by Kaucher form the basis of this recursive approach. Visualizations of directed sets will be presented in the second part of the paper.     

Global Solution of Optimization Problems with Parameter-Embedded Linear Dynamic Systems

This paper develops a theory for the global solution of nonconvex optimization problems with parameter-embedded linear dynamic systems. A quite general problem formulation is introduced and a solution is shown to exists. A convexity theory for integrals is then developed to construct convex relaxations for utilization in a branch-and-bound framework to calculate a global minimum. Interval analysis is employed to generate bounds on the state variables implied by the bounds on the embedded parameters. These bounds, along with basic integration theory, are used to prove convergence of the branch-and-bound algorithm to the global minimum of the optimization problem. The implementation of the algorithm is then considered and several numerical case studies are examined thoroughly     

计算具有区间参数结构的固有频率的优化方法

基于区间函数的单向包含性质，把具有区间非确定参数结构的固有频率所在区间范围问题 转化成两个全局优化问题，并采用一种实数编码遗传算法求取问题的全局解. 用一种能够求 得剪切型结构和弹簧质量系统特征值范围精确解的单调分析方法进行检验. 在一 些文献中，直接采用区间数运算法则和有限元法得到结构区间刚度阵和区间质量阵，并把关 于该区间刚度阵和区间质量阵的广义区间特征值问题的特征值区间作为待求的非确定性结构 的特征值所在的区间范围，该方法易于扩大问题的解域. 算例表明，可望得到结构 固有频率区间范围的准确解.     

非确定结构系统区间分析的泛灰求解方法

工程中的不确定性问题可以用区间分析、概率理论或模糊理论来求解。采用泛灰区间分析法来处理结构静力分析和设计中的不确定性问题。将结构系统中的不确定性参数用区间数来表示，用有限元法建立系统的控制方程。该控制方程是线性区间方程组。然后，在概述泛灰数的概念及其运算规则的基础上，介绍了泛灰数与区间数的转化，利用泛灰数的可扩展性对区间进行分析，研究了泛灰线性方程求解，然后将它应用于结构静力分析和设计中的不确定性问题，泛灰数不仅具有区间分析的功能，而且能解决区间分析所不能解决的问题。文中给出了两个算例，列出了本文算法与其他算法的结果比较。     

Improving Interval Analysis Bounds by Translations

We explore how a simple linear change of variable affects the inclusion functions obtained with Interval Analysis methods. Univariate and multivariate polynomial test functions are considered, showing that translation-based methods improve considerably the bounds computed by standard inclusion functions. An Interval Branch-and-Bound method for global optimization is then implemented to compare the different procedures, showing that, although with times higher than those given by Taylor forms, the number of clusters and iterations is strongly reduced.     

Interval Analysis on Directed Acyclic Graphs for Global Optimization

A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation. Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation. The implementation is based on earlier work by L.V. Kolev, (1997), Reliable Comput., 3, 83–93 on optimal slopes and by C. Bliek, (1992), Computer Methods for Design Automation, PhD Thesis, Department of Ocean Engineering, Massachusetts Institute of Technology on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly. Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian. The linear underestimators can be found either by slope computations, or by recursive backward underestimation. For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian). Mathematics Subject Classification (2000). primary 65G40, secondary 90C26