Robustness analysis of polynomials with polynomial parameterdependency using Bernstein expansion

This paper considers the robust stability verification of polynomials with coefficients depending polynomially on parameters varying in given intervals. Two algorithms are presented, both rely on the expansion of a multivariate polynomial into Bernstein polynomials. The first one is an improvement of the so-called Bernstein algorithm and checks the Hurwitz determinant for positivity over the parameter set. The second one is based on the analysis of the value set of the family of polynomials and profits from the convex hull property of the Bernstein polynomials. Numerical results to real-world control problems are presented showing the efficiency of both algorithms     

Converting standard bivariate polynomials to Bernstein form over arbitrary triangular regions

An efficient, robust algorithm is presented for converting a bivariate polynomial expressed in the power basis directly to its equivalent Bernstein (Bézier) form over an arbitrary triangular region. It represents an improvement over existing algorithms which, in the course of transforming the polynomial, may encounter degeneracy problems that must be handled with additional logic.     

Solving nonlinear polynomial systems in the barycentric Bernstein basis

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.     

Global optimization of mixed-integer nonlinear (polynomial) programming problems: the Bernstein polynomial approach

In this paper, we propose an algorithm for constrained global optimization of mixed-integer nonlinear programming (MINLP) problems. The proposed algorithm uses the Bernstein polynomial form in a branch-and-bound framework. Ingredients such as continuous relaxation, branching for integer decision variables, and fathoming for each subproblem in the branch-and-bound tree are used. The performance of the proposed algorithm is tested and compared with several state-of-the-art MINLP solvers, on two sets of test problems. The results of the tests show the superiority of the proposed algorithm over the state-of-the-art solvers in terms of the chosen performance metrics.     

On the consistency of cardinal direction constraints

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n⁵) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.     

Dual bases of a Bernstein polynomial basis on simplices

This paper extends the theory of dual bases of a one-variate B-spline basis to the case of Bernstein polynomials and presents methods of constructing dual bases of a Bernstein polynomial basis on a simplex from that of a one-variate polynomial basis, s{xⁱs}ⁿ_i=0 and s{B^k_i,k-i(x) = (^k_i)xⁱ(l-x)^k-i}s^k_i=0 on the interval [0,1].     

Multiple-model based predictive control of nonlinear hybrid systems based on global optimization using the Bernstein polynomial approach

In this paper, we propose a Bernstein polynomial based global optimization algorithm for the optimal feedback control of nonlinear hybrid systems using a multiple-model approach. Specifically, we solve at every sampling instant a polynomial mixed-integer nonlinear programming problem arising in the model predictive control strategy. The proposed algorithm uses the Bernstein polynomial form in a branch-and-bound framework, with new ingredients such as branching for integer decision variables and fathoming for each subproblem in the branch-and-bound tree. The performance of the proposed algorithm is tested and compared with existing algorithms on a benchmark three-spherical tank system. The test results show the superior performance of the proposed algorithm.     

Correspondence matching using kernel principal components analysis and label consistency constraints

This paper investigates spectral approaches to the problem of point pattern matching. We make two contributions. First, we consider rigid point-set alignment. Here we show how kernel principal components analysis (kernel PCA) can be effectively used for solving the rigid point correspondence matching problem when the point-sets are subject to outliers and random position jitter. Specifically, we show how the point- proximity matrix can be kernelised, and spectral correspondence matching transformed into one of kernel PCA. Second, we turn our attention to the matching of articulated point-sets. Here we show label consistency constraints can be incorporated into definition of the point proximity matrix. The new methods are compared to those of Shapiro and Brady and Scott and Longuet-Higgins, together with multidimensional scaling. We provide experiments on both synthetic data and real world data.     

差分隐私的查询一致性约束研究

针对差分隐私直方图发布中区间查询的不一致问题,研究已有需迭代调整的局部最优线性无偏估计算法LBLUE,提出一种不需迭代且满足一致性约束查询的CA算法。通过对1棵添加Laplace噪声的满k-叉区间树进行一致性调整：先利用TDICE算法进行自顶向下的不一致估计,再利用BUCE算法进行自底向上的一致性估计,得到满足一致性约束查询的差分隐私满k-叉区间树,遍历后发布满足一致性约束查询的直方图数据。经过证明和实验分析,一致性调整后的查询区间满足一致性约束查询,且精确度优于Boost-2算法和LBLUE算法的,同时算法的时间效率高于LBLUE算法的。     

Optimal computation of the Bernstein algorithm for the bound of an interval polynomial

If a polynomial is expanded in terms of Bernstein polynomial over an interval then the coefficients of the expansion may be used to provide upper and lower bounds for the value of the polynomial over the interval. When applying this method to interval polynomials straightforwardly, the coefficients of the expansion are computed with an increase in width due to dependency intervals. In this paper we show that if the computations are rearranged suitably then the Bernstein coefficients can be computed with no increase in width due to dependency intervals.     

A New Subdivision Algorithm for the Bernstein Polynomial Approach to Global Optimization

In this paper,an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems.The proposed algorithm is based on the Bernstein polynomial approach.Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point,modified rules for the selection of the subdivision direction,and a new acceleration device to avoid some unnecessary subdivisions.The performance of the proposed algorithm is numerically tested on a collection of 16 test problems.The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.     

GPU-based parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems

This paper proposes a parallel solver for the nonlinear systems in Bernstein form based on subdivision and the Newton-Raphson method, where the Kantorovich theorem is employed to identify the existence of a unique root and guarantee the convergence of the Newton-Raphson iterations. Since the Kantorovich theorem accommodates a singular Jacobian at the root, the proposed algorithm performs well in a multiple root case. Moreover, the solver is designed and implemented in parallel on Graphics Processing Unit(GPU) with SIMD architecture; thus, efficiency for solving a large number of systems is improved greatly, an observation validated by our experimental results.     

A hybrid evolutionary approach for solving constrained optimization problems over finite domains

A novel approach for the integration of evolution programs and constraint-solving techniques over finite domains is presented. This integration provides a problem-independent optimization strategy for large-scale constrained optimization problems over finite domains. In this approach, genetic operators are based on an arc-consistency algorithm, and chromosomes are arc-consistent portions of the search space of the problem. The paper describes the main issues arising in this integration: chromosome representation and evaluation, selection and replacement strategies, and the design of genetic operators. We also present a parallel execution model for a distributed memory architecture of the previous integration. We have adopted a global parallelization approach that preserves the properties, behavior, and fundamentals of the sequential algorithm. Linear speedup is achieved since genetic operators are coarse grained as they perform a search in a discrete space carrying out arc consistency. The implementation has been tested on a GRAY T3E multiprocessor using a complex constrained optimization problem.     

Inverse of polynomial matrices in the irreducible form

An algorithm is developed for finding the inverse of polynomial matrices in the irreducible form. The computational method involves the use of the left (right) matrix division method and the determination of linearly dependent vectors of the remainders. The obtained transfer function matrix has no nontrivial common factor between the elements of the numerator polynomial matrix and the denominator polynomial.     

Algebraic manipulation in the Bernstein form made simple via convolutions

Traditional methods for algebraic manipulation of polynomials in Bernstein form try to obtain an explicit formula for each coefficient of the result of a given procedure, such us multiplication, arbitrarily high degree elevation, composition, or differentiation of rational functions. Whereas this strategy often furnishes involved expressions, these operations become trivial in terms of convolutions between coefficient lists if we employ the scaled Bernstein basis, which does not include binomial coefficients. We also carry over this scheme from the univariate case to multivariate polynomials, Bézier simplexes of any dimension and B-bases of other functional spaces. Examples of applications in geometry processing are provided, such as conversions between the triangular and tensor-product Bézier forms.     

Symmetries of differential behaviors and finite group actions on free modules over a polynomial ring

In this paper we study finite group symmetries of differential behaviors (i.e., kernels of linear constant coefficient partial differential operators). They lead us to study the actions of a finite group on free modules over a polynomial ring. We establish algebraic results which are then used to obtain canonical differential representations of symmetric differential behaviors.     

Fault detection for discrete spatially interconnected systems with time-delay over finite frequency domains

This paper investigates the problem of fault detection observer design for discrete spatially interconnected time-delay systems (SITSs) in finite frequency range. Firstly, a delay-dependent generalised Kalman–Yakubivich–Popov (GKYP) lemma for SITSs is proposed. Then, by the giving GKYP lemma, a distributed fault detection observer design method can be derived by solving a set of linear matrix inequalities (LMIs). Finally, an illustrative example is provided to demonstrate the effectiveness of the proposed method.     

An approximate solution of the problem of optimal control over elliptic systems in domains of arbitrary form

A combination of the net method and method of fictitious domains is used for solving the problem of optimal control over elliptic systems in domains of arbitrary form. As is shown, the proposed difference scheme has the order of accuracy O(h^1/2) in the net norm W^1/2 (ω). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 3–8, November–December, 1999.