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
Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A {\em probing} algorithm is a bound-tightening procedure that explores the consequences of restricting a variable to a subinterval with the goal of tightening its bounds. We propose a variant of probing where exploration is based on iteratively applying a … 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
We present a modification of the DIRECT algorithm, called DIRECT-G, to solve a box-constrained global optimization problem arising in the detection of gravitational waves emitted by coalescing binary systems of compact objects. This is a hard problem since the objective function is highly nonlinear and expensive to evaluate, has a huge number of local extrema … Read more
The inertia of a Hermitian matrix is defined to be a triplet composed by the numbers of the positive, negative and zero eigenvalues of the matrix counted with multiplicities, respectively. In this paper, we give various closed-form formulas for the maximal and minimal values for the rank and inertia of the Hermitian expression $A + … Read more
Identifying and exploiting classes of nonconvex constraints whose feasible region is convex after branching can reduce the time to compute global solutions for nonlinear optimization problems. We develop techniques for identifying quadratic and nonlinear constraints whose feasible region can be represented as the union of a finite number of second-order cones, and we provide necessary … Read more
Research in optimization algorithm design is often accompanied by benchmarking a new al- gorithm. Some benchmarking is done as a proof-of-concept, by demonstrating the new algorithm works on a small number of dicult test problems. Alternately, some benchmarking is done in order to demonstrate that the new algorithm in someway out-performs previous methods. In this … Read more