Implementing Algorithms for Signal and Image Reconstruction on Graphical Processing Units

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

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

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

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

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

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

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

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

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

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