# Aug-PDG: Linear Convergence of Convex Optimization with Inequality
Constraints

Min Meng and Xiuxian Li M. Meng<EMAIL_ADDRESS>and X. Li
<EMAIL_ADDRESS>are with the Department of Control Science and
Engineering, College of Electronics and Information Engineering, Tongji
University, Shanghai, 201804, China and the Institute for Advanced Study,
Tongji University, Shanghai, 200092, China.

###### Abstract

This paper investigates the convex optimization problem with general convex
inequality constraints. To cope with this problem, a discrete-time algorithm,
called augmented primal-dual gradient algorithm (Aug-PDG), is studied and
analyzed. It is shown that Aug-PDG can converge semi-globally to the optimizer
at a linear rate under some mild assumptions, such as the quadratic gradient
growth condition for the objective function, which is strictly weaker than
strong convexity. To our best knowledge, this paper is the first to establish
a linear convergence for the studied problem in the discrete-time setting,
where an explicit bound is provided for the stepsize. Finally, a numerical
example is presented to illustrate the efficacy of the theoretical finding.

###### Index Terms:

Convex optimization, nonlinear inequality constraints, linear convergence,
augmented primal-dual gradient dynamics.

##  I Introduction

This paper deals with the constrained optimization problem formulated as
follows:

$\displaystyle\min\limits_{x\in\mathbb{R}^{n}}~{}~{}f(x)$
$\displaystyle\text{~{}~{}s.t.}~{}~{}g(x)\leq 0,$ (1)

where the objective function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$g(x)=(g_{1}(x),g_{2}(x),\ldots,g_{m}(x))^{T}$ with
$g_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ being convex and continuously
differentiable. By resorting to the (or augmented) Lagrangian $L(x,\lambda)$
of problem (1), the corresponding (or augmented) primal-dual gradient
algorithm (PDG) (or Aug-PDG) can be designed as

$\displaystyle x_{k+1}$
$\displaystyle=x_{k}-\alpha\nabla_{x}L(x_{k},\lambda_{k}),$
$\displaystyle\lambda_{k+1}$
$\displaystyle=[\lambda_{k}+\alpha\nabla_{\lambda}L(x_{k},\lambda_{k})]_{+},$
(2)

where $\alpha$ is a positive stepsize and $[\cdot]_{+}$ denotes the projection
operator onto the nonnegative orthants component-wisely. It is known that (2)
can find a saddle point of the Lagrangian $L(x,\lambda)$, and thus it has been
extensively studied to solve the constrained optimization problem [1].

Optimization has wide applications in power systems [2, 3], wireless
communication [4], game theory [5, 6], to name just a few. To date, there is a
large body of literature on theoretical analysis of asymptotic convergence of
various algorithms, including primal-dual gradient-based algorithms, for
tackling the optimization problem under different settings [7, 8, 9, 10, 11,
12, 13, 14, 15].

In recent decades, researchers have focused on the exponential/linear
convergence of primal-dual gradient-based algorithms. It is well-known that
when the objective function is strongly convex and smooth, the gradient decent
algorithm for unconstrained convex optimization can achieve global exponential
convergence in continuous-time and global linear convergence in discrete-time.
In the context of constrained optimization with equality constraints $Ax=b$ or
affine inequality constraints $Ax\leq b$, PDG is proved to converge globally
and exponentially in continuous-time setup [16]. A proximal gradient flow was
proposed in [17], which can be applied to resolve convex optimization problems
with affine inequality constraints and has global exponential convergence when
$A$ has full row rank. Local exponential convergence of the primal-dual
gradient dynamics can be established with the help of spectral bounds of
saddle matrices [18]. Recently, the authors in [19] proved that the Aug-PDGD
in continuous-time for optimization with affine equality and inequality
constraints achieves global exponential convergence, and the global linear
converge of primal-dual gradient optimization (PDGO) in discrete-time was
discussed in [20] by contraction theory. It should be noted that the
aforementioned works focus on unconstrained optimization or constrained
optimization with affine equality and/or affine inequality constraints. For
the case with nonlinear inequality constraints, the asymptotic/sublinear
convergence has been extensively studied such as in [21]. However, the linear
convergence for the optimization with nonlinear inequality constraints is
seldom investigated in the literature. One exception is the recent work [22],
where the authors established a semi-global exponential convergence of Aug-
PDGD in the sense that the convergence rate depends on the distance from the
initial point to the optimal point.

However, [22] concentrates on the continuous-time dynamics. As discrete-time
algorithms are easily implemented in practical applications, in this paper,
the discrete-time algorithm is addressed for the optimization problem with
nonlinear inequality constraints. Theoretical analysis based on a quadratic
Lyapunov function that has non-zero off-diagonal terms is presented to show
that the Aug-PDG achieves semi-global linear convergence, where an explicit
bound is established for the stepsize. The numerical results suggest that the
Aug-PDG indeed has different linear convergence rates for different initial
points.

The rest of this paper is organized as follows. Section II introduces
preliminaries on optimization with nonlinear equality constraints. The main
result on the semi-global linear convergence of Aug-PDGA, along with its
proof, is presented in Section III. Section IV provides a numerical example to
illustrate the feasibility of the obtained result. Section V makes a brief
conclusion.

Notations. Let $\mathbb{R}^{m}$, $\mathbb{R}_{+}^{m}$ and $\mathbb{R}^{m\times
n}$ be the sets of $m$-dimensional real column vectors, $m$-dimensional
nonnegative column vectors and $m\times n$ real matrices, respectively. Define
$[x]_{+}$ to be the component-wise projection of a vector $x\in\mathbb{R}^{m}$
onto $\mathbb{R}_{+}^{m}$. The symbol $x\geq 0$ for any vector
$x\in\mathbb{R}^{m}$ means that each entry of $x$ is nonnegative. For an
integer $n>0$, denote $[n]:=\\{1,2,\ldots,n\\}$. $I_{n}$ is the identity
matrix of dimension $n$. ${\bf 1}_{n}$ (resp. ${\bf 0}_{n}$) represents an
$n$-dimensional vector with all of its elements being 1 (resp. 0). For a
vector or matrix $A$, $A^{\top}$ denotes the transpose of $A$ and
$A_{\mathcal{I}}$ is a matrix composed of the rows of $A$ with the indices in
${\mathcal{I}}$. For real symmetric matrices $P$ and $Q$,
$P\succ(\succeq,\succ,\preceq)~{}Q$ means that $P-Q$ is positive (positive
semi-, negative, negative semi-) definite, while for two vectors/matrices
$w,v$ of the same dimension, $w\leq v$ means that each entry of $w$ is no
greater than the corresponding one of $v$. ${\rm
diag}\\{a_{1},a_{2},\ldots,a_{n}\\}$ represents a diagonal matrix with
$a_{i}$, $i\in[n]$, on its diagonal.

##  II Preliminaries

Consider problem (1). An augmented Lagrangian associated with problem (1) is
introduced as [23]

$\displaystyle L(x,\lambda):=f(x)+U_{\rho}(x,\lambda),$ (3)

where $x\in\mathbb{R}^{n}$,
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{m})^{\top}\in\mathbb{R}^{m}$,
$\rho>0$ is the penalty parameter, and

$\displaystyle U_{\rho}(x,\lambda):=\sum\limits_{i=1}^{m}\frac{[\rho
g_{i}(x)+\lambda_{i}]_{+}^{2}-\lambda_{i}^{2}}{2\rho}.$ (4)

It can be verified that $U_{\rho}(x,\lambda)$ is convex in $x$ and concave in
$\lambda$, and $U_{\rho}(x,\lambda)$ is continuously differentiable, i.e.,

$\displaystyle\nabla_{x}U_{\rho}(x,\lambda)$
$\displaystyle=\sum\limits_{i=1}^{m}[\rho g_{i}(x)+\lambda_{i}]_{+}\nabla
g_{i}(x),$ (5) $\displaystyle\nabla_{\lambda}U_{\rho}(x,\lambda)$
$\displaystyle=\sum\limits_{i=1}^{m}\frac{[\rho
g_{i}(x)+\lambda_{i}]_{+}-\lambda_{i}}{\rho}e_{i},$ (6)

where $e_{i}$ is an $n$-dimensional vector with the $i$th entry being 1 and
others 0. Then the augmented primal-dual gradient algorithm (Aug-PDG) can be
explicitly written as

$\displaystyle x_{k+1}$
$\displaystyle=x_{k}-\alpha\nabla_{x}L(x_{k},\lambda_{k})$
$\displaystyle=x_{k}-\alpha\nabla f(x_{k})-\alpha\sum\limits_{i=1}^{m}[\rho
g_{i}(x_{k})+\lambda_{i,k}]_{+}\nabla g_{i}(x_{k}),$ (7a)
$\displaystyle\lambda_{k+1}$
$\displaystyle=\lambda_{k}+\alpha\nabla_{\lambda}L(x_{k},\lambda_{k})$
$\displaystyle=\lambda_{k}+\alpha\sum\limits_{i=1}^{m}\frac{[\rho
g_{i}(x_{k})+\lambda_{i,k}]_{+}-\lambda_{i,k}}{\rho}e_{i},$ (7b)

where $\alpha\in(0,\rho]$ is the stepsize to be specified. Here, the initial
conditions are arbitrarily chosen as $x_{0}\in\mathbb{R}^{n}$ and
$\lambda_{0}\geq 0$.

To proceed, the following results are vital for solving the constrained
optimization problem.

###### Lemma 1

For Aug-PDG (7), if $\lambda_{0}\geq 0$, then $\lambda_{k}\geq 0$ for all
$k\geq 0$.

Proof. This result can be proved by mathematical induction. First note that
$\lambda_{0}\geq 0$. Assume now that $\lambda_{k}\geq 0$ for some $k\geq 0$,
then by (7b), one has that

$\displaystyle\lambda_{k+1}$
$\displaystyle=(1-\alpha/\rho)\lambda_{k}+\alpha\sum\limits_{i=1}^{m}\frac{[\rho
g_{i}(x_{k})+\lambda_{i,k}]_{+}}{\rho}e_{i}$
$\displaystyle\geq(1-\alpha/\rho)\lambda_{k}$ $\displaystyle\geq 0,$

where the first inequality is obtained based on the definition of the notation
$[\cdot]_{+}$ and the second inequality is derived following
$0<\alpha\leq\rho$ and inductive assumption $\lambda_{k}\geq 0$. The proof is
thus completed. $\blacksquare$

###### Lemma 2

A primal-dual pair $(x^{*},\lambda^{*})$ is an equilibrium point of the Aug-
PDG (7) if and only if $(x^{*},\lambda^{*})$ is a Karush-Kuhn-Tucker (KKT)
point of (1).

Proof. If a primal-dual pair $(x^{*},\lambda^{*})$ is an equilibrium point of
the Aug-PDG (7), that is,

$\displaystyle x^{*}$
$\displaystyle=x^{*}-\alpha\nabla_{x}L(x^{*},\lambda^{*}),$
$\displaystyle\lambda^{*}$
$\displaystyle=\lambda^{*}+\alpha\nabla_{\lambda}L(x^{*},\lambda^{*}),$

then $\nabla_{x}L(x^{*},\lambda^{*})=0$ and
$\nabla_{\lambda}L(x^{*},\lambda^{*})=0$. For
$\nabla_{\lambda}L(x^{*},\lambda^{*})=0$, an equivalent condition is that for
any $i\in[m]$,

$\displaystyle\lambda_{i}^{*}=[\rho g_{i}(x^{*})+\lambda_{i}^{*}]_{+},$ (8)

which implies $\lambda_{i}^{*}\geq 0$, $g_{i}(x^{*})\leq 0$, and
$\lambda_{i}^{*}g_{i}(x^{*})=0$. For $\nabla_{x}L(x^{*},\lambda^{*})=0$, one
can equivalently obtain that $\nabla f(x^{*})+\sum_{i=1}^{m}[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}\nabla g_{i}(x^{*})=\nabla
f(x^{*})+\sum_{i=1}^{m}\lambda_{i}^{*}\nabla g_{i}(x^{*})=0$. Thus, it can be
claimed that the primal-dual pair $(x^{*},\lambda^{*})$ is a KKT point.

Conversely, if $(x^{*},\lambda^{*})$ is a KKT point of (1), then $\nabla
f(x^{*})+\sum_{i=1}^{m}\lambda_{i}^{*}\nabla g_{i}(x^{*})=0$,
$\lambda_{i}^{*}g_{i}(x^{*})=0$, $\lambda^{*}\geq 0$ and $g_{i}(x^{*})\leq 0$.
Via a simple computation, $\nabla_{x}L(x^{*},\lambda^{*})=0$ and
$\nabla_{\lambda}L(x^{*},\lambda^{*})=0$, which implies that
$(x^{*},\lambda^{*})$ is an equilibrium point of the Aug-PDG (7).
$\blacksquare$

##  III Main Results

In this section, the main result on the linear convergence of Aug-PDG is
presented.

###  III-A Convergence Results

The following assumptions are essential for deriving the main result.

###### Assumption 1

The problem (1) has a unique feasible solution $x^{*}$, and at $x^{*}$, the
linear independence constraint qualification (LICQ) holds at $x^{*}$, i.e.,
$\\{\nabla g_{i}(x^{*})\mid i\in{\mathcal{I}}\\}$ is linearly independent,
where ${\mathcal{I}}:=\\{i\in[m]\mid g_{i}(x^{*})=0\\}$ is the so-called
active set at $x^{*}$.

Under Assumption 1, the optimal Lagrangian multiplier $\lambda^{*}$ is also
unique [24]. Denote by $J$ the Jacobian of $g(x)$ at $x^{*}$ and
$J_{\mathcal{I}}$ the matrix composed of the rows of $J$ with the indices in
${\mathcal{I}}$. LICQ in Assumption 1 also implies that
$J_{\mathcal{I}}J_{\mathcal{I}}^{\top}\succ 0$ [22]. Define

$\displaystyle\kappa:=\lambda_{\min}(J_{\mathcal{I}}J_{\mathcal{I}}^{\top})>0$
(9)

to be the smallest eigenvalue of $J_{\mathcal{I}}J_{\mathcal{I}}^{\top}$.

###### Assumption 2

The objective function $f(x)$ has a quadratic gradient growth with parameter
$\mu>0$ over $\mathbb{R}^{n}$, i.e.,

$\displaystyle(\nabla f(x)-\nabla
f(x^{*}))^{\top}(x-x^{*})\geq\mu\|x-x^{*}\|^{2},~{}\forall
x\in\mathbb{R}^{n}.$ (10)

The concept of quadratic gradient growth was introduced in [25], which is a
relaxation of strong convexity condition for guaranteeing linear convergence
of gradient-based optimization algorithms. In fact, the class of functions
having quadratic gradient growth include the strongly convex functions as a
proper subset and some functions with quadratic gradient growth are even not
convex.

###### Assumption 3

The objective function $f$ is $l$-smooth over $\mathbb{R}^{n}$, i.e.,
$\|\nabla f(x)-\nabla f(y)\|\leq l\|x-y\|$ for any $x,y\in\mathbb{R}^{n}$. For
any $i\in[m]$, $g_{i}(x)$ is $L_{gi}$-smooth and has bounded gradient, i.e.,
$\|\nabla g_{i}(x)-\nabla g_{i}(y)\|\leq L_{gi}\|x-y\|$ and $\|\nabla
g_{i}(x)\|\leq B_{gi}$ for some $L_{gi},B_{gi}>0$ and any
$x,y\in\mathbb{R}^{n}$.

Denote ${\mathcal{I}}^{c}:=[m]\backslash{\mathcal{I}}$,
$L_{g}:=\sqrt{\sum_{i=1}^{m}L_{gi}^{2}}$ and
$B_{g}:=\sqrt{\sum_{i=1}^{m}B_{gi}^{2}}$. Under Assumption 3, one can obtain
that

$\displaystyle\|J\|$ $\displaystyle\leq B_{g},$ (11)
$\displaystyle\|g(x)-g(y)\|$
$\displaystyle=\sqrt{\sum_{i=1}^{m}(g_{i}(x)-g_{i}(y))^{2}}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{m}B_{gi}^{2}\|x-y\|^{2}}$
$\displaystyle=B_{g}\|x-y\|.$ (12)

Denote $d_{0}:=\sqrt{\|x_{0}-x^{*}\|^{2}+\|\lambda_{0}-\lambda^{*}\|^{2}}$.
Before giving the main result of this paper, it is convenient to list the
following concept similar to that in continuous-time setting [26].

###### Definition 1

Consider the dynamics $z(t+1)=\phi(z(t))$ with initial point $z(0)=z_{0}$.
Assume that $z_{e}$ is an equilibrium point satisfying $z_{e}=\phi(z_{e})$.
$z_{e}$ is said to be a semi-global linear stable point if for any $h>0$,
there exist $c>0$ and $0<\gamma<1$ such that for any $z_{0}$ satisfying
$\|z_{0}-z_{e}\|\leq h$,

$\displaystyle\|z(t)-z_{e}\|\leq c\gamma^{t}\|z_{0}-z_{e}\|,~{}\forall t\geq
0.$

$z_{e}$ is said to be a global linear stable point if $c$ and $\gamma$ do not
depend on $h$.

Then the main result is presented as follows.

###### Theorem 1

Under Assumptions 1–3, if the stepsize $\alpha>0$ is chosen such that

$\displaystyle\alpha<\min\left\\{1,\rho,\frac{2\mu}{b_{1}+2a_{4}\delta},\frac{\kappa\delta}{2b_{2}+4a_{5}\delta},\frac{1-\pi^{*}}{2\rho(b_{2}+2a_{5}\delta)}\right\\},$
(13)

where $\delta>0$ satisfies

$\displaystyle\delta<\min\left\\{\frac{\mu}{2a_{3}},\frac{1-\pi^{*}}{2\rho(\kappa+8B_{g}^{2}+L_{g}^{2}(1-\pi^{*}))},B_{g}^{-1}\right\\},$
(14)

$\pi^{*}:=[\rho\max_{i\in{\mathcal{I}}^{c}}\\{g_{i}(x^{*})\\}/(\sqrt{C}d_{0})+1]_{+}^{2}$,
$b_{1}:=a_{1}+2B_{g}^{2}$, $b_{2}:=a_{2}+\frac{2}{\rho^{2}}$,
$a_{1}:=2l+4\theta_{1}^{2}$, $a_{2}:=4B_{g}^{2}$,
$a_{3}:=2B_{g}^{2}l^{2}/\kappa+2B_{g}^{2}\theta_{1}^{2}/\kappa+2B_{g}^{2}/(\kappa\rho^{2})+{\kappa}B_{g}^{2}\rho^{2}/4$,
$a_{4}:=B_{g}^{2}l^{2}/2+B_{g}^{2}\theta_{1}^{2}+2B_{g}^{2}$,
$a_{5}:=B_{g}^{2}+2/\rho^{2}$, and $\theta_{1}:=\rho
B_{g}^{2}+L_{g}\|\lambda^{*}\|$, then the sequences $\\{x_{k}\\}$ and
$\\{\lambda_{k}\\}$ generated by Aug-PDG (7) for the constrained optimization
(1) semi-globally converge to the optimal point of the optimization problem
(1) at a linear (or exponential) rate. Specifically, it holds that

$\displaystyle\|x_{k}-x^{*}\|^{2}+\|\lambda_{k}-\lambda^{*}\|^{2}\leq
C(1-\gamma)^{k}d_{0}^{2},$ (15)

where $0<\gamma<1$ satisfies

$\displaystyle\gamma\leq\min\\{c_{1},c_{2},c_{3}\\}$ (16)

with $c_{1}:=\mu\alpha-a_{3}\delta\alpha-
b_{1}\alpha^{2}/2-a_{4}\delta\alpha^{2}$,
$c_{2}:=\kappa\delta\alpha/4-b_{2}\alpha^{2}/2-a_{5}\delta\alpha^{2}$,
$c_{3}:=\frac{\alpha}{2\rho}(1-\pi^{*})-(\delta\alpha\kappa+b_{2}\alpha^{2}+2a_{5}\delta\alpha^{2})/2-4\alpha\delta
B_{g}^{2}$, and $C:=\lambda_{\max}(Q_{\delta})/\lambda_{\min}(Q_{\delta})\geq
1$ with $Q_{\delta}:=\left[\begin{array}[]{cc}I_{n}&\delta J^{\top}\\\ \delta
J&I_{m}\end{array}\right]$.

Proof. The proof is postponed to the next subsection. $\blacksquare$

###### Remark 1

The selection of parameters $\alpha$ and $\delta$ ensures that
$c_{1},c_{2},c_{3}$ are positive, and then $\gamma>0$ can be guaranteed. From
Theorem 1, one can see that the convergence rate is related to
$\pi^{*}=[\rho\max\\{g_{i}(x^{*})\\}/(\sqrt{C}d_{0})+1]_{+}^{2}$ and decrease
to 0 as $d_{0}$ goes to infinity. The decreasing rate also changes as
$(x_{k},\lambda_{k})$ approaches the optimal point. Specifically, the
decreasing rates are small at the beginning and then become large when
$(x_{k},\lambda_{k})$ goes to the optimal point. Therefore, Theorem 1 does not
guarantee the existence of a global linear convergence rate, and consequently
only semi-global linear stability can be ensured.

###### Remark 2

To our best knowledge, this paper is the first to investigate the linear
convergence for problem (1) in discrete-time setup. Compared with the most
related literature [22], where a continuous-time algorithm, called Aug-PDGD,
was studied with a semi-global exponential convergence, a discrete-time
algorithm Aug-PDG is analyzed here with a semi-global linear convergence.
Although discrete-time algorithms may be obtained by discretizing the
continuous-time Aug-PDGD using such as explicit Euler method, it is unclear
how to select the sampling stepsize to guarantee the convergence especially in
the sense of semi-global convergence. In comparison, an explicit bound on the
stepsize $\alpha$ is established here in Theorem 1.

###  III-B Proof of Theorem 1

To prove Theorem 1, an intermediate result is needed as follows.

###### Lemma 3

[19] For any $y,y^{*}\in\mathbb{R}$, there exists $\xi\in[0,1]$ such that
$[y]_{+}-[y^{*}]_{+}=\xi(y-y^{*})$. Specifically, $\xi$ can be chosen as
$\xi=\frac{[y]_{+}-[y^{*}]_{+}}{y-y^{*}}$ if $y\neq y^{*}$ and $\xi=0$ if
$y=y^{*}$.

Then the proof of Theorem 1 is presented as follows.

Define

$\displaystyle{V}_{\delta,k}$
$\displaystyle=\left[\begin{array}[]{cc}{x}_{k}-x^{*}\\\
\lambda_{k}-\lambda^{*}\end{array}\right]^{\top}Q_{\delta}\left[\begin{array}[]{c}{x}_{k}-x^{*}\\\
\lambda_{k}-\lambda^{*}\end{array}\right],$ (21)

where

$\displaystyle Q_{\delta}=\left[\begin{array}[]{cc}I_{n}&\delta J^{\top}\\\
\delta J&I_{m}\end{array}\right].$ (24)

As $\delta<B_{g}^{-1}$ from (14), one has
$I_{m}-\delta^{2}JJ^{\top}\succeq(1-\delta^{2}B_{g}^{2})I_{m}\succ 0$, which
implies $Q_{\delta}\succ 0$ by Schur complement. Then, in the following, we
discuss the bound of

$\displaystyle{V}_{\delta,k+1}=$
$\displaystyle\|{x}_{k+1}-x^{*}\|^{2}+\|\lambda_{k+1}-\lambda^{*}\|^{2}$
$\displaystyle+2\delta({x}_{k+1}-x^{*})^{\top}J^{\top}(\lambda_{k+1}-\lambda^{*}).$

Note that $(x^{*},\lambda^{*})$ is the KKT point of (1), that is,

$\displaystyle\nabla_{x}L(x^{*},\lambda^{*})$ $\displaystyle=0,$ (25)
$\displaystyle\nabla_{\lambda}L(x^{*},\lambda^{*})$ $\displaystyle=0.$ (26)

By iterations in (7), one has that

$\displaystyle\|{x}_{k+1}-x^{*}\|^{2}$
$\displaystyle=\|x_{k}-\alpha\nabla_{x}L(x_{k},\lambda_{k})-x^{*}+\alpha\nabla_{x}L(x^{*},\lambda^{*})\|^{2}$
$\displaystyle=\|x_{k}-x^{*}\|^{2}+\alpha^{2}\|\nabla_{x}L(x_{k},\lambda_{k})-\nabla_{x}L(x^{*},\lambda^{*})\|^{2}$
$\displaystyle~{}~{}~{}-2\alpha(\nabla_{x}L(x_{k},\lambda_{k})-\nabla_{x}L(x^{*},\lambda^{*}))^{\top}(x_{k}-x^{*}).$
(27)

By $\nabla_{x}L(x_{k},\lambda_{k})=\nabla
f(x_{k})+\nabla_{x}U(x_{k},\lambda_{k})=\nabla f(x_{k})+\sum_{i=1}^{m}[\rho
g_{i}(x_{k})+\lambda_{i,k}]_{+}\nabla g_{i}(x_{k})$, for the second term on
the right side of (27), one has that

$\displaystyle\alpha^{2}\|\nabla_{x}L(x_{k},\lambda_{k})-\nabla_{x}L(x^{*},\lambda^{*})\|^{2}$
$\displaystyle\leq 2\alpha^{2}\|\nabla f(x_{k})-\nabla f(x^{*})\|^{2}$
$\displaystyle~{}~{}~{}+2\alpha^{2}\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|^{2}.$
(28)

Note that

$\displaystyle\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})$
$\displaystyle=\sum_{i=1}^{m}[\rho g_{i}(x_{k})+\lambda_{i,k}]_{+}\nabla
g_{i}(x_{k})$ $\displaystyle~{}~{}~{}-\sum_{i=1}^{m}[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}\nabla g_{i}(x^{*})$
$\displaystyle=\sum_{i=1}^{m}([\rho g_{i}(x_{k})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+})\nabla g_{i}(x_{k})$
$\displaystyle~{}~{}~{}~{}+\sum_{i=1}^{m}[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}(\nabla g_{i}(x_{k})-\nabla g_{i}(x^{*})),$

then

$\displaystyle\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|$
$\displaystyle\leq\sum_{i=1}^{m}|[\rho g_{i}(x_{k})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}|\cdot\|\nabla g_{i}(x_{k})\|$
$\displaystyle~{}~{}~{}~{}+\sum_{i=1}^{m}[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}\|\nabla g_{i}(x_{k})-\nabla g_{i}(x^{*})\|.$
(29)

Define

$\displaystyle\xi_{i,k}=\frac{[\rho g_{i}(x_{k})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda^{*}]_{+}}{(\rho g_{i}(x_{k})+\lambda_{i,k})-(\rho
g_{i}(x^{*})+\lambda^{*})}$ (30)

if $(\rho g_{i}(x_{k})+\lambda_{i,k})-(\rho g_{i}(x^{*})+\lambda^{*})\neq 0$,
and

$\displaystyle\xi_{i,k}=0$ (31)

if $(\rho g_{i}(x_{k})+\lambda_{i,k})-(\rho g_{i}(x^{*})+\lambda^{*})=0$. Then
it can be obtained from Lemma 3 that

$\displaystyle[\rho g_{i}(x_{k})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}$
$\displaystyle=\rho\xi_{i,k}(g_{i}(x_{k})-g_{i}(x^{*}))+\xi_{i,k}(\lambda_{i,k}-\lambda_{i}^{*}).$
(32)

Substituting (32) into (29) yields that

$\displaystyle\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|$
$\displaystyle\leq\sum_{i=1}^{m}|\rho\xi_{i,k}(g_{i}(x_{k})-g_{i}(x^{*}))+\xi_{i,k}(\lambda_{i,k}-\lambda_{i}^{*})|\cdot\|\nabla
g_{i}(x_{k})\|$ $\displaystyle~{}~{}~{}+\sum_{i=1}^{m}[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}\|\nabla g_{i}(x_{k})-\nabla g_{i}(x^{*})\|$
$\displaystyle\leq\sum_{i=1}^{m}(\rho
B_{gi}\|x_{k}-x^{*}\|+|\lambda_{i,k}-\lambda_{i}^{*}|)B_{gi}$
$\displaystyle~{}~{}~{}+\sum_{i=1}^{m}\lambda_{i}^{*}L_{gi}\|x_{k}-x^{*}\|$
$\displaystyle\leq\theta_{1}\|x_{k}-x^{*}\|+B_{g}\|\lambda_{k}-\lambda^{*}\|,$
(33)

where Assumption 3 has been applied to get the second inequality, and the
third inequality is derived by
$\sum_{i=1}^{n}a_{i}b_{i}\leq\sqrt{\sum_{i=1}^{n}a_{i}^{2}}\sqrt{\sum_{i=1}^{n}b_{i}^{2}}$
for any $a_{i},b_{i}\in\mathbb{R}$, $\theta_{1}=\rho
B_{g}^{2}+L_{g}\|\lambda^{*}\|$ and $B_{g}=\sqrt{\sum_{i=1}^{m}B_{gi}^{2}}$,
$L_{g}=\sqrt{\sum_{i=1}^{m}L_{gi}^{2}}$.

By (33), (28) and Assumption 3, one has that

$\displaystyle\alpha^{2}\|\nabla_{x}L(x_{k},\lambda_{k})-\nabla_{x}L(x^{*},\lambda^{*})\|^{2}$
$\displaystyle\leq 2\alpha^{2}l^{2}\|x_{k}-x^{*}\|^{2}$
$\displaystyle~{}~{}~{}+2\alpha^{2}(\theta_{1}\|x_{k}-x^{*}\|+B_{g}\|\lambda_{k}-\lambda^{*}\|)^{2}$
$\displaystyle\leq 2\alpha^{2}l^{2}\|x_{k}-x^{*}\|^{2}$
$\displaystyle~{}~{}~{}+4\alpha^{2}(\theta_{1}^{2}\|x_{k}-x^{*}\|^{2}+B_{g}^{2}\|\lambda_{k}-\lambda^{*}\|^{2})$
$\displaystyle=a_{1}\alpha^{2}\|x_{k}-x^{*}\|^{2}+a_{2}\alpha^{2}\|\lambda_{k}-\lambda^{*}\|^{2},$
(34)

where $a_{1}=2l^{2}+4\theta_{1}^{2}$ and $a_{2}=4B_{g}^{2}$.

For the third term on the right side of (27),

$\displaystyle-2\alpha(\nabla_{x}L(x_{k},\lambda_{k})-\nabla_{x}L(x^{*},\lambda^{*}))^{\top}(x_{k}-x^{*})$
$\displaystyle=-2\alpha(\nabla f(x_{k})-\nabla f(x^{*}))^{\top}(x_{k}-x^{*})$
$\displaystyle~{}~{}~{}-2\alpha(\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*}))^{\top}(x_{k}-x^{*})$
$\displaystyle\leq-2\mu\alpha\|x_{k}-x^{*}\|^{2}+2\alpha(U(x^{*},\lambda_{k})-U(x_{k},\lambda_{k}))$
$\displaystyle~{}~{}~{}+2\alpha(U(x_{k},\lambda^{*})-U(x^{*},\lambda^{*})),$
(35)

where the inequality is derived based on Assumption 2 and the convexity of
$U(x,\lambda)$ at $x$, i.e.,

$\displaystyle
U(x,\lambda)-U(x^{\prime},\lambda)\geq(\nabla_{x}U(x^{\prime},\lambda))^{\top}(x-x^{\prime})$
(36)

for any $x,x^{\prime}\in\mathbb{R}^{n}$.

Plugging (34) and (35) into (27), one can obtain that

$\displaystyle\|{x}_{k+1}-x^{*}\|^{2}$
$\displaystyle\leq(1-2\mu\alpha+a_{1}\alpha^{2})\|x_{k}-x^{*}\|^{2}+a_{2}\alpha^{2}\|\lambda_{k}-\lambda^{*}\|^{2}$
$\displaystyle~{}~{}~{}+2\alpha(U(x^{*},\lambda_{k})-U(x_{k},\lambda_{k}))$
$\displaystyle~{}~{}~{}+2\alpha(U(x_{k},\lambda^{*})-U(x^{*},\lambda^{*})).$
(37)

For $\|\lambda_{k+1}-\lambda^{*}\|^{2}$, by iteration (7b), one has that

$\displaystyle\|\lambda_{k+1}-\lambda^{*}\|^{2}$
$\displaystyle=\|\lambda_{k}+\alpha\nabla_{\lambda}U(x_{k},\lambda_{k})-\lambda^{*}\|^{2}$
$\displaystyle=\|\lambda_{k}-\lambda^{*}\|^{2}+\alpha^{2}\|\nabla_{\lambda}U(x_{k},\lambda_{k})\|^{2}$
$\displaystyle~{}~{}~{}+2\alpha\nabla_{\lambda}U(x_{k},\lambda_{k}))^{\top}(\lambda_{k}-\lambda^{*}).$
(38)

Recalling
$\nabla_{\lambda}L(x^{*},\lambda^{*})=\nabla_{\lambda}U(x^{*},\lambda^{*})=0$
and the notation of $\xi_{i,k}$ in (30), (31), it can be obtained that

$\displaystyle\|\nabla_{\lambda}U(x_{k},\lambda_{k})\|^{2}$
$\displaystyle=\|\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})\|^{2}$
$\displaystyle=\left\|\sum_{i=1}^{m}\frac{[\rho
g_{i}(x_{k})+\lambda_{i,k}]_{+}-\lambda_{i,k}-[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+}+\lambda_{i}^{*}}{\rho}e_{i}\right\|^{2}$
$\displaystyle=\left\|\sum_{i=1}^{m}[\xi_{i,k}(g_{i}(x_{k})-g_{i}(x^{*}))+\frac{1}{\rho}(\xi_{i,k}-1)(\lambda_{i,k}-\lambda_{i}^{*})]e_{i}\right\|^{2}$
$\displaystyle=\left\|\Xi_{k}(g(x_{k})-g(x^{*}))+\frac{1}{\rho}(\Xi_{k}-I_{m})(\lambda_{k}-\lambda^{*})\right\|^{2}$
$\displaystyle\leq
2B_{g}^{2}\|x_{k}-x^{*}\|^{2}+\frac{2}{\rho^{2}}\|\lambda_{k}-\lambda^{*}\|^{2},$
(39)

where $\Xi_{k}=\text{diag}\\{\xi_{1,k},\ldots,\xi_{m,k}\\}$, the inequality is
obtained based on (12) and $\|\Xi_{k}\|\leq 1$, $\|\Xi_{k}-I_{m}\|\leq 1$ for
$\xi_{i,k}\in[0,1]$, $i\in[m]$.

In consideration that $U(x,\lambda)$ is concave at $\lambda$, one has

$\displaystyle(\nabla_{\lambda}U(x_{k},\lambda_{k}))^{\top}(\lambda_{k}-\lambda^{*})\leq
U(x_{k},\lambda_{k})-U(x_{k},\lambda^{*}).$ (40)

By (39) and (40), it can be derived from (38) that

$\displaystyle\|\lambda_{k+1}-\lambda^{*}\|^{2}$
$\displaystyle\leq(1+\frac{2\alpha^{2}}{\rho^{2}})\|\lambda_{k}-\lambda^{*}\|^{2}+2B_{g}^{2}\alpha^{2}\|x_{k}-x^{*}\|^{2}$
$\displaystyle~{}~{}~{}+2\alpha(U(x_{k},\lambda_{k})-U(x_{k},\lambda^{*})).$
(41)

On the other hand, it is easy to verify that

$\displaystyle({x}_{k+1}-x^{*})^{\top}J^{\top}(\lambda_{k+1}-\lambda^{*})$
$\displaystyle=(x_{k}-x^{*}-\alpha\nabla f(x_{k})+\alpha\nabla f(x^{*})$
$\displaystyle~{}~{}~{}-\alpha\nabla_{x}U(x_{k},\lambda_{k})+\alpha\nabla_{x}U(x^{*},\lambda^{*}))^{\top}J^{\top}$
$\displaystyle~{}~{}~{}(\lambda_{k}-\lambda^{*}+\alpha\nabla_{\lambda}U(x_{k},\lambda_{k})-\alpha\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle=(x_{k}-x^{*})^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\nabla f(x_{k})-\nabla
f(x^{*}))^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\nabla_{x}U(x^{*},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*}))^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda_{k}))^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}+\alpha({x}_{k+1}-x^{*})^{\top}J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})).$
(42)

By (33), one has that

$\displaystyle\|\nabla_{x}U(x^{*},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|$
$\displaystyle\leq B_{g}\|\lambda_{k}-\lambda^{*}\|,$ (43)
$\displaystyle\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda_{k})$
$\displaystyle\leq\theta_{1}\|x_{k}-x^{*}\|.$ (44)

Similar to (30)–(31), define

$\displaystyle\xi_{i,\lambda}=\left\\{\begin{array}[]{ll}\frac{[\rho
g_{i}(x^{*})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda^{*}_{i}]_{+}}{\lambda_{i,k}-\lambda^{*}},&\text{if}~{}\lambda_{i,k}\neq\lambda_{i}^{*},\\\
0,&\text{if}~{}\lambda_{i,k}=\lambda_{i}^{*},\end{array}\right.$ (47)

then

$\displaystyle\nabla_{x}U(x^{*},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})$
$\displaystyle=\sum_{i=1}^{m}([\rho g_{i}(x^{*})+\lambda_{i,k}]_{+}-[\rho
g_{i}(x^{*})+\lambda_{i}^{*}]_{+})\nabla g_{i}(x^{*})$
$\displaystyle=\sum_{i=1}^{m}\xi_{i,\lambda}(\lambda_{i,k}-\lambda_{i}^{*})\nabla
g_{i}(x^{*})$ $\displaystyle=J^{\top}\Xi_{\lambda}(\lambda_{k}-\lambda^{*}),$
(48)

where
$\Xi_{\lambda}:=\text{diag}\\{\xi_{1,\lambda},\ldots,\xi_{m,\lambda}\\}$. For
the last term of (42), it holds that

$\displaystyle\alpha({x}_{k+1}-x^{*})^{\top}J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle=\alpha({x}_{k}-x^{*})^{\top}J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle~{}-\alpha^{2}(\nabla{f(x_{k})}-\nabla{f(x^{*})})J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle~{}-\alpha^{2}(\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*}))^{\top}$
$\displaystyle~{}\times
J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle\leq\frac{2B_{g}^{2}\alpha}{\kappa\rho^{2}}\|x_{k}-x^{*}\|^{2}+\frac{\kappa\rho^{2}\alpha}{8}\|\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})\|^{2}$
$\displaystyle~{}~{}+\frac{B_{g}^{2}\alpha^{2}}{2}\|\nabla{f(x_{k})}-\nabla{f(x^{*})}\|^{2}$
$\displaystyle~{}~{}+\frac{B_{g}^{2}\alpha^{2}}{2}\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|^{2}$
$\displaystyle~{}~{}+\alpha^{2}\|\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})\|^{2},$
(49)

where the inequality has been obtained based on $\|J\|\leq B_{g}$ and
$w^{\top}v\leq\frac{\beta}{2}\|w\|^{2}+\frac{1}{2\beta}\|v\|^{2}$ for
$\beta=\frac{4}{\kappa\rho^{2}}$ and 1.

Therefore, by (39), (43)–(49), one can rewrite (42) as

$\displaystyle({x}_{k+1}-x^{*})^{\top}J^{\top}(\lambda_{k+1}-\lambda^{*})$
$\displaystyle=(x_{k}-x^{*})^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle-\alpha(\lambda_{k}-\lambda^{*})^{\top}\Xi_{\lambda}JJ^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\nabla f(x_{k})-\nabla
f(x^{*}))^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda_{k}))^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}+\alpha({x}_{k+1}-x^{*})^{\top}J^{\top}(\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*}))$
$\displaystyle\leq(x_{k}-x^{*})^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\lambda_{k}-\lambda^{*})^{\top}\Xi_{\lambda}JJ^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}+\frac{2\|J\|^{2}\alpha}{\kappa}\|\nabla
f(x_{k})-\nabla
f(x^{*})\|^{2}+\frac{\kappa\alpha}{8}\|\lambda_{k}-\lambda^{*}\|^{2}$
$\displaystyle~{}~{}~{}+\frac{2\|J\|^{2}\alpha}{\kappa}\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda_{k})\|^{2}$
$\displaystyle~{}~{}~{}+\frac{\kappa\alpha}{8}\|\lambda_{k}-\lambda^{*}\|^{2}+\frac{2B_{g}^{2}\alpha}{\kappa\rho^{2}}\|x_{k}-x^{*}\|^{2}$
$\displaystyle~{}~{}~{}+\frac{\kappa\rho^{2}\alpha}{8}\|\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})\|^{2}$
$\displaystyle~{}~{}~{}+\frac{B_{g}^{2}\alpha^{2}}{2}\|\nabla{f(x_{k})}-\nabla{f(x^{*})}\|^{2}$
$\displaystyle~{}~{}~{}+\frac{B_{g}^{2}\alpha^{2}}{2}\|\nabla_{x}U(x_{k},\lambda_{k})-\nabla_{x}U(x^{*},\lambda^{*})\|^{2}$
$\displaystyle~{}~{}~{}+\alpha^{2}\|\nabla_{\lambda}U(x_{k},\lambda_{k})-\nabla_{\lambda}U(x^{*},\lambda^{*})\|^{2},$
$\displaystyle\leq(x_{k}-x^{*})^{\top}J^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}-\alpha(\lambda_{k}-\lambda^{*})^{\top}\Xi_{\lambda}JJ^{\top}(\lambda_{k}-\lambda^{*})$
$\displaystyle~{}~{}~{}+(a_{3}\alpha+a_{4}\alpha^{2})\|x_{k}-x^{*}\|^{2}+(\frac{\kappa\alpha}{2}+a_{5}\alpha^{2})\|\lambda_{k}-\lambda^{*}\|^{2},$
(50)

where the last inequality is obtained by a simple computation, along with
(33), (39) and (44).

Define

$\displaystyle\tilde{\xi}_{i,k}:=\left\\{\begin{array}[]{ll}[\rho
g_{i}(x^{*})/\lambda_{i,k}+1]_{+}^{2},&i\in{\mathcal{I}}^{c},\lambda_{i,k}\neq
0,\\\ {[\rho
g_{i}(x^{*})/d_{0}+1]}_{+}^{2},&i\in{\mathcal{I}}^{c},\lambda_{i,k}=0,\\\
1,&i\in{\mathcal{I}},\end{array}\right.$ (54)

where
$\tilde{\Xi}_{k}:=\text{diag}\\{\tilde{\xi}_{1,k},\ldots,\tilde{\xi}_{m,k}\\}$.
Then

$\displaystyle U(x^{*},\lambda_{k})-U(x^{*},\lambda^{*})$
$\displaystyle=\frac{1}{2\rho}(\lambda_{k}-\lambda^{*})^{\top}(\tilde{\Xi}_{k}-I_{m})(\lambda_{k}-\lambda^{*}).$
(55)

Combining with (37), (41), (50) and (55), the bound of ${V}_{\delta,k+1}$ can
be derived that

$\displaystyle{V}_{\delta,k+1}$
$\displaystyle=\|x_{k+1}-x^{*}\|^{2}+\|\lambda_{k+1}-\lambda^{*}\|^{2}$
$\displaystyle~{}~{}~{}+2\delta({x}_{k+1}-x^{*})^{\top}J^{\top}(\lambda_{k+1}-\lambda^{*})$
$\displaystyle\leq(1-\gamma)V_{\delta,k}+\left[\begin{array}[]{c}x_{k}-x^{*}\\\
\lambda_{k}-\lambda^{*}\end{array}\right]^{\top}Q\left[\begin{array}[]{c}x_{k}-x^{*}\\\
\lambda_{k}-\lambda^{*}\end{array}\right],$ (60)

where

$\displaystyle Q=\left[\begin{array}[]{cc}Q_{1}&\gamma\delta J^{\top}\\\
\gamma\delta J&Q_{2}\end{array}\right]$ (63)

with
$Q_{1}:=(\gamma-2\mu\alpha+2a_{3}\delta\alpha+b_{1}\alpha^{2}+2a_{4}\delta\alpha^{2})I_{n}$,
$Q_{2}:=(\gamma+\delta\alpha\kappa+b_{2}\alpha^{2}+2a_{5}\delta\alpha^{2})I_{m}+\frac{\alpha}{\rho}(\tilde{\Xi}_{k}-I_{m})-\alpha\delta(\Xi_{\lambda}JJ^{\top}+JJ^{\top}\Xi_{\lambda})$,
$b_{1}=a_{1}+2B_{g}^{2}$, and $b_{2}=a_{2}+\frac{2}{\rho^{2}}$.

If $Q\preceq 0$, then ${V}_{\delta,k+1}\leq(1-\gamma)V_{\delta,k}$, indicating
that
$\lambda_{\min}(Q_{\delta})(\|{x}_{k+1}-x^{*}\|^{2}+\|{\lambda}_{k+1}-\lambda^{*}\|^{2})\leq\lambda_{\max}(Q_{\delta})(1-\gamma)(\|x_{k}-x^{*}\|^{2}+\|\lambda_{k}-\lambda^{*}\|^{2})$.
Therefore,

$\displaystyle\|{x}_{k+1}-x^{*}\|^{2}+\|{\lambda}_{k+1}-\lambda^{*}\|^{2}$
$\displaystyle\leq\frac{\lambda_{\max}(Q_{\delta})}{\lambda_{\min}(Q_{\delta})}(1-\gamma)(\|x_{k}-x^{*}\|^{2}+\|\lambda_{k}-\lambda^{*}\|^{2}).$
(64)

Thus, (15) holds for
$C=\lambda^{-1}_{\min}(Q_{\delta})\lambda_{\max}(Q_{\delta})$.

Note that $\left[\begin{array}[]{cc}-\gamma I_{n}&\gamma\delta J^{\top}\\\
\gamma\delta J&-\gamma I_{m}\end{array}\right]\preceq 0.$ Hence, to prove
$Q\preceq 0$, it suffices to ensure $Q\preceq\left[\begin{array}[]{cc}-\gamma
I_{n}&\gamma\delta J^{\top}\\\ \gamma\delta J&-\gamma
I_{m}\end{array}\right]$, i.e.,

$\displaystyle\left[\begin{array}[]{cc}Q_{1}+\gamma I_{n}&{\bf 0}_{n\times
m}\\\ {\bf 0}_{m\times n}&Q_{2}+\gamma I_{m}\end{array}\right]\preceq 0.$ (67)

By (16), one can obtain that
$2\gamma-2\mu\alpha+2a_{3}\delta\alpha+b_{1}\alpha^{2}+2a_{4}\delta\alpha^{2}\leq
0$, i.e., $Q_{1}+\gamma I_{m}\preceq 0$.

Next, consider
$\Theta:=\frac{\alpha}{\rho}(\tilde{\Xi}_{k}-I_{m})-\alpha\delta(\Xi_{\lambda}JJ^{\top}+JJ^{\top}\Xi_{\lambda})$
in $Q_{2}$. If
$\Theta+(2\gamma+\delta\alpha\kappa+b_{2}\alpha^{2}+2a_{5}\delta\alpha^{2})I_{m}\preceq
0$, then $Q_{2}+\gamma I_{m}\preceq 0$.

Note that $\xi_{i,\lambda}=\tilde{\xi}_{i,k}=1$ when $i\in{\mathcal{I}}$.
Partition $\Theta$ as

$\displaystyle\Theta=\left[\begin{array}[]{cc}\Theta_{1}&\Theta_{3}\\\
\Theta_{3}^{\top}&\Theta_{2}\end{array}\right]$ (70)

where

$\displaystyle\Theta_{1}$ $\displaystyle:=-2\delta\alpha
J_{\mathcal{I}}J_{\mathcal{I}}^{\top},$ $\displaystyle\Theta_{2}$
$\displaystyle:=\frac{\alpha}{\rho}(\tilde{\Xi}_{k,{\mathcal{I}}^{c}}-I)-\alpha\delta(\Xi_{\lambda,{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}^{\top}+J_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}^{\top}\Xi_{\lambda,{\mathcal{I}}^{c}}),$
$\displaystyle\Theta_{3}$ $\displaystyle:=-\delta\alpha
J_{\mathcal{I}}J_{{\mathcal{I}}^{c}}^{\top}(I+\Xi_{\lambda,{\mathcal{I}}^{c}}).$

Under LICQ in Assumption 1, it can be obtained that
$J_{I}J_{I}^{\top}\succeq\kappa I$. Then one can see from (16) that
$\Theta_{1}+(2\gamma+\delta\alpha\kappa+b_{2}\alpha^{2}+2a_{5}\delta\alpha^{2})I\preceq-\frac{1}{2}\delta\alpha
J_{\mathcal{I}}{\mathcal{J}}_{\mathcal{I}}^{\top}$.

By Lemma 6 in [19],
$L_{g}^{2}(I-\Xi_{{\mathcal{I}}^{c}})+\Xi_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}^{\top}+J_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}^{\top}\Xi_{{\mathcal{I}}^{c}}\succeq
0$, then since $\tilde{\xi}_{i,k}\leq\xi_{i,\lambda}$ for
$i\in{\mathcal{I}}^{c}$, one has

$\displaystyle\Theta_{2}\preceq\frac{\alpha}{\rho}(\tilde{\Xi}_{{\mathcal{I}}^{c}}-I)-\delta\alpha
L_{g}^{2}(\tilde{\Xi}_{{\mathcal{I}}^{c}}-I).$ (71)

Denote
$\phi=2\gamma+\delta\alpha\kappa+b_{2}\alpha^{2}+2a_{5}\delta\alpha^{2}$, then
one can obtain that

$\displaystyle\Theta_{2}+\phi I-\Theta_{3}^{\top}(\Theta_{1}+\phi
I_{m})^{-1}\Theta_{3}$ $\displaystyle\preceq\frac{\alpha}{\rho}(1-\delta\rho
L_{g}^{2})(\tilde{\Xi}_{{\mathcal{I}}^{c}}-I)+\phi I$
$\displaystyle~{}~{}~{}+2\alpha\delta(I+\Xi_{\lambda,{\mathcal{I}}^{c}})J_{{\mathcal{I}}^{c}}J_{\mathcal{I}}^{\top}(J_{\mathcal{I}}J_{{\mathcal{I}}})^{-1}J_{\mathcal{I}}J_{{\mathcal{I}}^{c}}^{\top}(I+\Xi_{\lambda,{\mathcal{I}}^{c}})$
$\displaystyle\preceq\frac{\alpha}{\rho}(1-\delta\rho
L_{g}^{2})(\tilde{\Xi}_{{\mathcal{I}}^{c}}-I)+\phi I$
$\displaystyle~{}~{}~{}+2\alpha\delta(I+\Xi_{\lambda,{\mathcal{I}}^{c}})J_{{\mathcal{I}}^{c}}J_{{\mathcal{I}}^{c}}^{\top}(I+\Xi_{\lambda,{\mathcal{I}}^{c}})$
$\displaystyle\preceq\frac{\alpha}{\rho}(1-\delta\rho
L_{g}^{2})(\tilde{\Xi}_{{\mathcal{I}}^{c}}-I)+\phi I+8\alpha\delta
B_{g}^{2}I,$ (72)

where $A^{\top}(AA^{\top})^{-1}A\preceq I$ for a full row rank matrix $A$ has
been applied in the second inequality.

If for all $i\in{\mathcal{I}}^{c}$ and $k\geq 0$,

$\displaystyle\tilde{\xi}_{i,k}\leq\pi^{*}=[\rho\max\limits_{i\in{\mathcal{I}}^{c}}\\{g_{i}(x^{*})\\}/(\sqrt{C}d_{0})+1]_{+}^{2},$
(73)

then one can obtain that the sum on the right hand of (72) is less than or
equal to 0 by (14) and (16), and then by Schur complement, $Q_{2}+\gamma
I_{m}\preceq 0$. Thus Theorem 1 is proved.

What we left is to show (73). Based on (8) and $g_{i}(x^{*})<0$ for
$i\in{\mathcal{I}}^{c}$, one has that $\lambda_{i}^{*}=0$,
$i\in{\mathcal{I}}^{c}$. For $k=0$, obviously, for all
$i\in{\mathcal{I}}^{c}$, $\tilde{\xi}_{i,0}\leq\pi^{*}$, which indicates that
(73) holds for $k=0$, and then ${V}_{\delta,1}\leq V_{\delta,0}$. Therefore,
invoking (64) yields that for all $i\in{\mathcal{I}}^{c}$,

$\displaystyle\tilde{\xi}_{i,1}\leq[\rho\max\limits_{i\in{\mathcal{I}}^{c}}\\{g_{i}(x^{*})\\}/(\sqrt{C}d_{0})+1]_{+}^{2}=\pi^{*}.$

Subsequently, by the mathematical induction, (73) can be proved. The proof is
completed. $\blacksquare$

##  IV Example

In this section, an example motivated by applications in power systems [22] is
presented to illustrate the feasibility of the discrete-time Aug-PGD (7).
Consider the following constrained optimization problem:

$\displaystyle\min\limits_{p_{i},q_{i}\in\mathbb{R}}~{}~{}~{}f(x)=\sum_{i=1}^{n}((p_{i}-p_{v,i})^{2}+q_{i}^{2})$
$\displaystyle~{}~{}\text{s.t.}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}g_{i}(x)=p_{1}^{2}+q_{i}^{2}-S_{i}\leq
0,$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}0\leq
p_{i}\leq p_{v,i},~{}i\in[n],$ (74)

where $x=(p_{1},\ldots,p_{n},q_{1},\ldots,q_{n})^{\top}$ and $p_{v,i},S_{i}$,
$i\in[n]$ are constants. The problem (74) along with an affine inequality
constraint was considered in [22] but via a continuous-time dynamics Aug-PDGD.
The affine inequality constraints can be regarded as special nonlinear
constrains. Hence the algorithm Aug-PDG studied in this paper is applicable to
the optimization problem (74).

Let $n=10$,

$\displaystyle S$ $\displaystyle=(S_{1},\ldots,S_{n})$
$\displaystyle=(2.7,1.35,2.7,1.35,2.025,2.025,2.7,2.7,1.35,2.025)$

and $p_{v}=(p_{v,1},\ldots,p_{v,n})=4S$. Choose $\rho=0.1$ and $\alpha=0.1$.
Three cases are simulated, where the initial point $(x_{0},\lambda_{0})$ is
selected randomly such that the distance from the initial point
$(x_{0},\lambda_{0})$ to the optimal point $(x^{*},\lambda^{*})$ (i.e.,
$d_{0}$) is $0.1\|(x^{*},\lambda^{*})\|$, $5\|(x^{*},\lambda^{*})\|$ and
$10\|(x^{*},\lambda^{*})\|$, respectively. The curves of the normalized
distance
$\frac{\|(x_{k}-x^{*},\lambda_{k}-\lambda^{*})\|}{\|(x^{*},\lambda^{*})\|}$
with respect to the iteration $k$ are shown in Figure 1, where for each case,
10 instances of randomly selected initial points are considered. From Figure
1, it can be seen that the convergence rates are different for different
$d_{0}$, and the distance $\|(x_{k}-x^{*},\lambda_{k}-\lambda^{*})\|$ linearly
decays on the whole. Moreover, for each case, the decreasing rate also changes
as $(x_{k},\lambda_{k})$ approaches the optimal point. Specifically, the
decreasing rates are small at the beginning and then become large when
$(x_{k},\lambda_{k})$ goes to the optimal point. These observations support
the semi-global linear convergence of the Aug-PDG, which is consistent with
our theory analysis.

Figure 1: Simulation of the relative distances to $\|(x^{*},\lambda^{*})\|$
with respect to iteration $k$.

##  V Conclusion

In this paper, the linear convergence of an Aug-PDG in discrete-time for
convex optimization with nonlinear inequality constraints has been
investigated. Under some mild assumptions, the Aug-PDG has been proved to
semi-globally converge at a linear rate, which depends on the distance from
the initial point to the optimal point. Future research of interest may be to
devise a method for solving the optimization problem under nonlinear
constraints with a global linear convergence rate.

## References

  * [1] A. Ruszczynski, _Nonlinear Optimization_. Princeton university press, 2011.
  * [2] M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architectures,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 255–312, 2007.
  * [3] C. Zhao, U. Topcu, N. Li, and S. Low, “Design and stability of load-side primary frequency control in power systems,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 5, pp. 1177–1189, 2014.
  * [4] J. Chen and V. K. Lau, “Convergence analysis of saddle point problems in time varying wireless systems-Control theoretical approach,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 1, pp. 443–452, 2012.
  * [5] B. Gharesifard and J. Cortes, “Distributed convergence to Nash equilibria in two-network zero-sum games,” _Automatica_ , vol. 49, no. 6, pp. 1683–1692, 2013.
  * [6] L. Pavel, “Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 4, pp. 1584–1597, 2020.
  * [7] B. Polyak, “Iterative methods using Lagrange multipliers for solving extremal problems with constraints of the equation type,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 10, no. 5, pp. 42–52, 1970.
  * [8] E. Golshtein, “Generalized gradient method for finding saddle points,” _Matekon_ , vol. 10, no. 3, pp. 36–52, 1974.
  * [9] A. Nedić and A. Ozdaglar, “Subgradient methods for saddle point problems,” _Journal of Optimization Theory and Applications_ , vol. 142, no. 1, pp. 205–228, 2009.
  * [10] D. Feijer and F. Paganini, “Stability of primal–dual gradient dynamics and applications to network optimization,” _Automatica_ , vol. 46, no. 12, pp. 1974–1981, 2010.
  * [11] A. Cherukuri, E. Mallada, and J. Cortés, “Asymptotic convergence of constrained primal–dual dynamics,” _Systems & Control Letters_, vol. 87, pp. 10–15, 2016.
  * [12] M. Hong, D. Hajinezhad, and M.-M. Zhao, “Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks,” in _International Conference on Machine Learning_ , 2017, pp. 1529–1538.
  * [13] Q. Lei, I. E.-H. Yen, C.-y. Wu, I. S. Dhillon, and P. Ravikumar, “Doubly greedy primal-dual coordinate descent for sparse empirical risk minimization,” in _International Conference on Machine Learning_ , 2017, pp. 2034–2042.
  * [14] X. Li, L. Xie, and Y. Hong, “Distributed continuous-time nonsmooth convex optimization with coupled inequality constraints,” _IEEE Transactions on Control of Network Systems_ , vol. 7, no. 1, pp. 74–84, 2020.
  * [15] X. Li, G. Feng, and L. Xie, “Distributed proximal algorithms for multi-agent optimization with coupled inequality constraints,” _IEEE Transactions on Automatic Control_ , 2020, DOI: 10.1109/TAC.2020.2989282.
  * [16] S. K. Niederländer, F. Allgöwer, and J. Cortés, “Exponentially fast distributed coordination for nonsmooth convex optimization,” in _IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 1036–1041.
  * [17] N. K. Dhingra, S. Z. Khong, and M. R. Jovanović, “The proximal augmented Lagrangian method for nonsmooth composite optimization,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 7, pp. 2861–2868, 2019.
  * [18] S. Q. Shen, T. Z. Huang, and J. Yu, “Eigenvalue estimates for preconditioned nonsymmetric saddle point matrices,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 31, no. 5, pp. 2453–2476, 2010.
  * [19] G. Qu and N. Li, “On the exponential stability of primal-dual gradient dynamics,” _IEEE Control Systems Letters_ , vol. 3, no. 1, pp. 43–48, 2019\.
  * [20] Y. Su, Y. Shi, and C. Sun, “Contraction analysis on primal-dual gradient optimization,” _arXiv preprint arXiv:1907.10171_ , 2019.
  * [21] A. Nedić, “Random algorithms for convex minimization problems,” _Mathematical Programming_ , vol. 129, no. 2, pp. 225–253, 2011.
  * [22] Y. Tang, G. Qu, and N. Li, “Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization,” _Systems & Control Letters_, vol. 144, p. 104754, 2020.
  * [23] D. P. Bertsekas, _Constrained Optimization and Lagrange Multiplier Methods_. Academic press, 2014.
  * [24] G. Wachsmuth, “On LICQ and the uniqueness of Lagrange multipliers,” _Operations Research Letters_ , vol. 41, no. 1, pp. 78–80, 2013.
  * [25] I. Necoara, Y. Nesterov, and F. Glineur, “Linear convergence of first order methods for non-strongly convex optimization,” _Mathematical Programming_ , vol. 175, no. 1-2, pp. 69–107, 2019.
  * [26] S. Sastry, _Nonlinear Systems: Analysis, Stability, and Control_. Springer Science & Business Media, 2013.


# SNR-Adaptive Ranging Waveform Design Based on
Ziv-Zakai Bound Optimization

Yifeng Xiong, , and Fan Liu Y. Xiong is with the School of Information and
Communication Engineering, Beijing University of Posts and Telecommunications,
Beijing 100876, China. (e-mail: yifengxiong@bupt.edu.cn)F. Liu is with the
Department of Electronic and Electrical Engineering, Southern University of
Science and Technology, Shenzhen 518055, China. (e-mail<EMAIL_ADDRESS>
###### Abstract

Location-awareness is essential in various wireless applications. The
capability of performing precise ranging is substantial in achieving high-
accuracy localization. Due to the notorious ambiguity phenomenon, optimal
ranging waveforms should be adaptive to the signal-to-noise ratio (SNR). In
this letter, we propose to use the Ziv-Zakai bound (ZZB) as the ranging
performance metric, as well as an associated waveform design algorithm having
theoretical guarantee of achieving the optimal ZZB at a given SNR. Numerical
results suggest that, in stark contrast to the well-known high-SNR design
philosophy, the detection probability of the ranging signal becomes more
important than the resolution in the low-SNR regime.

###### Index Terms:

SNR-adaptive ranging, waveform design, Ziv-Zakai bound, localization, wireless
sensing.

##  I Introduction

Location information acquisition is one of the most indispensable sensing
capabilities in wireless networks, which serves as a key enabler of a wide
range of tasks including autonomous driving, internet of things, logistic and
health care [1, 2, 3, 4]. Precise ranging is at the core of high-accuracy
localization systems, for which waveform design is an essential task.
Regarding ranging waveform design, a key observation is that the time-
resolution of a ranging signal is roughly proportional to the reciprocal of
its bandwidth, which has inspired many existing ranging techniques, including
techniques based on ultra-wideband (UWB) signals [5, 6], as well as those
benefitted from carrier aggregation [7, 8]. This insight has also given rise
to considerable efforts devoted to network operation techniques yielding
optimized bandwidth allocation strategies for localization systems [9, 10,
11].

From a theoretical perspective, the Cramér-Rao bound (CRB) of distance
corroborates the “large bandwidth” intuition, stating that the lowest
achievable mean-squared error (MSE) is inversely proportional to the squared
root-mean-square (RMS) bandwidth [6]. In more precise terms, the RMS bandwidth
is known to be proportional to the curvature of the signal autocorrelation
function (ACF) at the peak [6]. As it can be observed from Fig. 1, when the
signal-to-noise ratio (SNR) is high, the estimated distance (represented by
$\hat{d}_{\rm H}$ in Fig. 1) would lie within the mainlobe around the true
peak, and hence the ranging error is mainly determined by the aforementioned
curvature. However, when the SNR is relatively low, there is a non-negligible
probability that the maximum matched filter response locates at one of the ACF
sidelobes, resulting in larger ranging errors corresponding to $\hat{d}_{\rm
L}$ in Fig. 1. This issue is known as the “ambiguity phenomenon” [12], which
suggests that the optimal ranging waveform should be SNR-adaptive.

Designing SNR-adaptive ranging waveforms would certainly rely on SNR-dependent
performance metrics. CRB, being the most widely employed metric for
estimators, does depend on SNR. Unfortunately, CRB is related to the ranging
waveform only via its RMS bandwidth, suggesting that it does not account for
the ambiguity phenomenon. Therefore, CRB-based waveform design yields a single
waveform for any SNR. In fact, the actual MSE of the CRB-optimal waveform
never attains the corresponding CRB (at an arbitrarily high SNR), as will be
detailed later in this letter.

Figure 1: A sketchy illustration of the signal ACF and different types of
ranging errors.

A promising candidate metric accounting for the ambiguity phenomenon is the
Ziv-Zakai bound (ZZB) [13]. The main underlying idea of ZZB is that the MSE
can be expressed in terms of the error probability of binary detection
problems [14]. Intuitively, in the ranging problem, such binary detection
problems concern distinguishing the true ACF peak from the sidelobes, and
hence automatically take the ambiguity phenomenon into account. The ZZB of the
ranging problem has been derived and analyzed extensively in the existing
literature [13, 14, 15], showing that it does reflect the ambiguity issue in
practice. However, to the best knowledge of the authors, ZZB has not been
applied to waveform design, mainly due to its lack of closed-form expressions.

In this letter, instead of attempting to find suitable closed-form
approximations, we aim for designing SNR-adaptive ranging waveforms by
directly solving the ZZB optimization problem as a variational problem. Our
contributions are summarized as follows.

  * •

We show that the variational problem of ZZB optimization for ranging waveform
design is a convex problem;

  * •

We propose a discretized numerical reformulation of the ZZB optimization
problem preserving the convexity, as well as an associated computation-
efficient design algorithm based on the gradient projection method;

  * •

Using numerical examples, we demonstrate that smaller RMS bandwidth can be
more favorable under strong noise, suggesting that detection probability is
preferred to resolution in the low-SNR regime.

Notations: Throughout the letter, we use $[\bm{x}]_{i}$ to represent the
$i$-th entry of vector $\bm{x}$, and use $[\bm{A}]_{i,j}$ to represent the
$(i,j)$-th entry of matrix $\bm{A}$.

##  II System Model

Let us consider the generic time-based ranging model of

$y(t)=s(t-\tau)+n(t),$ (1)

where $y(t)$ denotes the received signal, $s(t)$ represents the transmitted
signal, $n(t)$ denotes the zero-mean white Gaussian noise having a constant
power spectral density of $N_{0}$. The term $\tau=d/c$ denotes the propagation
delay, with $c$ being the propagation speed (e.g. speed of light), and $d$
being the distance to be estimated. With this model in hand, we may obtain the
following likelihood function

$\displaystyle f(y;\tau)$ $\displaystyle\propto e^{-\frac{1}{N_{\rm
0}}\int_{-\infty}^{\infty}(y(t)-s(t-\tau))^{2}{\rm d}t}$ $\displaystyle\propto
e^{-\frac{2}{N_{\rm 0}}\left(R(\tau)+\int_{-\infty}^{\infty}n(t)s(t-\tau){\rm
d}t\right)},$ (2)

where $R(\tau)$ is the ACF of $s(t)$ given by
$R(\tau)=\int_{-\infty}^{\infty}s(t-\tau)s(t){\rm d}t$.

According to [15], when the a priori distribution of the delay $\tau$ is a
uniform distribution over $[\tau_{\min},\tau_{\max}]$, the ZZB of the distance
$d$ takes the following form

$\displaystyle\mathbb{E}\left\\{(d\\!-\\!\hat{d})^{2}\right\\}$
$\displaystyle\\!\geqslant\\!\zeta_{\rm SNR}[\widetilde{R}]$ $\displaystyle:$
$\displaystyle\\!=\\!\int_{0}^{\epsilon_{\max}}xQ\Big{(}\sqrt{2^{-1}{\rm
SNR}(1\\!-\\!\widetilde{R}(x))}\Big{)}{\rm d}x,$ (3)

where $\epsilon_{\max}$ is the maximum possible ranging error, namely
$\epsilon_{\max}=c(\tau_{\max}-\tau_{\min})/2$, $Q(\cdot)$ denotes the
function of
$Q(z)=\int_{z}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^{2}}{\rm d}x$,
$\widetilde{R}(x)$ denotes the normalized (and rescaled) ACF defined as

$\widetilde{R}(x)=R(x/c)/R(0),$ (4)

while ${\rm SNR}$ is the SNR given by ${\rm
SNR}=\frac{1}{N_{0}}\int_{-\infty}^{\infty}s^{2}(t){\rm d}t$.111A noteworthy
fact is that the ZZB is related to the ranging waveform only through its ACF.
The remaining degrees of freedom may be used to convey information. This
characteristic is particularly useful in the context of integrated sensing and
communication [16].

###### Remark 1

We are now in the position to illustrate a key difference between CRB-based
waveform design and the proposed ZZB-based design. Specifically, the CRB of
$d$ is given by [17]

$\mathbb{E}\\{(d-\hat{d})^{2}\\}\geqslant c^{2}(8\pi^{2}\beta^{2}{\rm
SNR})^{-1},$ (5)

where $\beta=\int_{-\infty}^{\infty}f^{2}|S(f)|^{2}{\rm
d}f/\int_{-\infty}^{\infty}|S(f)|^{2}{\rm d}f$ is the RMS bandwidth, with
$S(f)$ being the Fourier transform of $s(t)$. In this expression, the term
${\rm SNR}^{-1}$ is merely a linear proportional factor. Consequently, the
CRB-based optimal waveform does not vary with SNR. By contrast, observe that
in the expression (II) of ZZB, ${\rm SNR}^{-1}$ no longer affects the ZZB in a
simple linear manner, given the highly non-linear $Q$ function. Therefore, for
different SNR values, the optimal signal ACF $\widetilde{R}(x)$ will be
different. This enables us to design SNR-adaptive normalized ACFs.

##  III Problem Formulation and the Proposed Design Method

We consider the problem of SNR-adaptive waveform design under bandwidth
constraint. In this letter, we consider the baseband ranging scenario, and
assume that the fractional bandwidth is small.222The fractional bandwidth is
defined as $B_{\rm frac}=B/f_{\rm c}$, where $B$ is the signal bandwidth while
$f_{\rm c}$ denotes the carrier frequency. Baseband signal processing is known
to be sufficient in the sense of Le Cam’s distance when the fractional
bandwidth is small [18, Remark 4]. For a given design SNR ${\rm SNR}_{\rm D}$,
this problem can be expressed as

$\displaystyle\min_{\widetilde{R}(x)}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \zeta_{{\rm SNR}_{\rm D}}[\widetilde{R}]$ (6a)
$\displaystyle{\rm s.t.}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \widetilde{R}(0)=1,\leavevmode\nobreak\
\widetilde{R}(x)\leqslant 1,\leavevmode\nobreak\ \forall
x\in[0,\epsilon_{\max}].$ (6b) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \int_{-\infty}^{\infty}\widetilde{R}(x)e^{-j\omega x}{\rm
d}x\geqslant 0,\leavevmode\nobreak\ \forall\omega\in(-\infty,\infty),$ (6c)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\int_{-\infty}^{\infty}\widetilde{R}(x)e^{-j\omega x}{\rm
d}x=0,\leavevmode\nobreak\ \forall|\omega|>B,$ (6d)

where (6c) follows from the positive semi-definiteness of ACFs, (6d) is the
bandwidth constraint.333The bandwidth constraint is a low-pass constraint
since we consider baseband waveforms. This is an appropriate treatment when
the bandwidth of the baseband signal is much smaller compared to the carrier
frequency. In its original form, (6) is a variational problem which does not
admit any analytical solution. Nevertheless, we have the following result:

######  Proposition 1 (Convexity of Variational ZZB Optimization)

The objective functional $\zeta_{\rm SNR_{D}}[\widetilde{R}]$ is a convex
functional with respect to $\widetilde{R}(x)$.

###### Proof:

Please refer to Appendix A. ∎

Proposition 1 inspires us to find convex-preserving numerical reformulations
of (6), which guarantee the achievability of the global optimum. In this
letter, we consider the specific dicretized formulation as follows:

$\displaystyle\min_{\bm{r}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \zeta_{{\rm SNR}_{\rm
D}}(\bm{r}):=\sum_{i=1}^{N}x_{i}Q\left(\sqrt{2^{-1}{\rm SNR}_{\rm
D}(1\\!-\\!r_{i})}\right)$ (7a) $\displaystyle{\rm s.t.}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
r_{1}=1,\leavevmode\nobreak\ \bm{r}\preccurlyeq\bm{1},\leavevmode\nobreak\
\bm{C}\bm{r}\succcurlyeq\bm{0},$ (7b) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ [\bm{C}\bm{r}]_{i}=0,\leavevmode\nobreak\ \forall
i>B_{\rm dis},$ (7c)

where (7c) is the discretized version of the bandwidth constraint, $N$ is the
number of discretized sample points, $x_{i}=(i-1)\epsilon_{\max}/(N-1)$
denotes the $i$-th sample point, $\bm{r}=[r_{1},\dotsc,r_{N}]^{\rm T}$ is the
sampled version of $\widetilde{R}(x)$, and $\bm{C}$ is the matrix of discrete
cosine transform (DCT) satisfying

$[\bm{C}]_{k,n}=\sqrt{\frac{2}{N}}\cos\left(\frac{\pi}{4N}(2k-1)(2n-1)\right).$
(8)

Next, we show that this discretization is indeed convex-preserving.

###### Proposition 2

The problem (7) is convex.

###### Proof:

(Sketch) Computing the Hessian matrix of $\zeta_{{\rm SNR}_{\rm D}}(\bm{r})$
with respect to $\bm{r}$, and by noticing that $\frac{\partial^{2}\zeta_{{\rm
SNR}_{\rm D}}(\bm{r})}{\partial r_{i}\partial r_{j}}=0$ holds for any $i\neq
j$, we see that the Hessian matrix is positive semi-definite, and hence
$\zeta_{{\rm SNR}_{\rm D}}(\bm{r})$ is convex. This further implies that the
problem (7) is convex, since the feasible set characterized by (7b) and (7c)
is a convex polytope. ∎

In light of Proposition 2, we can obtain the global optimal solution of (7)
using the gradient projection method. The projection is practically
implementable since the Hessian matrix is diagonal and can be readily
calculated using (A). Specifically, the algorithm iterates as follows

$\displaystyle\bm{u}^{(l)}$
$\displaystyle={\cal{P}}_{{\cal{S}}}\big{(}\bm{r}^{(l-1)}-\sigma\nabla\zeta_{{\rm
SNR}_{\rm D}}(\bm{r}^{(l-1)})\big{)},$ (9a) $\displaystyle\bm{r}^{(l)}$
$\displaystyle=\bm{r}^{(l-1)}+\alpha_{l-1}(\bm{u}^{(l)}-\bm{r}^{(l-1)}),$ (9b)

until convergence, where $\sigma$ is a fixed step size, while $\alpha_{l-1}$
is a variable step size satisfying the Armijo’s condition [19]. The projection
operator ${\cal{P}}_{{\cal{S}}}(\bm{x})$ is defined by the following
optimization problem

${\cal{P}}_{{\cal{F}}}(\bm{x})=\mathop{\rm
argmin}_{\bm{r}}\leavevmode\nobreak\
\|\bm{x}-\bm{r}\|^{2},\leavevmode\nobreak\ {\rm s.t.}\leavevmode\nobreak\
\bm{r}\in{\cal{S}},$ (10)

where the feasible set ${\cal{S}}$ is given by

${\cal{S}}=\left\\{\bm{r}|r_{1}=1,\bm{r}\preccurlyeq\bm{1},\bm{C}\bm{r}\succcurlyeq\bm{0},[\bm{C}\bm{r}]_{i}=0,\forall
i>B_{\rm dis}\right\\}.$

Although problem (10) can be solved by general-purpose convex optimization
solvers (e.g. CVX [20]), such solvers may be computationally inefficient. To
this end, we apply Dykstra’s projection method [21] to simplify the procedure.
To elaborate, we compute ${\cal{P}}_{{\cal{S}}}(\bm{x})$ by iteratively
applying the following rules

$\displaystyle\bm{a}_{k}$
$\displaystyle={\cal{P}}_{{\cal{T}}}(\bm{x}_{k}+\bm{p}_{k}),\leavevmode\nobreak\
\bm{p}_{k+1}=\bm{x}_{k}+\bm{p}_{k}-\bm{a}_{k},$ (11a)
$\displaystyle\bm{x}_{k+1}$
$\displaystyle={\cal{P}}_{{\cal{F}}}(\bm{a}_{k}+\bm{q}_{k}),\leavevmode\nobreak\
\bm{q}_{k+1}=\bm{a}_{k}+\bm{q}_{k}-\bm{x}_{k+1},$ (11b)

ensuring that $\bm{x}_{k}$ converges to ${\cal{P}}_{{\cal{S}}}(\bm{x})$ as $k$
increases, where the notations $\bm{p}_{k}$ and $\bm{q}_{k}$ are temporary
intermediate variables, initialized by $\bm{p}_{0}=\bm{q}_{0}=\bm{0}$,
$\bm{x}_{0}=\bm{x}$, the “temporal domain feasible set” ${\cal{T}}$ and the
“frequency domain feasible set” ${\cal{F}}$ are defined as

$\displaystyle{\cal{T}}$
$\displaystyle=\left\\{\bm{r}|r_{1}=1,\bm{r}\preccurlyeq\bm{1}\right\\},$
(12a) $\displaystyle{\cal{F}}$
$\displaystyle=\left\\{\bm{r}|\bm{C}\bm{r}\succcurlyeq\bm{0},[\bm{C}\bm{r}]_{i}=0,\forall
i>B_{\rm dis}\right\\},$ (12b)

respectively. The corresponding projection operators are characterized by

$\displaystyle{[{\cal{P}}_{{\cal{T}}}(\bm{x})]}_{i}$
$\displaystyle=\left\\{\begin{array}[]{ll}1,&\hbox{$i=1$ or $i\neq
1,\leavevmode\nobreak\ r_{i}>1$;}\\\
x_{i},&\hbox{otherwise,}\end{array}\right.$ (13c)
$\displaystyle{[\bm{C}{\cal{P}}_{{\cal{F}}}(\bm{x})]}_{i}$
$\displaystyle=\left\\{\begin{array}[]{ll}0,&\hbox{$i>B_{\rm dis}$ or
$[\bm{C}\bm{x}]_{i}<0$;}\\\
{[\bm{C}\bm{x}]}_{i},&\hbox{otherwise.}\end{array}\right.$ (13f)

Overall, the algorithm requires only $\rm SNR_{D}$, the fixed step size
$\sigma$ and an initial guess $\bm{r}^{(0)}$ as inputs. The variable step
sizes $\\{\alpha_{l}\\}$ can be determined at runtime. The workflow of the
algorithm is summarized in Alg. 1.

###### Remark 2

Denoting the number of Dykstra’s iteration as $K$ (as used in Alg. 1), the
complexity of our projection method is on the order of $O(KN\log N)$, by
relying on fast DCT. By contrast, typical off-the-shelf solvers based on
interior-point method would yield a complexity of $O(N^{3.5})$. This
elucidates the computational efficiency of the proposed method.

Algorithm 1 The proposed waveform design algorithm.

1: Initialize $\bm{r}^{(0)}$;

2: for $l=1$:$L$ do

3: Compute $\bm{x}_{0}=\bm{r}^{(l-1)}-\sigma\nabla\zeta_{{\rm SNR}_{\rm
D}}(\bm{r}^{(l-1)})$;

4: Initialize $\bm{p}_{0}=\bm{q}_{0}=\bm{0}$;

5: for $k=1$:$K$ do

6:
$\bm{a}_{k}={\cal{P}}_{{\cal{T}}}(\bm{x}_{k}+\bm{p}_{k}),\leavevmode\nobreak\
\bm{p}_{k+1}=\bm{x}_{k}+\bm{p}_{k}-\bm{a}_{k}$;

7:
$\bm{x}_{k+1}={\cal{P}}_{{\cal{F}}}(\bm{a}_{k}+\bm{q}_{k}),\leavevmode\nobreak\
\bm{q}_{k+1}=\bm{a}_{k}+\bm{q}_{k}-\bm{x}_{k+1}$;

8: end for;

9: Let $\bm{u}^{(l)}=\bm{x}_{K}$;

10: Compute
$\bm{r}^{(l)}=\bm{r}^{(l-1)}+\alpha_{l-1}\left(\bm{u}^{(l)}-\bm{r}^{(l-1)}\right)$;

11: end for;

##  IV Numerical Results

Throughout the numerical examples, we consider the scenario where
$N=1000$,444$N=1000$ is chosen such that the discretization error is
negligible. $B_{\rm dis}=40$. The initial guess $\bm{r}^{(0)}$ is set to be
the Sinc pulse $\bm{s}$ satisfying

$[\bm{C}\bm{s}]_{i}=\left\\{\begin{array}[]{ll}c_{\rm s},&\hbox{$i\leqslant
B_{\rm dis}$;}\\\ 0,&\hbox{$i>B_{\rm dis}$,}\end{array}\right.$ (14)

where $c_{\rm s}$ is a constant ensuring that $s_{i}=1$. We also use the Sinc
pulse as a performance benchmark since it corresponds to a uniform frequency-
domain power allocation strategy. We assume that both the transmitter and the
receiver locate within the interval $[-1,1]$ on the real line, and thus the
maximum distance estimation error is $\epsilon_{\max}=2$.555The unit of the
distance is neglected as it is unnecessary for our purpose. We also use the
convention of $c=1$ for numerical convenience.

(a)

(b)

Figure 2: The MSE of the designed waveforms and benchmarks.

Before delving into details, we note that although the proposed algorithm
designs the waveform that achieves the lowest ZZB at a given design SNR $\rm
SNR_{D}$, the ZZB-optimal waveform at a specific $\rm SNR_{D}$ does not
necessarily achieve the optimal MSE at that SNR, since ZZB is a only lower
bound of the MSE. In light of this, we see that

######  Remark 3 (Adaptive Strategy)

We may conceive SNR-adaptive waveforms by selecting the ZZB-optimal waveform
achieving the lowest MSE at each $\rm SNR_{D}$.

We first demonstrate the optimal ZZB achieved by the proposed method,
portrayed in Fig. 2a. The first dotted line intersecting with the arrow in
Fig. 2a represent ${\rm SNR}_{\rm D}=10$dB, the second denotes ${\rm SNR}_{\rm
D}=13$dB, and so forth. The MSE achieved by certain ZZB-optimal waveforms at
fixed $\rm SNR_{D}$, and that achieved using the adaptive strategy are also
incorporated. Observe that the ZZB is achievable at relatively high SNR (i.e.
larger than around $16$dB). Another noteworthy issue is that the ZZB-optimal
waveform is indeed not necessarily MSE-optimal at ${\rm SNR}_{\rm D}$. For
example, in Fig. 2a, the ZZB-optimal waveform at ${\rm SNR_{D}}=18$dB is not
MSE-optimal until ${\rm SNR_{D}}=20$dB, while the ZZB-optimal waveform at
${\rm SNR_{D}}=13$dB is MSE-optimal around ${\rm SNR_{D}}=16.5$dB.

Next, let us compare the performance of the proposed SNR-adaptive waveforms
with that of the Sinc pulse, as portrayed in Fig. 2b. Observe that the Sinc
pulse achieves its corresponding CRB at relatively high SNRs. By contrast, the
optimal ZZB does not attain the optimal CRB even at ${\rm SNR}=30$dB, but the
gap between them shrinks as the SNR increases. Another closely-related
phenomenon is that the MSE of the CRB-optimal waveform is unfavorable over the
entire SNR range. To understand this phenomenon, first note that the CRB-
optimal waveform $\bm{r}_{\rm CRB}$ is a sinusoidal signal, namely
$[\bm{C}\bm{r}_{\rm CRB}]_{i}=1$ for $i=B_{\rm dis}$ and $[\bm{C}\bm{r}_{\rm
CRB}]_{i}=0$ otherwise, according to (5). This waveform will never exhibit a
CRB-achieving MSE at any SNR, since it is periodical and hence there will be
unresolvable integer ambiguities resulting in uniformly distributed ranging
errors across the entire region of interest, as can be observed from its poor
MSE performance in Fig. 2b. In contrast to CRB, ZZB can reflect the ambiguity
phenomenon. Consequently, the power spectral density of the ZZB-optimal
waveform would have its mass more biased towards $B_{\rm dis}$ as the SNR
increases, but will never become the impulse-like function corresponding to
the CRB-optimal waveform, as portrayed in Fig. 3a. Therefore, despite that the
ZZB-optimal waveforms do achieve their corresponding CRBs at high SNRs, the
optimal CRB is not achievable for any finite SNR. As an ultimate limit, in the
high-SNR regime, the minimum MSE is

$\frac{1}{B}\Big{(}\int_{0}^{B}f^{2}B^{-1}{\rm d}f\Big{)}^{-1}=\frac{1}{3}$
(15)

that of the MSE achieved by the Sinc pulse.

(a)

(b)

Figure 3: The frequency- and time-domain representations of the ZZB-optimal
waveforms at various design SNRs.

We have seen that in the high-SNR regime, the RMS bandwidth is an important
performance indicator, and provides a reasonable interpretation about the
performance gain of the SNR-adaptive waveform over the Sinc pulse. However,
similar arguments do not apply to the low-SNR regime. This can be seen from
Fig. 3a, in which the RMS bandwidth of the waveform at ${\rm SNR_{D}}=10$dB is
clearly smaller than that of the Sinc pulse, but it outperforms the Sinc pulse
in the low-SNR regime ($\leqslant 15$dB), as can be observed from Fig. 2a and
Fig. 2b.

Figure 4: The cumulative distribution of absolute ranging error at ${\rm
SNR}=10$dB, obtained by employing the Sinc pulse and the ZZB-optimal waveform
at ${\rm SNR}_{\rm D}=10$dB, respectively.

To further understand the low-SNR performance, in Fig. 4, we plot the
cumulative distribution function (CDF) of the absolute ranging error at ${\rm
SNR}=10$dB obtained by the ZZB-optimal waveform at ${\rm SNR_{D}}=10$dB, and
that of the Sinc pulse, respectively. Observe that when the cumulative
probability is larger than $0.7$, the CDF of the Sinc pulse behaves similar to
that of a uniform distribution, indicating that the Sinc pulse is essentially
a “random guess” in this regime, clearly outperformed by the ZZB-optimal
waveform. Interestingly, when the cumulative probability is less than $0.7$,
the Sinc pulse outperforms the ZZB-optimal waveform (as seen in the zoomed-in
figure). This phenomenon may be better illustrated by investigating the
normalized ACFs $\widetilde{R}(x)$ shown in Fig. 3b. It is seen that the ACF
mainlobe of the ZZB-optimal waveform at ${\rm SNR}_{\rm D}=10$dB is wider than
that of the Sinc pulse, which explains why the Sinc pulse outperforms the ZZB-
optimal waveform when the cumulative probability is less than $0.7$
(corresponding to the case in which the distance estimation still fall in the
mainlobe). Nevertheless, outside the mainlobe, the ${\rm SNR}_{\rm D}=10$dB
waveform still has a considerable autocorrelation, much larger than that of
the Sinc pulse. Consequently, the Sinc pulse would find the signal completely
lost in a strong noise, whereas the ${\rm SNR}_{\rm D}=10$dB waveform still
preserves some ranging information, since its relatively large ACF values
beyond the mainlobe would enhance the signal detection probability. This
reveals a design philosophy compared in stark contrast to that in the high-SNR
regime:

###### Remark 4

In the low-SNR regime, instead of improving the resolution, enhancing the
detection probability is of the highest priority. This suggests that
appropriately widening the ACF can be beneficial.

##  V Conclusions

In this letter, we have proposed a ranging waveform design method capable of
adpating to the SNR, based on the ZZB. The proposed design method is
guaranteed to yield the globally ZZB-optimal waveform due to the convexity of
the formulated problem.

Beyond the design method, the numerical results suggest that the waveform
design philosophy in the low-SNR regime is strikingly different from that in
the high-SNR regime: Essentially, the main performance indicator is the time-
resolution in the high-SNR regime, whereas the detection probability becomes
more crucial in the low-SNR regime. Therefore, larger RMS bandwidth would be
favorable for higher SNR, whereas smaller RMS bandwidth can be beneficial when
the SNR is relatively low, which improves the detection probability at the
cost of sacrificing some resolution. Possible applications of the proposed
method include pulse shaping for target ranging, and power allocation for
OFDM-based ranging systems.

##  Appendix A Proof of Proposition 1

###### Proof:

Note that for $x>0$, we have

$Q(\sqrt{x})=\frac{1}{2\sqrt{\pi}}\Gamma\Big{(}\frac{1}{2},\frac{1}{2}x\Big{)},$
(16)

where $\Gamma(s,t)$ denotes the incomplete Gamma function having the
derivative of $\frac{\partial\Gamma(s,t)}{\partial t}=-t^{s-1}e^{-t}$ [22].
Also observe that the expression of $\zeta_{\rm SNR_{D}}[\widetilde{R}]$ does
not contain the derivatives of $\widetilde{R}(x)$ with respect to $x$.
Therefore, according to the Euler-Lagrange equation, the first-order variation
of $\zeta_{\rm SNR_{D}}[\widetilde{R}]$ with respect to $\widetilde{R}$ is
given by

$\displaystyle\delta\zeta_{\rm SNR_{D}}$
$\displaystyle=\int_{0}^{\epsilon_{\max}}\left[x\frac{{\rm d}}{{\rm
d}\widetilde{R}}Q\left(\sqrt{2^{-1}{\rm SNR}_{\rm
D}(1-\widetilde{R})}\right)\right]\delta\widetilde{R}{\rm d}x$
$\displaystyle=\frac{x{\rm SNR}_{\rm
D}}{8\sqrt{\pi}}\int_{0}^{\epsilon_{\max}}\frac{e^{-\frac{\rm
SNR_{D}}{4}(1-\widetilde{R})}}{\sqrt{\frac{\rm
SNR_{D}}{2}(1-\widetilde{R})}}\cdot\delta\widetilde{R}{\rm d}x.$ (17)

The second-order variation takes the following form

$\displaystyle\delta^{2}\zeta_{\rm SNR_{D}}$ $\displaystyle=\frac{x\sqrt{\rm
SNR_{D}}}{4\sqrt{2\pi}}\int_{0}^{\epsilon_{\max}}e^{-\frac{\rm
SNR_{D}}{4}(1-\widetilde{R})}(\delta\widetilde{R})^{2}$ $\displaystyle\hskip
8.53581pt\times\left(\frac{\rm
SNR_{D}}{4}(1-\widetilde{R})^{\frac{1}{2}}+\frac{1}{2}(1-\widetilde{R})^{-\frac{3}{2}}\right){\rm
d}x.$ (18)

For $x\neq 0$, we have $1-\widetilde{R}(x)>0$. Thus for
$x\in(0,\epsilon_{\max}]$, the second-order variation satisfies
$\delta^{2}\zeta_{\rm SNR_{D}}>0$ for any $\delta\widetilde{R}$, implying that
the functional $\zeta_{\rm SNR_{D}}[\widetilde{R}]$ is convex. ∎

## References

  * [1] M. Z. Win, Y. Shen, and W. Dai, “A theoretical foundation of network localization and navigation,” _Proc. IEEE_ , vol. 106, no. 7, pp. 1136–1165, Jul. 2018.
  * [2] Y. Xiong, N. Wu, Y. Shen, and M. Z. Win, “Cooperative localization in massive networks,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 2, pp. 1237–1258, Feb. 2022.
  * [3] S. Kuutti, S. Fallah, K. Katsaros, M. Dianati, F. Mccullough, and A. Mouzakitis, “A survey of the state-of-the-art localization techniques and their potentials for autonomous vehicle applications,” _IEEE Internet Things J._ , vol. 5, no. 2, pp. 829–846, Feb. 2018.
  * [4] L. Chen _et al._ , “Robustness, security and privacy in location-based services for future IoT: A survey,” _IEEE Access_ , vol. 5, pp. 8956–8977, Apr. 2017.
  * [5] S. Gezici _et al._ , “Localization via ultra-wideband radios: A look at positioning aspects for future sensor networks,” _IEEE Signal Process. Mag._ , vol. 22, no. 4, pp. 70–84, Jul. 2005.
  * [6] Y. Shen and M. Z. Win, “Fundamental limits of wideband localization — part I: A general framework,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 10, pp. 4956–4980, Oct. 2010.
  * [7] T. Kazaz, G. J. M. Janssen, J. Romme, and A.-J. van der Veen, “Delay estimation for ranging and localization using multiband channel state information,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 4, pp. 2591–2607, Apr. 2022.
  * [8] M. Noschese, F. Babich, M. Comisso, and C. Marshall, “Multi-band time of arrival estimation for long term evolution (LTE) signals,” _IEEE Trans. Mobile Comput._ , vol. 20, no. 12, p. 3383–3394, Dec. 2021.
  * [9] M. Z. Win, W. Dai, Y. Shen, G. Chrisikos, and H. Vincent Poor, “Network operation strategies for efficient localization and navigation,” _Proc. IEEE_ , vol. 106, no. 7, pp. 1224–1254, Jul. 2018.
  * [10] T. Zhang, A. F. Molisch, Y. Shen, Q. Zhang, H. Feng, and M. Z. Win, “Joint power and bandwidth allocation in wireless cooperative localization networks,” _IEEE Trans. Wireless Commun._ , vol. 15, no. 10, pp. 6527–6540, Oct. 2016.
  * [11] T. Zhang, C. Qin, A. F. Molisch, and Q. Zhang, “Joint allocation of spectral and power resources for non-cooperative wireless localization networks,” _IEEE Trans. Commun._ , vol. 64, no. 9, pp. 3733–3745, Sep. 2016.
  * [12] S. Zafer, S. Gezici, and I. Guvenc, _Ultra-wideband Positioning Systems: Theoretical Limits, Ranging Algorithms, and Protocols_. Cambridge University Press, 2008.
  * [13] D. Chazan, M. Zakai, and J. Ziv, “Improved lower bounds on signal parameter estimation,” _IEEE Trans. Inf. Theory_ , vol. 21, no. 1, pp. 90–93, Jan. 1975.
  * [14] K. Bell, Y. Steinberg, Y. Ephraim, and H. Van Trees, “Extended Ziv-Zakai lower bound for vector parameter estimation,” _IEEE Trans. Inf. Theory_ , vol. 43, no. 2, pp. 624–637, Feb. 1997.
  * [15] A. Mallat, S. Gezici, D. Dardari, C. Craeye, and L. Vandendorpe, “Statistics of the MLE and approximate upper and lower bounds — part I: Application to TOA estimation,” _IEEE Trans. Signal Process._ , vol. 62, no. 21, pp. 5663–5676, Nov. 2014.
  * [16] Y. Xiong, F. Liu, Y. Cui, W. Yuan, T. X. Han, and G. Caire, “On the fundamental tradeoff of integrated sensing and communications under Gaussian channels,” _IEEE Trans. Inf. Theory_ , pp. 1–1, Early Access, 2023.
  * [17] A. Liu, Z. Huang, M. Li, Y. Wan, W. Li, T. X. Han, C. Liu, R. Du, D. K. P. Tan, J. Lu, Y. Shen, F. Colone, and K. Chetty, “A survey on fundamental limits of integrated sensing and communication,” _IEEE Commun. Surv. Tuts._ , vol. 24, no. 2, pp. 994–1034, 2nd Quart. 2022.
  * [18] Y. Han, Y. Shen, X.-P. Zhang, M. Z. Win, and H. Meng, “Performance limits and geometric properties of array localization,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 2, pp. 1054–1075, Feb. 2016.
  * [19] J. Nocedal and S. Wright, _Numerical Optimization_. Springer Science, 1999.
  * [20] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [21] J. P. Boyle and R. L. Dykstra, “A method for finding projections onto the intersection of convex sets in hilbert spaces,” in _Proc. Advances in Order Restricted Statistical Inference_. New York, NY: Springer New York, 1986, pp. 28–47.
  * [22] D. Zwillinger and A. Jeffrey, _Table of integrals, series, and products_ , 7th ed. Elsevier, 2007.

  *[CRB]: Cramér-Rao bound
  *[MSE]: mean-squared error
  *[RMS]: root-mean-square
  *[ACF]: autocorrelation function
  *[SNR]: signal-to-noise ratio
  *[ZZB]: Ziv-Zakai bound
  *[ACFs]: autocorrelation function
  *[DCT]: discrete cosine transform
  *[SNRs]: signal-to-noise ratio
  *[CRBs]: Cramér-Rao bound
  *[CDF]: cumulative distribution function