Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire

TB4 Optimisation globale I / Global Optimization I

3 mai 2011 13h30 – 15h10

Salle: Cogeco

Présidée par Charles Audet

4 présentations

• 13h30 - 13h55

A New Branching Strategy for Non-Convex Quadratic Programs with Non-Convex Quadratic Constraints

• Anthony Guillou, prés., GERAD - HEC Montréal
• Pierre Hansen, HEC Montréal
• Sylvain Perron, GERAD, HEC Montréal

Non-convex quadratic programs with non-convex quadratic constraints can be solved by the exact method based on the branch and cut algorithm of Audet et al.(2000). The algorithm, however, may lead to solution not necessarily strictly feasible. We present a new branching strategy improving the control on constraint feasibility.

• 13h55 - 14h20

A Simple Finite Simplicial Covering Algorithm for Concave Minimization Over a Polytope

• Christophe Meyer, prés., HEC Montréal

A simple, finite simplicial branch-and-bound algorithm is proposed for minimizing a concave function over a polytope. The algorithm requires the evaluation of the objective function only at extreme points of the polytope and of the initial simplex, which makes it particularly suitable when the function is costly to evaluate. Some preliminary computational results will be presented.

• 14h20 - 14h45

Best Proximity Point Theorems: Optimization and Approximation

• Sadiq Basha, prés., Anna University

Many mathematical problems can be formulated as a fixed point equation of form Tx=x where T is some suitable self-mapping. However, if T is not a self-mapping, the equation Tx=x does not necessarily have a solution. In such circumstances, one contemplates to find an approximate solution that is optimal in some sense. Indeed, in the setting of metric spaces, if T is a non-self mapping from A to B, then one seeks an approximate solution x in A such that the error d(x,Tx) is minimum. Considering the fact that d(x,Tx) is at least d(A,B), a best proximity point theorem investigates the existence of an approximate solution x such that d(x,Tx) attains the least possible value d(A,B). Essentially, a best proximity point theorem deals with the global minimization of the real valued function that maps every element x in A to d(x,Tx). The purpose of this article is to establish some interesting best proximity point theorems for generalized proximal contractions, thereby yielding an optimal approximate solution to some equations of form Tx=x where T is a generalized proximal contraction.

• 14h45 - 15h10

An Iterated Tabu Search for the Design of Energy Efficient Digital Filter with Finite Response

• Katayoon Moazzami, École Polytechnique de Montréal
• Marc Joliveau, prés., École Polytechnique de Montréal
• Michel Gendreau, Polytechnique Montréal
• François Gagnon, École de technologie supérieure

The presentation introduces an iterated tabu search based on a ruin and recreate principle, that designs finite response multiplierless digital filters with a free structure. The results show that the method construct circuits that reach the same level of performance than classical FIR filters, while using only the quantity of adders implied by traditional circuit architectures with multipliers.