We provide a specific representation of convex polynomials nonnegative on a convex (not necessarily compact) basic closed semi-algebraic set $K$ of $R^n$. Namely, they belong to a specific subset of the quadratic module generated by the concave polynomials that define $K$. Citation To appear in Archiv der Mathematik Article Download View Representation of nonnegative convex … Read more
We review several (and provide new) results on the theory of moments, sums of squares and basic semi-algebraic sets when convexity is present. In particular, we show that under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to … Read more
In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … Read more
The problem of approximately factoring a real or complex multivariate polynomial $f$ seeks minimal perturbations $\Delta f$ to the coefficients of the input polynomial $f$ so that the deformed polynomial $f + \Delta f$ has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomials that has non-trivial factors. (see … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more
Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more
In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more
We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive … Read more
In this paper we present the algorithmic framework and practical aspects of implementing a parallel version of a primal-dual semidefinite programming solver on a distributed memory computer cluster. Our implementation is based on the CSDP solver and uses a message passing interface (MPI), and the ScaLAPACK library. A new feature is implemented to deal with … Read more
This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more