∎

11institutetext: J. Zeng 22institutetext: School of Computer and Information
Engineering, Jiangxi Normal University, Nanchang, China.
Liu Bie Ju Centre for Mathematical Sciences, City University of Hong Kong,
Hong Kong.
22email<EMAIL_ADDRESS>33institutetext: W. Yin 44institutetext:
Department of Mathematics, University of California, Los Angeles, CA.
44email<EMAIL_ADDRESS>55institutetext: D.X. Zhou 66institutetext:
School of Data Science, Department of Mathematics, and Liu Bie Ju Centre for
Mathematical Sciences, City University of Hong Kong, Hong Kong.
66email<EMAIL_ADDRESS>
# Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with
Linear Constraints††thanks: We thank Kaizhao Sun for discussions that help us
complete this paper, as well as presenting to us an additional approach to
ensure boundedness. The work of J. Zeng is partly supported by National
Natural Science Foundation of China (No. 61977038) and the Thousand Talents
Plan of Jiangxi Province (No. jxsq2019201124). The work of D.-X. Zhou is
partly supported by Research Grants Council of Hong Kong (No. CityU 11307319),
Laboratory for AI-powered Financial Technologies, and the Hong Kong Institute
for Data Science.

Jinshan Zeng  Wotao Yin  Ding-Xuan Zhou

(Received: date / Accepted: date)

###### Abstract

The augmented Lagrangian method (ALM) is one of the most useful methods for
constrained optimization. Its convergence has been well established under
convexity assumptions or smoothness assumptions, or under both assumptions.
ALM may experience oscillations and divergence when the underlying problem is
simultaneously nonconvex and nonsmooth. In this paper, we consider the
linearly constrained problem with a nonconvex (in particular, weakly convex)
and nonsmooth objective. We modify ALM to use a Moreau envelope of the
augmented Lagrangian and establish its convergence under conditions that are
weaker than those in the literature. We call it the Moreau envelope augmented
Lagrangian (MEAL) method. We also show that the iteration complexity of MEAL
is $o(\varepsilon^{-2})$ to yield an $\varepsilon$-accurate first-order
stationary point. We establish its whole sequence convergence (regardless of
the initial guess) and a rate when a Kurdyka-Łojasiewicz property is assumed.
Moreover, when the subproblem of MEAL has no closed-form solution and is
difficult to solve, we propose two practical variants of MEAL, an inexact
version called iMEAL with an approximate proximal update, and a linearized
version called LiMEAL for the constrained problem with a composite objective.
Their convergence is also established.

###### Keywords:

Nonconvex nonsmooth optimization augmented Lagrangian method Moreau envelope
proximal augmented Lagrangian method Kurdyka-Łojasiewicz inequality

##  1 Introduction

In this paper, we consider the following optimization problem with linear
constraints

$\begin{array}[]{ll}\mathrm{minimize}_{x\in\mathbb{R}^{n}}&f(x)\\\
\mathrm{subject\ to}&Ax=b,\end{array}$ (1)

where $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a proper, lower-
semicontinuous weakly convex function, which is possibly nonconvex and
nonsmooth, $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$ are some
given matrix and vector, respectively. A function $f$ is said to be weakly
convex with a modulus $\rho>0$ if $f(x)+\frac{\rho}{2}\|x\|^{2}$ is convex on
$\mathbb{R}^{n}$, where $\|\cdot\|$ is the Euclidean norm. The class of weakly
convex functions is broad Nurminskii73 , including all convex functions,
smooth but nonconvex functions with Lipschitz continuous gradient, and their
composite forms (say, $f(x)=h(x)+g(x)$ with both $h$ and $g$ being weakly
convex, and $f(x)=g(h(x))$ with $g$ being convex and Lipschitz continuous and
$h$ being a smooth mapping with Lipschitz Jacobian (Drusvyatskiy-Paquette19, ,
Lemma 4.2)).

The augmented Lagrangian method (ALM) is a well-known algorithm for
constrained optimization by Hestenes Hestenes69  and Powell Powell69 . ALM has
been extensively studied and has a large body of literature (Bertsekas73 ;
Birgin10 ; Conn91 ; Conn96 ; Rockafellar73-ALM  just to name a few), yet _no
ALM algorithm can solve the underlying problem ( 1) without at least one of
the following assumptions_: convexity Bertsekas73 ; Bertsekas76 ; Fernadez12 ;
Polyak-Tretyakov73 ; Rockafellar73-ALM , or smoothness Andreani08 ; Andreani10
; Andreani19 ; Andreani18 ; Curtis15 , or solving nonconvex subproblems to
their global minima Birgin10 ; Birgin18 , or an auto-updated penalty sequence
staying bounded on the problem at hand Birgin20 ; Grapiglia-Yuan19 . Indeed,
without these assumptions, ALM may oscillate and even diverge unboundedly on
simple quadratic programs Wang19 ; Zhang-Luo18  on weakly convex objectives.
An example is given Sec. 7.1 below.

At a high level, we introduce a Moreau-envelope modification of the ALM for
solving (1) and show the method can converge under weaker conditions. In
particular, convexity is relaxed to weak convexity; nonsmooth functions are
allowed; the subproblems can be solved inexactly to some extent; linearization
can be applied to the Lipschitz-differential function in the objective; and,
there is no assumption on the rank of $A$. On the other hand, we introduce two
alternative subgradient properties in Definition 1 below as our main
assumption. By also assuming either a bounded energy sequence or bounded
primal-dual sequence, we derive certain subsequence rates of convergence. We
introduce a novel way to establish those boundedness properties based on a
feasible coercivity assumption and a local-stability assumption on the
subproblem. Finally, with the additional assumption of Kurdyka-Łojasiewicz
(KŁ) inequality, we establish global convergence. Overall, this paper shows
that the Moreau envelope technique makes ALM applicable to more problems.

###  1.1 Proposed Algorithms

To present our algorithm, define the augmented Lagrangian:

${\cal
L}_{\beta}(x,\lambda):=f(x)+\langle\lambda,Ax-b\rangle+\frac{\beta}{2}\|Ax-b\|^{2},$
(2)

and the _Moreau envelope_ of ${\cal L}_{\beta}(x,\lambda)$:

$\phi_{\beta}(z,\lambda)=\min_{x}\left\\{{\cal
L}_{\beta}(x,\lambda)+\frac{1}{2\gamma}\|x-z\|^{2}\right\\},$ (3)

where $\lambda\in\mathbb{R}^{m}$ is a multiplier vector, $\beta>0$ is a
penalty parameter, and $\gamma>0$ is a proximal parameter. The Moreau envelope
applies to the primal variable $x$ for each fixed dual variable $\lambda$.

We introduce Moreau Envelope Augmented Lagrangian method (dubbed MEAL) as
follows: given an initialization $(z^{0},\lambda^{0})$, $\gamma>0$, a sequence
of penalty parameters $\\{\beta_{k}\\}$ and a step size $\eta\in(0,2)$, for
$k=0,1,\ldots,$ run

$\mathrm{(MEAL)}\quad\left\\{\begin{array}[]{l}z^{k+1}=z^{k}-\eta\gamma\nabla_{z}\phi_{\beta_{k}}(z^{k},\lambda^{k}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}\nabla_{\lambda}\phi_{\beta_{k}}(z^{k},\lambda^{k}).\end{array}\right.$
(4)

The penalty parameter $\beta_{k}$ can either vary or be fixed.

Introduce

$x^{k+1}=\mathrm{Prox}_{\gamma,{\cal
L}_{\beta_{k}}(\cdot,\lambda^{k})}(z^{k}):=\operatorname*{argmin}_{x}\left\\{{\cal
L}_{\beta_{k}}(x,\lambda^{k})+\frac{1}{2\gamma}\|x-z^{k}\|^{2}\right\\},\
\forall k\in\mathbb{N},$

which yields
$\nabla_{z}\phi_{\beta_{k}}(z^{k},\lambda^{k})=\gamma^{-1}(z^{k}-x^{k+1})$ and
$\nabla_{\lambda}\phi_{\beta_{k}}(z^{k},\lambda^{k})=Ax^{k+1}-b$. Then, MEAL
(4) is equivalent to:

$\mathrm{(MEAL\
Reformulated)}\quad\left\\{\begin{array}[]{l}x^{k+1}=\mathrm{Prox}_{\gamma,{\cal
L}_{\beta_{k}}(\cdot,\lambda^{k})}(z^{k}),\\\
z^{k+1}=z^{k}-\eta(z^{k}-x^{k+1}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b).\end{array}\right.$ (5)

Next, we provide two practical variants of MEAL that do not require an
accurate computation of $\mathrm{Prox}_{\gamma,{\cal L}_{\beta}}$.

##### Inexact MEAL (iMEAL)

We call $x^{k+1}$ an $\epsilon_{k}$-accurate stationary point of the
$x$-subproblem in (5) if there exists

$s^{k}\in\partial_{x}{\cal
L}_{\beta_{k}}(x^{k+1},\lambda^{k})+\gamma^{-1}(x^{k+1}-z^{k})\quad\text{such
that}~{}\|s^{k}\|\leq\epsilon_{k}.$ (6)

iMEAL is described as follows: given an initialization $(z^{0},\lambda^{0})$,
$\gamma>0$, $\eta\in(0,2)$, and two positive sequences $\\{\epsilon_{k}\\}$
and $\\{\beta_{k}\\}$, for $k=0,1,\ldots,$ run

$\mathrm{(iMEAL)}\quad\left\\{\begin{array}[]{l}\mathrm{find\ an}\ x^{k+1}\
\mathrm{to\ satisfy}\ \eqref{iMealCond},\\\
z^{k+1}=z^{k}-\eta(z^{k}-x^{k+1}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b).\end{array}\right.$ (7)

##### Linearized MEAL (LiMEAL)

When problem (1) has the following form

$\begin{array}[]{ll}\mathop{\mathrm{minimize}}_{x\in\mathbb{R}^{n}}&f(x):=h(x)+g(x)\\\
\mathrm{subject\ to}&Ax=b,\end{array}$ (8)

where $h:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is Lipschitz-continuous
differentiable and $g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is weakly convex
and has an easy proximal operator (in particular, admitting a closed-form
solution) Hajinezhad-Hong19 ; Wang19 ; Xu-Yin-BCD13 ; Zeng-DGD18 , we shall
use $\nabla h$. Write $f^{k}(x):=h(x^{k})+\langle\nabla
h(x^{k}),x-x^{k}\rangle+g(x)$ and ${\cal
L}_{\beta,{f^{k}}}(x,\lambda):=f^{k}(x)+\langle\lambda,Ax-b\rangle+\frac{\beta}{2}\|Ax-b\|^{2}.$
We describe LiMEAL for (8) as: given $(z^{0},\lambda^{0})$, $\gamma>0$,
$\eta\in(0,2)$ and $\\{\beta_{k}\\}$, for $k=0,1,\ldots,$ run

$\mathrm{(LiMEAL)}\quad\left\\{\begin{array}[]{l}x^{k+1}=\mathrm{Prox}_{\gamma,{\cal
L}_{\beta_{k},{f^{k}}}(\cdot,\lambda^{k})}(z^{k}),\\\
z^{k+1}=z^{k}-\eta(z^{k}-x^{k+1}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b).\end{array}\right.$ (9)

Since one can choose to use $h$ or not in LiMEAL, LiMEAL is more general than
MEAL.

###  1.2 Relation to ALM and Proximal ALM

Like ALM, MEAL alternatively updates primal and dual variables; but unlike
ALM, MEAL applies the update to the Moreau envelope of augmented Lagrangian.
By Rockafellar-var97 , the Moreau envelope $\phi_{\beta_{k}}(z,\lambda^{k})$
provides a smooth approximation of ${\cal L}_{\beta_{k}}(x,\lambda^{k})$ from
below and shares the same minima. The smoothness of Moreau envelope alleviates
the possible oscillation that arises when ALM is applied to certain nonconvex
optimization problems.

For the problems satisfying the conditions in this paper, ALM may require a
sequence of possibly unbounded $\\{\beta_{k}\\}$. When $\beta_{k}$ is large,
the ALM subproblem is ill-conditioned. Therefore, bounding $\beta_{k}$ is
practically desirable Birgin-book14 ; Conn91 . MEAL and its practical variants
can use a fixed penalty parameter under a novel subgradient assumption in
Definition 1 later.

Proximal ALM was introduced in Rockafellar76-PALM . Its variants were recently
studied in Hajinezhad-Hong19 ; Hong17-Prox-PDA ; Zhang-Luo20 ; Zhang-Luo18 .
These methods add a proximal term to the augmented Lagrangian. Under the
reformulation (5), proximal ALM Rockafellar76-PALM  for problem (1) is a
special case of MEAL with the step size $\eta=1$. In Hong17-Prox-PDA , a
proximal primal-dual algorithm called Prox-PDA was proposed for problem (1).
Certain non-Euclidean matrix norms were adopted in Prox-PDA to guarantee the
strong convexity of the ALM subproblem. A proximal linearized version of Prox-
PDA for the composite optimization problem (8) was studied in Hajinezhad-
Hong19 . These methods are closely related to MEAL, but their convergence
conditions in the literature are stronger.

Recently, Zhang-Luo20 ; Zhang-Luo18  modified proximal inexact ALM for the
linearly constrained problems with an additional bounded box constraint set or
polyhedral constraint set, denoted by ${\cal C}$. Our method is partially
motivated by their methods. Their problems are equivalent to the composite
optimization problems (8) with $g(x)=\iota_{\cal C}(x)$, where $\iota_{\cal
C}(x)=0$ when $x\in{\cal C}$ and $+\infty$ otherwise. In this setting, the
methods in Zhang-Luo20 ; Zhang-Luo18  can be regarded as prox-linear versions
of LiMEAL (9), that is, yielding $x^{k+1}$ via a prox-linear scheme Xu-Yin-
BCD13  instead of the minimization scheme as used in LiMEAL (9), together with
an additional dual step size and a sufficiently small primal step size in
Zhang-Luo20 ; Zhang-Luo18 . Specifically, in the case of $g(x)=\iota_{\cal
C}(x)$, the updates of $x^{k+1}$ in methods in Zhang-Luo20 ; Zhang-Luo18  are
yielded by

$\displaystyle x^{k+1}=\mathrm{Proj}_{\cal C}(x^{k}-s\nabla
K(x^{k},z^{k},\lambda^{k})),$

where $K(x^{k},z^{k},\lambda^{k}))={\cal
L}_{\beta^{k},f}(x,\lambda^{k})+\frac{1}{2\gamma}\|x-z^{k}\|^{2}$, and
$\mathrm{Proj}_{\cal C}(x)$ is the projection of $x$ onto ${\cal C}$. Besides
the difference, LiMEAL can handle proximal functions beyond the indicator
function and permits a wider choice $\eta\in(0,2)$.

###  1.3 Other Related Literature

On convex and constrained problems, locally linear convergence111Locally
linear convergence means exponentially fast convergence to a local minimum
from a sufficiently close initial point. of ALM has been extensively studied
in the literature Bertsekas73 ; Bertsekas76 ; Bertsekas82 ; Conn00 ;
Fernadez12 ; Nocedal99 ; Polyak-Tretyakov73 , mainly under the second order
sufficient condition (SOSC) and constraint conditions such as the linear
independence constraint qualification (LICQ). Global convergence (i.e.,
convergence regardless of the initial guess) of ALM and its variants were
studied in Andreani07 ; Armand17 ; Birgin05 ; Birgin12 ; Birgin10 ; Conn91 ;
Conn96 ; Rockafellar73-ALM ; Tretykov73 , mainly under constraint
qualifications and assumed boundedness of nondecreasing penalty parameters. On
nonconvex and constrained problems, convergence of ALM was recently studied in
Andreani08 ; Andreani10 ; Andreani19 ; Andreani18 ; Birgin10 ; Birgin18 ;
Curtis15 , mainly under the following assumptions: solving nonconvex
subproblems to their approximate global minima or stationary points Birgin10 ;
Birgin18 , or boundedness of the nondecreasing penalty sequence Birgin20 ;
Grapiglia-Yuan19 . Most of them require Lipschitz differentiability of the
objective.

Convergence of proximal ALM and its variants was established under the
assumptions of either convexity in Rockafellar76-PALM  or smoothness (in
particular, Lipschitz differentiablity) in Hajinezhad-Hong19 ; Hong17-Prox-PDA
; Jiang19 ; Xie-Wright19 ; Zhang-Luo20 ; Zhang-Luo18 . Besides proximal ALM,
other related works for nonconvex and constrained problems include Bian15 ;
Haeser19 ; Nouiehed18 ; ONeill20 , which also assume smoothness of the
objective, plus either gradient or Hessian information.

###  1.4 Contribution and Novelty

MEAL, iMEAL and LiMEAL achieve the same order of iteration complexity
$o({\varepsilon^{-2}})$ to reach an $\varepsilon$-accurate first-order
stationary point, slightly better than those in the ALM literature Hajinezhad-
Hong19 ; Hong17-Prox-PDA ; Xie-Wright19 ; Zhang-Luo18 ; Zhang-Luo20  while
also requiring weaker conditions. Our methods have convergence guarantees for
a broader class of objective functions, for example, nonsmooth and nonconvex
functions like the smoothly clipped absolute deviation (SCAD) regularization
Fan-SCAD  and minimax concave penalty (MCP) regularization Zhang-MCP , which
are underlying the applications of statistical learning and beyond Wang19 .

Note that we only assume the feasibility of $Ax=b$, which is weaker than the
commonly-used hypotheses such as: the strict complementarity condition in
Zhang-Luo18 , certain rank assumption (such as
$\mathrm{Im}(A)\subseteq\mathrm{Im}(B)$ when considering the two- (multi-)
block case $Ax+By=0$) in Wang19 , and the linear independence constrained
qualification (LICQ) in Bertsekas82 ; Nocedal99  (which implies the full-rank
assumption in the linear constraint case).

Our analysis is noticeably different from those in the literature
Rockafellar76-PALM ; Hajinezhad-Hong19 ; Hong17-Prox-PDA ; Jiang19 ; Zhang-
Luo18 ; Zhang-Luo20 ; Xie-Wright19 ; Wang19 . We base our analysis on new
potential functions. The Moreau envelope in the potential functions is
partially motivated by Davis-Drusvyatskiy19 . Our overall potential functions
are new and tailored for MEAL, iMEAL, and LiMEAL and include the augmented
Lagrangian with additional terms. The technique of analysis may have its own
value for further generalizing and improving ALM-type methods.

###  1.5 Notation and Organization

We let $\mathbb{R}$ and $\mathbb{N}$ denote the sets of real and natural
numbers, respectively. Given a matrix $A$, $\mathrm{Im}(A)$ denotes its image,
and $\tilde{\sigma}_{\min}(A^{T}A)$ denotes the smallest positive eigenvalue
of $A^{T}A$. $\|\cdot\|$ is the Euclidean norm for a vector. Given any two
nonnegative sequences $\\{\xi_{k}\\}$ and $\\{\zeta_{k}\\}$, we write
$\xi_{k}=o(\zeta_{k})$ if
$\lim_{k\rightarrow\infty}\frac{\xi_{k}}{\zeta_{k}}=0$, and $\xi_{k}={\cal
O}(\zeta_{k})$ if there exists a positive constant $c$ such that $\xi_{k}\leq
c\zeta_{k}$ for all sufficiently large $k$.

In the rest of this paper, Section 2 presents background and preliminary
techniques. Section 3 states convergence results of MEAL and iMEAL. Section 4
presents the results of LiMEAL. Section 5 includes main proofs. Section 6
provides sufficient conditions for certain boundedness assumptions in above
results along with comparisons with the related work. Section 7 provides some
numerical experiments to demonstrate the effectiveness of proposed methods. We
conclude this paper in Section 8.

##  2 Background and Preliminaries

This paper uses extended-real-valued functions, for example,
$h:\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$. Write the domain of $h$ as
$\mathrm{dom}(h):=\\{x\in\mathbb{R}^{n}:h(x)<+\infty\\}$ and its range as
$\mathrm{ran}(h):=\\{y:y=h(x),\forall x\in\mathrm{dom}(h)\\}$. For each
$x\in\mathrm{dom}(h)$, the Fréchet subdifferential of $h$ at $x$, written as
$\widehat{\partial}h(x)$, is the set of vectors $v\in\mathbb{R}^{n}$
satisfying

$\liminf_{u\neq x,u\rightarrow x}\ \frac{h(u)-h(x)-\langle
v,u-x\rangle}{\|x-u\|}\geq 0.$

When $x\notin\mathrm{dom}(h),$ we define $\widehat{\partial}h(x)=\emptyset.$
The _limiting-subdifferential_ (or simply _subdifferential_) of $h$
Mordukhovich-2006  at $x\in\mathrm{dom}(h)$ is defined as

$\partial h(x):=\\{v\in\mathbb{R}^{n}:\exists x^{t}\to x,\;h(x^{t})\to
h(x),\;\widehat{\partial}h(x^{t})\ni v^{t}\to v\\}.$ (10)

A necessary (but not sufficient) condition for $x\in\mathbb{R}^{n}$ to be a
minimizer of $h$ is $0\in\partial h(x)$. A point that satisfies this inclusion
is called limiting-critical or simply critical. The distance between a point
$x$ and a subset ${\cal S}$ of $\mathbb{R}^{n}$ is defined as
$\mathrm{dist}(x,{\cal S})=\inf_{u}\\{\|x-u\|:u\in{\cal S}\\}$.

###  2.1 Moreau Envelope

Given a function $h:\mathbb{R}^{n}\rightarrow\mathbb{R}$, define its Moreau
envelope Moreau65 ; Rockafellar-var97 :

${\cal
M}_{\gamma,h}(z)=\min_{x}\left\\{h(x)+\frac{1}{2\gamma}\|x-z\|^{2}\right\\},$
(11)

where $\gamma>0$ is a parameter. Define its associated proximity operator

$\mathrm{Prox}_{\gamma,h}(z)=\operatorname*{argmin}_{x}\left\\{h(x)+\frac{1}{2\gamma}\|x-z\|^{2}\right\\}.$
(12)

If $h$ is $\rho$-weakly convex and $\gamma\in(0,\rho^{-1})$, then
$\mathrm{Prox}_{\gamma,h}$ is monotone, single-valued, and Lipschitz, and
${\cal M}_{\gamma,h}$ is differentiable with

$\nabla{\cal
M}_{\gamma,h}(z)=\gamma^{-1}\left(z-\mathrm{Prox}_{\gamma,h}(z)\right)\in\partial
h(\mathrm{Prox}_{\gamma,h}(z));$ (13)

see (Rockafellar-var97, , Proposition 13.37). From Drusvyatskiy18 ;
Drusvyatskiy-Paquette19 , we also have

$\displaystyle{\cal M}_{\gamma,h}(\mathrm{Prox}_{\gamma,h}(z))\leq h(z),$
$\displaystyle\|\mathrm{Prox}_{\gamma,h}(z)-z\|=\gamma\|\nabla{\cal
M}_{\gamma,h}(z)\|,$ $\displaystyle\mathrm{dist}(0,\partial
h(\mathrm{Prox}_{\gamma,h}(z)))\leq\|\nabla{\cal M}_{\gamma,h}(z)\|.$

The first relation above presents Moreau envelope as a smooth lower
approximation of $h$. By the second and third relations, small $\|\nabla{\cal
M}_{\gamma,h}(z)\|$ implies that $z$ is near its proximal point
$\mathrm{Prox}_{\gamma,h}(z)$ and $z$ is nearly stationary for $h$ Davis-
Drusvyatskiy19 . Therefore, $\|\nabla{\cal M}_{\gamma,h}(z)\|$ can be used as
a continuous stationarity measure. Hence, replacing the augmented Lagrangian
with its Moreau envelope not only generates a strongly convex subproblem but
also yields a stationarity measure.

###  2.2 Implicit Regularity Properties

Let $h$ be a proper, lower semicontinuous, $\rho$-weakly convex function.
Given a $\gamma\in(0,\rho^{-1})$, define the generalized inverse mapping of
$\mathrm{Prox}_{\gamma,h}$:

$\displaystyle\mathrm{Prox}_{\gamma,h}^{-1}(x):=\\{w:\mathrm{Prox}_{\gamma,h}(w)=x\\},\quad\forall
x\in\mathrm{ran}(\mathrm{Prox}_{\gamma,h}).$ (14)

In the definition below, we introduce two important regularity properties.

###### Definition 1

Let $h$ be a proper, lower semicontinuous and $\rho$-weakly convex function.

  1. (a)

We say $h$ satisfies the implicit Lipschitz subgradient property if for any
$\gamma\in(0,\rho^{-1})$, there exists $L>0$ (depending on $\gamma$) such that
for any $u,v\in\mathrm{ran}(\mathrm{Prox}_{\gamma,h})$,

$\|\nabla{\cal M}_{\gamma,h}(w)-\nabla{\cal M}_{\gamma,h}(w^{\prime})\|\leq
L\|u-v\|,\ \forall
w\in\mathrm{Prox}_{\gamma,h}^{-1}(u),w^{\prime}\in\mathrm{Prox}_{\gamma,h}^{-1}(v);$

  2. (b)

We say $h$ satisfies the implicit bounded subgradient property if for any
$\gamma\in(0,\rho^{-1})$, there exists $\hat{L}>0$ (depending on $\gamma$)
such that for any $u\in\mathrm{ran}(\mathrm{Prox}_{\gamma,h})$,

$\|\nabla{\cal M}_{\gamma,h}(w)\|\leq\hat{L},\ \forall
w\in\mathrm{Prox}_{\gamma,h}^{-1}(u).$

Since $\nabla{\cal M}_{\gamma,h}(x)\in\partial h(\mathrm{Prox}_{\gamma,h}(x))$
for any $x\in\mathbb{R}^{n}$, we have $\nabla{\cal M}_{\gamma,h}(w)\in\partial
h(u),\forall u\in\mathrm{ran}(\mathrm{Prox}_{\gamma,h})$ and
$w\in\mathrm{Prox}_{\gamma,h}^{-1}(u)$. Hence, the implicit Lipschitz
subgradient and implicit bounded subgradient imply, respectively, the
Lipschitz continuity and boundedness only on the components of $\partial h$
that are Moreau envelope gradients, but not on other components of $\partial
h$. When $h$ is differentiable, implicit Lipschitz subgradient implies
Lipschitz gradient. Having implicit bounded subgradients is weaker than having
bounded $\partial h$, which is commonly assumed in the analysis of nonconvex
algorithms (cf. Davis-Drusvyatskiy19 ; Hajinezhad-Hong19 ; Zeng-DGD18 ).
Nonsmooth and nonconvex functions like the SCAD regularization and MCP
regularization which appear in statistical learning Wang19 , have implicit
bounded subgradients.

###  2.3 Kurdyka-Łojasiewicz Inequality

The Kurdyka-Łojasiewicz (KŁ) inequality Bolte-KL2007a ; Bolte-KL2007b ;
Kurdyka-KL1998 ; Lojasiewicz-KL1963 ; Lojasiewicz-KL1993  is a property that
leads to global convergence of nonconvex algorithms in the literature (see,
Attouch13 ; Bolte2014 ; Wang19 ; Xu-Yin-BCD13 ; Zeng-BCD19 ; Zeng-ADMM19 ).
The following definition of Kurdyka-Łojasiewicz property is adopted from
Bolte-KL2007a .

###### Definition 2

A function $h:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ is said to
have the Kurdyka-Łojasiewicz property at $x^{*}\in\mathrm{dom}(\partial h)$ if
there exist a neighborhood ${\cal U}$ of $x^{*}$, a constant $\nu>0$, and a
continuous concave function $\varphi(s)=cs^{1-\theta}$ for some $c>0$ and
$\theta\in[0,1)$ such that the Kurdyka-Łojasiewicz inequality holds: for all
$x\in{\cal U}\cap\mathrm{dom}(\partial h)$ and $h(x^{*})<h(x)<h(x^{*})+\nu$,

$\varphi^{\prime}(h(x)-h(x^{*}))\cdot\mathrm{dist}(0,\partial h(x))\geq 1,$
(15)

(we use the conventions: $0^{0}=1,\infty/\infty=0/0=0$), where $\theta$ is
called the KŁ exponent of $h$ at $x^{*}$. Proper lower semicontinuous
functions satisfying the KŁ inequality at every point of
$\mathrm{dom}(\partial h)$ are called KŁ functions.

This property was firstly introduced by Lojasiewicz-KL1993  on real analytic
functions Krantz2002-real-analytic  for
$\theta\in\left[\tfrac{1}{2},1\right)$, was then extended to functions defined
on the o-minimal structure in Kurdyka-KL1998 , and was later extended to
nonsmooth subanalytic functions in Bolte-KL2007a . KŁ functions include real
analytic functions Krantz2002-real-analytic , semialgebraic functions Bochnak-
semialgebraic1998 , tame functions defined in some o-minimal structures
Kurdyka-KL1998 , continuous subanalytic functions Bolte-KL2007a , definable
functions Bolte-KL2007b , locally strongly convex functions Xu-Yin-BCD13 , as
well as many deep-learning training models Zeng-BCD19 ; Zeng-ADMM19 .

##  3 Convergence of MEAL

This section presents the convergence results of MEAL and iMEAL. We postpone
their proofs to Section 5.

###  3.1 Assumptions and Stationarity Measure

###### Assumption 1

The set ${\cal X}:=\\{x:Ax=b\\}$ is nonempty.

###### Assumption 2

The objective $f$ in problem (1) satisfies:

  1. (a)

$f$ is proper lower semicontinuous and $\rho$-weakly convex; and for any
$\gamma\in(0,\rho^{-1})$, either (b) or (c):

  2. (b)

$f$ satisfies the implicit Lipschitz subgradient property with a constant
$L_{f}>0$ (possibly depending on $\gamma$); or,

  3. (c)

$f$ satisfies the implicit bounded subgradient property with a constant
$\hat{L}_{f}>0$ (possibly depending on $\gamma$).

We do not assume the following hypotheses: the strict complementarity
condition used in Zhang-Luo18 , any rank assumption (such as
$\mathrm{Im}(A)\subseteq\mathrm{Im}(\mathrm{B})$ when considering the two-
(multi-)block case $Ax+By=0$) used in Wang19 , the linear independence
constrained qualification (LICQ) used in Bertsekas82 ; Nocedal99  (implying
the full-rank assumption in the linear constraint case). Assumption 2 is mild
as discussed in Section 2.2.

According to (3) and the update (4) of MEAL, we have

$\displaystyle\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})=\left(\begin{array}[]{c}(\eta\gamma)^{-1}(z^{k}-z^{k+1})\\\
\beta_{k}^{-1}(\lambda^{k+1}-\lambda^{k})\end{array}\right)\in\left(\begin{array}[]{c}\partial
f(x^{k+1})+A^{T}\lambda^{k+1}\\\ Ax^{k+1}-b\end{array}\right).$ (20)

Let

$\displaystyle\xi_{\mathrm{meal}}^{k}:=\min_{0\leq t\leq
k}\|\nabla\phi_{\beta_{t}}(z^{t},\lambda^{t})\|,\ \forall k\in\mathbb{N}.$
(21)

Then according to (20), the bound $\xi_{\mathrm{meal}}^{k}\leq\varepsilon$
implies

$\displaystyle\min_{0\leq t\leq
k}\mathrm{dist}\left\\{0,\left(\begin{array}[]{c}\partial
f(x^{t+1})+A^{T}\lambda^{t+1}\\\
Ax^{t+1}-b\end{array}\right)\right\\}\leq\xi^{k}_{\mathrm{meal}}\leq\varepsilon,$

that is, MEAL achieves $\varepsilon$-accurate first-order stationarity for
problem (1) within $k$ iterations. Hence, $\xi_{\mathrm{meal}}^{k}$ is a valid
stationarity measure of MEAL. Define iteration complexity:

$\displaystyle T_{\varepsilon}=\inf\left\\{t\geq
1:\|\nabla\phi_{\beta_{t}}(z^{t},\lambda^{t})\|\leq\varepsilon\right\\}.$ (22)

Comparing $T_{\varepsilon}$ to the common iteration complexity

$\displaystyle\hat{T}_{\varepsilon}=\inf\left\\{t\geq
1:\mathrm{dist}(0,\partial f(x^{t})+A^{T}\lambda^{t})\leq\epsilon\ \text{and}\
\|Ax^{t}-b\|\leq\varepsilon\right\\},$

we get $T_{\varepsilon}\geq\hat{T}_{\varepsilon}$.

If $f$ is differentiable, $\mathrm{dist}(0,\partial
f(x^{t})+A^{T}\lambda^{t})$ reduces to $\|\nabla f(x^{t})+A^{T}\lambda^{t}\|$.

###  3.2 Convergence Theorems of MEAL

We present the quantities used to state the convergence results of MEAL. Let

$\displaystyle{\cal P}_{\beta}(x,z,\lambda)={\cal
L}_{\beta}(x,\lambda)+\frac{1}{2\gamma}\|x-z\|^{2},$ (23)

for some $\beta,\gamma>0.$ Then according to (5), MEAL can be interpreted as a
primal-dual update with respect to ${\cal P}_{\beta_{k}}(x,z,\lambda)$ at the
$k$-th iteration, that is, updating $x^{k+1}$, $z^{k+1}$, and $\lambda^{k+1}$
by minimization, gradient descent, and gradient ascent respectively.

Based on (23), we introduce the following Lyapunov functions for MEAL:

$\displaystyle{\cal E}_{\mathrm{meal}}^{k}:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+2\alpha_{k}\|z^{k}-z^{k-1}\|^{2},\
\forall k\geq 1,$ (24)

associated with the implicit Lipschitz subgradient assumption and

$\displaystyle\tilde{\cal E}_{\mathrm{meal}}^{k}:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+3\alpha_{k}\|z^{k}-z^{k-1}\|^{2},\
\forall k\geq 1,$ (25)

associated with the implicit bounded subgradient assumption, where

$\displaystyle\alpha_{k}:=\frac{\beta_{k}+\beta_{k+1}+\gamma\eta(1-\eta/2)}{2c_{\gamma,A}\beta_{k}^{2}},\
\forall k\in\mathbb{N},$ (26)

and $c_{\gamma,A}:=\gamma^{2}\tilde{\sigma}_{\min}(A^{T}A)$. When $\beta$ is
fixed, we also fix

$\displaystyle\alpha:=\frac{2\beta+\gamma\eta(1-\eta/2)}{2c_{\gamma,A}\beta^{2}}.$
(27)

######  Theorem 3.1 (Iteration Complexity of MEAL)

Suppose that Assumptions 1 and 2(a) hold. Pick $\gamma\in(0,\rho^{-1})$ and
$\eta\in(0,2)$. Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated
by MEAL (5). The following claims hold:

  1. (a)

Set $\beta$ sufficiently large such that in (27),
$\alpha<\min\left\\{\frac{1-\gamma\rho}{4\gamma(1+\gamma
L_{f})^{2}},\frac{1}{8\gamma}(\frac{2}{\eta}-1)\right\\}$. Under Assumption
2(b), if $\\{{\cal E}_{\mathrm{meal}}^{k}\\}$ is lower bounded, then
$\xi^{k}_{\mathrm{meal}}=o(1/\sqrt{k})$ for $\xi_{\mathrm{meal}}^{k}$ in (21).

  2. (b)

Pick any $K\geq 1$. Set $\\{\beta_{k}\\}$ so that in (26),
$\alpha_{k}\equiv\frac{\alpha^{*}}{K}$ for some positive constant
$\alpha^{*}\leq\min\left\\{\frac{1-\rho\gamma}{6\gamma},\frac{1}{12\gamma}\left(\frac{2}{\eta}-1\right)\right\\}$.
Under Assumption 2(c), if $\\{\tilde{\cal E}_{\mathrm{meal}}^{k}\\}$ is lower
bounded, then $\xi_{\mathrm{meal}}^{K}\leq\tilde{c}_{1}/\sqrt{K}$ for some
constant $\tilde{c}_{1}>0$.

Section 6.1 provides conditions sufficient for the lower-boundedness
assumptions. Let us interpret the theorem. To achieve an
$\varepsilon$-accurate stationary point, the iteration complexity of MEAL is
$o(\varepsilon^{-2})$ assuming the implicit Lipschitz subgradient property and
${\cal O}(\varepsilon^{-2})$ assuming the implicit bounded subgradient
property. Both iteration complexities are consistent with the existing results
of ${\cal O}(\varepsilon^{-2})$ in Hajinezhad-Hong19 ; Hong17-Prox-PDA ; Xie-
Wright19 ; Zhang-Luo20 . The established results of MEAL also hold for
proximal ALM by setting $\eta=1$. We note that it is not our goal to pursue
any better complexity (e.g., using momentum) in this paper.

###### Remark 1

Let $\bar{\alpha}:=\min\left\\{\frac{1-\gamma\rho}{4\gamma(1+\gamma
L_{f})^{2}},\frac{1}{8\gamma}(\frac{2}{\eta}-1)\right\\}$. By (27), the
requirement $0<\alpha<\bar{\alpha}$ in Theorem 3.1(a) is met by setting

$\displaystyle\beta>\frac{1+\sqrt{1+\eta(2-\eta)\gamma
c_{\gamma,A}\bar{\alpha}}}{2c_{\gamma,A}\bar{\alpha}}.$ (28)

Similarly, the assumption $\alpha_{k}=\frac{\alpha^{*}}{K}$ in Theorem 3.1(b)
is met by setting

$\displaystyle\beta_{k}=\frac{K\left(1+\sqrt{1+\eta(2-\eta)\gamma
c_{\gamma,A}\alpha^{*}/K}\right)}{2c_{\gamma,A}\alpha^{*}},\ k=1,\ldots,K.$
(29)

Next, we establish global convergence (whole sequence convergence regardless
of initial points) and its rate for MEAL under the KŁ inequality (Definition
2). Let $\hat{z}^{k}:=z^{k-1}$,
$y^{k}:=(x^{k},z^{k},\lambda^{k},\hat{z}^{k}),\ \forall k\geq 1,$
$y:=(x,z,\lambda,\hat{z})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{n},$
and

$\displaystyle{\cal P}_{\mathrm{meal}}(y):={\cal
P}_{\beta}(x,z,\lambda)+3\alpha\|z-\hat{z}\|^{2}$ (30)

where $\alpha$ is defined in (27).

######  Proposition 1 (Global convergence and rate of MEAL)

Suppose that the assumptions required for Theorem 3.1(a) hold and that
$\\{(x^{k},z^{k},\lambda^{k})\\}$ generated by MEAL (5) is bounded. If ${\cal
P}_{\mathrm{meal}}$ satisfies the KŁ property at some point
$y^{*}:=(x^{*},x^{*},\lambda^{*},x^{*})$ with an exponent of $\theta\in[0,1)$,
where $(x^{*},\lambda^{*})$ is a limit point of $\\{(x^{k},\lambda^{k})\\}$,
then

  1. (a)

the whole sequence $\\{\hat{y}^{k}:=(x^{k},z^{k},\lambda^{k})\\}$ converges to
$\hat{y}^{*}:=(x^{*},x^{*},\lambda^{*})$; and

  2. (b)

the following rate-of-convergence results hold: (1) if $\theta=0$, then
$\\{\hat{y}^{k}\\}$ converges within a finite number of iterations; (2) if
$\theta\in(0,\frac{1}{2}]$, then $\|\hat{y}^{k}-\hat{y}^{*}\|\leq c\tau^{k}$
for all $k\geq k_{0}$, for certain $k_{0}>0,c>0,\tau\in(0,1)$; and (3) if
$\theta\in(\frac{1}{2},1)$, then $\|\hat{y}^{k}-\hat{y}^{*}\|\leq
ck^{-\frac{1-\theta}{2\theta-1}}$ for all $k\geq k_{0}$, for certain
$k_{0}>0,c>0$.

In Proposition 1, the KŁ property of ${\cal P}_{\mathrm{meal}}$ defined in
(30) plays a central role in the establishment of global convergence of MEAL.
The KŁ exponent determines the convergence speed of MEAL; particularly, the
exponent $\theta=1/2$ implies linear convergence so it is most desirable.
Below we give some results on $\theta$, which are obtainable from (Shiota1997,
, page 43), (Bolte-KL2007a, , Theorem 3.1), (Zeng-BCD19, , Lemma 5), and (Li-
Pong-KLexponent18, , Theorem 3.6 and Corollary 5.2).

###### Proposition 2

The following claims hold:

  1. (a)

If $f$ is subanalytic with a closed domain and continuous on its domain, then
${\cal P}_{\mathrm{meal}}$ defined in (30) is a KŁ function;

  2. (b)

If ${\cal L}_{\beta}(x,\lambda)$ defined in (2) has the KŁ property at some
point $(x^{*},\lambda^{*})$ with exponent $\theta\in[1/2,1)$, then ${\cal
P}_{\mathrm{meal}}$ has the KŁ property at $(x^{*},x^{*},\lambda^{*},x^{*})$
with exponent $\theta$;

  3. (c)

If $f$ has the following form:

$\displaystyle f(x)=\min_{1\leq i\leq
r}\left\\{\frac{1}{2}x^{T}M_{i}x+u_{i}^{T}x+c_{i}+P_{i}(x)\right\\},$ (31)

where $P_{i}$ are proper closed polyhedral functions, $M_{i}$ are symmetric
matrices of size $n$, $u_{i}\in\mathbb{R}^{n}$ and $c_{i}\in\mathbb{R}$ for
$i=1,\ldots,r$, then ${\cal L}_{\beta}$ is a KŁ function with an exponent of
$\theta=1/2$.

Claim (a) can be obtained as follows. The terms in ${\cal P}_{\mathrm{meal}}$
besides $f$ are polynomial functions, which are both real analytic and
semialgebraic Bochnak-semialgebraic1998 . Since $f$ is subanalytic with a
closed domain and continuous on its domain, by (Zeng-BCD19, , Lemma 5), ${\cal
P}_{\mathrm{meal}}$ is also subanalytic with a closed domain and continuous on
its domain. By (Bolte-KL2007a, , Theorem 3.1), ${\cal P}_{\mathrm{meal}}$ is a
KŁ function. Claim (b) can be verified by applying (Li-Pong-KLexponent18, ,
Theorem 3.6) to ${\cal P}_{\mathrm{meal}}$. Claim (c) can be established as
follows. The class of functions $f$ defined by (31) are weakly convex with a
modulus $\rho=2\max_{1\leq i\leq r}\|M_{i}\|$. According to (Li-Pong-
KLexponent18, , Sec. 5.2), this class covers many nonconvex functions such as
SCAD Fan-SCAD  and MCP Zhang-MCP  in statistical learning. The function ${\cal
L}_{\beta}(x,\lambda)=\frac{\beta}{2}\|Ax+\beta^{-1}\lambda-b\|^{2}+(f(x)-\frac{1}{2\beta}\|\lambda\|^{2})$.
according to (Li-Pong-KLexponent18, , Corollary 5.2), is a KŁ function with an
exponent of $1/2$. More results on the KŁ functions with exponent $1/2$ can be
found in Li-Pong-KLexponent18 ; Yu-Li-Pong-KLexponent21  and the references
therein.

###  3.3 Convergence of iMEAL

When considering iMEAL, the Lyapunov functions need to be slightly modified
into

$\displaystyle{\cal E}_{\mathrm{imeal}}^{k}:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+3\alpha_{k}\|z^{k}-z^{k-1}\|^{2},\
\forall k\geq 1,$ (32)

associated with the implicit Lipschitz subgradient assumption, and

$\displaystyle\tilde{\cal E}_{\mathrm{imeal}}^{k}:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+4\alpha_{k}\|z^{k}-z^{k-1}\|^{2},\
\forall k\geq 1,$ (33)

associated with the implicit bounded subgradient assumption, where
$\alpha_{k}$ is defined in (26).

######  Theorem 3.2 (Iteration Complexity of iMEAL)

Let Assumptions 1 and 2(a) hold, $\gamma\in(0,\rho^{-1})$, and $\eta\in(0,2)$.
Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by iMEAL (7)
with $\sum_{k=0}^{\infty}\epsilon_{k}^{2}<\infty$. The following claims hold:

  1. (a)

Set $\beta$ sufficiently large such that in (27),
$\alpha<\min\left\\{\frac{1-\gamma\rho}{6\gamma(1+\gamma
L_{f})^{2}},\frac{1}{12\gamma}(\frac{2}{\eta}-1)\right\\}$. Under Assumption
2(b), if $\\{{\cal E}_{\mathrm{imeal}}^{k}\\}$ is lower bounded, then
$\xi^{k}_{\mathrm{meal}}=o(1/\sqrt{k})$ (cf. (21)).

  2. (b)

Pick $K\geq 1$. Set $\\{\beta_{k}\\}$ such that in (26),
$\alpha_{k}\equiv\frac{\hat{\alpha}^{*}}{K}$ for some positive constant
$\hat{\alpha}^{*}\leq\min\left\\{\frac{1-\rho\gamma}{8\gamma},\frac{1}{16\gamma}(\frac{2}{\eta}-1)\right\\}$.
Under Assumption 2(c), if $\\{\tilde{\cal E}_{\mathrm{imeal}}^{k}\\}$ is lower
bounded, then $\xi_{\mathrm{meal}}^{K}\leq\tilde{c}_{2}/\sqrt{K}$ for some
constant $\tilde{c}_{2}>0$.

By Theorem 3.2, the iteration complexity of iMEAL is the same as that of MEAL
and also consistent with that of inexact proximal ALM Xie-Wright19  (when the
stationary accuracy $\epsilon_{k}$ is square summable). Moreover, if the
condition on $\epsilon_{k}$ is strengthened to be
$\sum_{k=0}^{\infty}\epsilon_{k}<+\infty$ as required in the literature
Rockafellar76-PALM ; Wang19 , then following a proof similar for Proposition
1, global convergence and similar rates of MEAL also hold for iMEAL under the
assumptions required for Theorem 3.2(a) and the KŁ property.

##  4 Convergence of LiMEAL for Composite Objective

This section presents the convergence results of LiMEAL (9) for the
constrained problem with a composite objective (8). The proofs are postponed
to Section 5 below. Similar to Assumption 2, we make the following
assumptions.

###### Assumption 3

The objective $f(x)=h(x)+g(x)$ in problem (8) satisfies:

  1. (a)

$h$ is differentiable and $\nabla h$ is Lipschitz continuous with a constant
$L_{h}>0$;

  2. (b)

$g$ is proper lower-semicontinuous and $\rho_{g}$-weakly convex; and either

  3. (c)

$g$ has the implicit Lipschitz subgradient property with a constant $L_{g}>0$;
or

  4. (d)

$g$ has the implicit bounded subgradient property with a constant
$\hat{L}_{g}>0$.

In (c) and (d), $L_{g}$ and $\hat{L}_{g}$ may depend on $\gamma$.

By the update (9) of LiMEAL, some simple derivations show that

$\displaystyle x^{k+1}=\mathrm{Prox}_{\gamma,g}(z^{k}-\gamma(\nabla
h(x^{k})+A^{T}\lambda^{k+1}))$ (34)

and

$\displaystyle
g_{\mathrm{limeal}}^{k}:=\left(\begin{array}[]{c}\gamma^{-1}(z^{k}-x^{k+1})+(\nabla
h(x^{k+1})-\nabla h(x^{k}))\\\
\beta_{k}^{-1}(\lambda^{k+1}-\lambda^{k})\end{array}\right)\in\left(\begin{array}[]{c}\partial
f(x^{k+1})+A^{T}\lambda^{k+1}\\\ Ax^{k+1}-b\end{array}\right).$ (39)

Actually, the term $\gamma^{-1}(z^{k}-x^{k+1})$ represents some prox-gradient
sequence frequently used in the analysis of algorithms for the unconstrained
composite optimization (e.g., Davis-Drusvyatskiy19 ). Thus, let

$\displaystyle\xi_{\mathrm{limeal}}^{k}:=\min_{0\leq t\leq
k}\|g_{\mathrm{limeal}}^{t}\|,\ \forall k\in\mathbb{N},$ (40)

which can be taken as an effective stationarity measure of LiMEAL for problem
(8).

In the following, we present the iteration complexity of LiMEAL for problem
(8). Since the prox-linear scheme is adopted in the update of $x^{k+1}$ in
LiMEAL as described in (9), thus, the proximal term (i.e.,
$\|x^{k}-x^{k-1}\|^{2}$) should be generally included in the associated
Lyapunov functions of LiMEAL, shown as follows:

$\displaystyle{\cal E}^{k}_{\mathrm{limeal}}$ $\displaystyle:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+3\alpha_{k}(\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}+\|z^{k}-z^{k-1}\|^{2})$
(41)

associated with the implicit Lipschitz gradient assumption, and

$\displaystyle\tilde{\cal E}_{\mathrm{limeal}}^{k}:={\cal
P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})+4{\alpha}_{k}(\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}+\|z^{k}-z^{k-1}\|^{2}),$
(42)

associated with the implicit bounded subgradient assumption, where
$\alpha_{k}$ is defined in (26).

The iteration complexity of MEAL can be similarly generalized to LiMEAL as
follows.

######  Theorem 4.1 (Iteration Complexity of LiMEAL)

Take Assumptions 1 and 3(a)-(b). Pick $\eta\in(0,2)$ and
$0<\gamma<\frac{2}{(\rho_{g}+L_{h})\left(1+\sqrt{1+\frac{2(2-\eta)\eta
L_{h}^{2}}{(\rho_{g}+L_{h})^{2}}}\right)}$. Let
$\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by LiMEAL (9). The
following claims hold:

  1. (a)

Set $\beta$ sufficiently large such that
$\alpha<\min\left\\{\frac{1}{12\gamma}(\frac{2}{\eta}-1),\frac{1-\gamma(\rho_{g}+L_{h})-\eta(1-\eta/2)\gamma^{2}L_{h}^{2}}{6\gamma\left((1+\gamma
L_{g})^{2}+\gamma^{2}L_{h}^{2}\right)}\right\\}$. Under Assumption 3(c), if
$\\{{\cal E}^{k}_{\mathrm{limeal}}\\}$ is lower bounded, then
$\xi^{k}_{\mathrm{limeal}}=o(1/\sqrt{k})$.

  2. (b)

Pick $K\geq 1$. Set $\\{\beta_{k}\\}$ such that
$\alpha_{k}\equiv\frac{\bar{\alpha}^{*}}{K}$ for some positive constant
$\bar{\alpha}^{*}\leq\min\Big{\\{}\frac{1-\gamma\left(\rho_{g}+L_{h})-\eta(1-\eta/2)\gamma^{2}L_{h}^{2}\right)}{8\gamma(1+\gamma^{2}L_{h}^{2})}$,
$\frac{1}{16\gamma}\left(\frac{2}{\eta}-1\right)\Big{\\}}$. Under Assumption
3(d), if $\\{\tilde{\cal E}^{k}_{\mathrm{limeal}}\\}$ is lower bounded, then
$\xi_{\mathrm{limeal}}^{K}\leq\tilde{c}_{3}/\sqrt{K}$ for some constant
$\tilde{c}_{3}>0$.

Similar to the discussions following Theorem 3.1, to yield an
$\varepsilon$-accurate first-order stationary point, the iteration complexity
of LiMEAL is $o(\varepsilon^{-2})$ under the implicit Lipschitz subgradient
assumption and ${\cal O}(\varepsilon^{-2})$ under the implicit bounded
subgradient assumption, as demonstrated by Theorem 4.1. The conditions on
$\beta$ and $\beta_{k}$ in these two cases can be derived similarly to (28)
and (29), respectively.

In the following, we establish the global convergence and rates of LiMEAL
under assumptions required for Theorem 4.1(a) and the KŁ property.
Specifically, let $\hat{x}^{k}:=x^{k-1},\ \hat{z}^{k}:=z^{k-1},\
{y}^{k}:=(x^{k},z^{k},\lambda^{k},\hat{x}^{k},\hat{z}^{k}),\ \forall k\geq 1,$
${y}:=(x,z,\lambda,\hat{x},\hat{z})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{n}\times\mathbb{R}^{n},$
and

$\displaystyle{\cal P}_{\mathrm{limeal}}({y}):={\cal
P}_{\beta}(x,z,\lambda)+4\alpha\left(\|z-\hat{z}\|^{2}+\gamma^{2}L_{h}^{2}\|x-\hat{x}\|^{2}\right).$
(43)

######  Proposition 3 (Global convergence and rates of LiMEAL)

Suppose that Assumptions 1 and 3(a)-(c) hold and that the sequence
$\\{(x^{k},z^{k},\lambda^{k})\\}$ generated by LiMEAL (9) is bounded. If
$\gamma\in(0,\frac{1}{\rho_{g}+L_{h}})$, $\eta\in(0,2)$,
$0<\alpha<\min\left\\{\frac{1}{8\gamma}\left(\frac{2}{\eta}-1\right),\frac{1-\gamma(\rho_{g}+L_{h})}{8\gamma\left((1+\gamma
L_{g})^{2}+\gamma^{2}L_{h}^{2}\right)}\right\\}$, and ${\cal
P}_{\mathrm{limeal}}$ satisfies the KŁ property at some point
$y^{*}:=(x^{*},x^{*},\lambda^{*},x^{*},x^{*})$ with an exponent of
$\theta\in[0,1)$, where $(x^{*},\lambda^{*})$ is a limit point of
$\\{(x^{k},\lambda^{k})\\}$, then

  1. (a)

the whole sequence $\\{\hat{y}^{k}:=(x^{k},z^{k},\lambda^{k})\\}$ converges to
$\hat{y}^{*}:=(x^{*},x^{*},\lambda^{*})$; and

  2. (b)

all the rates of convergence results in Proposition 1(b) also hold for LiMEAL.

###### Remark 2

The established results in this section is more general than those in Zhang-
Luo18  and done under weaker assumptions on $h$ and for more general class of
$g$. Specifically, as discussed in Section 1.2, the algorithm studied in
Zhang-Luo18  is a prox-linear version of LiMEAL with $g$ being an indicator
function of a box constraint set. In Zhang-Luo18 , global convergence and a
linear rate of proximal inexact ALM were proved for quadratic programming,
where that the augmented Lagrangian satisfies the KŁ inequality with exponent
$1/2$. Besides, the strict complementarity condition required in Zhang-Luo18
is also removed in this paper for LiMEAL.

##  5 Main Proofs

In this section, we first prove some lemmas and then present the proofs of our
main convergence results.

###  5.1 Preliminary Lemmas

####  5.1.1 Lemmas on Iteration Complexity and Global Convergence

The first lemma concerns the convergence speed of a nonenegative sequence
$\\{\xi_{k}\\}$ satisfying the following relation

$\displaystyle\tilde{\eta}\xi_{k}^{2}\leq({\cal E}_{k}-{\cal
E}_{k+1})+\tilde{\epsilon}_{k}^{2},\ \forall k\in\mathbb{N},$ (44)

where $\tilde{\eta}>0$, $\\{{\cal E}_{k}\\}$ and $\\{\tilde{\epsilon}_{k}\\}$
are two nonnegative sequences, and
$\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}<+\infty$.

###### Lemma 1

For any sequence $\\{\xi_{k}\\}$ satisfying (44),
$\tilde{\xi}_{k}:=\min_{1\leq t\leq k}\xi_{t}=o(1/\sqrt{k})$.

###### Proof

Summing (44) over $k$ from $1$ to $K$ and letting $K\rightarrow+\infty$ yields

$\displaystyle\sum_{k=1}^{\infty}\xi_{k}^{2}\leq\tilde{\eta}^{-1}\left({\cal
E}_{1}+\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}\right)<+\infty,$

which implies the desired convergence speed by
$\frac{k}{2}\tilde{\xi}_{k}^{2}\leq\sum_{\frac{k}{2}\leq j\leq
k}{\xi}_{j}^{2}\rightarrow 0$ as $k\rightarrow\infty$, as proved in (Deng-
parallelADMM17, , Lemma 1.1).

Then we provide a lemma to show the convergence speed of a nonenegative
sequence $\\{\xi_{k}\\}$ satisfying the following relation instead of (44)

$\displaystyle\tilde{\eta}\xi_{k}^{2}\leq({\cal E}_{k}-{\cal
E}_{k+1})+\tilde{\epsilon}_{k}^{2}+{\alpha}_{k}\tilde{L},\ \forall
k\in\mathbb{N},$ (45)

where $\tilde{\eta}>0,$ $\tilde{L}>0$, $\\{{\cal E}_{k}\\}$,
$\\{{\alpha}_{k}\\}$ and $\\{\tilde{\epsilon}_{k}\\}$ are nonnegative
sequences, and $\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}<+\infty$.

###### Lemma 2

Pick $K\geq 1$. Let $\\{\xi_{k}\\}$ be a nonnegative sequence satisfying (45).
Set $\alpha_{k}\equiv\frac{\tilde{\alpha}}{K}$ for some $\tilde{\alpha}>0$.
Then $\tilde{\xi}_{K}:=\min_{1\leq k\leq K}\xi_{k}\leq\tilde{c}/\sqrt{K}$ for
some constant $\tilde{c}>0$.

###### Proof

Summing (45) over $k$ from $1$ to $K$ yields

$\displaystyle\sum_{k=1}^{K}\xi_{k}^{2}\leq\frac{{\cal
E}_{1}+\sum_{k=1}^{K}\tilde{\epsilon}_{k}^{2}+\tilde{L}\sum_{k=1}^{K}\alpha_{k}}{\tilde{\eta}}.$

From $\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}<+\infty$ and
$\sum_{k=1}^{K}{\alpha}_{k}=\tilde{\alpha}$, we get
$K\tilde{\xi}_{K}^{2}\leq\sum_{k=1}^{K}\xi_{k}^{2}\leq\frac{{\cal
E}_{1}+\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}+\tilde{L}\tilde{\alpha}}{\tilde{\eta}}<+\infty$.
The result follows with $\tilde{c}:=\sqrt{{\cal
E}_{1}+\sum_{k=1}^{\infty}\tilde{\epsilon}_{k}^{2}+\tilde{L}\tilde{\alpha}}/\sqrt{{\tilde{\eta}}}$.

In both Lemmas 1 and 2, the nonnegative assumption on the sequence $\\{{\cal
E}_{k}\\}$ can be relaxed to its lower boundedness.

The following lemma presents the global convergence and rate of a sequence
generated by some algorithm for the nonconvex optimization problem, based on
the Kurdyka-Łojasiewicz inequality, where the global convergence result is
from (Attouch13, , Theorem 2.9) while the rate results are from (Attouch-
Bolte09, , Theorem 5).

######  Lemma 3 (Existing global convergence and rate)

Let ${\cal L}$ be a proper, lower semicontinuous function, and $\\{u^{k}\\}$
be a sequence that satisfies the following three conditions:

  1. (P1)

(Sufficient decrease condition) there exists a constant $a_{1}>0$ such that
${\cal L}(u^{k+1})+a_{1}\|u^{k+1}-u^{k}\|^{2}\leq{\cal L}(u^{k}),\ \forall
k\in\mathbb{N};$

  2. (P2)

(Bounded subgradient condition) for each $k\in\mathbb{N}$, there exists
$v^{k+1}\in\partial{\cal L}(u^{k+1})$ such that $\|v^{k+1}\|\leq
a_{2}\|u^{k+1}-u^{k}\|$ for some constant $a_{2}>0$;

  3. (P3)

(Continuity condition) there exist a subsequence $\\{u^{k_{j}}\\}$ and
$\tilde{u}$ such that $u^{k_{j}}\rightarrow\tilde{u}$ and ${\cal
L}(u^{k_{j}})\rightarrow{\cal L}(\tilde{u})$ as $j\rightarrow\infty$.

If ${\cal L}$ satisfies the KŁ inequality at $\tilde{u}$ with an exponent of
$\theta$, then

  1. (1)

$\\{u^{k}\\}$ converges to $\tilde{u}$; and

  2. (2)

depending on $\theta$, (i) if $\theta=0$, then $\\{u^{k}\\}$ converges within
a finite number of iterations; (ii) if $\theta\in(0,\frac{1}{2}]$, then
$\|u^{k}-\tilde{u}\|\leq c\tau^{k}$ for all $k\geq k_{0}$, for certain
$k_{0}>0,c>0,\tau\in(0,1)$; and (iii) if $\theta\in(\frac{1}{2},1)$, then
$\|u^{k}-\tilde{u}\|\leq ck^{-\frac{1-\theta}{2\theta-1}}$ for all $k\geq
k_{0}$, for certain $k_{0}>0,c>0$.

####  5.1.2 Lemmas on controlling dual ascent by primal descent

In the following, we establish several lemmas to show that the dual ascent
quantities of proposed algorithms can be controlled by the primal descent
quantities.

######  Lemma 4 (MEAL: controlling dual by primal)

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by MEAL (5).
Take $\gamma\in(0,\rho^{-1})$.

  1. (a)

Under Assumptions 1, 2(a), and 2(b), we have for any $k\geq 1$,

$\displaystyle\|A^{T}(\lambda^{k+1}-\lambda^{k})\|\leq(L_{f}+\gamma^{-1})\|x^{k+1}-x^{k}\|+\gamma^{-1}\|z^{k}-z^{k-1}\|,$
(46) $\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
2c_{\gamma,A}^{-1}\left[(\gamma
L_{f}+1)^{2}\|x^{k+1}-x^{k}\|^{2}+\|z^{k}-z^{k-1}\|^{2}\right],$ (47)

where $c_{\gamma,A}=\gamma^{2}\tilde{\sigma}_{\min}(A^{T}A)$.

  2. (b)

Alternatively, under Assumptions 1, 2(a), and 2(c), we have for any $k\geq 1$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
3c_{\gamma,A}^{-1}\left[4\gamma^{2}\hat{L}^{2}_{f}+\|x^{k+1}-x^{k}\|^{2}+\|z^{k}-z^{k-1}\|^{2}\right].$
(48)

###### Proof

The update (5) of $x^{k+1}$ implies

$\displaystyle
x^{k+1}=\operatorname*{argmin}_{x}\left\\{f(x)+\langle\lambda^{k},Ax-b\rangle+\frac{\beta_{k}}{2}\|Ax-b\|^{2}+\frac{1}{2\gamma}\|x-z^{k}\|^{2}\right\\}.$

Its optimality condition and the update (5) of $\lambda^{k+1}$ in MEAL
together give us

$\displaystyle 0\in\partial\left(f+\frac{1}{2\gamma}\|\cdot-(z^{k}-\gamma
A^{T}\lambda^{k+1})\|^{2}\right)(x^{k+1}).$ (49)

Let $w^{k+1}:=z^{k}-\gamma A^{T}\lambda^{k+1},\ \forall k\in\mathbb{N}.$ The
above inclusion implies

$\displaystyle x^{k+1}=\mathrm{Prox}_{\gamma,f}(w^{k+1}),$ (50)

and thus by (13),

$\displaystyle A^{T}\lambda^{k+1}$ $\displaystyle=-\nabla{\cal
M}_{\gamma,f}(w^{k+1})-\gamma^{-1}(x^{k+1}-z^{k}),$ (51)

which further implies

$\displaystyle\|A^{T}(\lambda^{k+1}-\lambda^{k})\|$
$\displaystyle=\|(\nabla{\cal M}_{\gamma,f}(w^{k+1})-\nabla{\cal
M}_{\gamma,f}(w^{k}))+\gamma^{-1}(x^{k+1}-x^{k})-\gamma^{-1}(z^{k}-z^{k-1})\|.$

(a) With Assumption 2(b), the above equality yields

$\displaystyle\|A^{T}(\lambda^{k+1}-\lambda^{k})\|\leq(L_{f}+\gamma^{-1})\|x^{k+1}-x^{k}\|+\gamma^{-1}\|z^{k}-z^{k-1}\|,$

which leads to (46). By Assumption 1 and the relation
$\lambda^{k+1}-\lambda^{k}=\beta_{k}(Ax^{k+1}-b)$,
$(\lambda^{k+1}-\lambda^{k})\in\mathrm{Im}(A)$. Thus, from the above
inequality, we deduce

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|\leq\tilde{\sigma}_{\min}^{-1/2}(A^{T}A)\left[(L_{f}+\gamma^{-1})\|x^{k+1}-x^{k}\|+\gamma^{-1}\|z^{k}-z^{k-1}\|\right],$

and, further by $(u+v)^{2}\leq 2(u^{2}+v^{2})$ for any $u,v\in\mathbb{R}$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
2\tilde{\sigma}_{\min}^{-1}(A^{T}A)\left[(L_{f}+\gamma^{-1})^{2}\|x^{k+1}-x^{k}\|^{2}+\gamma^{-2}\|z^{k}-z^{k-1}\|^{2}\right].$

(b) From Assumption 2(c), we have

$\displaystyle\|A^{T}(\lambda^{k+1}-\lambda^{k})\|\leq
2\hat{L}_{f}+\gamma^{-1}(\|x^{k+1}-x^{k}\|+\|z^{k}-z^{k-1}\|),$

which implies

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|\leq\tilde{\sigma}_{\min}^{-1/2}(A^{T}A)\left[2\hat{L}_{f}+\gamma^{-1}(\|x^{k+1}-x^{k}\|+\|z^{k}-z^{k-1}\|)\right],$

and further by $(a+c+d)^{2}\leq 3(a^{2}+c^{2}+d^{2})$ for any
$a,c,d\in\mathbb{R}$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
3\tilde{\sigma}_{\min}^{-1}(A^{T}A)\left[4\hat{L}^{2}_{f}+\gamma^{-2}(\|x^{k+1}-x^{k}\|^{2}+\|z^{k}-z^{k-1}\|^{2})\right].$

The similar lemma also holds for iMEAL shown as follows.

######  Lemma 5 (iMEAL: controlling dual by primal)

Let $(x^{k},z^{k},\lambda^{k})$ be a sequence generated by iMEAL (7). Take
$\gamma\in(0,\rho^{-1})$.

  1. (a)

Under Assumptions 1 2(a), and 2(b), for any $k\geq 1$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
3c_{\gamma,A}^{-1}\left[(\gamma
L_{f}+1)^{2}\|x^{k+1}-x^{k}\|^{2}+\|z^{k}-z^{k-1}\|^{2}+\gamma^{2}(\epsilon_{k}+\epsilon_{k-1})^{2}\right].$

  2. (b)

Alternatively, under Assumptions 1 2(a), and 2(c), for any $k\geq 1$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}\leq
4c_{\gamma,A}^{-1}\left[4\gamma^{2}\hat{L}^{2}_{f}+\|x^{k+1}-x^{k}\|^{2}+\|z^{k}-z^{k-1}\|^{2}+\gamma^{2}(\epsilon_{k}+\epsilon_{k-1})^{2}\right].$

###### Proof

The proof is similar to that of Lemma 4, but with (49) being replaced by

$\displaystyle
0\in\partial\left(f+\frac{1}{2\gamma}\left\|\cdot-\Big{(}z^{k}-\gamma(A^{T}\lambda^{k+1}-s^{k})\Big{)}\right\|^{2}\right)(x^{k+1}),$

and thus $w^{k+1}:=z^{k}-\gamma(A^{T}\lambda^{k+1}-s^{k}).$

######  Lemma 6 (LiMEAL: controlling dual by primal)

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by LiMEAL (9).
Take $\gamma\in(0,\rho_{g}^{-1})$.

  1. (a)

Under Assumptions 1, 3(a)-(b), and 3(c), for any $k\geq 1$,

$\displaystyle\|A^{T}(\lambda^{k+1}-\lambda^{k})\|$ (52)
$\displaystyle\leq(L_{g}+\gamma^{-1})\|x^{k+1}-x^{k}\|+L_{h}\|x^{k}-x^{k-1}\|+\gamma^{-1}\|z^{k}-z^{k-1}\|,$
$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}$ (53) $\displaystyle\leq
3c_{\gamma,A}^{-1}\left[(\gamma
L_{g}+1)^{2}\|x^{k+1}-x^{k}\|^{2}+\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}+\|z^{k}-z^{k-1}\|^{2}\right].$

  2. (b)

Alternatively, under Assumptions 1, 3(a)-(b), and 3(d), for any $k\geq 1$,

$\displaystyle\|\lambda^{k+1}-\lambda^{k}\|^{2}$ (54) $\displaystyle\leq
4c_{\gamma,A}^{-1}\left[4\gamma^{2}\hat{L}^{2}_{g}+\|x^{k+1}-x^{k}\|^{2}+\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}+\|z^{k}-z^{k-1}\|^{2}\right].$

###### Proof

The proof is also similar to that of Lemma 4, but (49) needs to be modified to

$\displaystyle
0\in\partial\left(g+\frac{1}{2\gamma}\|\cdot-\Big{(}z^{k}-\gamma(A^{T}\lambda^{k+1}+\nabla
h(x^{k}))\Big{)}\|^{2}\right)(x^{k+1}),$

and thus $w^{k+1}:=z^{k}-\gamma(A^{T}\lambda^{k+1}+\nabla h(x^{k}))).$

####  5.1.3 Lemmas on One-step Progress

Here, we provide several lemmas to characterize the progress achieved by a
single iterate of the proposed algorithms.

######  Lemma 7 (MEAL: one-step progress)

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by MEAL (4).
Take Assumption 2(a), $\gamma\in(0,\rho^{-1})$, and $\eta\in(0,2)$. Then for
any $k\in\mathbb{N}$,

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{(1-\gamma\rho)}{2\gamma}\|x^{k+1}-x^{k}\|^{2}$
(55)
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}+\frac{1}{4}\gamma\eta(2-\eta)\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-\alpha_{k}c_{\gamma,A}\|\lambda^{k+1}-\lambda^{k}\|^{2},$

where $\alpha_{k}$ is presented in (26) and
$c_{\gamma,A}=\gamma^{2}\tilde{\sigma}_{\min}(A^{T}A)$.

###### Proof

By the update (5) of $x^{k+1}$ in MEAL, $x^{k+1}$ is updated via minimizing a
strongly convex function ${\cal P}_{\beta_{k}}(x,z^{k},\lambda^{k})$ with
modulus at least $(\gamma^{-1}-\rho)$, we have

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k}}(x^{k+1},z^{k},\lambda^{k})\geq\frac{\gamma^{-1}-\rho}{2}\|x^{k+1}-x^{k}\|^{2}.$
(56)

Next, recall in (5), $z^{k+1}=z^{k}+\eta(x^{k+1}-z^{k})$ implies

$\displaystyle 2x^{k+1}-z^{k}-z^{k+1}=(2\eta^{-1}-1)(z^{k+1}-z^{k}).$ (57)

So we have

$\displaystyle{\cal P}_{\beta_{k}}(x^{k+1},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k}}(x^{k+1},z^{k+1},\lambda^{k})=\frac{1}{2\gamma}(\|x^{k+1}-z^{k}\|^{2}-\|x^{k+1}-z^{k+1}\|^{2})$
$\displaystyle=\frac{1}{2\gamma}\langle
z^{k+1}-z^{k},2x^{k+1}-z^{k}-z^{k+1}\rangle=\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}.$

Moreover, by the update $\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b)$, we
have

$\displaystyle{\cal P}_{\beta_{k}}(x^{k+1},z^{k+1},\lambda^{k})-{\cal
P}_{\beta_{k}}(x^{k+1},z^{k+1},\lambda^{k+1})=-\beta_{k}^{-1}\|\lambda^{k+1}-\lambda^{k}\|^{2},$

and

$\displaystyle{\cal P}_{\beta_{k}}(x^{k+1},z^{k+1},\lambda^{k+1})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})=\frac{\beta_{k}-\beta_{k+1}}{2\beta_{k}^{2}}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

Combining the above four terms of estimates yields

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})$ (58)
$\displaystyle\geq\frac{(1-\rho\gamma)}{2\gamma}\|x^{k+1}-x^{k}\|^{2}+\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-\frac{\beta_{k}+\beta_{k+1}}{2\beta_{k}^{2}}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

Then, we establish (55) from (58). By the definition (20) of
$\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})$, we have

$\displaystyle\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}=(\eta\gamma)^{-2}\|z^{k}-z^{k+1}\|^{2}+\beta_{k}^{-2}\|\lambda^{k+1}-\lambda^{k}\|^{2},$

which implies

$\displaystyle(\eta\gamma)^{-2}\|z^{k}-z^{k+1}\|^{2}=\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-\beta_{k}^{-2}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

Substituting this into the above inequality yields

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{(1-\gamma\rho)}{2\gamma}\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}+\frac{1}{4}\gamma\eta(2-\eta)\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-\alpha_{k}c_{\gamma,A}\|\lambda^{k+1}-\lambda^{k}\|^{2},$

where
$\alpha_{k}=\frac{\beta_{k}+\beta_{k+1}+\gamma\eta(1-\eta/2)}{2c_{\gamma,A}\beta_{k}^{2}}$.
This finishes the proof.

Next, we provide a lemma for iMEAL (7).

######  Lemma 8 (iMEAL: one-step progress)

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by iMEAL (7).
Take Assumptions 2(a) and (b), $\gamma\in(0,\rho^{-1})$, and $\eta\in(0,2)$.
It holds that

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})$ (59)
$\displaystyle\geq\frac{(1-\gamma\rho)}{2\gamma}\|x^{k+1}-x^{k}\|^{2}+\langle
s^{k},x^{k}-x^{k+1}\rangle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}$
$\displaystyle+\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-\alpha_{k}c_{\gamma,A}\|\lambda^{k+1}-\lambda^{k}\|^{2},\
\forall k\in\mathbb{N}.$

###### Proof

The proof of this lemma is similar to that of Lemma 7 and uses the descent
quantity along the update of $x^{k+1}$. By the update (7) of $x^{k+1}$ in
iMEAL and noticing that ${\cal
L}_{\beta_{k}}(x,\lambda^{k})+\frac{\|x-z^{k}\|}{2\gamma}$ is strongly convex
with modulus at least $(\gamma^{-1}-\rho)$, we have

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})$
$\displaystyle\geq{\cal P}_{\beta_{k}}(x^{k+1},z^{k},\lambda^{k})+\langle
s^{k},x^{k}-x^{k+1}\rangle+\frac{\gamma^{-1}-\rho}{2}\|x^{k+1}-x^{k}\|^{2}.$

By replacing (56) in the proof of Lemma 7 with the above inequality and
following the rest part of its proof, we obtain the following inequality

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{1-\gamma\rho}{2\gamma}\|x^{k+1}-x^{k}\|^{2}+\langle
s^{k},x^{k}-x^{k+1}\rangle$
$\displaystyle+\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-\frac{\beta_{k}+\beta_{k+1}}{2\beta_{k}^{2}}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

We can establish (59) with a derivation similar to that in the proof of Lemma
7.

Also, we state a similar lemma for one-step progress of LiMEAL (9) as follows.

######  Lemma 9 (LiMEAL: one-step progress)

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be a sequence generated by LiMEAL (9).
Take Assumptions 3(a) and (b), $\gamma\in(0,\rho_{g}^{-1})$, and
$\eta\in(0,2)$. We have

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})$ (60)
$\displaystyle\geq\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-\frac{1}{4}\gamma(2-\eta)\eta
L_{h}^{2}\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}+\frac{1}{4}\gamma(1-\eta_{k}/2)\eta\|g_{\mathrm{limeal}}^{k}\|^{2}-\alpha_{k}c_{\gamma,A}\|\lambda^{k+1}-\lambda^{k}\|^{2},\
\forall k\in\mathbb{N}.$

###### Proof

The proof of this lemma is similar to that of Lemma 7. By the update (9) of
$x^{k+1}$ in LiMEAL, $x^{k+1}$ is updated via minimizing
$(\gamma^{-1}-\rho_{g})$-strongly convex ${\cal
L}_{\beta_{k},f^{k}}(x,\lambda^{k})+\frac{\|x-z^{k}\|}{2\gamma}$, so

$\displaystyle{\cal
L}_{\beta_{k},f^{k}}(x^{k},\lambda^{k})+\frac{\|x^{k}-z^{k}\|^{2}}{2\gamma}\geq{\cal
L}_{\beta_{k},f^{k}}(x^{k+1},\lambda^{k})+\frac{\|x-z^{k}\|^{2}}{2\gamma}+\frac{\gamma^{-1}-\rho_{g}}{2}\|x^{k+1}-x^{k}\|^{2}.$

By definition, ${\cal L}_{\beta_{k},f^{k}}(x,\lambda)=h(x^{k})+\langle\nabla
h(x^{k}),x-x^{k}\rangle+g(x)+\langle\lambda,Ax-b\rangle+\frac{\beta}{2}\|Ax-b\|^{2}$
and ${\cal
P}_{\beta_{k}}(x,z,\lambda)=h(x)+g(x)+\langle\lambda,Ax-b\rangle+\frac{\beta_{k}}{2}\|Ax-b\|^{2}+\frac{\|x-z\|^{2}}{2\gamma}$,
so the above inequality implies

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})$
$\displaystyle\geq{\cal
P}_{\beta_{k}}(x^{k+1},z^{k},\lambda^{k})+\frac{\gamma^{-1}-\rho_{g}}{2}\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle-(h(x^{k+1})-h(x^{k})-\langle\nabla
h(x^{k}),x^{k+1}-x^{k}\rangle)$ $\displaystyle\geq{\cal
P}_{\beta_{k}}(x^{k+1},z^{k},\lambda^{k})+\frac{\gamma^{-1}-\rho_{g}-L_{h}}{2}\|x^{k+1}-x^{k}\|^{2},$

where the second inequality is due to the $L_{h}$-Lipschitz continuity of
$\nabla h$. By replacing (56) in the proof of Lemma 7 with the above
inequality and following the rest part of that proof, we obtain

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})$ (61)
$\displaystyle\geq\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}\|x^{k+1}-x^{k}\|^{2}+\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-\frac{\beta_{k}+\beta_{k+1}}{2\beta_{k}^{2}}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

Next, based on the above inequality, we establish (60). By the definition (39)
of $g_{\mathrm{limeal}}^{k}$ and noticing that
$z^{k}-x^{k+1}=-\eta^{-1}(z^{k+1}-z^{k})$ by the update (9) of $z^{k+1}$, we
have

$\|g_{\mathrm{limeal}}^{k}\|^{2}\leq
2L_{h}^{2}\|x^{k+1}-x^{k}\|^{2}+2(\gamma\eta)^{-2}\|z^{k+1}-z^{k}\|^{2}+\beta_{k}^{-2}\|\lambda^{k+1}-\lambda^{k}\|^{2},$

which implies

$(\gamma\eta)^{-2}\|z^{k+1}-z^{k}\|^{2}\geq\frac{1}{2}\|g_{\mathrm{limeal}}^{k}\|^{2}-\frac{1}{2}\beta_{k}^{-2}\|\lambda^{k+1}-\lambda^{k}\|^{2}-L_{h}^{2}\|x^{k+1}-x^{k}\|^{2}.$

Substituting this inequality into (61) yields

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})$
$\displaystyle\geq\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-\frac{1}{4}\gamma(2-\eta)\eta
L_{h}^{2}\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}+\frac{1}{4}\gamma(1-\eta/2)\eta\|g_{\mathrm{limeal}}^{k}\|^{2}-\alpha_{k}c_{\gamma,A}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

This finishes the proof of this lemma.

###  5.2 Proofs for Convergence of MEAL

Based on the above lemmas, we give proofs of Theorem 3.1 and Proposition 1.

####  5.2.1 Proof of Theorem 3.1

###### Proof

We first establish the $o(1/\sqrt{k})$ rate of convergence under the implicit
Lipschitz subgradient assumption (Assumption 2(b)) and then the convergence
rate result under the implicit bounded subgradient assumption (Assumption
2(c)).

(a) In the first case, $\beta_{k}=\beta$ and $\alpha_{k}=\alpha$. Substituting
(47) into (55) yields

$\displaystyle{\cal P}_{\beta}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta}(z^{k},\lambda^{k})\|^{2}$
$\displaystyle+\left(\frac{(1-\gamma\rho)}{2\gamma}-2\alpha(1+\gamma
L_{f})^{2}\right)\|x^{k+1}-x^{k}\|^{2}+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}$
$\displaystyle-2\alpha\|z^{k}-z^{k-1}\|^{2}.$

By the definition (24) of ${\cal E}_{\mathrm{meal}}^{k}$, the above inequality
implies

$\displaystyle{\cal E}_{\mathrm{meal}}^{k}-{\cal E}_{\mathrm{meal}}^{k+1}$
$\displaystyle\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta}(z^{k},\lambda^{k})\|^{2}+\left(\frac{1}{4\gamma}(\frac{2}{\eta}-1)-2\alpha\right)\|z^{k+1}-z^{k}\|^{2}$
$\displaystyle+\left(\frac{1-\gamma\rho}{2\gamma}-2\alpha(1+\gamma
L_{f})^{2}\right)\|x^{k+1}-x^{k}\|^{2}$ (62)
$\displaystyle\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta}(z^{k},\lambda^{k})\|^{2},$

where the second inequality holds due to the condition on $\alpha$. Thus,
claim (a) follows from the above inequality, Lemma 1 with
$\tilde{\epsilon}_{k}=0$ and the lower boundedness of $\\{{\cal
E}_{\mathrm{meal}}^{k}\\}$.

(b) Similarly, substituting (48) into (55) and using the definition (25) of
$\tilde{\cal E}_{\mathrm{meal}}^{k}$, we have

$\displaystyle\tilde{\cal E}_{\mathrm{meal}}^{k}-\tilde{\cal
E}_{\mathrm{meal}}^{k+1}\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-12\alpha_{k}\gamma^{2}\hat{L}_{f}^{2}$
$\displaystyle+\left(\frac{1-\gamma\rho}{2\gamma}-3\alpha_{k}\right)\|x^{k+1}-x^{k}\|^{2}+\left(\frac{1}{4\gamma}(\frac{2}{\eta}-1)-3\alpha_{k+1}\right)\|z^{k+1}-z^{k}\|^{2}.$

With $\alpha_{k}=\frac{\alpha^{*}}{K}$,

$\displaystyle\tilde{\cal E}_{\mathrm{meal}}^{k}-\tilde{\cal
E}_{\mathrm{meal}}^{k+1}\geq\frac{1}{2}\gamma(1-\eta/2)\eta\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-12\alpha_{k}\gamma^{2}\hat{L}_{f}^{2},$

which yields claim (b) by Lemma 2 with $\tilde{\epsilon}_{k}=0$ and the lower
boundedness of $\\{\tilde{\cal E}_{\mathrm{meal}}^{k}\\}$.

####  5.2.2 Proof of Proposition 1

###### Proof

With Lemma 3, we only need to check conditions $(P1)$-$(P3)$ hold for MEAL.

(a) Establishing $(P1)$: With $a:=\frac{\gamma\eta(2-\eta)}{4\beta}$, we have
$\frac{1+a}{\beta c_{\gamma,A}}=\alpha$ for $\alpha$ in (27). Substituting
(47) into (58) with fixed $\beta_{k}$ yields

$\displaystyle{\cal P}_{\beta}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta}(x^{k+1},z^{k+1},\lambda^{k+1})\geq(\frac{1-\rho\gamma}{2\gamma}-2\alpha(\gamma
L_{f}+1)^{2})\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-2\alpha\|z^{k}-z^{k-1}\|^{2}+a\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

For the definition (30) of ${\cal P}_{\mathrm{meal}}$ and the assumption on
$\alpha$, we deduce from the above inequality:

$\displaystyle{\cal P}_{\mathrm{meal}}(y^{k})-{\cal
P}_{\mathrm{meal}}(y^{k+1})\geq(\frac{1-\rho\gamma}{2\gamma}-2\alpha(\gamma
L_{f}+1)^{2})\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\left(\frac{1}{2\gamma}(\frac{2}{\eta}-1)-3\alpha\right)\|z^{k+1}-z^{k}\|^{2}+\alpha\|z^{k}-z^{k-1}\|^{2}+a\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|^{2}$
$\displaystyle\geq c_{1}\|y^{k+1}-y^{k}\|^{2},$ (63)

where $c_{1}:=\min\left\\{\frac{1-\rho\gamma}{2\gamma}-2\alpha(\gamma
L_{f}+1)^{2},\alpha,a\beta^{-1}\right\\}$ by
$\frac{1}{2\gamma}(\frac{2}{\eta}-1)-3\alpha\geq\alpha$. This yields $(P1)$
for MEAL.

(b) Establishing $(P2)$: Note that ${\cal
P}_{\mathrm{meal}}(y)=f(x)+\langle\lambda,Ax-b\rangle+\frac{\beta}{2}\|Ax-b\|^{2}+\frac{1}{2\gamma}\|x-z\|^{2}+3\alpha\|z-\hat{z}\|^{2}$.
The optimality condition from the update of $x^{k+1}$ in (5) is

$\displaystyle 0\in\partial
f(x^{k+1})+A^{T}\lambda^{k+1}+\gamma^{-1}(x^{k+1}-z^{k}),$

which implies
$\gamma^{-1}(z^{k}-z^{k+1})+A^{T}(\lambda^{k+1}-\lambda^{k})\in\partial_{x}{\cal
P}_{\mathrm{meal}}(y^{k+1}).$ From the update of $z^{k+1}$ in (5),
$z^{k+1}-x^{k+1}=-(1-\eta)\eta^{-1}(z^{k+1}-z^{k})$ and thus

$\displaystyle\partial_{z}{\cal
P}_{\mathrm{meal}}(y^{k+1})=\gamma^{-1}(z^{k+1}-x^{k+1})+6\alpha(z^{k+1}-z^{k})=\left(6\alpha-\frac{1-\eta}{\eta\gamma}\right)(z^{k+1}-z^{k}).$

The update of $\lambda^{k+1}$ in (5) yields $\partial_{\lambda}{\cal
P}_{\mathrm{meal}}(y^{k+1})=Ax^{k+1}-b=\beta^{-1}(\lambda^{k+1}-\lambda^{k}).$
Moreover, it is easy to show $\partial_{\hat{z}}{\cal
P}_{\mathrm{meal}}(y^{k+1})=6\alpha(z^{k}-z^{k+1}).$ Thus, let

$v^{k+1}:=\left(\begin{array}[]{c}\gamma^{-1}(z^{k}-z^{k+1})+A^{T}(\lambda^{k+1}-\lambda^{k})\\\
\left(6\alpha-\frac{1-\eta}{\eta\gamma}\right)(z^{k+1}-z^{k})\\\
\beta^{-1}(\lambda^{k+1}-\lambda^{k})\\\
6\alpha(z^{k}-z^{k+1})\end{array}\right),$

which obeys $v^{k+1}\in\partial{\cal P}_{\mathrm{meal}}(y^{k+1})$ and

$\displaystyle\|v^{k+1}\|$
$\displaystyle\leq\left(\gamma^{-1}+\left|6\alpha-\frac{1-\eta}{\eta\gamma}\right|+6\alpha\right)\|z^{k+1}-z^{k}\|+\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|+\|A^{T}(\lambda^{k+1}-\lambda^{k})\|$
$\displaystyle\leq\left(\gamma^{-1}+\left|6\alpha-\frac{1-\eta}{\eta\gamma}\right|+6\alpha\right)\|z^{k+1}-z^{k}\|+\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|$
$\displaystyle+(L_{f}+\gamma^{-1})\|x^{k+1}-x^{k}\|+\gamma^{-1}\|\hat{z}^{k+1}-\hat{z}^{k}\|,$

where the second inequality is due to (46). This yields $(P2)$ for MEAL.

(c) Establishing $(P3)$: $(P3)$ follows from the boundedness assumption of
$\\{y^{k}\\}$, and the convergence of $\\{{\cal P}_{\mathrm{meal}}(y^{k})\\}$
is implied by $(P1)$. This finishes the proof.

###  5.3 Proof for Convergence of iMEAL

In this subsection, we present the proof of Theorem 3.2 for iMEAL (7).

######  Proof (of Theorem 3.2)

We first show the $o(1/\sqrt{k})$ rate of convergence under Assumption 2(b)
and then the convergence rate result under Assumption 2(c).

(a) In this case, we use a fixed $\beta_{k}=\beta$ and thus
$\alpha_{k}=\alpha$. Substituting the inequality in Lemma 5(a) into (59) in
Lemma 8 yields

$\displaystyle{\cal P}_{\beta}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta}(z^{k},\lambda^{k})\|^{2}$
(64) $\displaystyle+\left(\frac{1-\gamma\rho}{2\gamma}-3\alpha(1+\gamma
L_{f})^{2}\right)\|x^{k+1}-x^{k}\|^{2}+\langle
s^{k},x^{k}-x^{k+1}\rangle-3\alpha\gamma^{2}(\epsilon_{k}+\epsilon_{k-1})^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-3\alpha\|z^{k}-z^{k-1}\|^{2}.$

Let $\delta:=2\left(\frac{(1-\gamma\rho)}{2\gamma}-3\alpha(1+\gamma
L_{f})^{2}\right)$. By the assumption
$0<\alpha<\min\big{\\{}\frac{1-\gamma\rho}{6\gamma(1+\gamma L_{f})^{2}}$,
$\frac{1}{12\gamma}(\frac{2}{\eta}-1)\Big{\\}}$, we have $\delta>0$ and
further

$\displaystyle\langle
s^{k},x^{k}-x^{k+1}\rangle\geq-\frac{\delta}{2}\|x^{k+1}-x^{k}\|^{2}-\frac{1}{2\delta}\|s^{k}\|^{2}\geq-\frac{\delta}{2}\|x^{k+1}-x^{k}\|^{2}-\frac{1}{2\delta}(\epsilon_{k}+\epsilon_{k-1})^{2}.$

Substituting this into (64) and noting the definition (32) of ${\cal
E}_{\mathrm{imeal}}^{k}$, we have

$\displaystyle{\cal E}_{\mathrm{imeal}}^{k}-{\cal
E}_{\mathrm{imeal}}^{k+1}\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta}(z^{k},\lambda^{k})\|^{2}-(3\alpha\gamma^{2}+\frac{1}{2\delta})(\epsilon_{k}+\epsilon_{k-1})^{2},$

which yields claim (a) by the assumption
$\sum_{k=1}^{\infty}(\epsilon_{k})^{2}<+\infty$ and Lemma 1.

(b) Then we establish claim (b) under Assumption 2(c). Substituting the
inequality in Lemma 5(b) into (59) in Lemma 8 yields

$\displaystyle{\cal P}_{\beta_{k}}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta_{k+1}}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{1}{2}\gamma\eta(1-\eta/2)\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}$
$\displaystyle+\left(\frac{(1-\gamma\rho)}{2\gamma}-4\alpha_{k}\right)\|x^{k+1}-x^{k}\|^{2}+\langle
s^{k},x^{k}-x^{k+1}\rangle-4\gamma^{2}\alpha_{k}(\epsilon_{k}+\epsilon_{k-1})^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-4\alpha_{k}\|z^{k}-z^{k-1}\|^{2}-16\alpha_{k}\gamma^{2}\hat{L}_{f}^{2}.$
(65)

Let
$\hat{\alpha}^{*}:=\min\left\\{\frac{1-\rho\gamma}{8\gamma},\frac{1}{16\gamma}(\frac{2}{\eta}-1)\right\\}$
and
$\tilde{\delta}:=2\left(\frac{(1-\gamma\rho)}{2\gamma}-4\hat{\alpha}^{*}\right)>0$.
We have

$\displaystyle\langle
s^{k},x^{k}-x^{k+1}\rangle\geq-\frac{\tilde{\delta}}{2}\|x^{k+1}-x^{k}\|^{2}-\frac{1}{2\tilde{\delta}}\|s^{k}\|^{2}\geq-\frac{\tilde{\delta}}{2}\|x^{k+1}-x^{k}\|^{2}-\frac{1}{2\tilde{\delta}}(\epsilon_{k}+\epsilon_{k-1})^{2}.$

Substituting this into (5.3), and by the definition (33) of $\tilde{\cal
E}_{\mathrm{imeal}}^{k}$ and setting of $\alpha_{k}$, we have

$\displaystyle\tilde{\cal E}_{\mathrm{imeal}}^{k}-\tilde{\cal
E}_{\mathrm{imeal}}^{k+1}$
$\displaystyle\geq\frac{1}{2}\gamma(1-\eta/2)\eta\|\nabla\phi_{\beta_{k}}(z^{k},\lambda^{k})\|^{2}-(4\alpha_{k}\gamma^{2}+\frac{1}{2\tilde{\delta}})(\epsilon_{k}+\epsilon_{k-1})^{2}-16\alpha_{k}\gamma^{2}\hat{L}_{f}^{2},$

which yields claim (b) by the assumption
$\sum_{k=1}^{\infty}(\epsilon_{k})^{2}<+\infty$ and Lemma 2.

###  5.4 Proofs for Convergence of LiMEAL

Now, we show proofs of main convergence theorems for LiMEAL (9).

####  5.4.1 Proof of Theorem 4.1

###### Proof

We first establish claim (a) and then claim (b) under the associated
assumptions.

(a) In this case, a fixed $\beta_{k}$ is used. Substituting (53) into (60)
yields

$\displaystyle{\cal P}_{\beta}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta}(x^{k+1},z^{k+1},\lambda^{k+1})\geq\frac{1}{4}\gamma(1-\eta/2)\eta\|g_{\mathrm{limeal}}^{k}\|^{2}$
$\displaystyle+\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-\frac{1}{4}\gamma(2-\eta)\eta
L_{h}^{2}-3(1+\gamma L_{g})^{2}\alpha\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\frac{1}{4\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-3\alpha(\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}+\|z^{k}-z^{k-1}\|^{2}).$

By the definition (41) of ${\cal E}^{k}_{\mathrm{limeal}}$, the above
inequality implies

$\displaystyle{\cal E}_{\mathrm{limeal}}^{k}-{\cal
E}_{\mathrm{limeal}}^{k+1}\geq\frac{1}{4}\gamma(1-\eta/2)\eta\|g_{\mathrm{limeal}}^{k}\|^{2}+\left(\frac{1}{4\gamma}(\frac{2}{\eta}-1)-3\alpha\right)\|z^{k+1}-z^{k}\|^{2}$
(66)
$\displaystyle+\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-\frac{1}{4}\gamma(2-\eta)\eta
L_{h}^{2}-3\alpha\left((1+\gamma
L_{g})^{2}+\gamma^{2}L_{h}^{2}\right)\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle\geq\frac{1}{4}\gamma(1-\eta/2)\eta\|g_{\mathrm{limeal}}^{k}\|^{2},$

where the second inequality holds under the conditions in Theorem 4.1(a). This
shows the claim (a) by Lemma 1 and the lower boundedness of $\\{{\cal
E}_{\mathrm{limeal}}^{k}\\}$.

(b) Similarly, substituting (54) into (60) and using the definitions of
${\alpha}_{k}$ in (26) and $\tilde{\cal E}^{k}_{\mathrm{limeal}}$ in (42), we
obtain

$\displaystyle\tilde{\cal E}_{\mathrm{limeal}}^{k}-\tilde{\cal
E}_{\mathrm{limeal}}^{k+1}$
$\displaystyle\geq\frac{1}{4}\gamma(1-\eta/2)\eta_{k}\|g_{\mathrm{limeal}}^{k}\|^{2}-16{\alpha}_{k}\gamma^{2}\hat{L}_{g}^{2}+\left(\frac{1}{4\gamma}(\frac{2}{\eta}-1)-4{\alpha}_{k+1}\right)\|z^{k+1}-z^{k}\|^{2}$
$\displaystyle+\left(\frac{(1-\gamma(\rho_{g}+L_{h}))}{2\gamma}-\frac{1}{4}\gamma(2-\eta)\eta
L_{h}^{2}-4\alpha_{k}-4\gamma^{2}L_{h}^{2}\alpha_{k+1}\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle\geq\frac{1}{4}c\gamma\eta\|g_{\mathrm{limeal}}^{k}\|^{2}-16{\alpha}_{k}\gamma^{2}\hat{L}_{g}^{2},$

where the second inequality is due to the settings of parameters presented in
Theorem 4.1(b). This inequality shows claim (b) by Lemma 2 and the lower
boundedness of $\\{\tilde{\cal E}_{\mathrm{limeal}}^{k}\\}$.

####  5.4.2 Proof of Proposition 3

###### Proof

By Lemma 3, we only need to verify conditions $(P1)$-$(P3)$ hold for LiMEAL.

(a) Establishing $(P1)$: Similar to the proof of Theorem 3.1, let
$a:=\frac{\gamma\eta(2-\eta)}{4\beta}$. Then $\frac{1+a}{\beta
c_{\gamma,A}}=\alpha$, where $\alpha$ is defined in (27). Substituting (53)
into (61) with fixed $\beta_{k}$ yields

$\displaystyle{\cal P}_{\beta}(x^{k},z^{k},\lambda^{k})-{\cal
P}_{\beta}(x^{k+1},z^{k+1},\lambda^{k+1})$
$\displaystyle\geq\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-3\alpha(1+\gamma
L_{g})^{2}\right)\|x^{k+1}-x^{k}\|^{2}-3\alpha\gamma^{2}L_{h}^{2}\|x^{k}-x^{k-1}\|^{2}$
$\displaystyle+\frac{1}{2\gamma}(\frac{2}{\eta}-1)\|z^{k+1}-z^{k}\|^{2}-3\alpha\|z^{k}-z^{k-1}\|^{2}+a\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|^{2}.$

By the definition (43) of ${\cal P}_{\mathrm{limeal}}$, the above inequality
implies

$\displaystyle{\cal P}_{\mathrm{limeal}}(y^{k})-{\cal
P}_{\mathrm{limeal}}(y^{k+1})$
$\displaystyle\geq\left(\frac{1-\gamma(\rho_{g}+L_{h})}{2\gamma}-4\alpha\left((1+\gamma
L_{g})^{2}+\gamma^{2}L_{h}^{2}\right)\right)\|x^{k+1}-x^{k}\|^{2}$
$\displaystyle+\left(\frac{1}{2\gamma}\left(\frac{2}{\eta}-1\right)-4\alpha\right)\|z^{k+1}-z^{k}\|^{2}+a\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|^{2}$
$\displaystyle+\alpha\left(\gamma^{2}L_{h}^{2}\|\hat{x}^{k+1}-\hat{x}^{k}\|^{2}+\|\hat{z}^{k+1}-\hat{z}^{k}\|^{2}\right),$

which, with the assumptions on the parameters, implies $(P1)$ for LiMEAL.

(b) Establishing $(P2)$: Note that ${\cal
P}_{\mathrm{limeal}}(y)=f(x)+\langle\lambda,Ax-b\rangle+\frac{\beta}{2}\|Ax-b\|^{2}+\frac{1}{2\gamma}\|x-z\|^{2}+4\alpha\gamma^{2}L_{h}^{2}\|x-\hat{x}\|^{2}+4\alpha\|z-\hat{z}\|^{2}$.
The update of $x^{k+1}$ in (9) has the optimality condition

$\displaystyle 0\in\partial g(x^{k+1})+\nabla
h(x^{k})+A^{T}\lambda^{k+1}+\gamma^{-1}(x^{k+1}-z^{k}),$

which implies

$\displaystyle(\nabla h(x^{k+1})-\nabla
h(x^{k}))+8\gamma^{2}L_{h}^{2}\alpha(x^{k+1}-x^{k})$
$\displaystyle+\gamma^{-1}(z^{k}-z^{k+1})+A^{T}(\lambda^{k+1}-\lambda^{k})\in\partial_{x}{\cal
P}_{\mathrm{limeal}}(y^{k+1}).$

The derivations for the other terms are straightforward and similar to those
in the proof of Proposition 1. We directly show the final estimate: for some
$v^{k+1}\in\partial{\cal P}_{\mathrm{limeal}}(y^{k+1})$,

$\displaystyle\|v^{k+1}\|$
$\displaystyle\leq\left(L_{h}+L_{g}+\gamma^{-1}+16\alpha\gamma^{2}L_{h}^{2}\right)\|x^{k+1}-x^{k}\|$
$\displaystyle+\left(\gamma^{-1}+\left|8\alpha-\frac{1-\eta}{\eta}\right|+8\alpha\right)\|z^{k+1}-z^{k}\|$
$\displaystyle+\beta^{-1}\|\lambda^{k+1}-\lambda^{k}\|+L_{h}\|\hat{x}^{k+1}-\hat{x}^{k}\|+\gamma^{-1}\|\hat{z}^{k+1}-\hat{z}^{k}\|,$

which yields $(P2)$ for LiMEAL.

(c) Establishing $(P3)$: $(P3)$ follows from the boundedness assumption of
$\\{y^{k}\\}$ and the convergence of $\\{{\cal P}_{\mathrm{limeal}}(y^{k})\\}$
by $(P1)$. This finishes the proof.

##  6 Discussions on Boundedness and Related Work

In this section, we discuss how to ensure the bounded sequences and then
compare our results to related other work.

###  6.1 Discussions on Boundedness of Sequence

Theorem 3.1 imposes the condition of lower boundedness of $\\{{\cal
E}_{\mathrm{meal}}^{k}\\}$ and Proposition 1 does with boundedness of the
generated sequence $\\{(x^{k},z^{k},\lambda^{k})\\}$. In this section, we
provide some sufficient conditions to guarantee the former and then the latter
boundedness conditions.

Besides the $\rho$-weak convexity of $f$ (implying the curvature of $f$ is
lower bounded by $\rho$), we impose the coerciveness on the constrained
problem (1) as follows.

######  Assumption 4 (Coercivity)

The minimal value $f^{*}:=\inf_{x\in{\cal X}}f(x)$ is finite (recall ${\cal
X}:=\\{x:Ax=b\\}$), and $f$ is coercive over the set ${\cal X}$, that is,
$f(x)\rightarrow\infty$ if $x\in{\cal X}$ and $\|x\|\rightarrow\infty$.

The coercive assumption is a common condition used to obtain the boundedness
of the sequence, for example, used in (Wang19, , Assumption A1) for the
nonconvex ADMM. Particularly, let $(x^{0},z^{0},\lambda^{0})$ be a finite
initial guess of MEAL and

$\displaystyle{\cal E}^{0}:={\cal E}_{\mathrm{meal}}^{1}<+\infty.$ (67)

By Assumption 4, if $x\in{\cal X}$ and $f(x)\leq{\cal E}^{0}$, then there
exists a positive constant ${\cal B}_{0}$ (possibly depending on ${\cal
E}^{0}$) such that $\|x\|\leq{\cal B}_{0}.$ Define another positive constant
as

$\displaystyle{\cal B}_{1}:={\cal B}_{0}+\sqrt{2\rho^{-1}\cdot\max\\{0,{\cal
E}^{0}-f^{*}\\}}.$ (68)

Given a $\gamma\in(0,1/\rho)$ and $z\in\mathbb{R}^{n}$ with $\|z\|\leq{\cal
B}_{1}$ and $u\in\mathrm{Im}(A)$, we define

$\displaystyle
x(u;z):=\operatorname*{argmin}_{\\{x:Ax=u\\}}\left\\{f(x)+\frac{1}{2\gamma}\|x-z\|^{2}\right\\}.$
(69)

Since $f$ is $\rho$-weakly convex by Assumption 2(a), then for any
$\gamma\in(0,1/\rho)$, the function $f(x)+\frac{1}{2\gamma}\|x-z\|^{2}$ is
strongly convex with respect to $x$, and thus the above $x(u;z)$ is well-
defined and unique for any given $z\in\mathbb{R}^{n}$ and
$u\in\mathrm{Im}(A)$. Motivated by (Boyd04, , Ch 5.6.3), we impose some local
stability on $x(u;z)$ defined in (69).

######  Assumption 5 (Local stability)

For any given $z\in\mathbb{R}^{n}$ with $\|z\|\leq{\cal B}_{1}$, there exist a
$\delta>0$ and a finite positive constant $\bar{M}$ (possibly depending on
$A$, ${\cal B}_{1}$ and $\delta$) such that

$\|x(u;z)-x(b;z)\|\leq\bar{M}\|u-b\|,\ \forall
u\in\mathrm{Im}(A)\cap\\{v:\|v-b\|\leq\delta\\}.$

The above local stability assumption is also related to the Lipschitz sub-
minimization path assumption suggested in (Wang19, , Assumption A3). As
discussed in Wang19 , the Lipschitz sub-minimization path assumption relaxes
the more stringent full-rank assumption used in the literature (see the
discussions in (Wang19, , Sections 2.2 and 4.1) and references therein). As
$\\{z\in\mathbb{R}^{n}:\|z\|\leq{\cal B}_{1}\\}$ is a compact set, $\bar{M}$
can be taken as the supremum of these stability constants over this compact
set. Based on Assumption 5, we have the following lemma.

###### Lemma 10

Let $\\{(x^{k},z^{k},\lambda^{k})\\}$ be the sequence generated by MEAL (5)
with fixed $\beta>0$ and $\eta>0$. If $\gamma\in(0,1/\rho)$,
$\|z^{k}\|\leq{\cal B}_{1}$ and $\|Ax^{k+1}-b\|\leq\delta$, there holds

$\|x^{k+1}-x(b;z^{k})\|\leq\bar{M}\|Ax^{k+1}-b\|,\ \forall k\in\mathbb{N}.$

###### Proof

Let $u^{k+1}=Ax^{k+1}$. By the update of $x^{k+1}$ in (5), there holds

${\cal P}_{\beta}(x^{k+1},z^{k},\lambda^{k})\leq{\cal
P}_{\beta}(x(u^{k+1};z^{k}),z^{k},\lambda^{k}).$

Noting that $Ax(u^{k+1};z^{k})=Ax^{k+1}$ due to its definition in (69), the
above inequality implies

$f(x^{k+1})+\frac{1}{2\gamma}\|x^{k+1}-z^{k}\|^{2}\leq
f(x(u^{k+1};z^{k}))+\frac{1}{2\gamma}\|x(u^{k+1};z^{k})-z^{k}\|^{2}.$

By the definition of $x(u^{k+1};z^{k})$ in (69) again and noting that
$Ax^{k+1}=u^{k+1}$, we have

$f(x^{k+1})+\frac{1}{2\gamma}\|x^{k+1}-z^{k}\|^{2}\geq
f(x(u^{k+1};z^{k}))+\frac{1}{2\gamma}\|x(u^{k+1};z^{k})-z^{k}\|^{2}.$

These two inequalities imply

$f(x^{k+1})+\frac{1}{2\gamma}\|x^{k+1}-z^{k}\|^{2}=f(x(u^{k+1};z^{k}))+\frac{1}{2\gamma}\|x(u^{k+1};z^{k})-z^{k}\|^{2},$

which yields

$x^{k+1}=x(u^{k+1};z^{k})=x(Ax^{k+1};z^{k})$

by the strong convexity of function $f(x)+\frac{1}{2\gamma}\|x-z^{k}\|^{2}$
for any $\gamma\in(0,1/\rho)$ and thus the uniqueness of $x(u^{k+1};z^{k})$.
Then by Assumption 5, we yield the desired result.

Based on the above assumptions, we establish the lower boundedness of
$\\{{\cal E}_{\mathrm{meal}}^{k}\\}$ and the boundedness of
$\\{(x^{k},z^{k},\lambda^{k})\\}$ as follows.

###### Proposition 4

Let $\\{(x^{k},z^{k},\lambda^{k})\\}_{k\in\mathbb{N}}$ be a sequence generated
by MEAL (5) with a finite initial guess $(x^{0},z^{0},\lambda^{0})$ such that
$\|z^{0}\|\leq{\cal B}_{1}$, where ${\cal B}_{1}$ is defined in (68). Suppose
that Assumptions 1, 2(a)-(b) and 4 hold and further Assumption 5 holds with
some $0<\bar{M}<\frac{2}{\sqrt{\sigma_{\min}(A^{T}A)}}$. If
$\gamma\in(0,\rho^{-1})$, $\eta\in(0,2)$ and
$\beta>\max\left\\{\frac{1+\sqrt{1+\eta(2-\eta)\gamma
c_{\gamma,A}\alpha_{\max}}}{2c_{\gamma,A}\alpha_{\max}},\frac{a_{2}+\sqrt{a_{2}^{2}+4a_{1}a_{3}}}{2a_{1}}\right\\},$
where $\alpha_{\max}:=\min\left\\{\frac{1-\gamma\rho}{4\gamma(1+\gamma
L_{f})^{2}},\frac{1}{8\gamma}(\frac{2}{\eta}-1)\right\\}$,
$c_{\gamma,A}=\gamma^{2}\sigma_{\min}(A^{T}A)$,
$a_{1}=4-\bar{M}^{2}\sigma_{\min}(A^{T}A)$,
$a_{2}=4(\bar{L}+\gamma^{-1})\bar{M}^{2}-\gamma\eta(2-\eta)$,
$a_{3}=(1+\gamma\bar{L})\eta(2-\eta)\bar{M}^{2}$ and $\bar{L}=\rho+2L_{f}$,
then the following hold:

  1. (a)

$\\{{\cal E}_{\mathrm{meal}}^{k}\\}$ is lower bounded;

  2. (b)

$\\{(x^{k},z^{k})\\}$ is bounded; and

  3. (c)

if further $\lambda^{0}\in\mathrm{Null}(A^{T})$ (the null space of $A^{T}$)
and $\|\nabla{\cal M}_{\gamma,f}(w^{1})\|$ is finite with $w^{1}=z^{0}-\gamma
A^{T}\lambda^{1}$, then $\\{\lambda^{k}\\}$ is bounded.

###### Proof

In order to prove this proposition, we firstly establish the following claim
for sufficiently large $k$:

Claim A: If $\|z^{k-1}\|\leq{\cal B}_{1},\|Ax^{k}-b\|\leq\delta,\forall k\geq
k_{0}$ for some sufficiently large $k_{0}$, then ${\cal
E}_{\mathrm{meal}}^{k}\geq f^{*}$, and $\|z^{k}\|\leq{\cal B}_{1}$ and
$\|x^{k}\|\leq{\cal B}_{2}$.

By Theorem 3.1(a), such $k_{0}$ does exist due to the lower boundedness of
$\\{{\cal E}_{meal}^{k}\\}$ for all finite $k$ and thus
$\xi_{\mathrm{meal}}^{k}\leq\hat{c}/\sqrt{k}$ for some constant $\hat{c}>0$
(implying $\|Ax^{k}-b\|$ is sufficiently small with a sufficiently large $k$
).

In the next, we show Claim A. By the definition (24) of ${\cal
E}_{\mathrm{meal}}^{k}$, we have

$\displaystyle{\cal E}_{\mathrm{meal}}^{k}$
$\displaystyle=f(x^{k})+\langle\lambda^{k},Ax^{k}-b\rangle+\frac{\beta}{2}\|Ax^{k}-b\|^{2}+\frac{1}{2\gamma}\|x^{k}-z^{k}\|^{2}+2\alpha\|z^{k}-z^{k-1}\|^{2}$
$\displaystyle=f(x^{k})+\langle
A^{T}\lambda^{k},x^{k}-\bar{x}^{k}\rangle+\frac{\beta}{2}\|Ax^{k}-b\|^{2}+\frac{1}{2\gamma}\|x^{k}-z^{k}\|^{2}+2\alpha\|z^{k}-z^{k-1}\|^{2},$

where

$\bar{x}^{k}:=x(b;z^{k-1})$

as defined in (69). Let $\bar{\lambda}^{k}$ be the associated optimal
Lagrangian multiplier of $\bar{x}^{k}$ and $\bar{w}^{k}=z^{k-1}-\gamma
A^{T}\bar{\lambda}^{k}$. Then we have

$\bar{x}^{k}=\mathrm{Prox}_{\gamma,f}(\bar{w}^{k}),$

and $\nabla{\cal M}_{\gamma,f}(\bar{w}^{k})\in\partial f(\bar{x}^{k})$. By
(51) in the proof of Lemma 4, we have

$\displaystyle A^{T}\lambda^{k}=-\nabla{\cal
M}_{\gamma,f}(w^{k})-\gamma^{-1}(x^{k}-z^{k-1}),$

and $\nabla{\cal M}_{\gamma,f}(w^{k})\in\partial f(x^{k})$, where
$w^{k}=z^{k-1}-\gamma A^{T}\lambda^{k}$. Substituting the above equation into
the previous equality yields

$\displaystyle{\cal E}_{\mathrm{meal}}^{k}$
$\displaystyle=f(x^{k})+\langle\nabla{\cal
M}_{\gamma,f}(w^{k}),\bar{x}^{k}-x^{k}\rangle+\frac{\beta}{2}\|Ax^{k}-b\|^{2}$
(70) $\displaystyle+\gamma^{-1}\langle
x^{k}-z^{k-1},\bar{x}^{k}-x^{k}\rangle+\frac{1}{2\gamma}\|x^{k}-z^{k}\|^{2}+2\alpha\|z^{k}-z^{k-1}\|^{2}.$

Noting that $\nabla{\cal M}_{\gamma,f}(\bar{w}^{k})\in\partial f(\bar{x}^{k})$
and by the $\rho$-weak convexity of $f$, we have

$f(x^{k})\geq f(\bar{x}^{k})+\langle\nabla{\cal
M}_{\gamma,f}(\bar{w}^{k}),x^{k}-\bar{x}^{k}\rangle-\frac{\rho}{2}\|x^{k}-\bar{x}^{k}\|^{2},$

which implies

$\displaystyle f(x^{k})+\langle\nabla{\cal
M}_{\gamma,f}(w^{k}),\bar{x}^{k}-x^{k}\rangle$ $\displaystyle\geq
f(\bar{x}^{k})-\frac{\rho}{2}\|\bar{x}^{k}-x^{k}\|^{2}-\langle\nabla{\cal
M}_{\gamma,f}(\bar{w}^{k})-\nabla{\cal
M}_{\gamma,f}(w^{k}),\bar{x}^{k}-x^{k}\rangle$ $\displaystyle\geq
f(\bar{x}^{k})-\frac{\rho}{2}\|\bar{x}^{k}-x^{k}\|^{2}-\|\nabla{\cal
M}_{\gamma,f}(\bar{w}^{k})-\nabla{\cal
M}_{\gamma,f}(w^{k})\|\cdot\|\bar{x}^{k}-x^{k}\|.$

By the implicit Lipschitz subgradient assumption (i.e., Assumption 2 (b)) and
the definition of $\bar{L}:=\rho+2L_{f}$, the above inequality yields

$\displaystyle f(x^{k})+\langle\nabla{\cal
M}_{\gamma,f}(w^{k}),\bar{x}^{k}-x^{k}\rangle\geq
f(\bar{x}^{k})-\frac{\bar{L}}{2}\|\bar{x}^{k}-x^{k}\|^{2}.$ (71)

Moreover, it is easy to show that

$\displaystyle\gamma^{-1}\langle
x^{k}-z^{k-1},\bar{x}^{k}-x^{k}\rangle+\frac{1}{2\gamma}\|x^{k}-z^{k}\|^{2}+2\alpha\|z^{k}-z^{k-1}\|^{2}$
(72)
$\displaystyle=\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}-\frac{1}{2\gamma}\|\bar{x}^{k}-x^{k}\|^{2}+\gamma^{-1}\langle
z^{k}-z^{k-1},\bar{x}^{k}-x^{k}\rangle+2\alpha\|z^{k}-z^{k-1}\|^{2}$
$\displaystyle=\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}-\left(\frac{1}{2\gamma}+\frac{1}{8\alpha\gamma^{2}}\right)\|\bar{x}^{k}-x^{k}\|^{2}+2\alpha\left\|(z^{k}-z^{k-1})+\frac{1}{4\alpha\gamma}(\bar{x}^{k}-x^{k})\right\|^{2}.$

Substituting (71)-(72) into (70) and by Lemma 10, we have

$\displaystyle{\cal E}_{\mathrm{meal}}^{k}$ $\displaystyle\geq
f(\bar{x}^{k})+\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}+2\alpha\left\|(z^{k}-z^{k-1})+\frac{1}{4\alpha\gamma}(\bar{x}^{k}-x^{k})\right\|^{2}$
$\displaystyle+\frac{1}{2}\left[\beta-\left(\frac{1}{4\alpha\gamma^{2}}+\bar{L}+\gamma^{-1}\right)\bar{M}^{2}\right]\|Ax^{k}-b\|^{2}$
$\displaystyle\geq
f(\bar{x}^{k})+\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}+2\alpha\left\|(z^{k}-z^{k-1})+\frac{1}{4\alpha\gamma}(\bar{x}^{k}-x^{k})\right\|^{2}$
(73) $\displaystyle\geq
f^{*}+\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}+2\alpha\left\|(z^{k}-z^{k-1})+\frac{1}{4\alpha\gamma}(\bar{x}^{k}-x^{k})\right\|^{2}$
(74) $\displaystyle>-\infty,$ (75)

where the second inequality follows from the definition of
$\alpha=\frac{2\beta+\gamma\eta(1-\eta/2)}{2\gamma^{2}\sigma_{\min}(A^{T}A)\beta^{2}}$
and the condition on $\beta$, the third inequality holds for
$\bar{x}^{k}:=x(b;z^{k-1})$ and thus $A\bar{x}^{k}=b$ and $f(\bar{x}^{k})\geq
f^{*}$, and the final inequality is due to Assumption 4. The above inequality
yields the lower boundedness of $\\{{\cal E}_{\mathrm{meal}}^{k}\\}$ in Claim
A. Thus, clam (a) in this proposition holds.

Then, we show the boundedness of $\\{(x^{k},z^{k})\\}$ in Claim A. By (73) and
(5.2.1), we have

$\displaystyle f(\bar{x}^{k})\leq{\cal E}^{0}:={\cal E}_{\mathrm{meal}}^{1},$

which implies $\|\bar{x}^{k}\|\leq{\cal B}_{0}$ by Assumption 4. By (74) and
the condition on $\gamma\in(0,\rho^{-1})$, we have
$f^{*}+\frac{\rho}{2}\|\bar{x}^{k}-z^{k}\|^{2}\leq
f^{*}+\frac{1}{2\gamma}\|\bar{x}^{k}-z^{k}\|^{2}\leq{\cal E}^{0},$ which
implies

$\displaystyle\|z^{k}\|\leq{\cal B}_{0}+\sqrt{2({\cal
E}^{0}-f^{*})/\rho}={\cal B}_{1}.$

By (74) again, we have
$\left\|(z^{k}-z^{k-1})+\frac{1}{4\alpha\gamma}(\bar{x}^{k}-x^{k})\right\|^{2}\leq\frac{{\cal
E}^{0}-f^{*}}{2\alpha},$ which, together with these existing bounds
$\|z^{k-1}\|\leq{\cal B}_{1}$, $\|z^{k}\|\leq{\cal B}_{1}$ and
$\|\bar{x}^{k}\|\leq{\cal B}_{0}$, yields

$\displaystyle\|x^{k}\|\leq{\cal B}_{0}+4\alpha\gamma\left(2{\cal
B}_{1}+\sqrt{\frac{{\cal E}^{0}-f^{*}}{2\alpha}}\right)=:{\cal B}_{2}.$ (76)

Thus, we have shown Claim A. Recursively, we can show that $\\{x^{k}\\}$ and
$\\{z^{k}\\}$ are respectively bounded by ${\cal B}_{2}$ and ${\cal B}_{1}$
for any $k\geq 1$, that is, claim (b) in this proposition holds.

In the following, we show claim (c) of this proposition. By the update of
$\lambda^{k+1}$ in (5), it is easy to show
$\lambda^{k}=\lambda^{0}+\hat{\lambda}^{k}$, where
$\hat{\lambda}^{k}=\beta\sum_{t=1}^{k}(Ax^{t}-b)\in\mathrm{Im}(A)$ by
Assumption 1. Furthermore, by the assumption that
$\lambda^{0}\in\mathrm{Null}(A^{T})$, we have

$\displaystyle\langle\lambda^{0},\hat{\lambda}^{k}\rangle=0,\ \forall k\geq
1.$ (77)

By (51), for any $k\geq 1$, we have

$\displaystyle A^{T}\lambda^{k}=-(\nabla{\cal M}_{\gamma,f}(w^{k})-\nabla{\cal
M}_{\gamma,f}(w^{1}))-\nabla{\cal
M}_{\gamma,f}(w^{1})-\gamma^{-1}(x^{k}-z^{k-1}),$

where $w^{k}=z^{k-1}-\gamma A^{T}\lambda^{k}$. By Assumption 2(b) and the
boundedness of $\\{(x^{k},z^{k})\\}$ shown before, the above equation implies

$\displaystyle\|A^{T}{\lambda}^{k}\|$ $\displaystyle\leq
L_{f}\|x^{k}-x^{1}\|+\|\nabla{\cal
M}_{\gamma,f}(w^{1})\|+\gamma^{-1}\|x^{k}-z^{k-1}\|$
$\displaystyle\leq\gamma^{-1}{\cal B}_{1}+(2L_{f}+\gamma^{-1}){\cal
B}_{2}+\|\nabla{\cal M}_{\gamma,f}(w^{1})\|<+\infty.$

By the relation $\lambda^{k}=\lambda^{0}+\hat{\lambda}^{k}$ and (77), the
above inequality implies

$\displaystyle\|A^{T}\hat{\lambda}^{k}\|\leq\gamma^{-1}{\cal
B}_{1}+(2L_{f}+\gamma^{-1}){\cal B}_{2}+\|\nabla{\cal M}_{\gamma,f}(w^{1})\|.$

Since $\hat{\lambda}^{k}\in\mathrm{Im}(A)$, the above inequality implies

$\displaystyle\|\hat{\lambda}^{k}\|\leq\tilde{\sigma}_{\min}^{-1/2}(A^{T}A)\|A^{T}\hat{\lambda}^{k}\|\leq\tilde{\sigma}_{\min}^{-1/2}(A^{T}A)\left[\gamma^{-1}{\cal
B}_{1}+(2L_{f}+\gamma^{-1}){\cal B}_{2}+\|\nabla{\cal
M}_{\gamma,f}(w^{1})\|\right],$

which yields the boundedness of $\\{\lambda^{k}\\}$ by the triangle
inequality. This finishes the proof.

The proof idea of claim (c) of this proposition is motivated by the proof of
(Zhang-Luo18, , Lemma 3.1). Based on Proposition 4, we show the lower
boundedness of the Lypunov function sequence and the boundedness of the
sequence generated by MEAL. Following the similar analysis of this section, we
can obtain the similar boundeness results for both iMEAL and LiMEAL.

###  6.2 Discussions on Related Work

When compared to the tightly related work Hajinezhad-Hong19 ; Hong17-Prox-PDA
; Jiang19 ; Rockafellar76-PALM ; Xie-Wright19 ; Zhang-Luo20 ; Zhang-Luo18 ,
this paper provides some slightly stronger convergence results under weaker
conditions. The detailed discussions and comparisons with these works are
shown as follows and presented in Tables 1 and 2.

Table 1: Convergence results of our and related algorithms for problem (1)

Algorithm | MEAL (our) | iMEAL (our) |  Prox-PDA Hong17-Prox-PDA  |  Prox-ALM Xie-Wright19
---|---|---|---|---
Assumption |  $f$: weakly convex, imp-Lip or imp-bound |  $\nabla f$: Lipschitz
Iteration |  imp-Lip: $o(\varepsilon^{-2})$ |  imp-Lip: $o(\varepsilon^{-2})$ | ${\cal O}(\varepsilon^{-2})$ | ${\cal O}(\varepsilon^{-2})$
complexity |  imp-bound: ${\cal O}(\varepsilon^{-2})$ |  imp-bound: ${\cal O}(\varepsilon^{-2})$
Global | $\checkmark$ under KŁ | – | – | –
Convergence

$\bullet$ imp-Lip: the implicit Lipschitz subgradient assumption 2(b);
$\bullet$ imp-bound: the implicit bounded subgradient assumption 2(c);
$\bullet$ Xie-Wright19  considers a nonlinear equality constraints $c(x)=0$
where $\nabla c$ is Lipschitz and bounded.

Table 2: Convergence results of our and related algorithms for the composite optimization problem (8). Algorithm | LiMEAL (our) |  PProx-PDA Hajinezhad-Hong19  |  Prox-iALM Zhang-Luo18  |  S-prox-ALM Zhang-Luo20
---|---|---|---|---
Assumption |  $\nabla h$: Lipschitz, |  $\nabla h$: Lipschitz, |  $\nabla h$: Lipschitz, |  $\nabla h$: Lipschitz,
$g$: weakly convex, |  $g$: convex, |  $g:\iota_{\cal C}(x)$, |  $g:\iota_{\cal P}(x)$,
imp-Lip or imp-bound |  $\partial g$: bounded |  ${\cal C}$: box constraint |  ${\cal P}$: polyhedral set
Iteration |  imp-Lip: $o(\varepsilon^{-2})$ | ${\cal O}(\varepsilon^{-2})$ | ${\cal O}(\varepsilon^{-2})$ | ${\cal O}(\varepsilon^{-2})$
complexity |  imp-bound: ${\cal O}(\varepsilon^{-2})$
Global | $\checkmark$ under KŁ | – |  $\checkmark$ for quadratic | –
Convergence | programming

When reduced to the case of linear constraints, the proximal ALM suggested in
Rockafellar76-PALM  is a special case of MEAL with $\eta=1$, and the Lipschitz
continuity of certain fundamental mapping at the origin (Rockafellar76-PALM, ,
p. 100) generally implies the KŁ property of the proximal augmented Lagrangian
with exponent $1/2$ at some stationary point, and thus, the linear convergence
of proximal ALM can be directly yielded by Proposition 1(b). Moreover, the
proposed algorithms still work (in terms of convergence) for some constrained
problems with nonconvex objectives and a fixed penalty parameter.

In Hong17-Prox-PDA , a proximal primal-dual algorithm (named Prox-PDA) was
proposed for the linearly constrained problem (1) with $b=0$. Prox-PDA is
shown as follows:

$\displaystyle\text{(Prox-PDA)}\
\left\\{\begin{array}[]{l}x^{k+1}=\operatorname*{argmin}_{x\in\mathbb{R}^{n}}\
\left\\{f(x)+\langle\lambda^{k},Ax\rangle+\frac{\beta}{2}\|Ax\|^{2}+\frac{\beta}{2}\|x-x^{k}\|^{2}_{B^{T}B}\right\\},\\\
\lambda^{k+1}=\lambda^{k}+\beta Ax^{k+1},\end{array}\right.$

where $B$ is chosen such that $A^{T}A+B^{T}B\succeq\mathrm{I}_{n}$ (the
identity matrix of size $n$). To achieve a $\sqrt{\varepsilon}$-accurate
stationary point, the iteration complexity of Prox-PDA is ${\cal
O}(\varepsilon^{-1})$ under the Lipschitz differentiability of $f$ (that is,
$f$ is differentiable and has Lipschitz gradient) and the assumption that
there exists some $\underline{f}>-\infty$ and some $\delta>0$ such that
$f(x)+\frac{\delta}{2}\|Ax\|^{2}\geq\underline{f}$ for any
$x\in\mathbb{R}^{n}$. Such iteration complexity of Prox-PDA is consistent with
the order of ${\cal O}(\varepsilon^{-2})$ to achieve an $\varepsilon$-accurate
stationary point. On one hand if we take $B=\mathrm{I}_{n}$ in Prox-PDA, then
it reduces to MEAL with $\gamma=\beta^{-1}$ and $\eta=1$. On the other hand,
by our main Theorem 3.1(a), the iteration complexity of the order of
$o(\varepsilon^{-2})$ is slightly better than that of Prox-PDA, under weaker
conditions (see, Assumption 2(a)-(b)). Moreover, we established the global
convergence and rate of MEAL under the KŁ inequality, while such global
convergence result is missing (though obtainable) for Prox-PDA in Hong17-Prox-
PDA .

A prox-linear variant of Prox-PDA (there dubbed PProx-PDA) was proposed in the
recent paper Hajinezhad-Hong19  for the linearly constrained problem (8) with
a composite objective. Besides Lipschitz differentiability of $h$, the
nonsmooth function $g$ is assumed to be convex with bounded subgradients.
These assumptions used in Hajinezhad-Hong19  are stronger than ours in
Assumption 3(a), (b) and (d), while the yielded iteration complexity of LiMEAL
(Theorem 4.1(b)) is consistent with that of PProx-PDA in (Hajinezhad-Hong19, ,
Theorem 1). Moreover, we establish the global convergence and rate of LiMEAL
(Proposition 3), which is missing (though obtainable) for PProx-PDA.

In Xie-Wright19 , an ${\cal O}(\varepsilon^{-2})$-iteration complexity of
proximal ALM was established for the constrained problem with nonlinear
equality constraints, under assumptions that the objective is differentiable
and its gradient is both Lipschitz continuous and bounded, and that the
Jacobian of the constraints is also Lipschitz continuous and bounded and
satisfies a full-rank property (see (Xie-Wright19, , Assumption 1)). If we
reduce their setting to linear constraints, their iteration complexity is
slightly worse than ours and their assumptions are stronger (of course, except
for the part on nonlinear constraints).

In Zhang-Luo18 , a very related algorithm (called Proximal Inexact Augmented
Lagrangian Multiplier method, dubbed Prox-iALM) was introduced for the
following linearly constrained problem

$\displaystyle\min_{x\in\mathbb{R}^{n}}\ h(x)\quad\mathrm{subject\ to}\quad
Ax=b,\ x\in{\cal C},$

where ${\cal C}$ is a box constraint set. Subsequence convergence to a
stationary point was established under the following assumptions: (a) the
origin is in the relative interior of the set $\\{Ax-b:x\in{\cal C}\\}$; (b)
the strict complementarity condition Nocedal99  holds for the above
constrained problem; (c) $h$ is differentiable and has Lipschitz continuous
gradient. Moreover, the global convergence and linear rate of this algorithm
was established for the quadratic programming, in which case, the augmented
Lagrangian satisfies the KŁ inequality with exponent $1/2$, by noticing the
connection between Luo-Tseng error bound and KŁ inequality Li-Pong-
KLexponent18 . According to Theorem 4.1 and Proposition 3, the established
convergence results in this paper are more general and stronger than that in
Zhang-Luo18  but under weaker assumptions. Particularly, besides the weaker
assumption on $h$, the strict complementarity condition (b) is also removed in
this paper for LiMEAL.

The algorithm studied in Zhang-Luo18  has been recently generalized to handle
the linearly constrained problem with the polyhedral set in Zhang-Luo20
(dubbed S-prox-ALM). Under the Lipschitz differentiability of the objective,
the iteration complexity of the order ${\cal O}(\varepsilon^{-2})$ was
established in Zhang-Luo20  for the S-prox-ALM algorithm. Such iteration
complexity is consistent with LiMEAL as shown in Theorem 4.1. Besides these
major differences between this paper and Zhang-Luo20 ; Zhang-Luo18 , the step
sizes $\eta$ are more flexible for both MEAL and LiMEAL (only requiring
$\eta\in(0,2)$), while the step sizes used in the algorithms in Zhang-Luo20 ;
Zhang-Luo18  should be sufficiently small to guarantee the convergence.
Meanwhile, the Lyapunov function used in this paper is motivated by the Moreau
envelope of the augmented Lagrangian, which is very different from the
Lyapunov function used in Zhang-Luo20 ; Zhang-Luo18 . Based on the defined
Lyapunov function, our analysis is much simpler than that in Zhang-Luo20 ;
Zhang-Luo18 .

##  7 Numerical Experiments

We use two experiments to demonstrate the effectiveness of the proposed
algorithms:

  1. 1.

The first experiment is based on a nonconvex quadratic program on which ALM
with any bounded penalty parameter diverges (Wang19, , Proposition 1) but
LiMEAL converges.

  2. 2.

The second experiment borrows a general quadratic program from (Zhang-Luo18, ,
Sec. 6.2) and LiMEAL outperforms Prox-iALM suggested in Zhang-Luo18 .

The source codes can be accessed at https://github.com/JinshanZeng/MEAL.

###  7.1 ALM vs LiMEAL

Consider the following optimization problem from (Wang19, , Proposition 1):

$\displaystyle\min_{x,y\in\mathbb{R}}\ x^{2}-y^{2},\quad\text{subject to}\
x=y,\ x\in[-1,1].$ (78)

ALM with any bounded penalty parameter $\beta$ diverges on this problem. By
Theorem 4.1 and Proposition 3, LiMEAL converges exponentially fast since its
augmented Lagrangian is a KŁ function with an exponent of $1/2$. For both ALM
and LiMEAL, we set the penalty parameter $\beta$ to 50. We set LiMEAL’s
proximal parameter $\gamma$ to $1/2$ and test three different values
$\eta^{\prime}s$: $0.5,1,1.5$. The curves of objective
$f(x^{k},y^{k})=(x^{k})^{2}-(y^{k})^{2}$, constraint violation error
$|x^{k}-y^{k}|$, multiplier sequences $\\{\lambda^{k}\\}$, and the norm of
gradient of Moreau envelope in (39), which is the stationarity measure, are
depicted in Fig. 1.

Observe that ALM diverges: its multiplier sequence $\\{\lambda^{k}\\}$
oscillates between two distinct values (Fig. 1 (a)) and the constraint
violation converges to a positive value (Fig. 1 (b)). Also observe that LiMEAL
converges exponentially fast (Fig. 1 (c)–(e)) and achieves the optimal
objective value of 0 in about 10 iterations (Fig. 1 (f)) with all $\eta$
values. This verifies Proposition 3.

(a) Divergent $\\{\lambda^{k}\\}$ of ALM

(b) Constraint violation of ALM

(c) Convergent $\\{\lambda^{k}\\}$ of LiMEAL

(d) Constraint violation of LiMEAL

(e) convergence rate of LiMEAL

(f) objective sequence of LiMEAL

Figure 1: Apply ALM and LiMEAL to problem (78). ALM diverges. LiMEAL quickly
converges.

###  7.2 Quadratic Programming

Consider the quadratic program with box constraints:

$\displaystyle\min_{x\in\mathbb{R}^{n}}\ \frac{1}{2}x^{T}Qx+r^{T}x\quad
s.t.\quad Ax=b,\ \ell_{i}\leq x_{i}\leq u_{i},\ i=1,\ldots,n,$ (79)

where $Q\in\mathbb{R}^{n\times n}$, $r\in\mathbb{R}^{n}$,
$A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, and
$\ell_{i},u_{i}\in\mathbb{R}$, $i=1,\ldots,n$. Let ${\cal
C}:=\\{x:\ell_{i}\leq x_{i}\leq u_{i},i=1,\ldots,n\\}$. Applying LiMEAL
yields: initialize $(x^{0},z^{0},\lambda^{0})$, $\gamma>0$, $\eta\in(0,2)$ and
$\beta>0$, for $k=0,1,\ldots,$ run

$\mathrm{(LiMEAL)}\quad\left\\{\begin{array}[]{l}\tilde{x}^{k}=(\beta
A^{T}A+\gamma^{-1}{\bf I}_{n})^{-1}(\gamma^{-1}z^{k}+\beta A^{T}b-r-
Qx^{k}-A^{T}\lambda^{k}),\\\ x^{k+1}=\mathrm{Proj}_{\cal C}(\tilde{x}^{k}),\\\
z^{k+1}=z^{k}-\eta(z^{k}-x^{k+1}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b).\end{array}\right.$

Applying Prox-iALM from (Zhang-Luo18, , Algorithm 2.2) yields: initialize
$(x^{0},z^{0},\lambda^{0})$, parameters $\beta,p,\alpha,s,\eta>0$, for
$k=0,1,\ldots,$ run

$\mathrm{(Prox-iALM)}\quad\left\\{\begin{array}[]{l}\bar{x}^{k}=(\beta
A^{T}A+p{\bf I}_{n})x^{k}+Qx^{k}+A^{T}\lambda^{k}-pz^{k}-(\beta A^{T}b-r),\\\
x^{k+1}=\mathrm{Proj}_{\cal C}(x^{k}-s\bar{x}^{k}),\\\
z^{k+1}=z^{k}-\eta(z^{k}-x^{k+1}),\\\
\lambda^{k+1}=\lambda^{k}+\beta_{k}(Ax^{k+1}-b).\end{array}\right.$

When $\eta=1$, then Prox-iALM reduces to Algorithm 2.1 in Zhang-Luo18 , which
we name iALM.

The experimental settings are similar to (Zhang-Luo18, , Sec. 6.2): set
$m=5,n=20$, generate the entries of $Q$, $A$, $b$, and $\tilde{x}$ by sampling
from the uniform distribution, and set $b=A\tilde{x}$. For LiMEAL, we set
$\beta=50,\gamma=\frac{1}{2\|Q\|_{2}}$ and test three values of
$\eta^{\prime}s$: $0.5,1,1.5$. For Prox-iALM, we use the parameter settings in
(Zhang-Luo18, , Sec. 6.2):
$p=2\|Q\|_{2},\beta=50,\alpha=\frac{\beta}{4},s=\frac{1}{2(\|Q\|_{2}+p+\beta\|A\|_{2}^{2})}$.
Moreover, we test two values of $\eta^{\prime}s$: $1$ and $0.5$ for Prox-iALM.
Prox-iALM with $\eta=1$ reduces to iALM. The curves of the objective sequence,
$\|Ax^{k}-b\|$, $\|x^{k+1}-z^{k}\|$ and the norm of gradient of the Moreau
envelope are depicted in Fig. 2. We observe that LiMEAL converges faster than
both iALM and Prox-iALM. By Fig. 2(d), LiMEAL converges exponentially fast
with all three values of $\eta^{\prime}s$. These results verify the results in
Proposition 3(b) since the augmented Lagrangian of problem (79) is a KŁ
function with an exponent of $1/2$.

(a) Objective sequence

(b) $\|Ax^{k}-b\|$

(c) $\|x^{k+1}-z^{k}\|$

(d) Convergence rates of LiMEAL

Figure 2: Performance of LiMEAL and Prox-iALM for the quadratic programming
problem (79).

##  8 Conclusion

This paper suggests a Moreau envelope augmented Lagrangian (MEAL) method for
the linearly constrained weakly convex optimization problem. By leveraging the
implicit smoothing property of Moreau envelope, the proposed MEAL generalizes
the ALM and proximal ALM to the nonconvex and nonsmooth case. To yield an
$\varepsilon$-accurate first-order stationary point, the iteration complexity
of MEAL is $o(\varepsilon^{-2})$ under the implicit Lipschitz subgradient
assumption and ${\cal O}(\varepsilon^{-2})$ under the implicit bounded
subgradient assumption. The global convergence and rate of MEAL are also
established under the further Kurdyka-Łojasiewicz inequality. Moreover, an
inexact variant (called iMEAL), and a prox-linear variant (called LiMEAL) for
the composite objective case are suggested and analyzed for different
practical settings. The convergence results established in this paper for MEAL
and its variants are generally stronger than the existing ones, but under
weaker assumptions.

One future direction of this paper is to get rid of the implicit Lipschitz
subgradient and implicit bounded subgradient assumptions, which in some extent
limit the applications of the suggested algorithms, though these two
assumptions are respectively weaker than the Lipschitz differentiable and
bounded subgradient assumptions commonly used in the literature. Another
direction is to generalize this work to the constrained problem with nonlinear
constraints. The third direction is to develop more practical variants of the
proposed methods as well as establish their convergence results. One possible
application of our study is robustness and convergence of stochastic gradient
descent in training parameters of structured deep neural networks such as deep
convolutional neural networks Zhou20 , where linear constraints can be used to
impose convolutional structures. We leave them in our future work.

## References

  * (1) Andreani, R., Birgin, E.G., Martinez, J.M., Schuverdt, M.L.: On augmented lagrangian methods with general lower-level constraints.  SIAM J. Optim. 18(4), 1286–1309 (2007)
  * (2) Andreani, R., Birgin, E.G., Martinez, J.M., Schuverdt, M.L.: Augmented lagrangian methods under the constant positive linear dependence constraint qualification.  Math. Program. 111, 5–32 (2008)
  * (3) Andreani, R., Birgin, E.G., Martinez, J.M., Schuverdt, M.L.: Second-order negative-curvature methods for box-constrained and general constrained optimization.  Comput. Optim. Appl. 45(2), 209–236 (2010)
  * (4) Andreani, R., Fazzio, N., Schuverdt, M.L., Secchin, L.: A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences.  SIAM J. Optim. 29(1), 743–766 (2019)
  * (5) Andreani, R., Secchin, L., Silva, P.: Convergence properties of a second order augmented lagrangian method for mathematical programs with complementarity constraints.  SIAM J. Optim. 28(3), 2574–2600 (2018)
  * (6) Armand, P., Omheni, R.: A globally and quadratically convergent primal-dual augmented lagrangian algorithm for equality constrained optimization.  Optim. Methods Softw. 32(1), 1–21 (2017)
  * (7) Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features.  Math. Program. 116, 5–16 (2009)
  * (8) Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi–algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods.  Math. Program. 137, 91–219 (2013)
  * (9) Bertsekas, D.P.: Convergence rate of penalty and multiplier methods.  In: Proc. IEEE Conf. on Decision and Control), pp. 260–264. SanDiego, California (1973)
  * (10) Bertsekas, D.P.: On penalty and multiplier methods for constrained minimization.  SIAM J. Control Optim. 14(2), 216–235 (1976)
  * (11) Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods.  Academic Press, London (1982)
  * (12) Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-lipschitz and nonconvex minimization.  Math. Program. 149(1), 301–327 (2005)
  * (13) Birgin, E.G., Castillo, R., Martinez, J.M.: Numerical comparison of augmented lagrangian algorithms for nonconvex problems.  Comput. Optim. Appl. 31, 31–56 (2005)
  * (14) Birgin, E.G., Floudas, C.A., Martinez, J.M.: Global minimization using an augmented lagrangian method with variable lower-level constraints.  Math. Program. 125, 139–162 (2010)
  * (15) Birgin, E.G., Floudas, C.A., Martinez, J.M.: The boundedness of penalty parameters in an augmented lagrangian method with constrained subproblems.  Optim. Methods Softw. 27(6), 1001–1024 (2012)
  * (16) Birgin, E.G., Haeser, G., Ramos, A.: Augmented lagrangians with constrained subproblems and convergence to second-order stationary points.  Comput. Optim. Appl. 69(1), 51–75 (2018)
  * (17) Birgin, E.G., Martinez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization, vol. vol. 10.  SIAM, Philadelphia (2014)
  * (18) Birgin, E.G., Martinez, J.M.: Complexity and performance of an augmented lagrangian algorithm.  Optim. Methods Softw. (2020)
  * (19) Bochnak, J., Coste, M., Roy, M.F.: Real algebraic geometry, vol. 36.  Springer Science & Business Media, Berlin (1998)
  * (20) Bolte, J., Daniilidis, A., Lewis, A.: The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.  SIAM J. Optim. 17(4), 1205–1223 (2007)
  * (21) Bolte, J., Daniilidis, A., Lewis, A., Shiota, M.: Clark subgradients of stratifiable functions.  SIAM J. Optim. 18(2), 556–572 (2007)
  * (22) Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems.  Math. Program. 146(1), 459–494 (2014)
  * (23) Boyd, S., Vandenberghe, L.: Convex Optimization.  Cambridge University Press, Cambridge, UK (2004)
  * (24) Conn, A.R., Gould, N.I.M., Startenaer, A., Toint, P.L.: Convergence properties of an augmented lagrangian algorithm for optimization with a combination of general equality and linear constraints.  SIAM J. Optim. 6, 674–703 (1996)
  * (25) Conn, A.R., Gould, N.I.M., Toint, P.L.: A globally convergent augmented lagrangian algorithm for optimization with general constraints and simple bounds.  SIAM J. Numer. Anal. 28, 545–572 (1991)
  * (26) Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods.  SIAM, Philadelphia (2000)
  * (27) Curtis, F.E., Jiang, H., Robinson, D.P.: An adaptive augmented lagrangian method for large-scale constrained optimization.  Math. Program. 152(1), 201–245 (2015)
  * (28) Davis, D., Drusvyatskiy, D.: Stochastic model-based minimization of weakly convex functions.  SIAM J. Optim. 29(1), 207–239 (2019)
  * (29) Deng, W., Lai, M.J., Peng, Z., Yin, W.: Parallel multi-block admm with $o(1/k)$ convergence.  J. Sci. Comput. 71, 712–736 (2017)
  * (30) Drusvyatskiy, D.: The proximal point method revisited.  SIAG/OPT Views and News 26, 1–8 (2018)
  * (31) Drusvyatskiy, D., Paquette, C.: Efficiency of minimizing compositions of convex functions and smooth maps.  Math. Program. 178, 503–558 (2019)
  * (32) Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties.  J Am Stat Assoc 96, 1348–1360 (2001)
  * (33) Fernadez, D., Solodov, M.V.: Local convergence of exact and inexact augmented lagrangian methods under the second-order sufficient optimality condition.  SIAM J. Optim. 22(2), 384–407 (2012)
  * (34) Grapiglia, G.N., Yuan, Y.X.: On the complexity of an augmented Lagrangian method for nonconvex optimization.  ArXiv e-prints (2019)
  * (35) Haeser, G., Liu, H., Ye, Y.: Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary.  Math. Program. 178, 263–299 (2019)
  * (36) Hajinezhad, D., Hong, M.: Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization.  Math. Program. 176, 207–245 (2019)
  * (37) Hestenes, M.R.: Multiplier and gradient methods.  J. Optim. Theory Appl. 4, 303–320 (1969)
  * (38) Hong, M., Hajinezhad, D., Zhao, M.M.: Prox-pda: The proximal primal-dual algorithm for fast dostributed nonconvex optimization and learning over networks.  In: Proc. of the 34th International Conference on Machine Learning (ICML), pp. 1529–1538. Sydney, Australia (2017)
  * (39) Jiang, B., Lin, T., Ma, S., Zhang, S.: Structured nonconvex and nonsmooth otpmization: algorithms and iteration complexity analysis.  Comput. Optim. Appl. 72(1), 115–157 (2019)
  * (40) Krantz, S., Parks, H.R.: A Primer of Real Analytic Functions (2nd Edition).  Birkhauser, Basel, Switzerland (2002)
  * (41) Kurdyka, K.: On gradients of functions definable in o-minimal structures.  Annales de l’institut Fourier 48(3), 769–783 (1998)
  * (42) Li, G., Pong, T.K.: Calculus of the exponent of kurdyka-łojasiewicz inequality and its applications to linear convergence of first-order methods.  Found. Comput. Math. 18, 1199–1232 (2018)
  * (43) Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In: Les Équations aux dérivées partielles.  Éditions du centre National de la Recherche Scientifique, Paris pp. 87–89 (1963)
  * (44) Łojasiewicz, S.: Sur la geometrie semi-et sous-analytique.  Annales de l’institut Fourier 43(5), 1575–1595 (1993)
  * (45) Mordukhovich, B.S.: Variational analysis and generalized differentiation I: Basic Theory.  Springer-Verlag, New York (2006)
  * (46) Moreau, J.: Proximité et dualité dans un espace hilbertien.  Bull. Soc. Math. France 93, 273–299 (1965)
  * (47) Nocedal, J., Wright, S.J.: Numerical Optimization.  Springer-Verlag, New York (1999)
  * (48) Nouiehed, M., Lee, J.D., Razaviyayn, M.: Convergence to second-order stationary for constrained non-convex optimization.  ArXiv e-prints (2018)
  * (49) Nurminskii, E.A.: The quasigradient method for the solving of the nonlinear programming problems.  Cybernetics 9, 145–150 (1973)
  * (50) O’Neill, M., Wright, S.J.: A log-barrier newton-cg method for bound constrained optimization with complexity guarantees.  IMA J. Numer. Anal. 00, 1–38 (2020)
  * (51) Polyak, B.T., Tretyakov, N.V.: The method of penalty bounds for constrained extremum problems.  Zh. Vych Mat i Mat. Fiz, 13:34-46 = U.S.S.R. Computational Mathematics and Mathmatical Physics 13, 42–58 (1973)
  * (52) Powell, M.J.D.: A method for nonlinear constraints in minimization problems.  in Optimization, R. Fletcher, ed. Academic Press, London pp. 283–298 (1969)
  * (53) Rockafellar, R.T.: The multiplier method of hestenes and powell applied to convex programming.  J. Optim. Theory Appl. 12, 555–562 (1973)
  * (54) Rockafellar, R.T.: Augmented lagrangians and applications of the proximal point algorithm in convex programming.  Math. Oper. Res. 1(2), 97–116 (1976)
  * (55) Rockafellar, R.T., Wets, R.J.B.: Variational Analysis.  Springer-Verlag, New York (1997)
  * (56) Shiota, M.: Geometry of Subanalytic and Semialgebraic Sets (Progress in Mathematics).  Birkhauser, Basel, Switzerland (1997)
  * (57) Tretykov, N.Y.: The method of penalty estimates of convex programming.  Economics and Mathematical Methods (Russian) 9, 525–540 (1973)
  * (58) Wang, Y., Yin, W., Zeng, J.: Global convergence of admm in nonconvex nonsmooth optimization.  J. Sci. Comput. 78, 29–63 (2019)
  * (59) Xie, Y., Wright, S.J.: Complexity of proximal augmented Lagrangian for nonconvex optimalization with nonlinear equality constraints.  ArXiv e-prints (2019)
  * (60) Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimizaton with applications to nonnegative tensor factorization and completion.  SIAM J. Imaging Sci. 6(3), 1758–1789 (2013)
  * (61) Yu, P., Li, G., Pong, T.: Kurdyka-łojasiewicz exponent via inf-projection.  Found. Comput. Math. (2021).  DOI https://doi.org/10.1007/s10208-021-09528-6
  * (62) Zeng, J., Lau, T.T.K., Lin, S.B., Yao, Y.: Global convergence of block coordinate descent in deep learning.  In: Proceedings of the 36th International Conference on Machine Learning (ICML). Long Beach, California, PMLR 97 (2019)
  * (63) Zeng, J., Lin, S.B., Yao, Y., Zhou, D.X.: On admm in deep learning: Convergence and saturation-avoidance.  J Mach Learn Res 22(199), 1–67 (2021)
  * (64) Zeng, J., Yin, W.: On nonconvex descentralized gradient descent.  IEEE Trans. Signal Process. 66(11), 2834–2848 (2018)
  * (65) Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty.  Ann. Stat. 38(2), 894–942 (2010)
  * (66) Zhang, J., Luo, Z.Q.: A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization.  ArXiv e-prints (2020)
  * (67) Zhang, J., Luo, Z.Q.: A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization.  SIAM J. Optim. 30(3), 2272–2302 (2020)
  * (68) Zhou, D.X.: Universality of deep convolutional neural networks.  Appl. Comput. Harmonic Anal. 48, 787–794 (2020)