A general class of algorithms for unconstrained optimization is introduced, which subsumes the classical trust-region algorithm and two of its newer variants, as well as the cubic and quadratic regularization methods. A unified theory of global convergence to first-order critical points is then described for this class. An extension to projection-based trust-region algorithms for nonlinear … Read more
The detection of gravitational waves is a long-awaited event in modern physics and, to achieve this challenging goal, detectors with high sensitivity are being used or are under development. In order to extract gravitational signals, emitted by coalescing binary systems of compact objects (neutron stars and/or black holes), from noisy data obtained by interferometric detectors, … Read more
In the interest of deriving classifiers that are robust to outlier observations, we present integer programming formulations of Vapnik’s support vector machine (SVM) with the ramp loss and hard margin loss. The ramp loss allows a maximum error of 2 for each training observation, while the hard margin loss calculates error by counting the number … Read more
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
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
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
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
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. CitationRapport de Recherche INRIA 6707, Oct. 2008.ArticleDownload View PDF
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
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