# A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints

arXiv: https://arxiv.org/abs/2511.03443 · HTML: https://mlsanity.com/paper/2511.03443/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 5 Nov 2025.

## Builds on (most cited first, 17 of 17)

- [Simple algorithms for optimization on Riemannian manifolds with constraints](https://mlsanity.com/paper/1901.10000/) (2019)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)
- [Clustering by Orthogonal NMF Model and Non-Convex Penalty Optimization](https://mlsanity.com/paper/1906.00570/) (2019)
- [An exact penalty approach for optimization with nonnegative orthogonality constraints](https://mlsanity.com/paper/1907.12424/) (2019)
- [A Semismooth Newton based Augmented Lagrangian Method for Nonsmooth Optimization on Matrix Manifolds](https://mlsanity.com/paper/2103.02855/) (2021)
- [Multipliers Correction Methods for Optimization Problems over the Stiefel Manifold](https://mlsanity.com/paper/2011.14781/) (2020)
- [A Decentralized Proximal Gradient Tracking Algorithm for Composite Optimization on Riemannian Manifolds](https://mlsanity.com/paper/2401.11573/) (2024)
- [An Exact Penalty Approach for Equality Constrained Optimization over a Convex Set](https://mlsanity.com/paper/2505.02495/) (2025)
- [Orthogonal symmetric non-negative matrix factorization under the stochastic block model](https://mlsanity.com/paper/1605.05349/) (2016)
- [A Communication-Efficient and Privacy-Aware Distributed Algorithm for Sparse PCA](https://mlsanity.com/paper/2106.03320/) (2021)
- [Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint](https://mlsanity.com/paper/2111.03457/) (2021)
- [Tight Error Bounds for the Sign-Constrained Stiefel Manifold](https://mlsanity.com/paper/2210.05164/) (2022)
- [Unsupervised Feature Selection via Nonnegative Orthogonal Constrained Regularized Minimization](https://mlsanity.com/paper/2403.16966/) (2024)
- [On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem](https://mlsanity.com/paper/2507.15264/) (2025)
- [Lp-norm regularization algorithms for optimization over permutation matrices](https://mlsanity.com/paper/1608.06695/) (2016)
- [Seeking Consensus on Subspaces in Federated Principal Component Analysis](https://mlsanity.com/paper/2012.03461/) (2020)
- [A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection](https://mlsanity.com/paper/1708.01072/) (2017)

## Abstract (arXiv)

In this paper, we investigate optimization problems with nonnegative and orthogonal constraints, where any feasible matrix of size n × p exhibits a sparsity pattern such that each row accommodates at most one nonzero entry. Our analysis demonstrates that, by fixing the support set, the global solution of the minimization subproblem for the proximal linearization of the objective function can be computed in closed form with at most n nonzero entries. Exploiting this structural property offers a powerful avenue for dramatically enhancing computational efficiency. Guided by this insight, we propose a support-set algorithm preserving strictly the feasibility of iterates. A central ingredient is a strategically devised update scheme for support sets that adjusts the placement of nonzero entries. We establish the convergence of the support-set algorithm to a first-order stationary point, and show that its iteration complexity required to reach an ε-approximate first-order stationary point is O (ε-2). Numerical results are strongly in favor of our algorithm in real-world applications, including nonnegative PCA, clustering, and community detection.