Month: October 2008

Implementing Algorithms for Signal and Image Reconstruction on Graphical Processing Units

  • Sangkyun Lee
  • Stephen Wright
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    Several highly effective algorithms that have been proposed recently for compressed sensing and image processing applications can be implemented efficiently on commodity graphical processing units (GPUs). The properties of algorithms and application that make for efficient GPU implementation are discussed, and computational results for several algorithms are presented that show large speedups over CPU implementations. … Read more

    A second derivative SQP method: theoretical issues

  • Nicholas I. M. Gould
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    Sequential quadratic programming (SQP) methods form a class of highly efficient algorithms for solving nonlinearly constrained optimization problems. Although second derivative information may often be calculated, there is little practical theory that justifies exact-Hessian SQP methods. In particular, the resulting quadratic programming (QP) subproblems are often nonconvex, and thus finding their global solutions may be … Read more

    Second-order analysis of optimal control problems with control and initial-final state constraints

  • Joseph Frédéric Bonnans
  • Nikolai Osmolovskii
    • Categories Systems governed by Differential Equations Optimization Tags , , , ,

    This paper provides an analysis of Pontryagine mimina satisfying a quadratic growth condition, for optimal control problems of ordinary differential equations with constraints on initial-final state, as well as control constraints satisfying the uniform positive linear independence condition. Citation Rapport de Recherche INRIA 6707, Oct. 2008. Article Download View Second-order analysis of optimal control problems … Read more

    The Knapsack Problem with Conflict Graphs

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories 0-1 Programming, Graphs and Matroids Tags ,

    We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin … Read more

    The Rotational Dimension of a Graph

  • Frank Göring
  • Christoph Helmberg
  • Markus Wappler
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    Given a connected graph $G=(N,E)$ with node weights $s\in\R^N_+$ and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of $G$: Find $v_i\in\R^{|N|}$, $i\in N$ so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter … Read more

    Dynamic Evolution for Risk-Neutral Densities

  • Ana M. Monteiro
  • Reha H. Tütüncü
  • Luis Nunes Vicente
    • Categories Finance and Economics, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Option price data is often used to infer risk-neutral densities for future prices of an underlying asset. Given the prices of a set of options on the same underlying asset with different strikes and maturities, we propose a nonparametric approach for estimating the evolution of the risk-neutral density in time. Our method uses bicubic splines … Read more

    Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

  • Viswanath Nagarajan
  • Vahab S. Mirrokni
  • Maxim Sviridenko
  • Jon Lee
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more

    Incorporating Minimum Frobenius Norm Models in Direct Search

  • Ana Luisa Custódio
  • Luis Nunes Vicente
  • Humberto Rocha
    • Categories Optimization Software Benchmark, Unconstrained Optimization Tags , , , , ,

    The goal of this paper is to show that the use of minimum Frobenius norm quadratic models can improve the performance of direct-search methods. The approach taken here is to maintain the structure of directional direct-search methods, organized around a search and a poll step, and to use the set of previously evaluated points generated … Read more

    A Multistage Stochastic Programming Approach to Open Pit Mine Production Scheduling with Uncertain Geology

  • Natashia Boland
  • Gary Froyland
  • Irina Dumitrescu
    • Categories Applications - OR and Management Sciences, Integer Programming, Stochastic Programming Tags , , ,

    The Open Pit Mine Production Scheduling Problem (OPMPSP) studied in recent years is usually based on a single geological estimate of material to be excavated and processed over a number of decades. However techniques have now been developed to generate multiple stochastic geological estimates that more accurately describe the uncertain geology. While some attempts have … Read more

    Efficient Algorithmic Techniques for Several Multidimensional Geometric Data Management and Analysis Problems

  • Mugurel Ionut Andreica
    • Categories Data-Mining, Facility Planning and Design Tags , , , ,

    this paper I present several novel, efficient, algorithmic techniques for solving some multidimensional geometric data management and analysis problems. The techniques are based on several data structures from computational geometry (e.g. segment tree and range tree) and on the well-known sweep-line method. Citation Proceedings of the 3rd International Conference “Knowledge Management – Projects, Systems and … Read more