ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions

We present a new derivative-free algorithm, ORBIT, for unconstrained local optimization of computationally expensive functions. A trust-region framework using interpolating Radial Basis Function (RBF) models is employed. The RBF models considered often allow ORBIT to interpolate nonlinear functions using fewer function evaluations than the polynomial models considered by present techniques. Approximation guarantees are obtained by … Read more

A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more

Parimutuel Betting on Permutations

We focus on a permutation betting market under parimutuel call auction model where traders bet on the final ranking of n candidates. We present a Proportional Betting mechanism for this market. Our mechanism allows the traders to bet on any subset of the n x n ‘candidate-rank’ pairs, and rewards them proportionally to the number … Read more

On sublattice determinants in reduced bases

We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more

First-order algorithm with (ln(1/\epsilon))$ convergence for $\epsilonhBcequilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, … Read more

Smoothing techniques for computing Nash equilibria of sequential games

We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for … Read more

Linear Programming for Mechanism Design: An Application to Bidder Collusion at First-Price Auctions

We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more

The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: a comparative study

In this paper, we propose a new recombination operator and test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the two following stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, … Read more

Information Relaxations and Duality in Stochastic Dynamic Programs

We describe a dual approach to stochastic dynamic programming: we relax the constraint that the chosen policy must be temporally feasible and impose a penalty that punishes violations of temporal feasibility. We describe the theory underlying this dual approach and demonstrate its use in dynamic programming models related to inventory control, option pricing, and oil … Read more

Newton’s Method for Multiobjective Optimization

We propose an extension of Newton’s Method for unconstrained multiobjective optimization (multicriteria optimization). The method does not scalarize the original vector optimization problem, i.e. we do not make use of any of the classical techniques that transform a multiobjective problem into a family of standard optimization problems. Neither ordering information nor weighting factors for the … Read more