A Smoothing Method for Sparse Optimization over Polyhedral Sets
Résumé
In this paper, we investigate a class of heuristics schemes to solve the NP-hard problem of minimizing over a polyhedral set. A well-known approximation is to consider the convex problem of minimizing We are interested in nding improved results in cases where the problem in does not provide an optimal solution to the problem. We consider a relaxation technique using a family of smooth concave functions depending on a parameter. Some other relaxations have already been tried in the literature and the aim of this paper is to provide a more general context. We use an homotopy algorithm, starting from a solution to the problem in and ending in a solution of the problem in We show convergence results, a kind of monotonicity of the solutions as well as error estimates leading to an exact penalization theorem. We also provide keys for implementing the algorithm and numerical simulations.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...