We show that the Hedge Algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a well-chosen convex function, namely as a Mirror Descent Scheme. Using this reformulation, we establish three modificitations and extensions of the Hedge Algorithm that are better or at least as … Read more
We consider penalized-likelihood reconstruction for X-ray computed tomography of objects that contain small metal structures. To reduce the beam hardening artefacts induced by these structures, we derive the reconstruction algorithm from a projection model that takes into account the photon emission spectrum and nonlinear variation of attenuation to photon energy. This algorithm requires excessively long … Read more
We consider the minimum spanning tree problem with conflict constraints (MSTC). It is observed that computing an $\epsilon$-optimal solution to MSTC is NP-hard for any $\epsilon >0$. For a general conflict graph, computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded … Read more
We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In \cite{Amico}, the authors … Read more
In this paper, we propose and study the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from … Read more
For a given connected graph G on n vertices and m edges, we prove that its independence number α(G) is at least ((2m+n+2) -sqrt(sqr(2m+n+2)-16sqr(n)))/8. ArticleDownload View PDF
We present a mathematical framework for the so-called multidisciplinary free material optimization (MDFMO) problems, a branch of structural optimization in which the full material tensor is considered as a design variable. We extend the original problem statement by a class of generic constraints depending either on the design or on the state variables. Among the … Read more
In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any … Read more
We extend Nesterov’s semidefinite programming (SDP) characterization of the cone of functions that can be expressed as sums of squares (SOS) of functions in finite dimensional linear functional spaces. Our extension is to algebraic systems that are endowed with a binary operation which map two elements of a finite dimensional vector space to another vector … Read more
Conjugate gradient methods are widely used for solving large-scale unconstrained optimization problems, because they do not need the storage of matrices. In this paper, we propose a general form of three-term conjugate gradient methods which always generate a sufficient descent direction. We give a sufficient condition for the global convergence of the proposed general method. … Read more