Iterative Minimization Schemes for Solving the Single Source Localization Problem

We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth and thus finding its global solution is in principal a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes … Read more

Stopping Rules for Box-Constrained Stochastic Global Optimization

We present three new stopping rules for Multistart based methods. The first uses a device that enables the determination of the coverage of the bounded search domain. The second is based on the comparison of asymptotic expectation values of observable quantities to the actually measured ones. The third offers a probabilistic estimate for the number … Read more

Semidefinite Representation of Convex Sets

Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more

Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming

We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that … Read more

Sufficient Conditions for a Real Polynomial to be a Sum of Squares

We provide explicit sufficient conditions for a polynomial $f$ to be a sum of squares (s.o.s.), linear in the coefficients of $f$. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most $2d$. We also provide a simple condition to ensure … Read more

Computable representations for convex hulls of low-dimensional quadratic forms

Let C be the convex hull of points {(1;x)(1,x’)| x \in F\subset R^n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. If n

Exploiting symmetries in SDP-relaxations for polynomial optimization

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization … Read more

Local versus Global Profit Maximization: The Case of Discrete Concave Production Functions

In this paper we show that for discrete concave functions, a local maximum need not be a global maximum. We also provide examples of discrete concave functions where this coincidence holds. As a direct consequence of this, we can establish the equivalence of local and global profit maximizers for an equivalent well-behaved production function that … Read more

Convergent SDP-relaxations in polynomial optimization with sparsity

We consider a polynomial programming problem P on a compact basic semi-algebraic set K described by m polynomial inequalities $g_j(X)\geq0$, and with polynomial criterion $f$. We propose a hierarchy of semidefinite relaxations in the spirit those of Waki et al. [9]. In particular, the SDP-relaxation of order $r$ has the following two features: (a) The … Read more

On the complexity of optimization over the standard simplex

We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on … Read more