It is shown that, contrary to a claim of [D. E. Finkel, and C. T. Kelley, Additive scaling and the DIRECT algorithm, J. Glob. Optim. 36 (2006) 597-608], it is possible to divide the smallest hypercube which contains the low function value by considering hyperrectangles whose points are located on the diagonal of the center … Read more
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
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
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
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
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
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
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
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
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