Optimization Online


Concave programming for minimizing the zero-norm over polyhedral sets

Francesco Rinaldi(frinaldi***at***iasi.cnr.it)
Fabio Schoen(fabio.schoen***at***unifi.it)
Marco Sciandrone(sciandro***at***dsi.unifi.it)

Abstract: Given a non empty polyhedral set, we consider the problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This nonsmooth combinatorial optimization problem is NP-Hard and arises in various fields such as machine learning, pattern recognition, signal processing. We propose two smooth approximations of the zero-norm function, where the approximating functions are separable and concave. We formally prove the equivalence between the approximating problems and the original nonsmooth problem. To this aim, we preliminarly state in a general setting theoretical conditions sufficient to guarantee the equivalence between pairs of problems. We also define an effective version of the Frank-Wolfe algorithm for the minimization of concave separable functions over polyhedral sets, and we prove the global convergence of the method. Finally, we report the numerical results on test problems showing both the usefulness of the new concave formulations and the efficiency in terms of computational time of the implemented minimization algorithm.

Keywords: Zero-norm, concave optimization, Frank-Wolfe algorithm

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: TR DSI 2008/02

Download: [PDF]

Entry Submitted: 03/25/2008
Entry Accepted: 03/25/2008
Entry Last Modified: 03/25/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society