Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints

Linglingzhi Zhu; Wentao Ding; Shangyuan Liu; Anthony Man-Cho So

math.OCApr 5, 2026

Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints

Authors: Linglingzhi Zhu, Wentao Ding, Shangyuan Liu, Anthony Man-Cho So

Organizations: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA · Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong

Abstract

Recent advancements in data science have significantly elevated the importance of orthogonally constrained optimization problems. The Riemannian approach has become a popular technique for addressing these problems due to the advantageous computational and analytical properties of the Stiefel manifold. Nonetheless, the interplay of nonsmoothness alongside orthogonality constraints introduces substantial challenges to current Riemannian methods, including scalability, parallelizability, complicated subproblems, and cumulative numerical errors that threaten feasibility. In this paper, we take a retraction-free primal-dual approach and propose a linearized smoothing augmented Lagrangian method specifically designed for nonsmooth and nonconvex optimization with orthogonality constraints. Our proposed method is single-loop and free of subproblem solving. We establish its iteration complexity of $O(ε^{-3})$ for finding $ε$ -KKT points, matching the best-known results in the Riemannian optimization literature. Additionally, by invoking the standard Kurdyka-Lojasiewicz (KL) property, we demonstrate asymptotic sequential convergence of the proposed algorithm. Numerical experiments on both smooth and nonsmooth orthogonal constrained problems demonstrate the superior computational efficiency and scalability of the proposed method compared with state-of-the-art algorithms.

Figures & tables

	Nonsmooth	Single-loop	Complexity	Sequential Convergence	Retraction-Free
SOC [ 28 ] /PAMAL [ 13 ]	✓		—
PCAL [ 17 ] /Landing [ 1 ]		✓	$\mathcal{O}(\epsilon^{-2})$		✓
ManPG [ 12 ]	✓		$\mathcal{O}(\epsilon^{-2})^{*}$
RPG [ 21 ]	✓		$\mathcal{O}(\epsilon^{-2})^{*}$	✓
ManAL [ 15 , 43 ]	✓		$\mathcal{O}(\epsilon^{-3})$
RADMM [ 31 ]	✓	✓	$\mathcal{O}(\epsilon^{-4})$

Table 1: Comparison of algorithms for nonconvex structured problems with orthogonality constraints

Panel of Figure 1 — Figure 1: Performance of LSALM in the Nonsmooth QP Experiment

Panel of Figure 2 — Figure 2: Feasibility and Update of Primal Variables with Different $\rho$

Panel of Figure 3 — Figure 3: Convergence of LSALM with varying $r$ and $\beta$

	ManPG-Ada					SOC					RADMM					LSALM
$m,n$	T(s)	#I	T/I(s)	Obj	S(%)	T(s)	#I	T/I(s)	Obj	S(%)	T(s)	#I	T/I(s)	Obj	S(%)	T(s)	#I	T/I(s)	Obj	S(%)
300, 150	33.5	504	0.066	-117.9	99.32	10.9	1694	0.006	-118.8	99.31	4.4	1235	0.004	-118.9	99.31	3.2	1101	0.003	-118.7	99.32
400, 200	65.9	398	0.166	-159.1	99.47	25.1	2287	0.011	-160.0	99.46	9.7	1570	0.006	-159.8	99.47	8.0	1480	0.005	-159.7	99.47
500, 250	134.2	442	0.303	-201.0	99.56	48.3	2885	0.017	-201.5	99.55	18.4	1964	0.009	-201.5	99.55	12.4	1562	0.008	-200.9	99.56
600, 300	301.9	536	0.563	-242.5	99.62	91.2	3249	0.028	-242.9	99.62	43.7	2554	0.017	-242.6	99.61	19.7	1508	0.013	-242.9	99.62
700, 350	440.0	546	0.805	-283.9	99.66	140.9	3713	0.038	-286.4	99.66	59.6	2623	0.023	-286.2	99.66	31.5	1783	0.018	-284.7	99.66

Table 2: Average Performance of the Algorithms for Different

(m,n)

Panel of Figure 4 — Figure 4: Comparison of Average CPU time and Per-Iteration Efficiency of the Algorithms

	ManPG-Ada			SOC			RADMM			LSALM
$m,n$	T(s)	#I	T/I(s)	T(s)	#I	T/I(s)	T(s)	#I	T/I(s)	T(s)	#I	T/I(s)
300, 150	1.2	75	0.016	2.4	368	0.007	1.0	257	0.004	0.5	280	0.003
400, 200	3.0	102	0.030	6.5	588	0.011	2.5	400	0.007	1.3	266	0.005
500, 250	6.3	90	0.070	8.3	491	0.017	3.2	332	0.010	1.5	207	0.007
600, 300	30.0	105	0.284	17.1	606	0.028	7.2	410	0.018	3.1	248	0.012
700, 350	42.0	119	0.352	26.7	696	0.038	10.8	469	0.023	4.6	282	0.016

Table 3: Average Performance of the Algorithms with RSM initialization for Different

(m,n)

	RGD				PCAL				Landing				LSALM
	Time(s)	#Iter	Obj	F-mea	Time(s)	#Iter	Obj	F-mea	Time(s)	#Iter	Obj	F-mea	Time(s)	#Iter	Obj	F-mea
No.30	1.37	1508	-142.0	0.77	1.07	4849	-142.0	0.77	0.90	4849	-142.0	0.77	0.73	2929	-142.0	0.77
No.60	1.42	1595	-135.8	0.82	1.12	5352	-135.8	0.82	0.97	5351	-135.8	0.82	0.79	3251	-135.8	0.83
No.90	1.57	1747	-131.8	0.84	1.33	6243	-131.8	0.84	1.13	6220	-131.8	0.84	0.83	3429	-133.5	0.91

Table 4: Average Results for Graph Matching

Orthogonal Optimization

See all 15 papers

Nonsmooth Optimization via Orthogonalized Momentum
Sep 12, 2026Lexiao Lai, Tianyi Lin, Jiayu ZhangMuon Optimizer Nonconvex Optimization
Department of Mathematics, The University of Hong Kong · Department of Industrial Engineering and Operations Research Columbia University
Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
Jul 9, 2026Linglingzhi Zhu, Jiajin LiPrimal-Dual Optimization Nonconvex Optimization
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.
Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization
Apr 13, 2025Qiankun Shi, Han Yuan, Xiao Wang +1Zeroth-Order Optimization Augmented Lagrangian Method
Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

Sep 12, 2026J/K move · Enter open · S save

Nonsmooth Optimization via Orthogonalized Momentum

Lexiao Lai, Tianyi Lin, Jiayu Zhang

Department of Mathematics, The University of Hong Kong · Department of Industrial Engineering and Operations Research Columbia University

Muon Optimizer Nonconvex Optimization Nonsmooth Convex Optimization

Open paper AskPDF arXiv

Modern real application problems involve matrix-valued parameters, yet conventional optimizers treat them as vectors, thereby motivating matrix-aware methods that exploit input-output geometry, such as Muon which orthogonalizes the momentum matrices before parameter updates. Its empirical success raises a conceptual question: can orthogonalized momentum remain effective beyond smooth optimization? This paper studies this question for locally Lipschitz functions using a generalized derivative framework compatible with backpropagation. Our first contribution is to identify a key limitation: for every fixed momentum factor

β\in[0,1)

, Muon can fail to approach the global optimal solution of a convex Lipschitz objective from almost every initialization, when step sizes adapt to the full gradient history. The failure can occur even along bounded iterates. Our example is inspired by the one of Parshakova et al. which only covers

β\in[0,\frac{1}{2})

. Then, we show that the obstruction lies in fixed momentum rather than orthogonalization. Indeed, when the momentum factor is adaptive and approaches 1 together with a vanishing step size, Muon recovers asymptotic convergence for nonconvex nonsmooth optimization under the boundedness and regularity conditions. Moreover, we propose MAGD, which combines orthogonalized momentum with gradient, weighted based on their relative progress. MAGD retains asymptotic convergence in nonconvex settings and achieves an

O(\min\{m,n\}ε^{-2})

rate in convex settings. A lower bound shows the optimal dimension dependence. Experiments on synthetic problems, image classification, and LLM pretraining show MAGD is a simple and practical alternative to Muon. Together, our results characterize when orthogonalized momentum fails without smoothness and how it can be made reliable and we hope that the analysis may be useful more broadly.

Abstract

Orthogonal Optimization

Explore similar work

Nonsmooth Optimization via Orthogonalized Momentum

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization