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
SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more
The problem of finding the optimal placement of $N$ identical, non overlapping, circles with maximum radius in the unit square is a well known challenge both in classical geometry and in optimization. A database of putative optima is currently maintained at \url{www.packomania.com}. Recently, through clever use of an extremely simple global optimization method, we succeeded … Read more
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
The DIRECT algorithm was motivated by a modification to Lipschitzian optimization. The algorithm begins its search by sampling the objective function at the midpoint of an interval, where this function attains its lowest value, and then divides this interval by trisecting it. One of its weakness is that if a global minimum lies at the … Read more
Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. To … Read more
Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. In … Read more
This article presents a concise review of the scientific–technical computing system Maple and its application potentials in Operations Research, systems modeling and optimization. The primary emphasis is placed on nonlinear optimization models that may involve complicated functions, and/or may have multiple – global and local – optima. We introduce the Global Optimization Toolbox to solve … Read more
We present a review of several professional software products that serve to analyze and solve nonlinear (global and local) optimization problems across a variety of hardware and software environments. The product versions discussed have been implemented for compiler platforms, spreadsheets, algebraic (optimization) modeling languages, and for integrated scientific-technical computing systems. The discussion highlights some of … Read more
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