An Improved Bernstein Global Optimization Algorithm for MINLP Problems with Application in Process Industry

We present an improved Bernstein global optimization algorithm to solve polynomial mixed-integer nonlinear programming (MINLP) problems. The algorithm is of branch-and-bound type, and uses the Bernstein form of the polynomials for the global optimization. The new ingredients in the algorithm include a modified subdivision procedure, a vectorized Bernstein cut-off test and a new branching rule for the decision variables. The performance of the improved algorithm is tested and compared with earlier reported Bernstein global optimization algorithm (to solve polynomial MINLPs) and with several state-of-the-art MINLP solvers on a set of 19 test problems. The results of the tests show the superiority of the improved algorithm over the earlier reported Bernstein algorithm and the state-of-the-art solvers in terms of the chosen performance metrics. Similarly, efficacy of the improved algorithm in handling a real-world MINLP problem is brought out via a trim-loss minimization problem from the process industry.     

Bézier form of dual bivariate Bernstein polynomials

Dual Bernstein polynomials of one or two variables have proved to be very useful in obtaining Bézier form of the L ₂-solution of the problem of best polynomial approximation of Bézier curve or surface. In this connection, the Bézier coefficients of dual Bernstein polynomials are to be evaluated at a reasonable cost. In this paper, a set of recurrence relations satisfied by the Bézier coefficients of dual bivariate Bernstein polynomials is derived and an efficient algorithm for evaluation of these coefficients is proposed. Applications of this result to some approximation problems of Computer Aided Geometric Design (CAGD) are discussed.     

Fast construction of constant bound functions for sparse polynomials

A new method for the representation and computation of Bernstein coefficients of multivariate polynomials is presented. It is known that the coefficients of the Bernstein expansion of a given polynomial over a specified box of interest tightly bound the range of the polynomial over the box. The traditional approach requires that all Bernstein coefficients are computed, and their number is often very large for polynomials with moderately-many variables. The new technique detailed represents the coefficients implicitly and uses lazy evaluation so as to render the approach practical for many types of non-trivial sparse polynomials typically encountered in global optimization problems; the computational complexity becomes nearly linear with respect to the number of terms in the polynomial, instead of exponential with respect to the number of variables. These range-enclosing coefficients can be employed in a branch-and-bound framework for solving constrained global optimization problems involving polynomial functions, either as constant bounds used for box selection, or to construct affine underestimating bound functions. If such functions are used to construct relaxations for a global optimization problem, then sub-problems over boxes can be reduced to linear programming problems, which are easier to solve. Some numerical examples are presented and the software used is briefly introduced.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

On the formulation of a BEM in the Bézier–Bernstein space for the solution of Helmholtz equation

This paper proposes a novel boundary element approach formulated on the Bézier-Bernstein basis to yield a geometry-independent field approximation. The proposed method is geometrically based on both computer aid design (CAD) and isogeometric analysis (IGA), but field variables are independently approximated from the geometry. This approach allows the appropriate approximation functions for the geometry and variable field to be chosen. We use the Bézier–Bernstein form of a polynomial as an approximation basis to represent both geometry and field variables. The solution of the element interpolation problem in the Bézier–Bernstein space defines generalised Lagrange interpolation functions that are used as element shape functions. The resulting Bernstein–Vandermonde matrix related to the Bézier–Bernstein interpolation problem is inverted using the Newton-Bernstein algorithm. The applicability of the proposed method is demonstrated solving the Helmholtz equation over an unbounded region in a two-and-a-half dimensional (2.5D) domain.     

Interpolation and convergence of Bernstein-Bézier coefficients

In this paper, two ways of the proof are given for the fact that the Bernstein-Bézier coefficients (BB-coefficients) of a multivariate polynomial converge uniformly to the polynomial under repeated degree elevation over the simplex. We show that the partial derivatives of the inverse Bernstein polynomial A _n (g) converge uniformly to the corresponding partial derivatives of g at the rate 1/n. We also consider multivariate interpolation for the BB-coefficients, and provide effective interpolation formulas by using Bernstein polynomials with ridge form which essentially possess the nature of univariate polynomials in computation, and show that Bernstein polynomials with ridge form with least degree can be constructed for interpolation purpose, and thus a computational algorithm is provided correspondingly.     

Bernstein polynomial basis for numerical solution of boundary value problems

The purpose of this paper is to propose a computational method for the approximate solution of linear and nonlinear two-point boundary value problems. In order to approximate the solution, the expansions in terms of the Bernstein polynomial basis have been used. The properties of the Bernstein polynomial basis and the corresponding operational matrices of integration and product are utilized to reduce the given boundary value problem to a system of algebraic equations for the unknown expansion coefficients of the solution. On this approach, the problem can be solved as a system of algebraic equations. By considering a special case of the problem, an error analysis is given for the approximate solution obtained by the present method. At last, five examples are examined in order to illustrate the efficiency of the proposed method.     

Solutions of differential equations in a Bernstein polynomial basis

An algorithm for approximating solutions to differential equations in a modified new Bernstein polynomial basis is introduced. The algorithm expands the desired solution in terms of a set of continuous polynomials over a closed interval and then makes use of the Galerkin method to determine the expansion coefficients to construct a solution. Matrix formulation is used throughout the entire procedure. However, accuracy and efficiency are dependent on the size of the set of Bernstein polynomials and the procedure is much simpler compared to the piecewise B spline method for solving differential equations. A recursive definition of the Bernstein polynomials and their derivatives are also presented. The current procedure is implemented to solve three linear equations and one nonlinear equation, and excellent agreement is found between the exact and approximate solutions. In addition, the algorithm improves the accuracy and efficiency of the traditional methods for solving differential equations that rely on much more complicated numerical techniques. This procedure has great potential to be implemented in more complex systems where there are no exact solutions available except approximations.     

Bounds on a polynomial

Methods are given for isolating and approximating the maxima, minima, and real roots of a polynomial with real coefficients. The methods are based on a variation diminishing property of the Bernstein coefficients of the polynomial and use of a recursive bisection technique.     

Gauss–Lobatto to Bernstein polynomials transformation

The aim of this paper is to transform a polynomial expressed as a weighted sum of discrete orthogonal polynomials on Gauss–Lobatto nodes into Bernstein form and vice versa. Explicit formulas and recursion expressions are derived. Moreover, an efficient algorithm for the transformation from Gauss–Lobatto to Bernstein is proposed. Finally, in order to show the robustness of the proposed algorithm, experimental results are reported.     

Orthogonal polynomials with respect to the sum of an arbitrary measure and a Bernstein–Szegö measure

In the present paper we study the orthogonal polynomials with respect to a measure which is the sum of a finite positive Borel measure on [0,2π] and a Bernstein–Szegö measure. We prove that the measure sum belongs to the Szegö class and we obtain several properties about the norms of the orthogonal polynomials, as well as, about the coefficients of the expression which relates the new orthogonal polynomials with the Bernstein–Szegö polynomials. When the Bernstein–Szegö measure corresponds to a polynomial of degree one, we give a nice explicit algebraic expression for the new orthogonal polynomials.     

Real intersection points of piecewise algebraic curves

The piecewise algebraic curve, as the set of zeros of a bivariate spline function, is a generalization of the classical algebraic curve. In this work, we present an algorithm for computing the real intersection points of piecewise algebraic curves. It is primarily based on the interval zeros of the univariate interval polynomial in Bernstein form. An illustrative example is provided to show that the proposed algorithm is flexible.     

Algorithms for checking rational roots of b-functions and their applications

The Bernstein–Sato polynomial of a hypersurface is an important object with many applications. However, its computation is hard, as a number of open questions and challenges indicate. In this paper we propose a family of algorithms called checkRoot for optimized checking whether a given rational number is a root of Bernstein–Sato polynomial and in the affirmative case, computing its multiplicity. These algorithms are used in the new approach to compute the global or local Bernstein–Sato polynomial and b-function of a holonomic ideal with respect to a weight vector. They can be applied in numerous situations, where a multiple of the Bernstein–Sato polynomial can be established. Namely, a multiple can be obtained by means of embedded resolution, for topologically equivalent singularities or using the formula of A?Campo and spectral numbers. We also present approaches to the logarithmic comparison problem and the intersection homology D-module. Several applications are presented as well as solutions to some challenges which were intractable with the classical methods. One of the main applications is the computation of a stratification of affine space with the local b-function being constant on each stratum. Notably, the algorithm we propose does not employ primary decomposition. Our results can be also applied for the computation of Bernstein–Sato polynomials for varieties. The examples in the paper have been computed with our implementation of the methods described in Singular:Plural.     

Vibro-acoustic Investigations Using Finite and Infinite Elements

The solution of large systems of equations often involves the use of iterative solution procedures, mostly by means of Krylov subspace methods. The performance of these methods, however, strongly depends on the spectrum of the resulting system matrices, which is affected by the polynomial approximation function space. The current work shows that finite elements based on Bernstein polynomials yield particularly good performance in combination with commonly employed Krylov solvers. Adapting the basis of Astley-Leis infinite elements, the Bernstein polynomials may also be used for exterior acoustic simulations. The efficiency of such elements for interior acoustic problems as well as for sound radiation analyses is assessed. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bernstein Polynomial Collocation Method for Elliptic Boundary Value Problems

We present a summary of recent developments in application of Bernstein polynomials to solution of elliptic boundary value problems with a pseudospectral method. Solution is approximated using Benstein polynomial interpolant defined at points of the extrema of Chebyshev polynomials i.e. the Chebyshev-Gauss-Lobatto (CGL) nodes. This approach brings impovement comparing to the Bernstein interpolation at equidistant nodes we used previously [1]. We show that this approach leads to spectral convergence and accuracy comparable to that of pseudospectral methods with orthogonal polynomials (Chebyshev, Legendre). The algorithm is implemented in open source library bernstein-poly , which is available online. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear polynomial constraints inferencing algorithm

This paper propose the inference mechanism for handling linear polynomial constraints called consistency checking algorithm based on the feasibility checking algorithm borrowed from linear programming. In contrast with other approaches, proposed algorithm can efficiently and coherented by linear polynomial forms. The developed algorithm is successfully applied to the symbolic simulation that offers a convenient means to conduct multiple, simultaneous exploration of model behaviors.     

Identification of multiple-input single-output Hammerstein models using Bezier curves and Bernstein polynomials

This paper considers the implementation of Bezier–Bernstein polynomials and the Levenberg–Marquart algorithm for identifying multiple-input single-output (MISO) Hammerstein models consisting of nonlinear static functions followed by a linear dynamical subsystem. The nonlinear static functions are approximated by the means of Bezier curves and Bernstein basis functions. The identification method is based on a hybrid scheme including the inverse de Casteljau algorithm, the least squares method, and the Levenberg–Marquart (LM) algorithm. Furthermore, results based on the proposed scheme are given which demonstrate substantial identification performance.     

Connections between two-variable Bernstein and Jacobi polynomials on the triangle

Connection coefficients between the two-variable Bernstein and Jacobi polynomial families on the triangle are given explicitly as evaluations of two-variable Hahn polynomials. Dual two-variable Bernstein polynomials are introduced. Explicit formula in terms of two-variable Jacobi polynomials and a recurrence relation are given.     

Constructive D-Module Theory with Singular

We overview numerous algorithms in computational D-module theory together with the theoretical background as well as the implementation in the computer algebra system Singular. We discuss new approaches to the computation of Bernstein operators, of logarithmic annihilator of a polynomial, of annihilators of rational functions as well as complex powers of polynomials. We analyze algorithms for local Bernstein–Sato polynomials and also algorithms, recovering any kind of Bernstein–Sato polynomial from partial knowledge of its roots. We address a novel way to compute the Bernstein–Sato polynomial for an affine variety algorithmically. All the carefully selected nontrivial examples, which we present, have been computed with our implementation. We also address such applications as the computation of a zeta-function for certain integrals and revealing the algebraic dependence between pairwise commuting elements.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.