An exact penalty approach for optimization with nonnegative orthogonality constraints
Abstract Optimization with nonnegative orthogonality constraints has wide applications in machine learning and data sciences. It is NP-hard due to some combinatorial properties of the constraints. We first propose an equivalent optimization formulation with nonnegative and multiple sp...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148140 |
| _version_ | 1826199428722065408 |
|---|---|
| author | Jiang, Bo Meng, Xiang Wen, Zaiwen Chen, Xiaojun |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Jiang, Bo Meng, Xiang Wen, Zaiwen Chen, Xiaojun |
| author_sort | Jiang, Bo |
| collection | MIT |
| description | Abstract
Optimization with nonnegative orthogonality constraints has wide applications in machine learning and data sciences. It is NP-hard due to some combinatorial properties of the constraints. We first propose an equivalent optimization formulation with nonnegative and multiple spherical constraints and an additional single nonlinear constraint. Various constraint qualifications, the first- and second-order optimality conditions of the equivalent formulation are discussed. By establishing a local error bound of the feasible set, we design a class of (smooth) exact penalty models via keeping the nonnegative and multiple spherical constraints. The penalty models are exact if the penalty parameter is sufficiently large but finite. A practical penalty algorithm with postprocessing is then developed to approximately solve a series of subproblems with nonnegative and multiple spherical constraints. We study the asymptotic convergence and establish that any limit point is a weakly stationary point of the original problem and becomes a stationary point under some additional mild conditions. Extensive numerical results on the problem of computing the orthogonal projection onto nonnegative orthogonality constraints, the orthogonal nonnegative matrix factorization problems and the K-indicators model show the effectiveness of our proposed approach. |
| first_indexed | 2024-09-23T11:20:03Z |
| format | Article |
| id | mit-1721.1/148140 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:20:03Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1481402024-01-29T21:30:21Z An exact penalty approach for optimization with nonnegative orthogonality constraints Jiang, Bo Meng, Xiang Wen, Zaiwen Chen, Xiaojun Massachusetts Institute of Technology. Operations Research Center Abstract Optimization with nonnegative orthogonality constraints has wide applications in machine learning and data sciences. It is NP-hard due to some combinatorial properties of the constraints. We first propose an equivalent optimization formulation with nonnegative and multiple spherical constraints and an additional single nonlinear constraint. Various constraint qualifications, the first- and second-order optimality conditions of the equivalent formulation are discussed. By establishing a local error bound of the feasible set, we design a class of (smooth) exact penalty models via keeping the nonnegative and multiple spherical constraints. The penalty models are exact if the penalty parameter is sufficiently large but finite. A practical penalty algorithm with postprocessing is then developed to approximately solve a series of subproblems with nonnegative and multiple spherical constraints. We study the asymptotic convergence and establish that any limit point is a weakly stationary point of the original problem and becomes a stationary point under some additional mild conditions. Extensive numerical results on the problem of computing the orthogonal projection onto nonnegative orthogonality constraints, the orthogonal nonnegative matrix factorization problems and the K-indicators model show the effectiveness of our proposed approach. 2023-02-22T15:19:33Z 2023-02-22T15:19:33Z 2022-03-25 2023-02-22T05:30:29Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/148140 Jiang, Bo, Meng, Xiang, Wen, Zaiwen and Chen, Xiaojun. 2022. "An exact penalty approach for optimization with nonnegative orthogonality constraints." en https://doi.org/10.1007/s10107-022-01794-8 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Jiang, Bo Meng, Xiang Wen, Zaiwen Chen, Xiaojun An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title | An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title_full | An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title_fullStr | An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title_full_unstemmed | An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title_short | An exact penalty approach for optimization with nonnegative orthogonality constraints |
| title_sort | exact penalty approach for optimization with nonnegative orthogonality constraints |
| url | https://hdl.handle.net/1721.1/148140 |
| work_keys_str_mv | AT jiangbo anexactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT mengxiang anexactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT wenzaiwen anexactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT chenxiaojun anexactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT jiangbo exactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT mengxiang exactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT wenzaiwen exactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints AT chenxiaojun exactpenaltyapproachforoptimizationwithnonnegativeorthogonalityconstraints |