Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric …
Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric univariate polynomial non-negative on the unit circle can be decomposed as a Hermitian square with complex coefficients. Here we focus on the case of polynomials with Gaussian integer coefficients, i.e., with real and imaginary parts being integers.
In this paper, we investigate the topological structure of solution sets of monotone vector variational inequalities (VVIs). We show that if the weak Pareto solution set of a monotone VVI …
In this paper, we investigate the topological structure of solution sets of monotone vector variational inequalities (VVIs). We show that if the weak Pareto solution set of a monotone VVI is disconnected, then each connected component of the set is unbounded. Similarly, this property holds for the proper Pareto solution set. Two open questions on the topological structure of the solution sets of (symmetric) monotone VVIs are raised at the end of the paper.
Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of …
Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates.
In this paper, we aim at computing all local minimizers of a polynomial optimization problem under genericity conditions. By using a technique in computer algebra, we provide a univariate representation …
In this paper, we aim at computing all local minimizers of a polynomial optimization problem under genericity conditions. By using a technique in computer algebra, we provide a univariate representation for the set of local minimizers. In particular, for an unconstrained problem, the coordinates of all local minimizers can be represented by several univariate polynomial equalities and one univariate polynomial matrix inequality. We also develop the technique for constrained problems having equality constraints. Based on the above technique, we design algorithms to enumerate the local minimizers. At the end of the paper, we provide some experimental examples.
Abstract In this paper, we propose criteria for unboundedness of the images of set-valued mappings having closed graphs in Euclidean spaces. We focus on mappings whose domains are non-closed or …
Abstract In this paper, we propose criteria for unboundedness of the images of set-valued mappings having closed graphs in Euclidean spaces. We focus on mappings whose domains are non-closed or whose values are connected. These criteria allow us to see structural properties of solutions in vector optimization, where solution sets can be considered as the images of solution mappings associated to specific scalarization methods. In particular, we prove that if the domain of a certain solution mapping is non-closed, then the weak Pareto solution set is unbounded. Furthermore, for a quasi-convex problem, we demonstrate two criteria to ensure that if the weak Pareto solution set is disconnected then each connected component is unbounded.
By using the squared slack variables technique, we show that a general polynomial complementarity problem can be formulated as a system of polynomial equations. Thus, the solution set of such …
By using the squared slack variables technique, we show that a general polynomial complementarity problem can be formulated as a system of polynomial equations. Thus, the solution set of such a problem is the image of a real algebraic set under a certain projection. This paper points out that, generically, this polynomial system has finitely many complex zeros. In such a case, we use techniques from symbolic computation to compute a univariate representation of the solution set. Consequently, univariate representations of special solutions, such as least-norm and sparse solutions, are obtained. After that, enumerating solutions boils down to solving problems governed by univariate polynomials. We also provide some experiments on small-scale problems with worst-case scenarios. At the end of the paper, we propose a method for computing approximate solutions to copositive polynomial complementarity problems that may have infinitely many solutions.
By using the squared slack variables technique, we show that a general polynomial complementarity problem can be formulated as a system of polynomial equations. Thus, the solution set of such …
By using the squared slack variables technique, we show that a general polynomial complementarity problem can be formulated as a system of polynomial equations. Thus, the solution set of such a problem is the image of a real algebraic set under a certain projection. This paper points out that, generically, this polynomial system has finitely many complex zeros. In such a case, we use techniques from symbolic computation to compute a univariate representation of the solution set. Consequently, univariate representations of special solutions, such as least-norm and sparse solutions, are obtained. After that, enumerating solutions boils down to solving problems governed by univariate polynomials. We also provide some experiments on small-scale problems with worst-case scenarios. At the end of the paper, we propose a method for computing approximate solutions to copositive polynomial complementarity problems that may have infinitely many solutions.
Abstract In this paper, we propose criteria for unboundedness of the images of set-valued mappings having closed graphs in Euclidean spaces. We focus on mappings whose domains are non-closed or …
Abstract In this paper, we propose criteria for unboundedness of the images of set-valued mappings having closed graphs in Euclidean spaces. We focus on mappings whose domains are non-closed or whose values are connected. These criteria allow us to see structural properties of solutions in vector optimization, where solution sets can be considered as the images of solution mappings associated to specific scalarization methods. In particular, we prove that if the domain of a certain solution mapping is non-closed, then the weak Pareto solution set is unbounded. Furthermore, for a quasi-convex problem, we demonstrate two criteria to ensure that if the weak Pareto solution set is disconnected then each connected component is unbounded.
Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of …
Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates.
In this paper, we aim at computing all local minimizers of a polynomial optimization problem under genericity conditions. By using a technique in computer algebra, we provide a univariate representation …
In this paper, we aim at computing all local minimizers of a polynomial optimization problem under genericity conditions. By using a technique in computer algebra, we provide a univariate representation for the set of local minimizers. In particular, for an unconstrained problem, the coordinates of all local minimizers can be represented by several univariate polynomial equalities and one univariate polynomial matrix inequality. We also develop the technique for constrained problems having equality constraints. Based on the above technique, we design algorithms to enumerate the local minimizers. At the end of the paper, we provide some experimental examples.
Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric …
Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric univariate polynomial non-negative on the unit circle can be decomposed as a Hermitian square with complex coefficients. Here we focus on the case of polynomials with Gaussian integer coefficients, i.e., with real and imaginary parts being integers.
In this paper, we investigate the topological structure of solution sets of monotone vector variational inequalities (VVIs). We show that if the weak Pareto solution set of a monotone VVI …
In this paper, we investigate the topological structure of solution sets of monotone vector variational inequalities (VVIs). We show that if the weak Pareto solution set of a monotone VVI is disconnected, then each connected component of the set is unbounded. Similarly, this property holds for the proper Pareto solution set. Two open questions on the topological structure of the solution sets of (symmetric) monotone VVIs are raised at the end of the paper.