This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that … Read more
Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the … Read more
In this paper we study the link between a semi-infinite chance-constrained optimization problem and its randomized version, i.e. the problem obtained by sampling a finite number of its constraints. Extending previous results on the feasibility of randomized convex programs, we establish here the feasibility of the solution obtained after the elimination of a portion of … Read more
We propose novel necessary and sufficient conditions for a sensing matrix to be “s-good” — to allow for exact L1-recovery of sparse signals with s nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect L1-recovery (nonzero measurement noise, nearly s-sparse signal, near-optimal solution of the optimization problem yielding … Read more
In this paper, we study a gradient based method for general cone programming (CP) problems. In particular, we first consider four natural primal-dual convex smooth minimization reformulations for them, and then discuss a variant of Nesterov’s smooth (VNS) method recently proposed by Tseng [30] for solving these reformulations. The associated worst-case major arithmetic operations costs … Read more
Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie … Read more
We modify the first order algorithm for convex programming proposed by Nesterov. The resulting algorithm keeps the optimal complexity obtained by Nesterov with no need of a known Lipschitz constant for the gradient, and performs better in practically all examples in a set of test problems. CitationTechnical Report, Federal University of Santa Catarina, 2008.ArticleDownload View … Read more
The elegant results for strong duality and strict complementarity for linear programming, \LP, can fail for cone programming over nonpolyhedral cones. One can have: unattained optimal values; nonzero duality gaps; and no primal-dual optimal pair that satisfies strict complementarity. This failure is tied to the nonclosure of sums of nonpolyhedral closed cones. We take a … Read more
We provide a specific representation of convex polynomials nonnegative on a convex (not necessarily compact) basic closed semi-algebraic set $K$ of $R^n$. Namely, they belong to a specific subset of the quadratic module generated by the concave polynomials that define $K$. CitationTo appear in Archiv der MathematikArticleDownload View PDF
Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more