Search

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases. [ABSTRACT FROM AUTHOR]

We present a modification of the DIRECT (DIviding RECTangles) 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 and unavailable derivatives. DIRECT performs a sampling of the feasible domain over a set of points that becomes dense in the limit, thus ensuring the everywhere dense convergence; however, it becomes ineffective on significant instances of the problem under consideration, because it tends to produce a uniform coverage of the feasible domain, by oversampling regions that are far from the optimal solution. DIRECT has been modified by embodying information provided by a suitable discretization of the feasible domain, based on the signal theory, which takes into account the variability of the objective function. Numerical experiments show that DIRECT-G largely outperforms DIRECT and the grid search, the latter being the reference algorithm in the astrophysics community. Furthermore, DIRECT-G is comparable with a genetic algorithm specifically developed for the problem. However, DIRECT-G inherits the convergence properties of DIRECT, whereas the genetic algorithm has no guarantee of convergence. [ABSTRACT FROM AUTHOR]

In this article, we consider a particular class of nonlinear mixed variable optimization problems where the structure and the number of variables of the problem depend on the values of some discrete variables. The peculiarity of this class is that, for fixed values of the integer variables, the corresponding continuous optimization problem contains no constraints and a large number of variables. For such a class of problems we propose two minimization algorithms and prove their global convergence properties. [ABSTRACT FROM AUTHOR]