Month: June 2012

Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper we study new stochastic approximation (SA) type algorithms, namely, the accelerated SA (AC-SA), for solving strongly convex stochastic composite optimization (SCO) problems. Specifically, by introducing a domain shrinking procedure, we significantly improve the large-deviation results associated with the convergence rate of a nearly optimal AC-SA algorithm presented by the authors. Moreover, we … Read more

    A new Search via Probability Algorithm for solving Engineering Optimization Problems

  • Nguyen Huu Thong
    • Categories Applications - Science and Engineering, Global Optimization, Stochastic Programming Tags , , ,

    The Search Algorithms have been introduced in the paper [3][6] under the name ‘Search via Probability Algorithm’. These optimization techniques converge very fast and are very efficient for solving optimization problems with very large scale feasible domains. But these optimization techniques are not effective in solving the numerical optimization problems with long narrow feasible domains. … Read more

    Newton-Like Methods for Sparse Inverse Covariance Estimation

  • Jorge Nocedal
  • Peder Olsen
  • Figen Oztoprak
  • Stephen Rennie
    • Categories Convex Optimization Tags , ,

    We propose two classes of second-order optimization methods for solving the sparse inverse covariance estimation problem. The first approach, which we call the Newton-LASSO method, minimizes a piecewise quadratic model of the objective function at every iteration to generate a step. We employ the fast iterative shrinkage thresholding method (FISTA) to solve this subproblem. The … Read more

    Upper bounds for packings of spheres of several radii

  • David de Laat
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    We give theorems that can be used to upper bound the densities of packings of different spherical caps in the unit sphere and of translates of different convex bodies in Euclidean space. These theorems extend the linear programming bounds for packings of spherical caps and of convex bodies through the use of semidefinite programming. We … Read more

    Quantitative Stability Analysis of Stochastic Generalized Equations

  • Yongchao Liu
  • Werner Romisch
  • Huifu Xu
    • Categories Stochastic Programming Tags , , , , , , ,

    We consider the solution of a system of stochastic generalized equations (SGE) where the underlying functions are mathematical expectation of random set-valued mappings. SGE has many applications such as characterizing optimality conditions of a nonsmooth stochastic optimization problem and a stochastic equilibrium problem. We derive quantitative continuity of expected value of the set-valued mapping with … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson’s infinite group problem, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically, for deciding extremality in this important class of minimal valid functions. Article … Read more

    Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this … Read more

    Automated improvement of radiation therapy treatment plans by optimization under reference dose constraints

  • Albin Fredriksson
    • Categories Applications - Science and Engineering Tags ,

    A method is presented that automatically improves upon previous treatment plans by optimization under reference dose constraints. In such an optimization, a previous plan is taken as reference and a new optimization is performed towards some goal, such as minimization of the doses to healthy structures, under the constraint that no structure can become worse … Read more

    Supermodularity and Affine Policies in Dynamic Robust Optimization

  • Dan Iancu
  • Mayank Sharma
  • Maxim Sviridenko
    • Categories Dynamic Programming, Polyhedra, Robust Optimization Tags , , , , ,

    This paper considers robust dynamic optimization problems, where the unknown parameters are modeled as uncertainty sets. We seek to bridge two classical paradigms for solving such problems, namely (1) Dynamic Programming (DP), and (2) policies parameterized in model uncertainties (also known as decision rules), obtained by solving tractable convex optimization problems. We provide a set … Read more

    Aircraft deconfliction with speed regulation: new models from mixed-integer optimization

  • Sonia Cafieri
  • Nicolas Durand
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , , ,

    Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact … Read more