Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares

We study ellipsoid bounds for the solutions of polynomial systems of equalities and inequalities. The variable μ can be considered as parameters perturbing the solution x. For example, bounding the zeros of a system of polynomials whose coefficients depend on parameters is a special case of this problem. Our goal is to find minimum ellipsoid bounds just for x. Using theorems from real algebraic geometry, the ellipsoid bound can be found by solving a particular polynomial optimization problem with sums of squares (SOS) techniques. Some numerical examples are also given.     

Extremal polynomials for obtaining bounds for spherical codes and designs

We investigate two extremal problems for polynomials giving upper bounds for spherical codes and for polynomials giving lower bounds for spherical designs, respectively. We consider two basic properties of the solutions of these problems. Namely, we estimate from below the number of double zeros and find zero Gegenbauer coefficients of extremal polynomials. Our results allow us to search effectively for such solutions using a computer. The best polynomials we have obtained give substantial improvements in some cases on the previously known bounds for spherical codes and designs. Some examples are given in Section 6. This research was partially supported by the Bulgarian NSF under Contract I-35/1994.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

The ERES method for computing the approximate GCD of several polynomials

The computation of the greatest common divisor (GCD) of a set of polynomials has interested the mathematicians for a long time and has attracted a lot of attention in recent years. A challenging problem that arises from several applications, such as control or image and signal processing, is to develop a numerical GCD method that inherently has the potential to work efficiently with sets of several polynomials with inexactly known coefficients. The presented work focuses on: (i) the use of the basic principles of the ERES methodology for calculating the GCD of a set of several polynomials and defining approximate solutions by developing the hybrid implementation of this methodology. (ii) the use of the developed framework for defining the approximate notions for the GCD as a distance problem in a projective space to develop an optimization algorithm for evaluating the strength of different ad-hoc approximations derived from different algorithms. The presented new implementation of ERES is based on the effective combination of symbolic–numeric arithmetic (hybrid arithmetic) and shows interesting computational properties for the approximate GCD problem. Additionally, an efficient implementation of the strength of an approximate GCD is given by exploiting some of the special aspects of the respective distance problem. Finally, the overall performance of the ERES algorithm for computing approximate solutions is discussed.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

The Moment Problem Associated with the q -Laguerre Polynomials

Abstract. We consider the indeterminate Stieltjes moment problem associated with the q -Laguerre polynomials. A transformation of the set of solutions, which has all the classical solutions as fixed points, is established and we present a method to construct, for instance, continuous singular solutions. The connection with the moment problem associated with the Stieltjes—Wigert polynomials is studied; we show how to come from q -Laguerre solutions to Stieltjes—Wigert solutions by letting the parameter α —> ∞ , and we explain how to lift a Stieltjes—Wigert solution to a q -Laguerre solution at the level of Pick functions. Based on two generating functions, expressions for the four entire functions from the Nevanlinna parametrization are obtained.     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

Optimale Fehlerabschätzungen mit dualen Funktionalen bei semilinearen Randwertaufgaben gewöhnlicher Differentialgleichungen

In Shampine [7] it is shown how to obtain variational error bounds for approximate solutions of boundary value problems for semilinear ordinary differential equations. These bounds are depending on a certain constantK, the existence of which is assumed. Our paper aims at practical computation; in order to get applicableL _∞-error bounds,K has to be computed explicitly. Using Gårding's inequality, we obtainK=K(?) depending on a positive parameter ?. In order to make these bounds efficient,K(?) will be optimized. In application only the maximal zeros of three polynomials have to be computed. Some numerical examples are given to compare the error bounds with the actual errors.     

Interpolation Wavelets in Boundary Value Problems

We propose and validate a simple numerical method that finds an approximate solution with any given accuracy to the Dirichlet boundary value problem in a disk for a homogeneous equation with the Laplace operator. There are many known numerical methods that solve this problem, starting with the approximate calculation of the Poisson integral, which gives an exact representation of the solution inside the disk in terms of the given boundary values of the required functions. We employ the idea of approximating a given 2π-periodic boundary function by trigonometric polynomials, since it is easy to extend them to harmonic polynomials inside the disk so that the deviation from the required harmonic function does not exceed the error of approximation of the boundary function. The approximating trigonometric polynomials are constructed by means of an interpolation projection to subspaces of a multiresolution analysis (approximation) with basis 2π-periodic scaling functions (more exactly, their binary rational compressions and shifts). Such functions were constructed by the authors earlier on the basis of Meyer-type wavelets; they are either orthogonal and at the same time interpolating on uniform grids of the corresponding scale or only interpolating. The bounds on the rate of approximation of the solution to the boundary value problem are based on the property ofMeyer wavelets to preserve trigonometric polynomials of certain (large) orders; this property was used for other purposes in the first two papers listed in the references. Since a numerical bound of the approximation error is very important for the practical application of the method, a considerable portion of the paper is devoted to this issue, more exactly, to the explicit calculation of the constants in the order bounds of the error known earlier.     

Distribution of polynomial discriminants modulo a prime

We obtain bounds of sums of additive characters with discriminants of polynomials over finite fields. We use these bounds to study the distribution of discriminants modulo a prime p.     

Survivable network design with shared-protection routing

In this paper we study the problem of designing a survivable telecommunication network with shared-protection routing. We develop a heuristic algorithm to solve this problem. Recent results in the area of global re-routing have been used to obtain very tight lower bounds for the problem. Our results indicate that in a majority of problem instances, the average gap between the heuristic solutions and the lower bounds is within 5%. Computational experience is reported on randomly generated problem instances with up to 35 nodes, 80 edges and 595 demand pairs and also on the instances available in SNDlib database.     

The nonexistence of spurious solutions to discrete,two-point boundary value problems

We investigate difference equations which arise as discrete approximations to two-point boundary value problems for systems of second-order, ordinary differential equations. We formulate conditions under which all solutions to the discrete problem satisfy certain a priori bounds which are independent of the step-size. As a result, the nonexistence of spurious solutions are guaranteed. Some existence and convergence theorems for solutions to the discrete problem are also presented.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

On the calculation of a membership function for the solution of a fuzzy linear optimization problem

In the present paper the fuzzy linear optimization problem (with fuzzy coefficients in the objective function) is considered. Recent concepts of fuzzy solution to the fuzzy optimization problem based on the level-cut and the set of Pareto optimal solutions of a multiobjective optimization problem are applied. Chanas and Kuchta suggested one approach to determine the membership function values of fuzzy optimal solutions of the fuzzy optimization problem, which is based on calculating the sum of lengths of certain intervals. The purpose of this paper is to determine a method for realizing this idea. We derive explicit formulas for the bounds of these intervals in the case of triangular fuzzy numbers and show that only one interval needs to be considered.     

Computing closely matching upper and lower bounds on textile nesting problems

We consider an industrial cutting problem in textile manufacturing and report on algorithms for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

Bivariate Gonarov polynomials and integer sequences

Univariate Gonarov polynomials arose from the Gonarov interpolation problem in numerical analysis.They provide a natural basis of polynomials for working with u-parking functions,which are integer sequences whose order statistics are bounded by a given sequence u.In this paper,we study multivariate Gonarov polynomials,which form a basis of solutions for multivariate Gonarov interpolation problem.We present algebraic and analytic properties of multivariate Gonarov polynomials and establish a combinatorial relation with integer sequences.Explicitly,we prove that multivariate Gonarov polynomials enumerate k-tuples of integers sequences whose order statistics are bounded by certain weights along lattice paths in Nk.It leads to a higher-dimensional generalization of parking functions,for which many enumerative results can be derived from the theory of multivariate Gonarov polynomials.     

The Betti polynomials of powers of an ideal

For an ideal I in a regular local ring or a graded ideal I in the polynomial ring we study the limiting behavior of as k goes to infinity. By Kodiyalam’s result it is known that β_i(S/I^k) is a polynomial for large k. We call these polynomials the Kodiyalam polynomials and encode the limiting behavior in their generating polynomial. It is shown that the limiting behavior depends only on the coefficients on the Kodiyalam polynomials in the highest possible degree. For these we exhibit lower bounds in special cases and conjecture that the bounds are valid in general. We also show that the Kodiyalam polynomials have weakly descending degrees and identify a situation where the polynomials all have the highest possible degree.