GRASP is a multi-start metaheuristic for combinatorial optimization problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. An intensification … Read more
GRASP (Greedy Randomized Adaptive Search Procedures) is a multistart metaheuristic for producing good-quality solutions of combinatorial optimization problems. Each GRASP iteration is usually made up of a construction phase, where a feasible solution is constructed, and a local search phase which starts at the constructed solution and applies iterative improvement until a locally optimal solution … Read more
Experience has shown that a crafted combination of concepts of different metaheuristics can result in robust combinatorial optimization schemes and produce higher solution quality than the individual metaheuristics themselves, especially when solving difficult real-world combinatorial optimization problems. This chapter gives an overview of different ways to hybridize GRASP (Greedy Randomized Adaptive Search Procedures) to create … Read more
The aim of this paper is to give a survey of some basic theory of semi-infinite programming. In particular, we discuss various approaches to derivations of duality, discretization and first and second order optimality conditions. Some of the surveyed results are well known while others seem to be less noticed in that area of research. … Read more
Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more
Focusing on what an optimization problem may comply with, the so-called convergence conditions have been proposed and sequentially a stochastic optimization algorithm named as DSZ algorithm is presented in order to deal with both unconstrained and constrained optimizations. Its principle is discussed in the theoretical model of DSZ algorithm, from which we present a practical … Read more
We consider an implementation of the recursive multilevel trust-region algorithm proposed by Gratton, Mouffe, Toint, Weber (2008) for bound-constrained nonlinear problems, and provide numerical experience on multilevel test problems. A suitable choice of the algorithm’s parameters is identified on these problems, yielding a satisfactory compromise between reliability and efficiency. The resulting default algorithm is then … Read more
We describe computational procedures to solve a wide-ranging class of stochastic programs with chance constraints where the random components of the problem are discretely distributed. Our procedures are based on a combination of Lagrangian relaxation and scenario decomposition, which we solve using a novel variant of Rockafellar and Wets’ progressive hedging algorithm. Experiments demonstrate the … Read more
We review several (and provide new) results on the theory of moments, sums of squares and basic semi-algebraic sets when convexity is present. In particular, we show that under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to … Read more
In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … Read more