Month: February 2012

Sparse/Robust Estimation and Kalman Smoothing with Nonsmooth Log-Concave Densities: Modeling, Computation, and Theory

  • Aleksandr Y. Aravkin
  • James V. Burke
  • Gianluigi Pillonetto
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Convex and Nonsmooth Optimization

    Piecewise linear quadratic (PLQ) penalties play a crucial role in many applications, including machine learning, robust statistical inference, sparsity promotion, and inverse problems such as Kalman smoothing. Well known examples of PLQ penalties include the l2, Huber, l1 and Vapnik losses. This paper builds on a dual representation for PLQ penalties known from convex analysis. … Read more

    An aggressive reduction scheme for the simple plant location problem

  • Adam N. Letchford
  • Sebastian J. Miller
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags ,

    Pisinger et al. introduced the concept of `aggressive reduction’ for large-scale combinatorial optimisation problems. The idea is to spend much time and effort in reducing the size of the instance, in the hope that the reduced instance will then be small enough to be solved by an exact algorithm. We present an aggressive reduction scheme … Read more

    Non-Convex Mixed-Integer Nonlinear Programming: A Survey

  • Samuel Burer
  • Adam N. Letchford
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , , ,

    A wide range of problems arising in practical applications can be formulated as Mixed-Integer Nonlinear Programs (MINLPs). For the case in which the objective and constraint functions are convex, some quite effective exact and heuristic algorithms are available. When non-convexities are present, however, things become much more difficult, since then even the continuous relaxation is … Read more

    ON REGULARITY CONDITIONS FOR COMPLEMENTARITY PROBLEMS

  • Alexey F. Izmailov
  • A. S. Kurennoy
    • Categories Complementarity and Variational Inequalities Tags , , , , , , , , , ,

    In the context of mixed complementarity problems, various concepts of solution regularity are known, each of them playing a certain role in related theoretical and algorithmic developments. In this note, we provide the complete picture of relations between the most important regularity conditions for mixed complementarity problems. A special attention is paid to the particular … Read more

    A Stochastic Gradient Method with an Exponential Convergence Rate for Strongly-Convex Optimization with Finite Training Sets

  • Francis Bach
  • Mark Schmidt
  • Nicolas Le Roux
    • Categories Convex Optimization, Stochastic Approaches

    We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. Numerical … Read more

    Competitive location in networks with threshold-sensitive customer behaviour

  • Pablo Dorta-González
  • Dolores R. Santos-Peñate
  • Rafael Suárez-Vega
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    We consider the (r|X_p)-medianoid problem in networks. Goods are assumed to be essential and the only decision criterion is the travel distance. The portion of demand captured by the competitors is modelled by a general capture function which includes the binary, partially binary and proportional customer choice rules as specific cases. We prove that, under … Read more

    A regularized simplex method

  • Krisztian Eretnek
  • Csaba I. Fábián
  • Olga Papp
    • Categories Convex and Nonsmooth Optimization, Linear Programming Tags , ,

    In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a certain convex polyhedral objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized simplex method. (Regularization is performed in the dual space and … Read more

    Decomposition Algorithms with Parametric Gomory Cuts for Two-Stage Stochastic Integer Programs

  • Dinakar Gade
  • Simge Küçükyavuz
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags , , , , ,

    We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the L-shaped or Benders methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology … Read more

    Numerical Optimization of Eigenvalues of Hermitian Matrix Functions

  • Mustafa Kilic
  • E. Alper Yildirim
  • Emre Mengi
    • Categories Global Optimization Applications, Quadratic Programming Tags , , , ,

    The eigenvalues of a Hermitian matrix function that depends on one parameter analytically can be ordered so that each eigenvalue is an analytic function of the parameter. Ordering these analytic eigenvalues from the largest to the smallest yields continuous and piece-wise analytic functions. For multi-variate Hermitian matrix functions that depend on $d$ parameters analytically, the … Read more

    Solving trajectory optimization problems via nonlinear programming: the brachistochrone case study

  • Jean-Pierre Dussault
    • Categories Nonlinear Optimization Tags

    This note discusses reformulations the brachistochrone problem suitable for solution via NLP. The availability of solvers and modeling languages such as AMPL makes it tempting to formulate discretized optimization problems and get solutions to the discretized versions of trajectory optimization problems. We use the famous brachistochrone problem to warn that the resulting solutions may be … Read more