Extrema of a Real Polynomial

In this paper, we investigate critical point and extrema structure of a multivariate real polynomial. We classify critical surfaces of a real polynomial f into three classes: repeated, intersected and primal critical surfaces. These different critical surfaces are defined by some essential factors of f, where an essential factor of f means a polynomial factor of f–c ₀, for some constant c ₀. We show that the degree sum of repeated critical surfaces is at most d–1, where d is the degree of f. When a real polynomial f has only two variables, we give the minimum upper bound for the number of other isolated critical points even when there are nondegenerate critical curves, and the minimum upper bound of isolated local extrema even when there are saddle curves. We show that a normal polynomial has no odd degree essential factors, and all of its even degree essential factors are normal polynomials, up to a sign change. We show that if a normal quartic polynomial f has a normal quadratic essential factor, a global minimum of f can be either easily found, or located within the interior(s) of one or two ellipsoids. We also show that a normal quartic polynomial can have at most one local maximum.     

The geometry of the asymptotics of polynomial maps

The aim of this paper is to develop a theory for the asymptotic behavior of polynomials and of polynomial maps overR and overC and to apply it to the Jacobian conjecture. This theory gives a unified frame for some results on polynomial maps that were not related before. A well known theorem of J. Hadamard gives a necessary and sufficient condition on a local diffeomorphismf: R ⁿ →R ⁿ to be a global diffeomorphism. In order to show thatf is a global diffeomorphism it suffices to exclude the existence of asymptotic values forf. The real Jacobian conjecture was shown to be false by S. Pinchuk. Our first application is to understand his construction within the general theory of asymptotic values of polynomial maps and prove that there is no such counterexample for the Jacobian conjecture overC. In a second application we reprove a theorem of Jeffrey Lang which gives an equivalent formulation of the Jacobian conjecture in terms of Newton polygons. This generalizes a result of Abhyankar. A third application is another equivalent formulation of the Jacobian conjecture in terms of finiteness of certain polynomial rings withinC[U, V]. The theory has a geometrical aspect: we define and develop the theory of etale exotic surfaces. The simplest such surface corresponds to Pinchuk's construction in the real case. In fact, we prove one more equivalent formulation of the Jacobian conjecture using etale exotic surfaces. We consider polynomial vector fields on etale exotic surfaces and explore their properties in relation to the Jacobian conjecture. In another application we give the structure of the real variety of the asymptotic values of a polynomial mapf: R ² →R ² .     

Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization

We introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches in global optimization are based on convex relaxations. Thanks to the fact that only simple bound constraints are present, minimizing the separable underestimator can be done very quickly. The underestimators are computed monomial-wise after the original polynomial has been shifted. We show that such valid underestimators exist and their degree can be bounded when the degree of the polynomial objective function is bounded, too. For the quartic case, all optimal monomial underestimators are determined analytically. We implemented and tested the branch-and-bound algorithm where these underestimators are hardcoded. The comparison against standard global optimization and polynomial optimization solvers clearly shows that our method outperforms the others, the only exception being the binary case where, though, it is still competitive. Moreover, our branch-and-bound approach suffers less in case of dense polynomial objective function, i.e., in case of polynomials having a large number of monomials. This paper is an extended and revised version of the preliminary paper [4].     

On the convergence rate of grid search for polynomial optimization over the simplex

We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator \({r} \in \mathbb {N}\). It was shown in De Klerk et al. (SIAM J Optim 25(3):1498–1514, 2015) that the accuracy of this approximation depends on r as \(O(1/r^2)\) if there exists a rational global minimizer. In this note we show that the rational minimizer condition is not necessary to obtain the \(O(1/r^2)\) bound.     

A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

An Upper Bound for the Excessive Index of an r‐Graph

We construct a family of r‐graphs having a minimum 1‐factor cover of cardinality (disproving a conjecture of Bonisoli and Cariolaro, Birkhäuser, Basel, 2007, 73–84). Furthermore, we show the equivalence between the statement that is the best possible upper bound for the cardinality of a minimum 1‐factor cover of an r‐graph and the well‐known generalized Berge–Fulkerson conjecture.     

Prime filtrations and Stanley decompositions of squarefree modules and Alexander duality

In this paper we study how prime filtrations and squarefree Stanley decompositions of squarefree modules over the polynomial ring and over the exterior algebra behave with respect to Alexander duality. The results which we obtained suggest a lower bound for the regularity of a \mathbb Zⁿ{\mathbb {Z}^n}-graded module in terms of its Stanley decompositions. For squarefree modules this conjectured bound is a direct consequence of Stanley’s conjecture on Stanley decompositions. We show that for pretty clean rings of the form R/I, where I is a monomial ideal, and for monomial ideals with linear quotient our conjecture holds.     

Global optimization of rational functions: a semidefinite programming approach

We consider the problem of global minimization of rational functions on (unconstrained case), and on an open, connected, semi-algebraic subset of , or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [16]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

A polynomial class of Markus–Yamabe counterexamples and examples in ℝ3

We give a polynomial family of counterexamples to the Markus–Yamabe conjecture which contains and generalizes that of Cima–Gasull–Mañosas. Furthermore, we construct a new class of polynomial vector fields in ?³ having the origin as a global attractor which satisfy the Markus–Yamabe hypotheses.     

A note on some embedding problems for oriented graphs

We conjecture that every oriented graph G on n vertices with δ⁺(G), δ^?(G)≥5n/12 contains the square of a Hamilton cycle. We also give a conjectural bound on the minimum semidegree which ensures a perfect packing of transitive triangles in an oriented graph. A link between Ramsey numbers and perfect packings of transitive tournaments is also considered. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 330–336, 2012     

The de Bruijn–Erd?s theorem for hypergraphs

Fix integers n ≥ r ≥ 2. A clique partition of ${{[n] \choose r}}$ is a collection of proper subsets ${A_1, A_2, \ldots, A_t \subset [n]}$ such that ${\bigcup_i{A_i \choose r}}$ is a partition of ${{[n]\choose r}}$ . Let cp(n, r) denote the minimum size of a clique partition of ${{[n] \choose r}}$ . A classical theorem of de Bruijn and Erd?s states that cp(n, 2) =?n. In this paper we study cp(n, r), and show in general that for each fixed r ≥ 3, $${\rm cp}(n, r) \geq (1 + o(1))n^{r/2} \quad \quad {\rm as} \, \, n \rightarrow \infty.$$ We conjecture cp(n, r) =?(1 +?o(1))n ^r/2. This conjecture has already been verified (in a very strong sense) for r = 3 by Hartman–Mullin–Stinson. We give further evidence of this conjecture by constructing, for each r ≥ 4, a family of (1?+?o(1))n ^r/2 subsets of [n] with the following property: no two r-sets of [n] are covered more than once and all but o(n ^r ) of the r-sets of [n] are covered. We also give an absolute lower bound ${{\rm cp}(n, r) \geq {n \choose r}/{q + r - 1 \choose r}}$ when n =?q ² + q +?r ? 1, and for each r characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of cp(n, r) to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.     

On connectedness of sets in the real spectra of polynomial rings

Let R be a real closed field. The Pierce–Birkhoff conjecture says that any piecewise polynomial function f on R ⁿ can be obtained from the polynomial ring R[x ₁,..., x _n ] by iterating the operations of maximum and minimum. The purpose of this paper is threefold. First, we state a new conjecture, called the Connectedness conjecture, which asserts, for every pair of points , the existence of connected sets in the real spectrum of R[x ₁,..., x _n ], satisfying certain conditions. We prove that the Connectedness conjecture implies the Pierce–Birkhoff conjecture. Secondly, we construct a class of connected sets in the real spectrum which, though not in itself enough for the proof of the Pierce–Birkhoff conjecture, is the first and simplest example of the sort of connected sets we really need, and which constitutes the first step in our program for a proof of the Pierce–Birkhoff conjecture in dimension greater than 2. Thirdly, we apply these ideas to give two proofs that the Connectedness conjecture (and hence also the Pierce–Birkhoff conjecture in the abstract formulation) holds locally at any pair of points , one of which is monomial. One of the proofs is elementary while the other consists in deducing this result as an immediate corollary of the main connectedness theorem of this paper.     

On the number of invariant lines for polynomial systems

In this paper we will revise the mistakes in a previous paper of Zhang Xikang (Number of integral lines of polynomial systems of degree three and four, J. Nanjing Univ. Math. Biquarterly, Supplement, 1993, pp. 209-212) for the proof of the conjecture on the maximum number of invariant straight lines of cubic and quartic polynomial differential systems; and also prove the conjecture in a previous paper of the second author (Qualitative theory of polynomial differential systems, Shanghai Science-Technical Publishers, Shanghai, 1995, p. 474) for a certain special case of the degree polynomial systems. Furthermore, we will prove that cubic and quartic differential systems have invariant straight lines along at most six and nine different directions, respectively, and also show that the maximum number of the directions can be obtained.

     

Geometric proof of a conjecture of Fulton

We give a geometric proof of a conjecture of Fulton on the multiplicities of irreducible representations in a tensor product of irreducible representations for GL(r).     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

New bounds on the unconstrained quadratic integer programming problem

We consider the maximization for a given symmetric . It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV ^T where with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem . In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.     

Approximation of conic section by quartic Bzier curve with endpoints continuity condition

A new method for approximation of conic section by quartic B′ezier curve is presented, based on the quartic B′ezier approximation of circular arcs. Here we give an upper bound of the Hausdorff distance between the conic section and the approximation curve, and show that the error bounds have the approximation order of eight. Furthermore, our method yields quartic G2 continuous spline approximation of conic section when using the subdivision scheme,and the effectiveness of this method is demonstrated by some numerical examples.     

On the global minimum in a balanced circular packing problem

The paper considers balanced packing problem of a given family of circles into a larger circle of the minimal radius as a multiextremal nonlinear programming problem. We reduce the problem to unconstrained minimization problem of a nonsmooth function by means of nonsmooth penalty functions. We propose an efficient algorithm to search for local extrema and an algorithm for improvement of the lower bound of the global minimum value of the objective function. The algorithms employ nonsmooth optimization methods based on Shor’s r-algorithm. Computational results are given.