We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a … Read more
We first show that a continuous function “f” is nonnegative on a closed set K if and only if (countably many) moment matrices of some signed measure dnu = fdmu are all positive semidefinite (if K is compact mu is an arbitrary finite Borel measure with support exactly K). In particular, we obtain a convergent … Read more
For a given linear matrix function $A_1 – B_1XB^*_1$, where $X$ is a variable Hermitian matrix, this paper derives a group of closed-form formulas for calculating the global maximum and minimum ranks and inertias of the matrix function subject to a pair of consistent matrix equations $B_2XB^*_2 = A_2$ and $B_3XB_3^* = A_3$. As applications, … Read more
We consider the inverse optimization problem associated with the polynomial program $f^*=\min \{f(x):x\inK\}$ and a given current feasible solution $y\in K$. We provide a numerical scheme to compute an inverse optimal solution. That is, we compute a polynomial $\tilde{f}$ (which may be of same degree as $f$ if desired) with the following properties: (a) $y$ … Read more
In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more
The $\epsilon$-pseudospectral abscissa $\alpha_\epsilon$ and radius $\rho_\epsilon$ of an n x n matrix are respectively the maximal real part and the maximal modulus of points in its $\epsilon$-pseudospectrum, defined using the spectral norm. It was proved in [A.S. Lewis and C.H.J. Pang. Variational analysis of pseudospectra. SIAM Journal on Optimization, 19:1048-1072, 2008] that for fixed … Read more
In this note we establish a relation between two bounds for convex maximization problems, the one based on a concavity cut, and the surrogate dual bound. Both bounds have been known in the literature for a few decades but, to the authors’ knowledge, the relation between them has not been previously observed in the literature. … Read more
We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more
This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules … Read more
In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional … Read more