Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/90721
Title: | A subgradient-based approach for finding the maximum feasible subsystem with respect to a set | Authors: | Ye, M Pong, TK |
Issue Date: | 2020 | Source: | SIAM journal on optimization, 2020, v. 30, no. 2, p. 1274-1299 | Abstract: | We propose a subgradient-based method for finding the maximum feasible subsystem in a collection of closed sets with respect to a given closed set C (MFSC). In this method, we reformulate the MFSC problem as an ℓ0 optimization problem and construct a sequence of continuous optimization problems to approximate it. The objective of each approximation problem is the sum of the composition of a nonnegative nondecreasing continuously differentiable concave function with the squared distance function to a closed set. Although this objective function is nonsmooth in general, a subgradient can be obtained in terms of the projections onto the closed sets. Based on this observation, we adapt a subgradient projection method to solve these approximation problems. Unlike classical subgradient methods, the convergence (clustering to stationary points) of our subgradient method is guaranteed with a nondiminishing stepsize under mild assumptions. This allows us to further study the sequential convergence of the subgradient method under suitable Kurdyka-Łojasiewicz assumptions. Finally, we illustrate our algorithm numerically for solving the MFSC problems on a collection of halfspaces and a collection of unions of halfspaces, respectively, with respect to the set of s-sparse vectors. | Keywords: | Kurdyka-Łojasiewicz property Maximum feasible subsystem Subgradient methods |
Publisher: | Society for Industrial and Applied Mathematics | Journal: | SIAM journal on optimization | ISSN: | 1052-6234 | EISSN: | 1095-7189 | DOI: | 10.1137/18M1186320 | Rights: | © 2020 Society for Industrial and Applied Mathematics First Published in SIAM Journal on Optimization in Volume 30, Issue 2, published by the Society for Industrial and Applied Mathematics (SIAM). Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2438_MFBC_algorithm_rev1.pdf | Pre-Published version | 626.64 kB | Adobe PDF | View/Open |
Page views
29
Last Week
2
2
Last month
Citations as of Jun 4, 2023
Downloads
6
Citations as of Jun 4, 2023
SCOPUSTM
Citations
2
Citations as of Jun 8, 2023
WEB OF SCIENCETM
Citations
2
Citations as of Jun 8, 2023

Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.