Transposition theorems and qualification-free optimality conditions

New theorems of the alternative for polynomial constraints (based on the Positivstellensatz from real algebraic geometry) and for linear constraints (generalizing the transposition theorems of Motzkin and Tucker) are proved. Based on these, two Karush-John optimality conditions — holding without any constraint qualification — are proved for single- or multi-objective constrained optimization problems. The first … Read more

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note we show that the SQO problem may be reformulated as an (exponentially sized) linear program. Citation … Read more

A PTAS for the minimization of polynomials of fixed degree over the simplex

We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

Jordan-algebraic aspects of nonconvex optimization over symmetric cones

We illustrate the usefulness of Jordan-algebraic technique for nonconvex optimization by considering a potential-reduction algorithm for a nonconvex quadratic function over the domain obtained as the intersection of a symmetric cone with an affine subspace Citation Preprint, September,2004 Article Download View Jordan-algebraic aspects of nonconvex optimization over symmetric cones

Constrained Global Optimization with Radial Basis Functions

Response surface methods show promising results for global optimization of costly non convex objective functions, i.e. the problem of finding the global minimum when there are several local minima and each function value takes considerable CPU time to compute. Such problems often arise in industrial and financial applications, where a function value could be a … Read more

Convergence Analysis of the DIRECT Algorithm

The DIRECT algorithm is a deterministic sampling method for bound constrained Lipschitz continuous optimization. We prove a subsequential convergence result for the DIRECT algorithm that quantifies some of the convergence observations in the literature. Our results apply to several variations on the original method, including one that will handle general constraints. We use techniques from … Read more

On the Globally Concavized Filled Function Method

In this paper we present a new definition on the globally concavized filled function for the continuous global minimization problem, which was modified from that by Ge [3]. A new class of globally concavized filled functions are constructed. These functions contain two easily determinable parameters, which are not dependent on the radius of the basin … Read more

A Simplicial Branch-and-Bound Algorithm for Solving Quadratically Constrained Quadratic Programs

We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be … Read more

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more

Semidefinite Approximations for Global Unconstrained Polynomial Optimization

We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more