Exact penalization for cardinality and rank-constrained optimization problems via partial regularization. (4th March 2023)

• Record Type: Journal Article
• Authors: Lu, Zhaosong; Li, Xiaorui; Xiang, Shuhuang
• Is Part Of: Optimization methods and software. Volume 38:Number 2(2023)
• Page Start: 412
• Page End: 433
• Publication Date: 2023-03-04
• Subjects: Sparse optimization -- low-rank optimization -- cardinality constraint -- rank constraint -- partial regularization -- exact penalty; 65C60 -- 65K05 -- 90C26 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2142583
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we consider a class of constrained optimization problems whose constraints involve a cardinality or rank constraint. The penalty formulation based on a partial regularization has recently been promoted in the literature to approximate these problems, which usually outperforms the penalty formulation based on a full regularization in terms of solution quality. Nevertheless, the relation between the penalty formulation with a partial regularizer and the original problem was not much studied yet. Under some suitable assumptions, we show that the penalty formulation based on a partial regularization is an exact reformulation of the original problem in the sense that they both share the same global minimizers. We also show that a local minimizer of the original problem is that of the penalty reformulation. These results provide some theoretical justification for the often-observed superior performance of the penalty model based on a partial regularizer over a corresponding full regularizer.