A subgradient-based approach for finding the maximum feasible subsystem with respect to a set

Minglu Ye, Ting Kei Pong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)1274-1299
Number of pages26
JournalSIAM Journal on Optimization
Volume30
Issue number2
DOIs
Publication statusPublished - 28 Apr 2020

Keywords

  • Kurdyka-Łojasiewicz property
  • Maximum feasible subsystem
  • Subgradient methods

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this