Global optimization for sparse solution of least squares problems
| Autor: | Ramzi Ben Mhenni, Jordan Ninin, Sébastien Bourguignon |
|---|---|
| Přispěvatelé: | Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Equipe Models and AlgoriThms for pRocessIng and eXtracting information (Lab-STICC_MATRIX), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Institut Mines-Télécom [Paris] (IMT)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-Institut Mines-Télécom [Paris] (IMT)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL), École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne), Lab-STICC_ENSTAB_CID_PRASYS, IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
Control and Optimization Optimization problem Branch-and-bound Cardinality constraint 0211 other engineering and technologies 02 engineering and technology Sparse approximation Cardinality Quadratic equation [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing 0202 electrical engineering electronic engineering information engineering Global optimization Integer programming ComputingMilieux_MISCELLANEOUS Mathematics 021103 operations research Applied Mathematics 020206 networking & telecommunications [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Search tree Continuous relaxation Homotopy continuation Relaxation (approximation) [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] Portfolio optimization Software |
| Zdroj: | Optimization Methods and Software Optimization Methods and Software, Taylor & Francis, In press, ⟨10.1080/10556788.2021.1977809⟩ ICCOPT, International Conference on Continuous Optimization ICCOPT, International Conference on Continuous Optimization, 2019, Berlin, Germany |
| ISSN: | 1055-6788 1029-4937 |
| DOI: | 10.1080/10556788.2021.1977809⟩ |
| Popis: | International audience; Finding solutions to least-squares problems with low cardinality has found many applications, including portfolio optimization, subset selection in statistics, and inverse problems in signal processing. Although most works consider local approaches that scale with high-dimensional problems, some others address its global optimization via mixed integer programming (MIP) reformulations. We propose dedicated branch-and-bound methods for the exact resolution of moderate-size, yet difficult, sparse optimization problems, through three possible formulations: cardinality-constrained and cardinality-penalized least-squares, and cardinality minimization under quadratic constraints. A specific tree exploration strategy is built. Continuous relaxation problems involved at each node are reformulated as (Formula presented.) -norm-based optimization problems, for which a dedicated algorithm is designed. The obtained certified solutions are shown to better estimate sparsity patterns than standard methods on simulated variable selection problems involving highly correlated variables. Problem instances selecting up to 24 components among 100 variables, and up to 15 components among 1000 variables, can be solved in less than 1000 s. Unguaranteed solutions obtained by limiting the computing time to 1s are also shown to provide competitive estimates. Our algorithms strongly outperform the CPLEX MIP solver as the dimension increases, especially for quadratically-constrained problems. The source codes are made freely available online. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|