About [q]-regularity properties of collections of sets

Categories Nonsmooth Optimization

We examine three primal space local Hoelder type regularity properties of finite collections of sets, namely, [q]-semiregularity, [q]-subregularity, and uniform [q]-regularity as well as their quantitative characterizations. Equivalent metric characterizations of the three mentioned regularity properties as well as a sufficient condition of [q]-subregularity in terms of Frechet normals are established. The relationships between [q]-regularity … Read more

Quasi-Newton updates with weighted secant equations

Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

We provide a formula for variational quasi-Newton updates with multiple weighted secant equations. The derivation of the formula leads to a Sylvester equation in the correction matrix. Examples are given. CitationReport naXys-09-2013, Namur Centre for Complex Systems, Unibersity of Namur, Namur (Belgium)ArticleDownload View PDF

Price of Anarchy for Non-atomic Congestion Games with Stochastic Demands

Categories Applications - OR and Management Sciences, Transportation Tags , , ,

We generalize the notions of user equilibrium and system optimum to non-atomic congestion games with stochastic demands. We establish upper bounds on the price of anarchy for three different settings of link cost functions and demand distributions, namely, (a) affine cost functions and general distributions, (b) polynomial cost functions and general positive-valued distributions, and (c) … Read more

On the irreducibility, Lyapunov rank, and automorphisms of speical Bishop-Phelps cones

Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

Motivated by optimization considerations, we consider special Bishop-Phelps cones in R^n which are of the form {(t,x): t \geq ||x||} for some norm on R^(n-1). We show that for n bigger than 2, such cones are always irreducible. De fining the Lyapunov rank of a proper cone K as the dimension of the Lie algebra of … Read more

An Active-Set Quadratic Programming Method Based On Sequential Hot-Starts

Categories Quadratic Programming Tags , , , , , , ,

A new method for solving sequences of quadratic programs (QPs) is presented. For each new QP in the sequence, the method utilizes hot-starts that employ information computed by an active-set QP solver during the solution of the first QP. This avoids the computation and factorization of the full matrices for all but the first problem … Read more

Computing a Cournot Equilibrium in Integers

Categories Applications - OR and Management Sciences, Integer Programming Tags

We give an efficient algorithm for computing a Cournot equilibrium when the producers are confined to integers, the inverse demand function is linear, and costs are quadratic. The method also establishes existence, which follows in much more generality because the problem can be modelled as a potential game. CitationSchool of Operations Research and Information Engineering, … Read more

Information Relaxations, Duality, and Convex Dynamic Programs

Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Dynamic Programming Tags , , ,

We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs), following Brown, Smith, and Sun (2010). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these nonanticipativity constraints. In this paper, we study DPs that have a convex structure and … Read more

Strongly Agree or Strongly Disagree?: Rating Features in Support Vector Machines

Categories (Mixed) Integer Linear Programming, Data-Mining Tags , , , ,

In linear classifiers, such as the Support Vector Machine (SVM), a score is associated with each feature and objects are assigned to classes based on the linear combination of the scores and the values of the features. Inspired by discrete psychometric scales, which measure the extent to which a factor is in agreement with a … Read more

Conic separation of finite sets:The homogeneous case

Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , , , ,

This work addresses the issue of separating two finite sets in $\mathbb{R}^n $ by means of a suitable revolution cone $$ \Gamma (z,y,s)= \{x \in \mathbb{R}^n : s\,\Vert x-z\Vert – y^T(x-z)=0\}.$$ The specific challenge at hand is to determine the aperture coefficient $s$, the axis $y$, and the apex $z$ of the cone. These parameters … Read more

Conic separation of finite sets: The non-homogeneous case

Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , ,

We address the issue of separating two finite sets in $\mathbb{R}^n $ by means of a suitable revolution cone $$ \Gamma (z,y,s)= \{x \in \mathbb{R}^n :\, s\,\Vert x-z\Vert – y^T(x-z)=0\}.$$ One has to select the aperture coefficient $s$, the axis $y$, and the apex $z$ in such a way as to meet certain optimal separation … Read more