Optimal subgradient algorithms with application to large-scale linear inverse problems

  • Masoud Ahookhosh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , , , , ,

    This study addresses some algorithms for solving structured unconstrained convex optimization problems using first-order information where the underlying function includes high-dimensional data. The primary aim is to develop an implementable algorithmic framework for solving problems with multi-term composite objective functions involving linear mappings using the optimal subgradient algorithm, OSGA, proposed by {\sc Neumaier} in \cite{NeuO}. … Read more

    Planning for Mining Operations with Time and Resource Constraints

  • Christina Burt
  • Peter J. Stuckey
  • Nir Lipovetzky
  • Adrian R. Pearce
    • Categories Production and Logistics, Scheduling, Transportation Tags , , ,

    We study a daily mine planning problem where, given a set of blocks we wish to mine, our task is to generate a mining sequence for the excavators such that blending resource constraints are met at various stages of the sequence. Such time-oriented resource constraints are not traditionally handled well by automated planners. On the … Read more

    String-Averaging Expectation-Maximization for Maximum Likelihood Estimation in Emission Tomography

  • Yair Censor
  • Álvaro Rodolfo De Pierro
  • Elias Salomão Helou
  • Tai-Been Chen
  • I-Liang Chern
  • Ming Jiang
  • Henry Horng-Shing Lu
    • Categories Biomedical Applications, Convex Optimization Tags , , , , , ,

    We study the maximum likelihood model in emission tomography and propose a new family of algorithms for its solution, called String-Averaging Expectation-Maximization (SAEM). In the String-Averaging algorithmic regime, the index set of all underlying equations is split into subsets, called “strings,” and the algorithm separately proceeds along each string, possibly in parallel. Then, the end-points … Read more

    OSGA: A fast subgradient algorithm with optimal complexity

  • Arnold Neumaier
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more

    Global optimization on the torus, the sphere and the rotation group

  • Manuel Gräf
  • Ralf Hielscher
    • Categories Global Optimization Tags , , , , ,

    Detecting all local extrema or the global extremum of a polynomial on the torus, the sphere or the rotation group is a tough yet often requested numerical problem. We present a heuristic approach that applies common descent methods like nonlinear conjugated gradients or Newtons methods simultaneously to a large number of starting points. The corner … Read more

    Feasibility-Seeking and Superiorization Algorithms Applied to Inverse Treatment Planning in Radiation Therapy

  • Yair Censor
  • Ran Davidi
  • Sarah Geneser
  • Reinhard W. Schulte
  • Lei Xing
    • Categories Biomedical Applications, Convex Optimization Tags , , , ,

    We apply the recently proposed superiorization methodology (SM) to the inverse planning problem in radiation therapy. The inverse planning problem is represented here as a constrained minimization problem of the total variation (TV) of the intensity vector over a large system of linear two-sided inequalities. The SM can be viewed conceptually as lying between feasibility-seeking … Read more

    Minimum Cost Path Problem for Plug-in Hybrid Electric Vehicles

  • Okan Arslan
  • Oya Ekin Karasan
  • Baris Yildiz
    • Categories Applications - OR and Management Sciences, Network Optimization, Transportation

    We introduce a practically important and theoretically challenging problem: finding the minimum cost path for PHEVs in a road network with refueling and charging stations. We show that this problem is NP-complete and present a mixed integer quadratically constrained formulation, a discrete approximation dynamic programming heuristic, and a shortest path heuristic as solution methodologies. Practical … Read more

    The continuous knapsack set

  • Sanjeeb Dash
  • Oktay Gunluk
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming Tags ,

    We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n non-negative integer and m non-negative bounded continuous variables. When n = 1, this set is a slight generalization of the single arc flow set studied by Magnanti, Mirchandani, and Vachani (1993). We first show that in … Read more

    Sparsity Optimization in Design of Multidimensional Filter Networks

  • Mats Andersson
  • Oleg Burdakov
  • Hans Knutsson
  • Spartak Zikrin
    • Categories Applications - Science and Engineering, Global Optimization Applications, Multi-Criteria Optimization

    Filter networks are used as a powerful tool aimed at reducing the image processing time and maintaining high image quality. They are composed of sparse sub-filters whose high sparsity ensures fast image processing. The filter network design is related to solving a sparse optimization problem where a cardinality constraint bounds above the sparsity level. In … Read more

    Approximating Convex Functions By Non-Convex Oracles Under The Relative Noise Model

  • Nir Halman
    • Categories Approximation Algorithms Tags ,

    We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an L-approximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be … Read more