On the Minimization Over Sparse Symmetric Sets: Projections, Optimality Conditions, and Algorithms

We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve because the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to b...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2016-02, Vol.41 (1), p.196-223
Main Authors: Beck, Amir, Hallak, Nadav
Format: Article
Language:English
Subjects:
block-type methods
Functions, Continuous
Fuzzy sets
Mathematical optimization
Mathematical problems
Mathematical research
optimality conditions
Optimization algorithms
Set theory
sparse optimization
Studies
Symmetry
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve because the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to be nonconvex. We begin with a study of the properties of the orthogonal projection operator onto sparse symmetric sets. Based on this study, we derive efficient methods for computing sparse projections under various symmetry assumptions. We then introduce and study three types of optimality conditions: basic feasibility, L -stationarity, and coordinatewise optimality. A hierarchy between the optimality conditions is established by using the results derived on the orthogonal projection operator. Methods for generating points satisfying the various optimality conditions are presented, analyzed, and finally tested on specific applications.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.2015.0722