Entity

Time filter

Source Type

Belhaiza S.,King Fahd University of Petroleum and Minerals | Audet C.,Ecole Polytechnique de Montreal | Hansen P.,GERAD
Automatica | Year: 2012

In this paper, we introduce the notion of set of -proper equilibria for a bimatrix game. We define a 01 mixed quadratic program to generate a sequence of -proper Nash equilibria and show that the optimization results provide reliable indications on strategy profiles that could be used to generate proper equilibria analytically. This approach can be generalized in order to find at least one proper equilibrium for any bimatrix game. Finally, we define another 01 mixed quadratic program to identify non-proper extreme Nash equilibria. © 2011 Published by Elsevier Ltd. All rights reserved. Source

Anjos M.F.,GERAD | Anjos M.F.,Ecole Polytechnique de Montreal | Chang X.-W.,McGill University | Ku W.-Y.,University of Toronto
Journal of Global Optimization | Year: 2014

The integer least squares problem is an important problem that arises in numerous applications.We propose a real relaxation-based branch-and-bound (RRBB) method for this problem. First, we define a quantity called the distance to integrality, propose it as a measure of the number of nodes in the RRBB enumeration tree, and provide computational evidence that the size of the RRBB tree is proportional to this distance. Since we cannot know the distance to integrality a priori, we prove that the norm of the Moore-Penrose generalized inverse of the matrix of coefficients is a key factor for bounding this distance, and then we propose a preconditioning method to reduce this norm using lattice reduction techniques. We also propose a set of valid box constraints that help accelerate the RRBB method. Our computational results showthat the proposed preconditioning significantly reduces the size of the RRBB enumeration tree, that the preconditioning combined with the proposed set of box constraints can significantly reduce the computational time of RRBB, and that the resulting RRBB method can outperform the Schnorr and Eucher method, a widely used method for solving integer least squares problems, on some types of problem data. © Springer Science+Business Media New York 2014. Source

Talgorn B.,GERAD | Le Digabel S.,McGill University | Kokkolaras M.,Ecole Polytechnique de Montreal
Journal of Mechanical Design, Transactions of the ASME | Year: 2015

Typical challenges of simulation-based design optimization include unavailable gradients and unreliable approximations thereof, expensive function evaluations, numerical noise, multiple local optima, and the failure of the analysis to return a value to the optimizer. One possible remedy to alleviate these issues is to use surrogate models in lieu of the computational models or simulations and derivative-free optimization algorithms. In this work, we use the R dynaTree package to build statistical surrogates of the blackboxes and the direct search method for derivative-free optimization. We present different formulations for the surrogate problem (SP) considered at each search step of the mesh adaptive direct search (MADS) algorithm using a surrogate management framework. The proposed formulations are tested on 20 analytical benchmark problems and two simulation-based multidisciplinary design optimization (MDO) problems. Numerical results confirm that the use of statistical surrogates in MADS improves the efficiency of the optimization algorithm. Copyright © 2015 by ASME. Source

This technical note presents a continuum approach to a non-Gaussian initial mean consensus problem via Mean Field (MF) stochastic control theory. In this problem formulation: (i) each agent has simple stochastic dynamics with inputs directly controlling its state's rate of change and (ii) each agent seeks to minimize by continuous state feedback its individual discounted cost function involving the mean of the states of all other agents. For this dynamic game problem, a set of coupled deterministic (Hamilton-Jacobi-Bellman and Fokker-Planck-Kolmogorov) equations is derived approximating the stochastic system of agents as the population size goes to infinity. In a finite population system (analogous to the MF LQG framework): (i) the resulting decentralized MF control strategies possess an $\epsilon N-Nash equilibrium property where$\epsilon N goes to zero as the population size $N$ approaches infinity and (ii) these MF control strategies steer each individual's state toward the initial state population mean which is reached asymptotically as time goes to infinity. Hence, the system with decentralized MF control strategies reaches mean-consensus on the initial state population mean asymptotically as time goes to infinity. © 1963-2012 IEEE. Source