A distributed semismooth Newton based augmented Lagrangian method for distributed optimization

Qihao Ma; Chengjing Wang; Peipei Tang; Dunbiao Niu; Aimin Xu

math.OCFeb 27, 2026

A distributed semismooth Newton based augmented Lagrangian method for distributed optimization

Authors: Qihao Ma, Chengjing Wang, Peipei Tang, Dunbiao Niu, Aimin Xu

Organizations: School of Mathematics, Southwest Jiaotong University, No.999, Xian Road, West Park, High-tech Zone, Chengdu 611756, China · School of Computer and Computing Science, Hangzhou City University, Zhejiang Key Laboratory of Big Data Intelligent Computing, Hangzhou, 310015, China · Department of Control Science and Engineering, College of Electronics and Information Engineering, National Key Laboratory of Autonomous Intelligent Unmanned Systems, Tongji University, Shanghai 201804, China · Institute of Mathematics, Zhejiang Wanli University, Ningbo 315100, China

Abstract

This paper proposes a novel distributed semismooth Newton based augmented Lagrangian method for solving a class of optimization problems over networks, where the global objective is defined as the sum of locally held cost functions, and communication is restricted to neighboring agents. Specifically, we employ the augmented Lagrangian method to solve an equivalently reformulated constrained version of the original problem. Each resulting subproblem is solved inexactly via a distributed semismooth Newton method. By fully leveraging the structure of the generalized Hessian, a distributed accelerated proximal gradient method is proposed to compute the Newton direction efficiently, eliminating the need to communicate with full Hessian matrices. Theoretical results are also obtained to guarantee the convergence of the proposed algorithm. Numerical experiments demonstrate the efficiency and superiority of our algorithm compared to state-of-the-art distributed algorithms.

Figures & tables

	$\displaystyle u_{i}^{t}$	$\displaystyle=\sigma x_{i}^{t}-\lambda_{i},$
	$\displaystyle u_{i+m}^{t}$	$\displaystyle=\sigma\sum_{k\in\mathcal{N}_{i}}L_{ik}x_{k}^{t}-\lambda_{i+m},$

Algorithm 1 DiSSN method for problem ( 13 ) at the

i

-th agent

\tilde{x}_{i}^{j}=x_{i}^{j}+\beta(x_{i}^{j}-x_{i-1}^{j}),

Algorithm 2 DAPG method at the

i

-th agent

	$\displaystyle u_{i}^{k+1}$	$\displaystyle=\sigma_{k+1}x_{i}^{k+1}-\lambda_{i}^{k},$
	$\displaystyle u_{i+m}^{k+1}$	$\displaystyle=\sigma_{k+1}\sum_{t\in\mathcal{N}_{i}}L_{it}{x}_{t}^{k+1}-\lambda_{i+m}^{k},$

Algorithm 3 DSSNAL method for problem ( 6 ) at the

i

-th agent

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
rand(2,400)	4.2-5	300000 $\|$ 5(26247) $\|$ 5862	3.07-1 $\|$ 9.21-9 $\|$ 9.98-7	6.218+1 $\|$ 6.170+1 $\|$ 6.170+1	11:08 $\|$ 0:02 $\|$ 0:06
rand(4,800)	2.7-4	300000 $\|$ 5(82125) $\|$ 29587	2.96-1 $\|$ 4.32-7 $\|$ 9.89-7	1.432+2 $\|$ 1.312+2 $\|$ 1.312+2	11:48 $\|$ 0:03 $\|$ 1:10
rand(6,1200)	5.2-4	300000 $\|$ 6(138084) $\|$ 60000	3.02-1 $\|$ 1.34-8 $\|$ 1.10-5	2.150+2 $\|$ 1.949+2 $\|$ 1.949+2	12:05 $\|$ 0:09 $\|$ 3:07
rand(8,1600)	6.3-4	300000 $\|$ 6(74454) $\|$ 60000	2.91-1 $\|$ 6.44-8 $\|$ 1.21-3	2.781+2 $\|$ 2.659+2 $\|$ 2.668+2	14:26 $\|$ 0:13 $\|$ 5:02
rand(10,2000)	8.8-4	300000 $\|$ 6(123938) $\|$ 60000	3.23-1 $\|$ 1.67-7 $\|$ 8.73-3	3.473+2 $\|$ 3.309+2 $\|$ 3.312+2	15:49 $\|$ 0:23 $\|$ 6:26

TABLE I: Numerical comparisons for the Huber regression problem on the random data problem

(m=50)

. In this table ‘

a

’=FDPG, ‘

b

’=DSSNAL, ‘

c

’=Prox-NIDS.

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
abalone.scale(8,4177)	2.9-2	300000 $\|$ 7(221676) $\|$ 60000	1.84-2 $\|$ 5.05-7 $\|$ 2.78-3	9.724+2 $\|$ 9.688+2 $\|$ 9.689+2	10:31 $\|$ 0:32 $\|$ 10:03
ailerons51tst(40,2750)	1.1-2	300000 $\|$ 8(482837) $\|$ 60000	9.28-3 $\|$ 3.21-7 $\|$ 2.68-6	9.972+2 $\|$ 9.948+2 $\|$ 9.948+2	48:23 $\|$ 12:14 $\|$ 20:16
anacalt(7,4052)	3.5-6	300000 $\|$ 8(172518) $\|$ 60000	1.83-2 $\|$ 1.13-7 $\|$ 9.84-3	1.289+3 $\|$ 1.287+3 $\|$ 1.287+3	11:19 $\|$ 0:42 $\|$ 8:08
concrete(8,1030)	8.0-4	300000 $\|$ 6(188681) $\|$ 60000	4.21-2 $\|$ 3.57-7 $\|$ 7.65-4	4.165+2 $\|$ 4.088+2 $\|$ 4.089+2	12:47 $\|$ 0:09 $\|$ 3:11
friedman(5,1200)	5.0-3	300000 $\|$ 5(84622) $\|$ 53798	2.92-1 $\|$ 3.72-7 $\|$ 9.86-7	4.613+2 $\|$ 4.400+2 $\|$ 4.400+2	11:13 $\|$ 0:12 $\|$ 2:49

TABLE II: Numerical comparisons for the Huber regression problem on the UCL datasets

(m=50)

. In this table ‘

a

’=FDPG, ‘

b

’=DSSNAL, ‘

c

’=Prox-NIDS.

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
rand(6,300)	3.7-4	300000 $\|$ 6(28834) $\|$ 18193	4.17-1 $\|$ 6.05-9 $\|$ 9.94-7	3.457+2 $\|$ 2.955+2 $\|$ 2.955+2	6:52 $\|$ 0:07 $\|$ 0:26
rand(7,600)	5.4-4	300000 $\|$ 6(29018) $\|$ 43939	4.69-1 $\|$ 6.21-8 $\|$ 9.93-7	6.092+2 $\|$ 5.949+2 $\|$ 5.949+2	7:17 $\|$ 0:13 $\|$ 1:23
rand(8,900)	6.8-4	300000 $\|$ 6(29254) $\|$ 60000	3.37-1 $\|$ 3.29-7 $\|$ 1.63-5	9.216+2 $\|$ 8.946+2 $\|$ 8.946+2	9:46 $\|$ 0:20 $\|$ 3:11
rand(9,1200)	8.6-4	300000 $\|$ 6(29537) $\|$ 60000	3.46-1 $\|$ 9.01-7 $\|$ 5.11-4	1.349+3 $\|$ 1.193+3 $\|$ 1.195+3	11:35 $\|$ 0:24 $\|$ 3:57
rand(10,1500)	1.5-3	300000 $\|$ 7(49682) $\|$ 60000	4.27-1 $\|$ 2.37-7 $\|$ 2.17-3	1.507+3 $\|$ 1.484+3 $\|$ 1.487+3	12:57 $\|$ 0:38 $\|$ 4:55

TABLE III: Numerical comparisons for the support vector classification problem on the random data problem

(m=50)

. In this table ‘

a

’=FDPG, ‘

b

’=DSSNAL, ‘

c

’=Prox-NIDS.

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
abalone.scale(8,4177)	2.9-2	300000 $\|$ 8(225632) $\|$ 60000	3.09-2 $\|$ 6.01-7 $\|$ 3.15-3	2.598+3 $\|$ 2.586+3 $\|$ 2.587+3	10:05 $\|$ 1:15 $\|$ 9:34
anacalt(7,4052)	3.2-2	300000 $\|$ 8(171935) $\|$ 60000	4.03-2 $\|$ 7.97-7 $\|$ 3.85-3	3.682+3 $\|$ 3.624+3 $\|$ 3.625+3	10:19 $\|$ 1:12 $\|$ 8:46
concrete(8,1030)	2.1-3	300000 $\|$ 7(102761) $\|$ 60000	5.96-2 $\|$ 7.84-8 $\|$ 6.44-4	5.139+2 $\|$ 5.108+2 $\|$ 5.108+2	10:43 $\|$ 0:24 $\|$ 3:38
friedman(5,1200 )	4.2-3	300000 $\|$ 6(26883) $\|$ 54779	3.39-1 $\|$ 1.63-7 $\|$ 9.98-7	1.108+3 $\|$ 1.057+3 $\|$ 1.057+3	5:52 $\|$ 0:19 $\|$ 2:49
mortgage(15,1649)	1.5-3	300000 $\|$ 6(172642) $\|$ 60000	8.73-3 $\|$ 6.35-7 $\|$ 2.51-3	1.219+2 $\|$ 1.197+2 $\|$ 1.217+2	16:23 $\|$ 0:39 $\|$ 6:42

TABLE IV: Numerical comparisons for the support vector classification problem on the UCL datasets

(m=50)

. In this table ‘

a

’=FDPG, ‘

b

’=DSSNAL, ‘

c

’=Prox-NIDS.

Distributed Optimization

Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.

See all 92 papers

Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration
Feb 18, 2026Luyao Guo, Xinli Shi, Wenying Xu +1Distributed Optimization Nonsmooth Convex Optimization
School of Computer Science and Engineering, Suzhou University of Technology, Suzhou 215500, China · School of Mathematics, Southeast University, Nanjing 210096, China · School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China
Scalar Communication via Random Direction Refreshing for Distributed Optimization
Oct 5, 2026Mohammadreza Rostami, Solmaz S. KiaDistributed Optimization Decentralized Optimization
Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
Jul 2, 2026Siyuan Zhang, Nachuan Xiao, Xin LiuStochastic Optimization Nonconvex Optimization

Feb 18, 2026J/K move · Enter open · S save

Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration

Luyao Guo, Xinli Shi, Wenying Xu, Jinde Cao

School of Computer Science and Engineering, Suzhou University of Technology, Suzhou 215500, China · School of Mathematics, Southeast University, Nanjing 210096, China · School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China

Distributed Optimization Nonsmooth Convex Optimization

Open paper AskPDF arXiv

This paper is concerned with the distributed composite optimization problem over networks, where agents aim to minimize a sum of local smooth components and a common nonsmooth term. Leveraging the probabilistic local updates mechanism, we propose a communication-efficient Adapt-Then-Combine (ATC) framework, FlexATC, unifying numerous ATC-based distributed algorithms. Under stepsizes independent of the network topology and the number of local updates, we establish sublinear and linear convergence rates for FlexATC in convex and strongly convex settings, respectively. Remarkably, in the strong convex setting, the linear rate is decoupled from the objective functions and network topology, and FlexATC permits communication to be skipped in most iterations without any deterioration of the linear rate. In addition, the proposed unified theory demonstrates for the first time that local updates provably lead to communication acceleration for ATC-based distributed algorithms. Numerical experiments further validate the efficacy of the proposed framework and corroborate the theoretical results.

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
rand(2,400)	4.2-5	300000 $\|$ 5(26247) $\|$ 5862	3.07-1 $\|$ 9.21-9 $\|$ 9.98-7	6.218+1 $\|$ 6.170+1 $\|$ 6.170+1	11:08 $\|$ 0:02 $\|$ 0:06
rand(4,800)	2.7-4	300000 $\|$ 5(82125) $\|$ 29587	2.96-1 $\|$ 4.32-7 $\|$ 9.89-7	1.432+2 $\|$ 1.312+2 $\|$ 1.312+2	11:48 $\|$ 0:03 $\|$ 1:10
rand(6,1200)	5.2-4	300000 $\|$ 6(138084) $\|$ 60000	3.02-1 $\|$ 1.34-8 $\|$ 1.10-5	2.150+2 $\|$ 1.949+2 $\|$ 1.949+2	12:05 $\|$ 0:09 $\|$ 3:07
rand(8,1600)	6.3-4	300000 $\|$ 6(74454) $\|$ 60000	2.91-1 $\|$ 6.44-8 $\|$ 1.21-3	2.781+2 $\|$ 2.659+2 $\|$ 2.668+2	14:26 $\|$ 0:13 $\|$ 5:02
rand(10,2000)	8.8-4	300000 $\|$ 6(123938) $\|$ 60000	3.23-1 $\|$ 1.67-7 $\|$ 8.73-3	3.473+2 $\|$ 3.309+2 $\|$ 3.312+2	15:49 $\|$ 0:23 $\|$ 6:26

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
abalone.scale(8,4177)	2.9-2	300000 $\|$ 7(221676) $\|$ 60000	1.84-2 $\|$ 5.05-7 $\|$ 2.78-3	9.724+2 $\|$ 9.688+2 $\|$ 9.689+2	10:31 $\|$ 0:32 $\|$ 10:03
ailerons51tst(40,2750)	1.1-2	300000 $\|$ 8(482837) $\|$ 60000	9.28-3 $\|$ 3.21-7 $\|$ 2.68-6	9.972+2 $\|$ 9.948+2 $\|$ 9.948+2	48:23 $\|$ 12:14 $\|$ 20:16
anacalt(7,4052)	3.5-6	300000 $\|$ 8(172518) $\|$ 60000	1.83-2 $\|$ 1.13-7 $\|$ 9.84-3	1.289+3 $\|$ 1.287+3 $\|$ 1.287+3	11:19 $\|$ 0:42 $\|$ 8:08
concrete(8,1030)	8.0-4	300000 $\|$ 6(188681) $\|$ 60000	4.21-2 $\|$ 3.57-7 $\|$ 7.65-4	4.165+2 $\|$ 4.088+2 $\|$ 4.089+2	12:47 $\|$ 0:09 $\|$ 3:11
friedman(5,1200)	5.0-3	300000 $\|$ 5(84622) $\|$ 53798	2.92-1 $\|$ 3.72-7 $\|$ 9.86-7	4.613+2 $\|$ 4.400+2 $\|$ 4.400+2	11:13 $\|$ 0:12 $\|$ 2:49

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
rand(6,300)	3.7-4	300000 $\|$ 6(28834) $\|$ 18193	4.17-1 $\|$ 6.05-9 $\|$ 9.94-7	3.457+2 $\|$ 2.955+2 $\|$ 2.955+2	6:52 $\|$ 0:07 $\|$ 0:26
rand(7,600)	5.4-4	300000 $\|$ 6(29018) $\|$ 43939	4.69-1 $\|$ 6.21-8 $\|$ 9.93-7	6.092+2 $\|$ 5.949+2 $\|$ 5.949+2	7:17 $\|$ 0:13 $\|$ 1:23
rand(8,900)	6.8-4	300000 $\|$ 6(29254) $\|$ 60000	3.37-1 $\|$ 3.29-7 $\|$ 1.63-5	9.216+2 $\|$ 8.946+2 $\|$ 8.946+2	9:46 $\|$ 0:20 $\|$ 3:11
rand(9,1200)	8.6-4	300000 $\|$ 6(29537) $\|$ 60000	3.46-1 $\|$ 9.01-7 $\|$ 5.11-4	1.349+3 $\|$ 1.193+3 $\|$ 1.195+3	11:35 $\|$ 0:24 $\|$ 3:57
rand(10,1500)	1.5-3	300000 $\|$ 7(49682) $\|$ 60000	4.27-1 $\|$ 2.37-7 $\|$ 2.17-3	1.507+3 $\|$ 1.484+3 $\|$ 1.487+3	12:57 $\|$ 0:38 $\|$ 4:55

dataname(n,S)	$\gamma$	iter	$R_{{\rm KKT}}$	obj	time
dataname(n,S)	$\gamma$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$	$a\ \|\ b\ \|\ c$
abalone.scale(8,4177)	2.9-2	300000 $\|$ 8(225632) $\|$ 60000	3.09-2 $\|$ 6.01-7 $\|$ 3.15-3	2.598+3 $\|$ 2.586+3 $\|$ 2.587+3	10:05 $\|$ 1:15 $\|$ 9:34
anacalt(7,4052)	3.2-2	300000 $\|$ 8(171935) $\|$ 60000	4.03-2 $\|$ 7.97-7 $\|$ 3.85-3	3.682+3 $\|$ 3.624+3 $\|$ 3.625+3	10:19 $\|$ 1:12 $\|$ 8:46
concrete(8,1030)	2.1-3	300000 $\|$ 7(102761) $\|$ 60000	5.96-2 $\|$ 7.84-8 $\|$ 6.44-4	5.139+2 $\|$ 5.108+2 $\|$ 5.108+2	10:43 $\|$ 0:24 $\|$ 3:38
friedman(5,1200 )	4.2-3	300000 $\|$ 6(26883) $\|$ 54779	3.39-1 $\|$ 1.63-7 $\|$ 9.98-7	1.108+3 $\|$ 1.057+3 $\|$ 1.057+3	5:52 $\|$ 0:19 $\|$ 2:49
mortgage(15,1649)	1.5-3	300000 $\|$ 6(172642) $\|$ 60000	8.73-3 $\|$ 6.35-7 $\|$ 2.51-3	1.219+2 $\|$ 1.197+2 $\|$ 1.217+2	16:23 $\|$ 0:39 $\|$ 6:42

Abstract

Distributed Optimization

Explore similar work

Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration

Scalar Communication via Random Direction Refreshing for Distributed Optimization

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization