# A Two-level ADMM Algorithm for AC OPF with Convergence Guarantees

Kaizhao Sun, and Xu Andy Sun The authors are with the H. Milton Stewart of
Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta,
GA, 30332 USA (email<EMAIL_ADDRESS>andy.sun@isye.gatech.edu).Manuscript
received [TO BE ADDED]

###### Abstract

This paper proposes a two-level distributed algorithmic framework for solving
the AC optimal power flow (OPF) problem with convergence guarantees. The
presence of highly nonconvex constraints in OPF poses significant challenges
to distributed algorithms based on the alternating direction method of
multipliers (ADMM). In practice, such algorithms heavily rely on warm start or
parameter tuning to display convergence behavior; in theory, convergence is
not guaranteed for nonconvex network optimization problems like AC OPF. In
order to overcome such difficulties, we propose a new distributed
reformulation for AC OPF and a two-level ADMM algorithm that goes beyond the
standard framework of ADMM. We establish the global convergence and iteration
complexity of the proposed algorithm under mild assumptions. Extensive
numerical experiments over some largest NESTA test cases (9000- and 13000-bus
systems) demonstrate advantages of the proposed algorithm over existing ADMM
variants in terms of convergence, scalability, and robustness. Moreover, under
appropriate parallel implementation, the proposed algorithm exhibits fast
convergence comparable to or even better than the state-of-the-art centralized
solver.

###### Index Terms:

Distributed optimization, optimal power flow, augmented Lagrangian method,
alternating direction method of multipliers.

##  I Introduction

The AC optimal power flow (OPF) is a basic building block in electric power
grid operation and planning. It is a highly nonconvex optimization problem,
due to nonlinear power flow equations, and is shown to be an NP-hard decision
problem [bienstock2015strong, lehmann2016ac]. Any computational method to be
deployed in power system practice should meet the stringent requirement that
the algorithm has guaranteed robust performance and requires minimal tuning
and intervention in face of variations in system conditions. Moreover, to
effectively coordinate multiple regions in a large power grid, distributed
algorithms that do not require sharing critical private information between
regions should be highly desirable. However, such a goal has remained
challenging for solving large-scale AC-OPF problems. Many existing algorithms
are only suited for centralized operation. Most distributed or decentralized
algorithms for solving AC-OPF do not have guaranteed convergence performance
and require extensive parameter tuning and experimentation.

In this paper, we develop a distributed algorithm for solving large-scale AC
OPF problems, and the proposed algorithm is proven to have global convergence.
This is the first time that guaranteed convergence performance under mild and
realistic conditions is achieved and iteration complexity bounds are obtained
for a distributed computation framework for solving AC OPF.

###  I-A Literature Review

The research community has extensively studied local nonlinear optimization
methods such as the interior point methods e.g. [jabr2002primal,
zimmerman2011matpower]. Another line of research looks into convex relaxations
of AC OPF and has drawn significant attentions in recent years. In particular,
the semidefinite programming (SDP) relaxation is firstly applied to the OPF
problem in [bai2008semidefinite], and sufficient conditions are studied to
guarantee the exactness of SDP relaxations [lavaei2014geometry]. However, SDP
suffers from expensive computation cost for large-scale problems, while the
second-order cone programming (SOCP) relaxation initially proposed in
[jabr2006radial] offers a favorable alternative. The strong SOCP relaxation
proposed in [kocuk2016strong] is shown to be close to or dominates the SDP
relaxation, while the computation time of SOCP can be orders of magnitude
faster than SDP. However, obtaining a primal feasible solution is a common
challenge facing these convex relaxation methods.

The alternating direction method of multipliers (ADMM) offers a powerful
framework for distributed computation. Sun et al. [sun2013fully] apply ADMM to
decompose the computation down to each individual bus, and observe the
convergence is sensitive to initial conditions. Erseghe
[erseghe2014distributed, erseghe2015distributed] studies the case where the
network is divided into overlapping subregions, and voltage information of
shared buses are duplicated by their connected subregions. In
[erseghe2014distributed], ADMM is directly applied to the underlying
distributed reformulation, and convergence is established by assuming
nonconvex OPF and ADMM subproblems have zero duality gaps. In
[erseghe2015distributed], standard ALM techniques are adopted inside ADMM.
Subsequential convergence is proved under the assumption that the penalty
parameter stays finite, which is basically assuming the algorithm converges to
a feasible solution. The assumption is quite strong as quadratic penalty in
general does not admit an exact penalization for nonconvex problems
[feizollahi2017exact]. A more recent work [mhanna_adaptive_2019] applies ADMM
to a component-based distributed reformulation of AC OPF. The ADMM penalty is
adaptively changed in every iteration, and the resulting algorithm numerically
converges for various networks under adaptive hyperparameter tuning. In
summary, existing ADMM-based algorithms either directly apply ADMM or its
variant as a heuristic, or rely on strong assumptions to establish asymptotic
convergence. See [molzahn2017survey] for a recent survey on distributed
optimization techniques for OPF.

###  I-B Contribution

In this paper, we address the convergence issues of ADMM by proposing a two-
level distributed algorithmic framework. The proposed framework is motivated
by our observation that some crucial structure necessary for the convergence
of nonconvex ADMM is absent in traditional distributed reformulations of AC
OPF, and we overcome such technical difficulty by embedding a three-block ADMM
inside the classic ALM framework. We present the global convergence and
iteration complexity results of the proposed framework, which rely on mild and
realistic assumptions. We demonstrate the convergence, scalability, and
robustness of the proposed algorithm over some largest NESTA test cases
[coffrin2014nesta], on which existing ADMM variants may fail to converge.
Generically, distributed algorithms can be slow due to limited access to
global information and communication delay; however, we show that, with proper
parallel implementation, the proposed algorithm achieves fast convergence
close to or even better than centralized solver.

###  I-C Notation and Organization

Throughout this paper, we use $\mathbb{R}^{n}$ to denote the $n$-dimensional
real Euclidean space; the inner product of $x,y\in\mathbb{R}^{n}$ is denoted
by $\langle x,y\rangle$; the Euclidean norm is denoted by $\|x\|$, and the
$\ell^{\infty}$ norm is denoted by $\|x\|_{\infty}$. When $x$ consists of $p$
subvectors, we write $x=(x_{1},\cdots,x_{p})$. We use $\mathbb{Z}_{++}$ to
denote the set of positive integers, and $[n]=\\{1,\cdots,n\\}$. For a closed
set $C\subset\mathbb{R}^{n}$, the projection operator onto $C$ is denoted by
$\mathrm{Proj}_{C}(x)$, and the indicator function of $C$ is denoted by
$\mathbb{I}_{C}(x)$, which takes value 0 if $x\in C$ and $+\infty$ otherwise.

The rest of this paper is organized as follows. In section II, we review the
AC OPF problem and nonconvex ADMM literature. Then in section III, we present
a new distributed reformulation and the proposed two-level algorithm. In
section IV, we state the main convergence results of the proposed two-level
algorithm, and discuss related convergence issues. Finally, we present
computational experiments in section V, and conclude this paper in section VI.

##  II Background

###  II-A AC OPF Formulation

Consider a power network $G(\mathcal{N},\mathcal{E})$ where $\mathcal{N}$
denotes the set of buses and $\mathcal{E}$ denotes the set of transmission
lines. Let $\delta(i)$ be the set of neighbours of $i\in\mathcal{N}$. Let
$Y=G+\mathbf{j}B$ denote the complex nodal admittance matrix, where
$\mathbf{j}=\sqrt{-1}$ and
$G,B\in\mathbb{R}^{|\mathcal{N}|\times|\mathcal{N}|}$. Let $p^{g}_{i}$,
$q^{g}_{i}$ (resp. $p^{d}_{i}$, $q^{d}_{i}$) be the real and reactive power
produced by generator(s) (resp. loads) at bus $i$; if there is no generator
(resp. load) attached to bus $i$, then $p^{g}_{i}$, $q^{g}_{i}$ (resp.
$p^{d}_{i}$, $q^{d}_{i}$) are set to 0. The complex voltage $v_{i}$ at bus $i$
can be expressed by its real and imaginary parts as
$v_{i}=e_{i}+\mathbf{j}f_{i}$. The rectangular formulation of AC OPF is given
as

$\displaystyle\min\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle\sum_{i\in\mathcal{N}}f_{i}(p^{g}_{i})$ (1a)
$\displaystyle\mathrm{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle p^{g}_{i}-p^{d}_{i}=G_{ii}(e_{i}^{2}+f_{i}^{2})+$
$\displaystyle\sum_{j\in{\delta}(i)}G_{ij}(e_{i}e_{j}+f_{i}f_{j})-B_{ij}(e_{i}f_{j}-e_{j}f_{i})$
$\displaystyle\forall i\in\mathcal{N}$ (1b) $\displaystyle
q^{g}_{i}-q^{d}_{i}=-B_{ii}(e_{i}^{2}+f_{i}^{2})+$
$\displaystyle\sum_{j\in{\delta}(i)}-B_{ij}(e_{i}e_{j}+f_{i}f_{j})-G_{ij}(e_{i}f_{j}-e_{j}f_{i})$
$\displaystyle\forall i\in\mathcal{N}$ (1c) $\displaystyle
p_{ij}^{2}+q_{ij}^{2}\leq\overline{s}_{ij}^{2}\quad\quad\leavevmode\nobreak\
\leavevmode\nobreak\ \forall(i,j)\in\mathcal{E}$ (1d)
$\displaystyle\underline{v}_{i}^{2}\leq
e_{i}^{2}+f_{i}^{2}\leq\overline{v}_{i}^{2}\quad\quad\quad\quad\quad\quad\leavevmode\nobreak\
\forall i\in\mathcal{N}$ (1e) $\displaystyle\underline{p^{g}_{i}}\leq
p^{g}_{i}\leq\overline{p^{g}_{i}},\leavevmode\nobreak\ \leavevmode\nobreak\
\underline{q^{g}_{i}}\leq q^{g}_{i}\leq\overline{q^{g}_{i}}\quad\quad\forall
i\in\mathcal{N}$ (1f)

where

$\displaystyle
p_{ij}=-G_{ij}(e_{i}^{2}+f_{i}^{2}-e_{i}e_{j}-f_{i}f_{j})-B_{ij}(e_{i}f_{j}-e_{j}f_{i}),$
(2a) $\displaystyle
q_{ij}=B_{ij}(e_{i}^{2}+f_{i}^{2}-e_{i}e_{j}-f_{i}f_{j})-G_{ij}(e_{i}f_{j}-e_{j}f_{i}).$
(2b)

In (1a), the objective $f_{i}(p^{g}_{i})$ represents the real power generation
cost at bus $i$. Constraints (1b) and (1c) correspond to real and reactive
power injection balance at bus $i$. The real and reactive power flow
$p_{ij},q_{ij}$ on line $(i,j)$ are given in (2), and (1d) restricts the
apparent power flow on each transmission line. Constraints (1e)-(1f) limit
voltage magnitude, real power output, and reactive power output at each bus to
its physical capacity. Since the objective is typically linear or quadratic in
real generation, formulation (1) is a nonconvex quadratically constrained
quadratic program (QCQP) problem.

###  II-B Nonconvex ADMM

ADMM was proposed in 1970s [glowinski1975approximation, gabay1976dual] and
regarded as a close variant of the augmented Lagrangian method
(ALM)[hestenes1969multiplier, powell1967method]. The standard ADMM framework
consists of a Gauss-Seidel type update on blocks of variables in each ALM
subproblem and then a dual update using current primal residuals. The update
of each individual block can be decomposed and carried out in parallel given
certain separable structures are available. More recently, researchers
realized that the ADMM framework can be used to solve more complicated
nonconvex multi-block problems in the form

$\displaystyle\min_{x=(x_{1},\cdots,x_{p})}\quad$
$\displaystyle\sum_{i=1}^{p}f_{i}(x_{i})+g(x)$ (3a)
$\displaystyle\mathrm{s.t.}\quad$
$\displaystyle\sum_{i=1}^{p}A_{i}x_{i}=b,\leavevmode\nobreak\
\leavevmode\nobreak\ x_{i}\in\mathcal{X}_{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\in[p],$ (3b)

where the primal variable $x$ is partitioned into $p$ subvectors
$x_{i}\in\mathbb{R}^{n_{i}}$ for $i\in[p]$, and $f_{i}$’s,
$\mathcal{X}_{i}$’s, and $g$ can be potentially nonconvex. Different
assumptions on the problem data are proposed to ensure global convergence to
stationary solutions and in general an iteration complexity of
$\mathcal{O}(1/\epsilon^{2})$ is expected [wang2014convergence,
wang2015global, jiang2019structured]. Though motivated by different
applications and adopting different analysis techniques, all these convergence
results on nonconvex ADMM rely on the following three assumptions:

  * (a)

All nonconvex subproblems need to be solved to global optimality;

  * (b)

The functions $f_{p}$ and $g$ (if exist) are Lipschitz continuous
differentiable, and $\mathcal{X}_{p}=\mathbb{R}^{n_{p}}$;

  * (c)

The image space of $A_{p}$ is sufficiently large, i.e.,
$\mathrm{Im}([A_{1},\cdots,A_{p-1},b])\subseteq\mathrm{Im}(A_{p})$.

These three assumptions together restrict the application of ADMM on the OPF
problem. No matter what reformulation of (1) is used, ADMM subproblems would
still have highly nonconvex constraints, so Assumption (a) is unrealistic for
the OPF problem. Fortunately, this assumption can be relaxed to finding a
stationary solution with improved augmented Lagrangian function value, which
usually can be achieved at the successful termination of some nonlinear
solvers. It turns out that Assumptions (b) and (c) cannot be satisfied
simultaneously if ADMM were to achieve parallel computation among different
agents [sun2019two]. Such limitation motivate us to go beyond the framework of
ADMM.

##  III A New Distributed Reformulation and a Two-level ADMM Algorithm

###  III-A A New Distributed Reformulation

Suppose the network $G$ is partitioned into $R$ subregions
$\mathcal{R}_{1},\cdots,\mathcal{R}_{R}\subseteq\mathcal{N}$, each of which is
assigned to a local control or operating agent. We say $(i,j)\in\mathcal{E}$
is a tie-line if $i\in\mathcal{R}_{r}$, $j\in\mathcal{R}_{l}$, and $r\neq l$.
Agent $r$ controls variables $x_{i}=(p^{g}_{i},q^{g}_{i},e_{i},f_{i})$ for all
$i\in\mathcal{R}_{r}$. We extend the notation $\delta(\mathcal{R}_{r})$ to
denote the set of all buses connected to (but not in) $\mathcal{R}_{r}$ by
some tie-lines.

The constraints of OPF couple adjacent agents. For example, suppose $(i,j)$ is
a tie-line where $i\in\mathcal{R}_{r}$ and $j\in\mathcal{R}_{l}$. Agent $r$
requires the information of variables $(e_{j},f_{j})$ to construct constraints
(1b)-(1d); however, agent $r$ cannot directly access $(e_{j},f_{j})$ as they
are controlled by agent $l$, and agent $l$ faces the same situation. In order
for these two agents to solve their localized problems in parallel, it is
necessary to break the coupling by introducing auxiliary variables. We let
each agent $r$ keep additional variables $x_{j}^{r}=(e^{r}_{j},f^{r}_{j})$ for
all $j\in\delta(\mathcal{R}_{r})$. A direct consequence is that all
constraints in formulation (1) are decomposed to local agents. For example,
for each $i\in\mathcal{R}_{r}$, constraints (1b)-(1d) can be rewritten as

$\displaystyle p^{g}_{i}-p^{d}_{i}=G_{ii}(e_{i}^{2}+f_{i}^{2})+$
$\displaystyle\sum_{j\in{\delta}(i)\cap\mathcal{R}_{r}}G_{ij}(e_{i}e_{j}+f_{i}f_{j})-B_{ij}(e_{i}f_{j}-e_{j}f_{i})+$
$\displaystyle\sum_{j\in{\delta}(i)\cap\delta(\mathcal{R}_{r})}G_{ij}(e_{i}e^{r}_{j}+f_{i}f^{r}_{j})-B_{ij}(e_{i}f^{r}_{j}-e^{r}_{j}f_{i})$
(4a) $\displaystyle q^{g}_{i}-q^{d}_{i}=-B_{ii}(e_{i}^{2}+f_{i}^{2})+$
$\displaystyle\sum_{j\in{\delta}(i)\cap\mathcal{R}_{r}}-B_{ij}(e_{i}e_{j}+f_{i}f_{j})-G_{ij}(e_{i}f_{j}-e_{j}f_{i})+$
$\displaystyle\sum_{j\in{\delta}(i)\cap\delta(\mathcal{R}_{r})}-B_{ij}(e_{i}e^{r}_{j}+f_{i}f^{r}_{j})-G_{ij}(e^{r}_{i}f_{j}-e^{r}_{j}f_{i})$
(4b) $\displaystyle
p_{ij}^{2}+q_{ij}^{2}\leq\bar{s}_{ij}^{2}\quad\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall(i,j)\in\mathcal{E},j\in\mathcal{R}_{r}$ (4c)
$\displaystyle{p^{r}_{ij}}^{2}+{q^{r}_{ij}}^{2}\leq\bar{s}_{ij}^{2}\leavevmode\nobreak\
\quad\forall(i,j)\in\mathcal{E},j\not\in\mathcal{R}_{r},$ (4d)

where $p_{ij}$, $q_{ij}$ are given in (2), and

$\displaystyle
p^{r}_{ij}=-G_{ij}(e_{i}^{2}+f_{i}^{2}-e_{i}e^{r}_{j}-f_{i}f^{r}_{j})-B_{ij}(e_{i}f^{r}_{j}-e^{r}_{j}f_{i}),$
(5a) $\displaystyle
q^{r}_{ij}=B_{ij}(e_{i}^{2}+f_{i}^{2}-e_{i}e^{r}_{j}-f_{i}f^{r}_{j})-G_{ij}(e_{i}f^{r}_{j}-e^{r}_{j}f_{i}).$
(5b)

Notice that all variables appeared in (4) are controlled by agent $r$, and all
such variables are grouped together and denoted by
$x^{r}=\left(\\{x_{i}\\}_{i\in\mathcal{R}_{r}},\\{x^{r}_{j}\\}_{j\in\delta(\mathcal{R}_{r})}\right)$.
Moreover, local nonconvex constraints of $\mathcal{R}_{r}$ can be conveniently
expressed as

$\displaystyle\mathcal{X}_{r}=\\{x^{r}\leavevmode\nobreak\
|\leavevmode\nobreak\ \eqref{eq: localconstr},\eqref{acropf:
vm_bounds}-\eqref{acropf: q_bounds}\leavevmode\nobreak\ \forall
i\in\mathcal{R}_{r}\\}.$ (6)

Notice that for every $j\in\cup_{r=1}^{R}\delta(\mathcal{R}_{r})$, bus $j$ is
connected to some tie-line, and thus at least two regions need to keep a local
copy of $(e_{j},f_{j})$. We use $R(j)$ to denote the subregion where bus $j$
is located, and $N(j)$ to denote the set of subregions that share a tie-line
with $R(j)$ through bus $j$. Naturally we want to impose consensus on local
copies of the same variables:

$e^{l}_{j}=e_{j},\leavevmode\nobreak\ f^{l}_{j}=f_{j}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall l\in N(j).$ (7)

If (7) is used, agents from $N(j)$ and agent $R(j)$ will need to alternatively
solve their subproblems in order to parallelize the computation. However, ADMM
does not guarantee convergence when both subproblems carry nonconvex
functional constraints. In order to solve this issue, we follow the idea
proposed in [sun2019two] by using a global copy
$\bar{x}_{j}=(\bar{e}_{j},\bar{f}_{j})$ and local slack variables
$z^{l}_{j}=(z^{l}_{e_{j}},z^{l}_{f_{j}})$ for $l\in N(j)\cup\\{R(j)\\}$. For
notational consistency, we also write
$x^{R(j)}_{j}=(e_{j},f_{j})=(e_{j}^{R(j)},f_{j}^{R(j)})$. The consensus is
then achieved through

$\displaystyle e^{l}_{j}-\bar{e}_{j}+$ $\displaystyle
z^{l}_{e_{j}}=0,\leavevmode\nobreak\ f^{l}_{j}-\bar{f}_{j}+$ $\displaystyle
z^{l}_{f_{j}}=0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l\in
N(j)\cup\\{R(j)\\}$ $\displaystyle z^{l}_{e_{j}}=0,$ $\displaystyle
z^{l}_{f_{j}}=0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l\in
N(j)\cup\\{R(j)\\}.$ (8)

Denote $x=\left(\\{x^{r}\\}_{r\in[R]}\right)$,
$\bar{x}=\left(\\{\bar{x}_{j}\\}_{j\in\cup_{r}\delta(\mathcal{R}_{r})}\right)$,
and $z=\left(\\{z^{l}_{j}\\}_{l\in
N(j)\cup\\{R(j)\\},j\in\cup_{r}\delta(\mathcal{R}_{r})}\right)$. Now we can
now abstract the AC OPF problem as:

$\displaystyle\min_{x,\bar{x},z}\quad$
$\displaystyle\sum_{r=1}^{R}c_{r}(x^{r}):=\sum_{r=1}^{R}\left(\sum_{i\in\mathcal{R}_{r}}f_{i}(p^{g}_{i})\right)$
(9) $\displaystyle\mathrm{s.t.}\quad$ $\displaystyle
Ax+B\bar{x}+z=0,\leavevmode\nobreak\ z=0,\leavevmode\nobreak\
x^{r}\in\mathcal{X}_{r}\leavevmode\nobreak\ \forall
r\in[R],\leavevmode\nobreak\ \bar{x}\in\bar{\mathcal{X}}.$

The objective $c_{r}(x^{r})$ is the sum of all generators’ costs in
$\mathcal{R}_{r}$. The linear coupling constraints (8) is compactly expressed
as $Ax+B\bar{x}+z=0$ with matrices $A$ and $B$ of proper dimensions. Each
local agent $r$ controls local OPF constraints $\mathcal{X}_{r}$ defined in
(6). Moreover, without changing the feasible region of (1), we may restrict
$\bar{x}$ inside some convex set $\bar{\mathcal{X}}$. For example, we can
simply let $\bar{\mathcal{X}}$ be a hypercube

$\bar{\mathcal{X}}=\prod_{j\in\cup_{r}\delta(\mathcal{R}_{r})}\bar{\mathcal{X}}_{j}:=\prod_{j\in\cup_{r}\delta(\mathcal{R}_{r})}\Big{\\{}\bar{x}_{j}|\leavevmode\nobreak\
\|\bar{x}_{j}\|_{\infty}\leq\bar{v}_{j}\Big{\\}}$ (10)

which is compact and easy to project onto.

Next we define stationarity for problem (9). After projecting out the slack
variable $z$, the Lagrangian function of (9) is

$L(x,\bar{x},y)=\sum_{r=1}^{R}(c_{r}(x^{r})+\mathbb{I}_{\mathcal{X}_{r}}(x^{r}))+\mathbb{I}_{\bar{\mathcal{X}}}(\bar{x})+\langle
y,Ax+B\bar{x}\rangle.$ (11)

We use $\partial f(\cdot)$ to denote the general subdifferential of a proper
lower semi-continuous function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$
[rockafellar2009variational, Def 8.3], and $N_{C}(x)$ to denote the general
normal cone of $C$ at $x\in C$ [rockafellar2009variational, Def 6.3].

######  Definition 1.

We say $(x,\bar{x},y)$ is an $\epsilon$-stationary point of problem (9) if
there exist $(d_{1},d_{2},d_{3})$ such that
$\max\\{\|d_{1}\|,\|d_{2}\|,\|d_{3}\|\\}\leq\epsilon$ where

$\displaystyle d_{1}$
$\displaystyle\in\partial\left(\sum_{r=1}^{R}c_{r}(x^{r})+\mathbb{I}_{\mathcal{X}_{r}}(x^{r})\right)+A^{\top}y$
(12a) $\displaystyle d_{2}$ $\displaystyle\in N_{\bar{\mathcal{X}}}+B^{\top}y$
(12b) $\displaystyle d_{3}$ $\displaystyle=Ax+B\bar{x};$ (12c)

or equivalently, $(d_{1},d_{2},d_{3})\in\partial L(x,\bar{x},y)$. We simply
say $(x,\bar{x},y)$ is a stationary point if $0\in\partial L(x,\bar{x},y)$ or
$\epsilon=0$.

If cost functions are concatenated as $c(x)=\sum_{r=1}^{R}c_{r}(x^{r})$, which
is assumed to be continuously differentiable, and let
$\mathcal{X}=\prod_{r=1}^{R}\mathcal{X}_{r}$, then (12a) can be further
reduced to

$0\in\nabla c(x)+N_{\mathcal{X}}(x)+A^{\top}y.$ (13)

###  III-B A Divergent Example for Two-block Nonconvex ADMM

Before presenting our proposed algorithm, we use a concrete example to
demonstrate that the vanilla version of ADMM indeed may suffer divergence for
OPF instances. Notice that without introducing slack variable $z$ and the
constraint $z=0$ as in (9), the distributed OPF problem can be formulated as a
two-block nonconvex problem

$\displaystyle\min_{x\in\mathcal{X},\bar{x}\in\bar{\mathcal{X}}}\quad
c(x)\quad\mathrm{s.t.}\quad Ax+B\bar{x}=0,$ (14)

which was also directly used to develop distributed algorithms
[erseghe2014distributed, erseghe2015distributed]. We partition the IEEE case30
available from [zimmerman2011matpower] into three subregions, directly apply
the vanilla version ADMM to the two-block formulation (14) with different
penalty parameter $\rho$, and plot the Infeasibility $\|Ax^{t}+B\bar{x}^{t}\|$
and Generation Cost $c(x^{t})$ as in Figure 1.

Figure 1: Divergent behaviour of vanilla ADMM

As we can see, the primal residual and generation costs exhibit oscillating
patterns for $\rho\in\\{1000,2000,3000,4000\\}$, and do not converge even when
ADMM has performed 2000 iterations. For $\rho=5000$, the primal residual
converges to 0.0093, and the generation cost at termination is below the lower
bound obtained from SOCP; these two facts indicate that ADMM indeed converges
to an infeasible solution.

We believe such failures of ADMM to obtain feasible solutions result from the
conflict between the aforementioned assumptions (b) and (c). To be more
specific, it is straightforward to verify that
$\mathrm{Im}(B)\subsetneq\mathrm{Im}(A)$: given a global copy $\bar{x}_{j}$,
every local agent $l\in N(j)\cup R(j)$ can always keep the same value
$x^{l}_{j}=\bar{x}_{j}$ so that the constraint $Ax+B\bar{x}=0$ is satisfied,
but the converse is in general not true. However, there are functional
constraints $\mathcal{X}$ associated with $x$, as agents need to coordinate
local OPF constraints. As a result, the block with “larger” image ($A$) does
not have a smooth objective ($c(x)+\mathbb{I}_{\mathcal{X}}(x)$), so
assumptions (b) and (c) cannot be satisfied simultaneously. Admittedly, we
observe convergence when a even larger penalty $\rho$ is used; however, we
want to empathize that despite the numerical success with adaptive parameter
tuning [mhanna_adaptive_2019], the traditional ADMM framework has no guarantee
of convergence and could fail for nonconvex distributed OPF.

###  III-C A New Two-level ADMM Algorithm

In this section we give a full description of the two-level algorithm applied
to the OPF problem. The key idea is to dualize and penalize the constraint
$z=0$ in (9), and apply three-block ADMM to solve the subproblem

$\displaystyle\min_{x\in\mathcal{X},\bar{x}\in\bar{\mathcal{X}},z}\quad$
$\displaystyle\sum_{r=1}^{R}c_{r}(x^{r})+\langle\lambda^{k},z\rangle+\frac{\beta^{k}}{2}\|z\|^{2}$
(15) $\displaystyle\mathrm{s.t.}\quad$ $\displaystyle Ax+B\bar{x}+z=0,$

with some dual variable $\lambda^{k}$ and penalty $\beta^{k}$, to an
approximate stationary solution in the following sense.

######  Definition 2.

We say $(x,\bar{x},z,y)$ is an $\epsilon$-stationary point of problem (15) if
there exist $(d_{1},d_{2},d_{3})$ such that
$\max\\{\|d_{1}\|,\|d_{2}\|,\|d_{3}\|\\}\leq\epsilon$, where $d_{1}$ and
$d_{2}$ satisfy (12a)-(12b), $d_{3}=Ax+B\bar{x}+z$, and
$\lambda^{k}+\beta^{k}z+y=0$.

Then at termination of ADMM, we update $\lambda^{k+1}$ and $\beta^{k+1}$ as in
the classic ALM framework in order to drive $z$ to 0. We say
$i\subseteq\mathcal{R}_{r}$ is a boundary bus of $\mathcal{R}_{r}$ if $i$ is
connected to another subregion through a tie-line, and denote the set of
boundary buses in $\mathcal{R}_{r}$ by $B(\mathcal{R}_{r})$. Note that the
inner-level ADMM dual variable and outer-level ALM dual variable $(y,\lambda)$
can be decomposed into subvectors
$\left(\\{y^{r}_{j},\lambda^{r}_{j}\\}_{j\in\delta(\mathcal{R}_{r})\cup
B(\mathcal{R}_{r})}\right)$ for $r\in[R]$, so they are controlled and updated
by different agents in parallel. See Algorithm 1 for a detailed description.

Algorithm 1 : A Two-level ADMM Algorithm

1: Initialize starting points
$(x^{0},\bar{x}^{0})\in\mathcal{X}\times\bar{\mathcal{X}}$ and
$\lambda^{1}\in[\underline{\lambda},\overline{\lambda}]$; $\beta^{1}>0$,
$k\leftarrow 1$;

2: while outer stopping criteria is not satisfied do

3: Initialize $(x^{0},\bar{x}^{0},z^{0},y^{0})$ such that
$\lambda^{k}+\beta^{k}z^{0}+y^{0}=0$; $\rho\leftarrow 2\beta^{k}$;
$t\leftarrow 1$

4: while inner stopping criteria is not satisfied do

5: each agent $r\in[R]$ updates $(x^{r})^{t+1}$ by solving :
$\displaystyle\min_{x^{r}\in\mathcal{X}_{r}}\leavevmode\nobreak\ $
$\displaystyle F_{r}^{t}(x^{r}):=c_{r}(x^{r})$
$\displaystyle+\sum_{j\in\delta(\mathcal{R}_{r})\cup
B(\mathcal{R}_{r})}\Big{(}\langle(y^{r}_{j})^{t},x^{r}_{j}\rangle$
$\displaystyle+\frac{\rho}{2}\|x^{r}_{j}-(\bar{x}_{j})^{t}+(z^{r}_{j})^{t}\|^{2}\Big{)};$
(16)

6: each agent $r\in[R]$ sends $(x^{r}_{j})^{t+1}$ to $R(j)$ for
$j\in\delta(\mathcal{R}_{r})$, and receives
$\left((x^{l}_{i})^{t+1},(z^{l}_{i})^{t},(y^{l}_{i})^{t}\right)$ from every
agent $l\in N(i)$ for all $i\in B(\mathcal{R}_{r});$

7: each agent $r\in[R]$ updates global copy $\bar{x}^{t+1}_{i}=$
$\displaystyle\mathrm{Proj}_{\bar{\mathcal{X}}_{i}}\left(\frac{\sum_{l\in
N(i)\cup
R(i)}\left[(y^{l}_{i})^{t}+\rho\left((x^{l}_{i})^{t+1}+(z^{l}_{i})^{t}\right)\right]}{(|N(i)|+1)\rho}\right)$
(17) for all $i\in B(\mathcal{R}_{r});$

8: each agent $r\in[R]$ sends $(\bar{x}_{i})^{t+1}$ to agents in $N(i)$ for
$i\in B(\mathcal{R}_{r})$, and receives $(\bar{x}_{j})^{t+1}$ from agent
$R(j)$ for all $j\in\delta(\mathcal{R}_{r});$

9: each agent $r\in[R]$ update local slack variable
$\displaystyle(z^{r}_{j})^{t+1}=\frac{-(\lambda^{r}_{j})^{k}-(y^{r}_{j})^{t}-\rho\left((x^{r}_{j})^{t+1}-(\bar{x}_{j})^{t+1}\right)}{\beta^{k}+\rho}$
(18) and dual variable
$\displaystyle(y^{r}_{j})^{t+1}=(y^{r}_{j})^{t}+\rho\left[(x^{r}_{j})^{t+1}-(\bar{x}_{j})^{t+1}+(z^{r}_{j})^{t+1}\right]$
(19) for all $j\in\delta(\mathcal{R}_{r})\cup B(\mathcal{R}_{r})$;

10: $t\leftarrow t+1$;

11: end while

12: denote the solution from the inner loop as $(x^{k},\bar{x}^{k},z^{k})$;

13: each agent $r\in[R]$ updates outer-level dual variable
$(\lambda^{r}_{j})^{k+1}$ for all $j\in\delta(\mathcal{R}_{r})\cup
B(\mathcal{R}_{r})$ and penalty $\beta^{k+1}$;

14: $k\leftarrow k+1$;

15: end while

All agents simultaneously solve lower-dimensional nonconvex subproblems (5) by
some nonlinear optimization solver. Then each agent $r\in[R]$ sends the
current local estimation of voltage $(x^{r}_{j})^{t+1}$ to $R(j)$ for all
neighboring buses $j\in\delta(\mathcal{R}_{r})$. For each bus $j$ connected to
a tie-line, We let agent $R(j)$ collect estimations
$\\{(x^{l}_{j})^{t+1}\\}_{l\in N(j)}$ and update global copy
$(\bar{x}_{j})^{t+1}$, though in practice any agents from $N(j)$ can be
assigned for this task. Notice that the global copy update (17) involves a
projection evaluation, which in general does not admit a closed-form solution;
however, if (10) is used for $\bar{\mathcal{X}}$, then $\bar{x}^{t+1}_{j}$ is
exactly the component-wise projection of the argument in (17) onto the box
$\bar{\mathcal{X}}_{j}$. After agent $R(j)$ broadcasts $(\bar{x}_{j})^{t+1}$
to agents from $N(j)$, all agents are then able to update the slack variable
and dual variables as in (18) and (19). When the inner-level iterates satisfy
certain stopping criteria, all agents will update the outer-level dual
variable $\lambda^{k+1}$ and penalty $\beta^{k+1}$, as in line 13 of Algorithm
1, which we will elaborate in the next section.

##  IV Convergence and Related Issues

In this section, we state the convergence results of the two-level ADMM
framework for AC OPF, and discuss related issues. We require the following
mild assumptions.

######  Assumption 1.

  * (a)

The objective $c_{r}(\cdot)$ is continuous differentiable. The functional
constraints $\mathcal{X}_{r}$’s and $\bar{\mathcal{X}}$ are compact, and
$\bar{\mathcal{X}}$ is convex.

  * (b)

For any $t\in\mathbb{Z}_{++}$, every local agent $r\in[R]$ is able to find a
stationary solution $(x^{r})^{t+1}$ of subproblem (5) such that
$F^{t}_{r}\left((x^{r})^{t+1}\right)\leq F^{t}_{r}\left((x^{r})^{t}\right)$.

For Assumption 1(a), the objective function $c_{r}(\cdot)$ is usually linear
or convex quadratic with respect to the argument; without loss of generality,
we may assume the set $\mathcal{X}_{r}$ defined in (6) also enforces bounds on
local copies $\\{(e^{r}_{j},f^{r}_{j})\\}_{j\in\delta(\mathcal{R}_{r})}$, and
thus $\mathcal{X}_{r}$ is ensured to be compact. The assumption on
$\bar{\mathcal{X}}$ is justified in (10). Assumption 1(b) requires the
nonconvex subproblem (5) to be solved to a stationary solution $(x^{r})^{t+1}$
that has an improved objective value of $F^{t}_{r}$ compared to the previous
iterate $(x^{r})^{t}$. Notice that $(x^{r})^{t}$ is already feasible, i.e.
$(x^{r})^{t}\in\mathcal{X}_{r}$, so we believe this assumption is reasonable
if the nonlinear solver is warm-started. In addition, Assumption 1(b) is
weaker than assuming $(x^{r})^{t+1}$ is a global minimizer of (5), which is
commonly adopted in nonconvex ADMM.

###  IV-A Global Convergence

We consider two different rules for updating $(\lambda^{k+1},\beta^{k+1})$.
Let $c>1$, $\theta\in[0,1)$, and $\\{\eta_{k}\\}_{k}$ be a nonnegative
sequence convergent to 0. Consider

$\displaystyle\lambda^{k+1}=$
$\displaystyle\mathrm{Proj}_{[\underline{\lambda},\overline{\lambda}]}(\lambda^{k}+\beta^{k}z^{k}),$
(20a) $\displaystyle\beta^{k+1}=$
$\displaystyle\begin{cases}\beta^{k}&\text{if\leavevmode\nobreak\
}\|z^{k}\|\leq\theta\|z^{k+1}\|,\\\ c\beta^{k}&\text{otherwise;}\end{cases}$
(20b)

and

$\displaystyle(\lambda^{k+1},\beta^{k+1})=\begin{cases}(\lambda^{k}+\beta^{k}z^{k},\beta^{k})&\text{if\leavevmode\nobreak\
}\|z^{k}\|\leq\eta_{k},\\\
(\lambda^{k},c\beta^{k})&\text{otherwise.}\end{cases}$ (21)

######  Theorem 1 (Global Convergence).

Suppose Assumption 1 holds, and the $k$-th inner-level ADMM is solved to an
$\epsilon_{k}$-stationary point $(x^{k},\bar{x}^{k},z^{k},y^{k})$ of (15) such
that $\epsilon_{k}\rightarrow 0$ as $k\rightarrow+\infty$. Moreover, the
outer-level dual variable $\lambda^{k+1}$ and penalty $\beta^{k+1}$ are
updated according to either (20) or (21). Then the following claims hold.

  1. 1.

The sequence $\\{(x^{k},\bar{x}^{k},z^{k})\\}_{k}$ is bounded, and therefore
there exists at least one limit point $(x^{*},\bar{x}^{*},z^{*})$, where
$x^{*}\in\mathcal{X}=\prod_{r=1}^{R}\mathcal{X}_{r}$ and
$\bar{x}^{*}\in\bar{X}$.

  2. 2.

Either $(x^{*},\bar{x}^{*})$ is feasible, i.e., $Ax^{*}+B\bar{x}^{*}=0$, or
$(x^{*},\bar{x}^{*})$ is a stationary point of the feasibility problem

$\displaystyle\min_{x,\bar{x}}\leavevmode\nobreak\
\frac{1}{2}\|Ax+B\bar{x}\|^{2}\leavevmode\nobreak\
\mathrm{s.t.}\leavevmode\nobreak\
x\in\mathcal{X},\bar{x}\in\bar{\mathcal{X}}.$ (22)

  3. 3.

Suppose problem (9) is feasible and the set of stationary points is nonempty.
Let $(x^{*},\bar{x}^{*},z^{*})$ be a limit point, and
$\\{(x^{k_{r}},\bar{x}^{k_{r}},z^{k_{r}})\\}_{r}$ be the subsequence
convergent to it. If $\\{y^{k_{r}}\\}_{r}$ has a limit point $y^{*}$, then
$(x^{*},\bar{x}^{*},y^{*})$ is a stationary point of problem (9).

We note that in part 3 of Theorem 1, we make the assumption that the dual
variable $\\{y^{k_{r}}\\}_{r}$ has a limit point. This is a standard
sequentially bounded constraint qualification (SBQC) [luo1996exact]. Proof of
Theorem 1 can be found in [appendix].

###  IV-B Iteration Complexity

######  Theorem 2 (Iteration Complexity).

Suppose Assumption 1 holds, and there exists $0<\bar{L}<+\infty$ such that

$\displaystyle\overline{L}\geq$
$\displaystyle\sum_{r=1}^{R}c_{r}((x^{r})^{0})+\langle\lambda^{k},z^{0}\rangle+\frac{\beta^{k}}{2}\|z^{0}\|^{2}$
$\displaystyle+\langle
y^{0},Ax^{0}+B\bar{x}^{0}+z^{0}\rangle+\frac{\rho}{2}\|Ax^{0}+B\bar{x}^{0}+z^{0}\|^{2}$
(23)

for all $k\in\mathbb{Z}_{++}$. Further assume each inner-level ADMM is solved
to an $\epsilon$-stationary point $(x^{k},\bar{x}^{k},z^{k},y^{k})$ of (15),
and $\beta^{k}=c^{k}\beta^{0}$ for some $c>1$, $\beta^{0}>0$. Define

  * •

$\tau=\max\\{\|A\|,\|B\|,\frac{1}{4\beta^{0}}\\}$,

  * •

$M=\max_{\lambda\in[\underline{\lambda},\overline{\lambda}]}\|\lambda\|$,

  * •

$\underline{L}=\min_{x\in\mathcal{X}}c(x)-M^{2}/\beta^{0}$,

  * •

$r_{\max}=\max_{x\in\mathcal{X},\bar{x}\in\bar{\mathcal{X}}}\|Ax+B\bar{x}\|$
(since $\mathcal{X},\bar{\mathcal{X}}$ compact),

  * •

and for $K\in\mathbb{Z}_{++}$,

$T(K)=\left\lceil\left(\frac{8\beta^{0}(\overline{L}-\underline{L})\tau^{2}c}{c-1}\right)\left(\frac{c^{K}-1}{\epsilon^{2}}\right)\right\rceil+K.$

Then Algorithm 1 finds an $\epsilon$-stationary solution of problem (9) in no
more than

$K_{1}=\left\lceil\log_{c}\left(\frac{2(\overline{L}-\underline{L}+Mr_{\max})}{\beta^{0}\epsilon^{2}}\right)\right\rceil$

outer ALM iterations and $T(K_{1})=\mathcal{O}(1/\epsilon^{4})$ inner ADMM
iterations. Moreover, if $\|\lambda^{k}+\beta^{k}z^{k}\|\leq\Lambda$ for all
outer index $k$, then Algorithm 1 finds an $\epsilon$-stationary solution of
problem (9) in no more than

$K_{2}=\max\Bigg{\\{}\left\lceil\log_{c}\left(\frac{1}{2\beta^{0}\tau}\right)\right\rceil,\left\lceil\log_{c}\left(\frac{2(\Lambda+M)}{\beta^{0}\epsilon}\right)\right\rceil\Bigg{\\}}$

outer ALM iterations and $T(K_{2})=\mathcal{O}(1/\epsilon^{3})$ inner ADMM
iterations.

The proof of Theorem 2 can be found in [appendix]. We make some remarks.

  1. 1.

The assumption (2) can be satisfied trivially, for example, if a feasible
solution $(x^{0},\bar{x}^{0})$ for (9) is known a priori and
$(x^{0},\bar{x}^{0},z^{0}=0)$ is always used to start inner ADMM. In this
case, we can choose $\overline{L}=\max_{x\in\mathcal{X}}c(x)$.

  2. 2.

In view of (8), we can calculate $\|A\|$ and $\|B\|$ directly. Each row of $A$
has exactly one non-zero entry, and each column of $A$ has at most one non-
zero entry, so $A^{\top}A$ is a diagonal matrix with either 0 or 1 on the
diagonal, and thus $\|A\|=1$. The number of non-zero entries in each column of
$B$ specifies how many subregions keep a local copy of this global variable,
so $B^{\top}B$ is also a diagonal matrix, and we have

${\|B\|=\left(\max_{j\in\cup_{r=1}^{R}B(\mathcal{R}_{r})}|N(j)|+1\right)^{1/2}\leq\sqrt{R}.}$

  3. 3.

The complexity results suggest that a smaller $M$ is preferred, and $M=0$
corresponds to the penalty method. However, we empirically observe that a
relatively large range for $\lambda$ usually results in faster convergence,
which is also better than the $\mathcal{O}(1/\epsilon^{3})$ or
$\mathcal{O}(1/\epsilon^{4})$ iteration upper bound. We believe such phenomena
can be explained by the local convergence properties of ALM.

##  V Numerical Experiments

In this section, we demonstrate the performance of the proposed algorithmic
framework. All codes are written in the Julia programming language 1.2.0, and
implemented on a Red Hat Enterprise Linux Server 7.6 with 85 Intel 2.10GHz
CPUs. All nonlinear constrained problems are modeled using the JuMP
optimization package [DunningHuchetteLubin2017] and solved by IPOPT
[wachter2006implementation] with linear solver MA57.

###  V-A Network Information and Partition Generation

We experimented on the two largest networks from NESTA, namely,
nesta_case9241pegase (“9K”) and nesta_case13659pegase (“13K”). The centralized
information are given in Tabel I. We generate different partitions using the
multilevel k-way partitioning algorithm [karypis1998multilevelk] on the
underlying graph, which is available from Metis.jl, the Julia wrapper of the
Metis library. Each test case is partitioned into $R$ subregions, where $R$
ranges from 25 to 70 with an interval length of 5.

Table I: Centralized Information Case | AC Obj. | AC Time(s) | SOCP Obj. | SOCP Time(s) | Gap (%)
---|---|---|---|---|---
9K | 315913.26 | 51.13 | 310382.99 | 1224.81 | 1.76
13K | 386117.10 | 160.10 | 380262.34 | 990.50 | 1.51
Table II: Performance of the Two-level ADMM Algorithm wih Heuristics |  |  | TL-1 | TL-2 | TL-3
---|---|---|---|---|---
Case | Tie-line | Dim | Outer | Inner | Gap (%) | $\|r\|_{\infty}$ | Outer | Inner | Gap (%) | $\|r\|_{\infty}$ | Outer | Inner | Gap (%) | $\|r\|_{\infty}$
9K-25 | 357 | 2084 | 88 | 317 | 1.96 | 2.97E-03 | 237 | 270 | 1.97 | 2.89E-03 | 246 | 261 | 1.95 | 2.91E-03
9K-30 | 412 | 2478 | 58 | 189 | 1.51 | 3.20E-03 | 139 | 173 | 1.65 | 3.49E-03 | 148 | 163 | 1.62 | 3.50E-03
9K-35 | 518 | 2984 | 46 | 112 | 1.00 | 2.64E-03 | 82 | 115 | 1.07 | 2.63E-03 | 87 | 101 | 1.10 | 2.72E-03
9K-40 | 514 | 3108 | 57 | 186 | 0.54 | 3.91E-03 | 118 | 151 | 0.58 | 3.82E-03 | 126 | 140 | 0.57 | 3.69E-03
9K-45 | 603 | 3538 | 39 | 89 | 0.17 | 2.13E-03 | 62 | 91 | 0.34 | 2.18E-03 | 66 | 80 | 0.28 | 2.23E-03
9K-50 | 676 | 3808 | 40 | 92 | -0.18 | 2.57E-03 | 63 | 90 | -0.11 | 2.62E-03 | 67 | 81 | -0.11 | 2.62E-03
9K-55 | 651 | 3776 | 59 | 181 | 0.47 | 4.38E-03 | 127 | 161 | 0.49 | 4.28E-03 | 133 | 148 | 0.47 | 4.19E-03
9K-60 | 693 | 4080 | 49 | 120 | 0.00 | 3.73E-03 | 85 | 118 | -0.02 | 3.75E-03 | 90 | 104 | -0.06 | 3.63E-03
9K-65 | 741 | 4292 | 55 | 137 | 0.07 | 2.94E-03 | 106 | 140 | 0.20 | 3.11E-03 | 112 | 126 | 0.20 | 3.10E-03
9K-70 | 764 | 4430 | 38 | 86 | -0.33 | 2.26E-03 | 63 | 87 | -0.24 | 2.34E-03 | 65 | 80 | -0.30 | 2.29E-03
13K-25 | 371 | 2234 | 32 | 69 | 1.52 | 3.51E-03 | 47 | 73 | 1.58 | 3.38E-03 | 49 | 63 | 1.55 | 3.43E-03
13K-30 | 452 | 2536 | 28 | 57 | 1.30 | 2.26E-03 | 38 | 60 | 1.33 | 2.36E-03 | 39 | 53 | 1.33 | 2.45E-03
13K-35 | 482 | 2846 | 32 | 67 | 0.74 | 3.37E-03 | 45 | 67 | 0.77 | 3.45E-03 | 48 | 62 | 0.78 | 3.44E-03
13K-40 | 533 | 3066 | 25 | 48 | 1.20 | 2.73E-03 | 34 | 54 | 1.30 | 2.73E-03 | 35 | 48 | 1.28 | 2.69E-03
13K-45 | 655 | 3768 | 31 | 64 | 1.19 | 4.05E-03 | 43 | 66 | 1.28 | 4.07E-03 | 46 | 60 | 1.27 | 4.05E-03
13K-50 | 618 | 3692 | 25 | 48 | 0.53 | 2.82E-03 | 33 | 56 | 0.60 | 3.03E-03 | 35 | 49 | 0.59 | 3.15E-03
13K-55 | 721 | 4246 | 25 | 46 | 0.62 | 3.98E-03 | 31 | 53 | 0.64 | 4.01E-03 | 33 | 47 | 0.65 | 4.00E-03
13K-60 | 717 | 4176 | 22 | 40 | 1.04 | 2.42E-03 | 27 | 47 | 1.07 | 2.46E-03 | 27 | 41 | 1.07 | 2.44E-03
13K-65 | 736 | 4258 | 21 | 38 | 0.81 | 2.11E-03 | 26 | 44 | 0.82 | 2.18E-03 | 26 | 40 | 0.83 | 2.23E-03
13K-70 | 843 | 4784 | 25 | 47 | 1.19 | 4.24E-03 | 32 | 56 | 1.25 | 4.16E-03 | 29 | 53 | 1.22 | 4.21E-03
We use “9K-$R$” to denote the nesta_case9241_pegase with $R$ partitions, and
similar for nesta_case13659_pegase.

###  V-B Three Acceleration Heuristics

It is known that the choice of penalty parameter $\rho$ significantly affects
the convergence of ADMM and can potentially accelerate the algorithm
[mhanna_adaptive_2019]. Indeed, we observed that for some large cases, the
inner-level ADMM may suffer from slow convergence to high accuracy when a
constant penalty penalty $\rho$ is used. As a result, given parameters
$\theta\in[0,1)$ and $\gamma>1$, we propose three different heuristics to
properly accelerate Algorithm 1.

  1. 1.

Adaptive ADMM penalty: the inner-level ADMM penalty is indexed as $\rho^{t}$
and updated as follows: $\rho^{t+1}=\gamma\rho^{t}$ if
$\|Ax^{t+1}+B\bar{x}^{t+1}+z^{t+1}\|>\theta\|Ax^{t}+B\bar{x}^{t}+z^{t}\|$, and
$\rho^{t+1}=\rho^{t}$ otherwise; in words, we increase the ADMM penalty if the
three-block residual $\|Ax^{t+1}+B\bar{x}^{t+1}+z^{t+1}\|$ does not decrease
sufficiently.

  2. 2.

Different ADMM penalties: we assign a different ADMM penalty for each row of
the coupling constraint $Ax+B\bar{x}+z=0$, and each penalty is updated
according to the first heuristic, where the violation of each single
constraint is measured, and the corresponding penalty is adjusted. Notice the
ALM penalty $\beta$ is a fixed constant for all components of $z$ during the
inner ADMM.

  3. 3.

Different ALM penalties: we assign a different ALM penalty $\beta^{t}_{i}$ for
each component $z_{i}$ of the slack variable, and also update it inside ADMM
iterations: $\beta_{i}^{t+1}=\gamma\beta_{i}^{t}$ if
$|z_{i}^{t+1}|>\theta|z_{i}^{t}|$, and $\beta_{i}^{t+1}=\beta_{i}^{t}$
otherwise; the corresponding ADMM penalty $\rho^{t}_{i}$ is always assigned to
be $2\beta^{t}_{i}$, as required in our analysis. When the $k$-th ADMM
terminates, current values of $z_{i}^{k}$ and $\beta_{i}^{k}$ are used to
update outer level dual variable $\lambda_{i}^{k+1}$.

We note that the first two heuristics have been used to accelerate ADMM, while
the last heuristic also penalizes the slack variable $z$ adaptively in ADMM
iterations.

###  V-C Implementation Details

#### Parallelization of nonconvex subproblems

Each JuMP model carrying a subregion’s localized OPF constraints is
initialized on a worker thread. During each (inner) iteration, these models
are solved in parallel on worker threads by IPOPT, which consist of the major
computation of the algorithm. Then current local solutions are gathered
through the master thread, and auxiliary primal variables and dual variables
in different subregions are updated in closed form.

#### Parameters and Initialization

For the heuristics introduced in the previous subsection, we set $\gamma=6.0$,
$\theta=0.8$; for the first two heuristics, when ADMM terminates, the outer-
level penalty is updated as $\beta^{k+1}=c\beta^{k}$ where $c=6.0$. The
initial value $\beta^{0}$ is set to 1000.0, and an upper bound of $1.0e24$ is
imposed in all penalty updates. Each component of $\lambda$ is bounded between
$\pm 1.0e12$. Flat start is used to initialize IPOPT: we choose
$(e_{i},f_{i},p^{g}_{i},q_{i}^{g})=(1,0,0,0)$ for all $i\in\mathcal{N}$. Dual
variables $y^{0}$ and $\lambda^{0}$ are initialized with zeros.

#### Scaling of IPOPT

The proposed algorithm inevitably needs to deal with potentially large
penalties and dual variables, and we observe that IPOPT will encounter
numerical failures or produce oscillating solutions. To overcome this problem,
we manually scale the objective of the each JuMP model so that the largest
coefficient passed to the solver is in the order of $1.0e+8$. This trick helps
IPOPT output stable solutions efficiently without running into numerical
troubles.

#### Termination of Inner and Outer Iterations

We stop the inner-level ADMM if: (1)
$\|Ax^{k}+B\bar{x}^{t}+z^{t}\|\leq\sqrt{d}/(2500k)$ where $d$ is the dimension
of the coupling constraint and $k$ is the current outer-level iteration index,
or (2) $\|z^{t}-z^{t-1}\|\leq 1.0e-8$. The first condition ensures the ADMM
primal residual is under certain tolerance, which also tends to 0 as
$k\rightarrow\infty$. The second condition measures the dual residual of the
last block in (15); if this quantity is small, then we believe $z^{t}$ has
stabilized in the current inner iteration, which encourages us to terminate
ADMM early and proceed to update outer-level dual variable. The outer level is
terminated if the two-block residual satisfies
$\|Ax^{k}+B\bar{x}^{k}\|\leq\sqrt{d}2.0e-4$, which measures the infeasibility
of the original OPF problem.

###  V-D Numerical Performance

The results are displayed in Table II. We use “TL-1”, “TL-2”, and “TL-3” to
denote the two-level ADMM algorithm combined with the three heuristics
mentioned in the previous section. The total number of tie-lines and the
dimension of the coupling constraints of each case are recorded in the second
and third columns. For each heuristic, we report the number of outer
iterations (“Outer”), number of inner iterations (“Inner”), duality gap with
SOCP lower bound (“Gap (%)”), and max violation of the coupling at termination
(“$\|r\|_{\infty}$”). The three algorithms reach the desired infeasibility
tolerance in all test instances, and the max constraint violation is in the
order of $10^{-3}$. Overall the generation costs at termination are very close
to the SOCP lower bound, indicating the algorithms converge to solutions with
high qualities. Moreover, we emphasize the scalability of the algorithm by
pointing out that, the number of inner and outer iterations are stable across
instances, even though the dimension of the coupling ranges from 2000 to near
5000.

Figure 2: Average Time v.s. Number of Partitions

We plot the averaged computation time for the proposed algorithm combined with
three heuristics in Fig. 2 (left). During our experiments shown in Table II,
the number of partitions is equal to the number of threads used for
parallelization, so that each IPOPT model is assigned to a worker thread. The
computation time drops significantly and becomes comparable to the centralized
solver as the number of partitions increases: 735.50 to 97.04 seconds for
9K-bus system, and 1513.66 to 167.57 seconds for 13K-bus system. This is due
to the OPF problem is decomposed into lower-dimensional subproblems, which are
effectively solved on different threads in parallel. We further partition the
networks into 80, 120, 160, 200, and 240 partitions, and investigate the
average subproblem time in Fig. 2 (right). For the 9K-bus system, the averaged
subproblem solution time drops from 2.61 to 1.15 seconds, while for the
13K-bus system, this metric drops more significantly from 22.13 to 0.7
seconds. Our results validate the feasibility of using parallelization to
speed up computation.

###  V-E Comparison with One-level ADMM Variants

To further illustrate the advantage of the proposed two-level ADMM algorithm,
we implement two state-of-the-art one-level ADMM variants and display their
results in Table III.

Table III: Comparison with One-level ADMM Variants |  Modified ADMM[erseghe2015distributed] |  ADMM-g [jiang2019structured] | Proposed TL-1
---|---|---|---
Case | Gap(%) | Time (s) | Gap(%) | Time (s) | Gap(%) | Time (s)
13K-25 | 88.98 | 2869.48 | -6.14 | 1946.21 | 1.52 | 1788.62
13K-30 | 90.64 | 2507.26 | -6.21 | 1874.13 | 1.30 | 680.16
13K-35 | 91.86 | 2034.09 | -6.97 | 1510.31 | 0.74 | 752.41
13K-40 | 92.79 | 2168.87 | -8.09 | 1555.16 | 1.20 | 430.68
13K-45 | 93.54 | 1428.20 | -8.06 | 1436.43 | 1.19 | 306.79
13K-50 | 94.15 | 1463.57 | -8.44 | 1405.47 | 0.53 | 374.15
13K-55 | 94.65 | 1521.64 | -12.59 | 1370.72 | 0.62 | 204.50
13K-60 | 95.09 | 1459.83 | -8.26 | 1208.48 | 1.04 | 157.32
13K-65 | 95.44 | 1910.87 | -9.16 | 1279.62 | 0.81 | 207.58
13K-70 | 95.75 | 1821.54 | -12.20 | 1340.73 | 1.19 | 160.20

All implementation issues mentioned above are considered; however, for all
cases, both one-level ADMM algorithms fail to achieve the desired
infeasibility tolerance within 1000 iterations. For the modified ADMM
[erseghe2015distributed], the penalty parameter quickly reaches the upper
bound $10^{24}$, which indicates their assumption for convergence is not
satisfied, and such large penalty leads to solutions with high generation
costs. Jiang et al. [jiang2019structured] realize that ADMM can be used to
solve the relaxed problem (15) with $\lambda^{k}=0$ and large enough constant
$\beta$. When $\beta=\mathcal{O}(1/\epsilon^{2})$, their proposed ADMM variant
is guaranteed to find an $\epsilon$-stationary solution of the original
problem. Using parameters suggested in their analysis, we observe that the
true infeasibility $\|Ax^{t}+B\bar{x}^{t}\|$ decreases very slowly, though the
three-block residual $\|Ax^{t}+B\bar{x}^{t}+z^{t}\|$ converges to near 0 fast.
This indicates the need for a more careful tuning of the penalty $\beta$, but
there is no principled way to select all hyperparameters in their algorithm
for OPF instances.

##  VI Conclusion

In this paper we propose a two-level distributed ADMM framework for solving AC
OPF. Instead of relying on parameter tuning to exhibit convergence behaviour,
the proposed algorithm is proven to have guaranteed global convergence.
Iteration complexity bound is also obtained, and can be further accelerated by
suitable heuristics. Promising numerical results over some large-scale test
cases show that the proposed algorithm provides a new, robust distributed, and
convergence-guaranteed algorithmic framework for solving real-world sized AC
OPF problems.

## Appendix

###  VI-A Proof of Theorem 1

###### Proof.

The claims under condition (20) are proved in Theorem 1-2 of [sun2019two]. We
shall prove the claims under condition (21).

  1. 1.

The first claim follows from the compactness of $\mathcal{X}_{r}$’s and
$\bar{\mathcal{X}}$ and the fact that
$\|Ax^{k}+B\bar{x}^{k}+z^{k}\|\rightarrow 0$.

  2. 2.

First we assume the sequence $\\{\beta^{k}\\}_{k}$ stays finite. Then there
exists $K>0$ such that $\eta_{k}\geq\|z^{k}\|$ for all $k\geq K$, which
follows $\|z^{k}\|\rightarrow 0$. Next assume $\beta^{k}\rightarrow+\infty$,
and assume without loss of generality that
$(x^{k},\bar{x}^{k},z^{k})\rightarrow(x^{*},\bar{x}^{*},z^{*})$. If the first
case in (21) is executed infinitely many times, we have $\|z^{k}\|\rightarrow
0$; otherwise we must have $\|\lambda^{k}\|$ stays constant for all
sufficiently large $k$. Define
$\tilde{\lambda}^{k}:=\lambda^{k}+\beta^{k}z^{k}=-y^{k}$. If
$\\{\tilde{\lambda}^{k}\\}$ has a bounded subsequence, then we have
$\|z^{k}\|\rightarrow 0$ as $\beta^{k}$ converges to infinity. In all the
previous cases, we have
$\|Ax^{k}+B\bar{x}^{k}\|\leq\|Ax^{k}+B\bar{x}^{k}+z^{k}\|+\|z^{k}\|\leq\epsilon_{k}+\|z^{k}\|\rightarrow
0$, and thus $\|Ax^{*}+B\bar{x}^{*}\|=0$. In the last case we have
$\beta^{k}\rightarrow\infty$, $\|\lambda^{k}\|$ stays bounded, and
$\|\tilde{\lambda}^{k}\|\rightarrow\infty$. By the definition of
$\tilde{\lambda}^{k}$, we can see
$y^{k}/\beta^{k}\rightarrow-z^{*}=Ax^{*}+B\bar{x}^{*}$. At termination of
ADMM, we have

$\displaystyle d_{1}^{k}$ $\displaystyle\in\nabla
c(x^{k})+A^{\top}y^{k}+N_{\mathcal{X}}(x^{k})$ (24a) $\displaystyle d_{2}^{k}$
$\displaystyle\in B^{\top}y^{k}+N_{\bar{\mathcal{X}}}(\bar{x}^{k})$ (24b)
$\displaystyle d_{3}^{k}$ $\displaystyle=Ax^{k}+B\bar{x}^{k}+z^{k},$ (24c)

where
$\max\\{\|d_{1}^{k}\|,\|d_{2}^{k}\|,\|d_{3}^{k}\|\\}\leq\epsilon_{k}\rightarrow
0$. By the closeness of normal cone, dividing vectors in (24a)-(24b) by
$\beta^{k}$, and then taking limit, we have $0\in
A^{\top}(Ax^{*}+B\bar{x}^{*})+N_{\mathcal{X}}(x^{*})$ and $0\in
B^{\top}(Ax^{*}+B\bar{x}^{*})+N_{\bar{\mathcal{X}}}(\bar{x}^{*})$, which imply
$(x^{*},\bar{x}^{*})$ is stationary for (22).

  3. 3.

Using the same case analysis as in Part (2), we can see $\|z^{k}\|\rightarrow
0$ (along the subsequence converging to $z^{*}$). Thus taking limit on (24)
completes the proof.

∎

###  VI-B Proof of Theorem 2

###### Proof.

We use $T_{k}$ to denote the number of inner iterations of the $k$-th ADMM,
which produces a $\epsilon$-stationary solution point of (15). By Lemma 3 of
[sun2019two], we can find $(x^{k},\bar{x}^{k},z^{k},y^{k})$ and corresponding
$(d_{1}^{k},d_{2}^{k},d_{3}^{k})$ (see Definition 2) such that

$\max\\{\|d_{1}^{k}\|,\|d_{2}^{k}\|,\|d_{3}^{k}\|\\}\leq\rho^{k}\tau\left(\frac{2(\overline{L}-\underline{L})}{\beta^{k}T_{k}}\right)^{1/2}.$

Recall $\rho^{k}=2\beta^{k}=2\beta^{0}c^{k}$; it is sufficient to find a
$T_{k}$ with

$T_{k}\leq\frac{8\beta^{0}(\overline{L}-\underline{L})\tau^{2}c^{k}}{\epsilon^{2}}+1$

in order to get
$\max\\{\|d_{1}^{k}\|,\|d_{2}^{k}\|,\|d_{3}^{k}\|\\}\leq\epsilon$. Let $K$
denote the number of outer-level ALM iterations. Then the total number of
inner iterations is bounded by

$\sum_{k=1}^{K}T_{k}\leq\left\lceil\left(\frac{8\beta^{0}(\overline{L}-\underline{L})\tau^{2}c}{c-1}\right)\left(\frac{c^{K}-1}{\epsilon^{2}}\right)\right\rceil+K.$

Now it remains to bound the number of outer-level iterations $K$. Notice that
the dual residuals are controlled by $\epsilon$ at the end of each inner-level
ADMM, so it is sufficient to ensure $\|Ax^{K}+B\bar{x}^{K}\|\leq\epsilon$. By
Theorem 3 of [sun2019two],

$\displaystyle\|Ax^{K}+Bx^{K}\|^{2}\leq\frac{2(\overline{L}-c(x^{K})+\langle\lambda^{k},Ax^{K}+Bx^{K}\rangle)}{\beta^{K}},$

and the claimed $K_{1}$ is sufficient to ensure
$\|Ax^{K_{1}}+Bx^{K_{2}}\|\leq\epsilon$. Furthermore, if
$\|\lambda^{k}+\beta^{k}z^{k}\|\leq\Lambda$ for all outer index $k$, then we
have

$\|z^{K}\|=\frac{\|\lambda^{K}+\beta^{K}z^{K}-\lambda^{K}\|}{\beta^{K}}\leq\frac{\Lambda+M}{\beta^{0}c^{K}}.$

Again by Lemma 3 of [sun2019two], we have

$\|Ax^{K}+B\bar{x}^{K}+z^{K}\|\leq\frac{1}{2}\left(\frac{2(\overline{L}-\underline{L})}{\beta^{K}T_{K}}\right)^{1/2}\leq\frac{\epsilon}{4\beta^{0}c^{K}\tau}$

where the last inequality is due to the choice of $T_{K}$. It is
straightforward to verify that the claimed $K_{2}$ ensures

$\displaystyle\|Ax^{K_{2}}+B\bar{x}^{K_{2}}\|\leq$
$\displaystyle\|Ax^{K_{2}}+B\bar{x}^{K_{2}}+z^{K_{2}}\|+\|z^{K_{2}}\|$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$

This completes the proof. ∎


# Enhancing Portuguese Sign Language Animation with Dynamic Timing and
Mouthing

Inês Lacerda  Instituto Superior Técnico, Universidade de Lisboa  INESC-ID
Hugo Nicolau  Instituto Superior Técnico, Universidade de Lisboa  Interactive
Technologies Institute / LARSYS  Luísa Coheur  Instituto Superior Técnico,
Universidade de Lisboa  INESC-ID

###### Abstract

Current signing avatars are often described as unnatural as they cannot
accurately reproduce all the subtleties of synchronized body behaviors of a
human signer. In this paper, we propose a new dynamic approach for transitions
between signs, focusing on mouthing animations for Portuguese Sign Language.
Although native signers preferred animations with dynamic transitions, we did
not find significant differences in comprehension and perceived naturalness
scores. On the other hand, we show that including mouthing behaviors improved
comprehension and perceived naturalness for novice sign language learners.
Results have implications in computational linguistics, human-computer
interaction, and synthetic animation of signing avatars.

##  1 Introduction

Spoken/written language and sign language are different: one is an audio-oral
language while the other is a spatial-visual language. Vocabulary and
grammatical rules are also quite different. These differences lead to a
language barrier between Deaf111Deaf with a capital refers to people who
identify with the deaf culture and have been deaf before they started to learn
a language. They are pre-lingually deaf. and hearing people. In this paper, we
contribute to breaking down the language barrier between European Portuguese
and Portuguese Sign Language (LGP).

Sign language translators typically require two components: a language
translator and a signing avatar. The translator converts written text (or
speech) into a sequence of glosses (i.e., lexical units representing each
gesture or sign); then, the avatar displays the synthesized glosses and
additional linguistic components as signing animations. Signing avatars must
account not only for multiple co-occurring linguistic processes but also for
the naturalness of the movements. However, most avatars are described as
unnatural, emotionless, and stiff Kipp et al. (2011) because they cannot
accurately reproduce a human signer’s subtleties. Therefore, one of the goals
of an automatic sign language translator is to perform secondary movements
based on human kinematics, so that animations are understandable and perceived
as natural.

Planning and scripting a signing avatar’s facial and body movements is
difficult. Minor variations in timing and speed parameters can lead to
significant differences in the quality and understandability of sign
animations Huenerfauth (2009); Al-khazraji et al. (2018). In the case of sign
languages, transitions between signs rely heavily on the phonology of the
previous and following signs and determine the movement fluidity that allows
sign streams to be intelligible. Therefore, transitions can impact the
comprehension and naturalness of sign animations. In this paper, we introduce
a new approach for interpolating signs, dynamic transitions, which change
according to the previous and following signs. We aimed to answer the
following research question:

RQ1: Do dynamic transitions improve linguistic comprehension, naturalness, and
preference of sign Language animations?

We conducted a user study with 11 native speakers to understand the effect of
dynamic transitions and optional transition speed. Overall, results show that
dynamic transitions are equivalent to constant transitions in each of the
former dimensions (comprehension, naturalness and preference). However,
dynamic transitions enhance linguistic comprehension for signs that comprise
one sole meaning (i.e., composite utterances and negatives) and require faster
transitions.

In addition to transitions between signs, the avatar’s secondary movements –
those that are added to improve the naturalness of the avatar and are not part
of the morphosyntactic structure of sign languages – can also greatly impact
the signing quality and the way the thought or feeling is conveyed. Secondary
movements include eye blink, mouthing, and facial and corporal movements. In
this paper, we study the effect of adding mouthing – the production of visual
morphemes or syllables that derive from spoken language (Figure 1) – to an
existing avatar.

Figure 1: Avatar with (left) and without mouthing (right).

Some believe that mouthing is incorporated into the morphosyntactic structures
of sign languages, and some believe they are not Crasborn et al. (2008); Wolfe
et al. (2018b). Nevertheless, it is interesting that mouthing can be combined
with manual signs to create complex signs with a composite meaning. For
example, the manual sign “mouse” in British Sign Language (BSL) can be
accompanied by the mouth action “baby”, forming the composite meaning “baby
mouse” Crasborn et al. (2008). Notice that mouthing should only be reproduced
when there are no phonological facial expressions that contain the mouth
(e.g., cheeks puffed, tongue touching the chin, morphemes). Thus, our second
research question was:

RQ2: Does mouthing impact linguistic comprehension, naturalness, and
preference of sign language animations?

Results show that the avatar with mouthing achieves better results in terms of
comprehension, naturalness, and preference. To the best of our knowledge,
research in the field has not yet been published on whether mouthing can
improve comprehension; therefore, this user study can give valuable input into
this topic.

The paper is organized as follows: in Section 2 we present related work, in
Section 3 we present our models and in Section 4 we evaluate them. Then, in
Section 5, we present the main conclusions and future work.

##  2 State of the Art

Research regarding hand signs and facial expressions in Sign Language
animations is scarce, and in a synthetic context, the blending of the two is
still an open challenge. Existing solutions rely on Sign Language Annotations
Elliott et al. (2000), Keyframe Animations Adamo-Villani (2008), and Motion
Capture methods Gibet et al. (2011). Each approach provides advantages and
disadvantages but all require a balance between quality and cost. The more
accurate and natural the animations are, the more costly they are to be
generated.

Some work regarding modeling timing and pausing parameters for manual
components has been done for American Sign Language (ASL) Huenerfauth (2009);
Al-khazraji et al. (2018). However, to the best of our knowledge, no study
proposes any kind of dynamic transition that rely on the phonology of the
previous and following signs for sign language animations.

Prior research has been dedicated to mouthing. Mouthing or lip-sync appeared
first in the 1920s with the advent of sound cartoons Wolfe et al. (2018a).
Speech can be discretized as a sequence of sounds known as phonemes. Each
phoneme is associated with a facial pose; however, not all vocal articulations
are visible, and some are irrelevant in the visual domain. For instance,
nasality and voicing Serra et al. (2012b). Phonemes usually have many-to-one
relationships with visemes (i.e., facial and oral poses of phonemes) because
different phonemes can have the same facial pose. It is also important to note
that visual speech cannot be directly generated by concatenating visemes
because it will over-articulate the produced animation.

Mouthing animations can be produced manually or automatically Wolfe et al.
(2018b). A manual approach requires animators to draw each viseme by hand and
later use an interpolation scheme that concatenates the visemes according to
the animated utterances. This method is time-consuming since it requires
animators to manually select the viseme and its timing. These limitations led
to the development of automatic techniques that synchronize audio with
visemes. In automation approaches, visemes are collections of 3D data and
artists can rely on muscle-based systems or blend shapes expressed as polygon
meshes to model avatars’ lip positions to depict visemes.

Automated techniques depend on the source of dialog to generate animation. If
it is a pre-recorded voice track, a speech recognition system can be used;
otherwise, if it is a text containing a dialog, a text-to-speech system must
be used. Both techniques require the same process: detecting the phonemes and
then selecting the corresponding visemes that can be interpolated between
keyframes in the avatar. No matter the technique, the best mapping between
phonemes and visemes is still a debatable issue. Many studies have been
developed to understand the best Phoneme-Viseme mappings. The work presented
in Bear et al. (2014) examined 120 mappings and analyzed their effect on
visual lip reading using hidden Markov model (HMM) recognizers. Although
phoneme-viseme mappings are not universal among languages or within a
language, some phoneme-viseme mappings have overlapping sets. For instance,
similarly to English, Amazon Polly’s Phoneme-Viseme
mapping222https://docs.aws.amazon.com/polly/latest/dg/ph-table-portuguese.html
for European Portuguese also contains the viseme [/p/ /b/ /m/] as a set, even
though these are two different languages.

Some projects have been exploring the possibility of incorporating mouthings
in Sign Language animations. The ViSiCAST project Elliott et al. (2000)
developed the Signing Gesture Markup Language, which is an XML-compliant
representation of signs based on HamNoSys333http://www.sign-lang.uni-
hamburg.de/dgs-korpus/index.php/hamnosys-97.html. In this project, phonemes
are described based on the International Phonetic Alphabet (IPA) transcription
and then visemes are mapped using the Speech Assessment Methods Phonetic
Alphabet (SAMPA) encoding conventions Glauert et al. (2004). Some work in the
area of visual speech animation has been done for ASL and Swiss German Sign
Language Wolfe et al. (2018b).

The work described in Serra et al. (2012a) is the first automatic visual
speech system for European Portuguese (EP) based on viseme concatenations.
This project used two phoneme-viseme mappings: one mapping with 14 different
viseme classes and another mapping with 10 different viseme classes. Both
Phoneme-Viseme mappings resulted in slightly different vowel classifications,
but the number of vocalic viseme classes remained unchanged. Each viseme class
was then created in the avatar by an experienced digital artist. After
creating the mappings and the visemes, the system was divided into two main
components: a speech processing component and a 3D animation engine. The
speech process component processed the data (e.g., text, audio, or both) and
obtained the phonetic transcriptions using an EP phonetic lexicon developed by
Microsoft together with Microsoft Speech API
(SAPI)444https://docs.microsoft.com/en-us/previous-
versions/windows/desktop/ms723627(v=vs.85) as an automatic speech recognition
(ASR) model. The SAPI system used recognition events to detect the different
utterances from the audio and stored a list of words and their corresponding
IPA formats. The SAPI does not provide the phonemes’ duration and timing,
therefore, the EP phonemes’ duration was gathered from a database of 100 hours
of Portuguese speech provided by Microsoft. The 3D animation engine
encapsulated the data obtained from the speech process component and
translated it into the 3D animation. The cartoon character relied on a bone-
based rig, and each viseme was interpolated using the timing obtained by the
speech process component and the animation curves defined by the animator.

Figure 2: Overall architecture of the text-to-sign translator.

Finally, we highlight the work developed in Crasborn et al. (2008), where the
authors studied the mouth actions from a cross-linguistic perspective for
three European Sign Languages: Sign Language of the Netherlands (NGT), British
Sign Language (BSL), and Swedish Sign Language (SSL). Considering all the
possible mouth action, the authors concluded that mouthing is the mouth action
with the highest values, almost in all three languages (57% in SSL, 51% in
BSL, and 39% in NGT). In this study, the authors also confirmed the hypothesis
that mouthings spread analogously to “native” mouth gestures; thus, mouthings
have indeed a grammatical function in sign languages. Based on all results
gathered from the study, mouthing occurs for all three sign languages, and
without it, a signing avatar would look unnatural and could omit important
information, thus, resulting in incomprehensible utterances. Therefore, we can
conclude that an avatar capable of producing mouthing is an essential part of
any automatic written/spoken to sign translation system.

##  3 Synthesis of Sign Language Animations

We used an existing text-to-sign language translator Cabral et al. (2020);
Neves et al. (2020); Gonçalves et al. (2021) to evaluate our animations
(overall architecture in Figure 2). This system is divided into two main
modules. The first module performs a translation process, consisting of the
translation of text from Portuguese into LGP, in which the LGP sentence is
represented by a sequence of glosses and additional morphosyntactic
information. The second module consists of an avatar that animates the LGP
translated message received from the first module, by using a database with
synthesized signs (i.e., animations).

In the following sections, we describe the dynamic transitions and how we have
implemented the mouthing process.

###  3.1 Dynamic transitions

Considering that transitions between signs rely heavily on the phonology of
the previous and following signs and determine the movement fluidity that
allows sign streams to be intelligible, we propose dynamic transitions, which
interpolate signs through transitions that change according to the
previous/following signs.

While we iterate over each gloss in run-time, the differences between hand
positions in the last keyframe of the previous sign and the first keyframe of
the following sign are calculated and then the squared magnitude of these
vectors is computed555The hand positions are obtained from the bones of the
skeleton. While creating the database that contains the synthesized sign
animations, we also created a JSON file that contains, for each sign and in
each keyframe, the facial expressions used, and the hand positions based on
the bones of the skeleton. In runtime, we use this information to obtain the
hand positions to generate the dynamic transitions.. Calculating the squared
magnitude of a vector is much faster than using the magnitude property since
it does not require a slow square root operation that makes the magnitude
property take longer to
execute666https://docs.unity3d.com/ScriptReference/Vector3-sqrMagnitude.html.

These squared magnitude values are then converted to percentages by defining a
scale. To decide this scale, we checked all signs created to find two signs
that have the closest hand position differences (e.g., signs “EU” and “TER”)
and two signs that have the furthest hand position differences (e.g., signs
“ELE” and “TER”). Based on our findings, we defined two scales: one that
includes both hands (if the left hand has movement), and another that only
considers the right hand (if the left hand has no movement). Using these
scales, the squared magnitude values are converted to percentages that range
between 0% and 100%.

Finally, to find the duration value used in the transition between signs, we
use the percentage calculated to linearly interpolate between two duration
values. These two duration values correspond to the lowest and highest values
that the duration of transitions can take. We defined these values by
analyzing the lowest and highest transition duration in multiple videos of an
LGP corpus777https://portallgp.ics.lisboa.ucp.pt/corpus_lgp/. Furthermore, two
empirical studies developed by Sedeeq Al-khazraji et al. (2020, 2021) found
that ASL signers prefer slower transitions than the timing of human signers
and that they prefer animations with an average transition time of 0.5
seconds. Based on the analysis of our LGP corpus, we decided that the duration
of transitions would range between 0.3 seconds and 1.1 seconds because this
range would include 0.5 seconds as the average transition time and these are
slightly slower than the human signing transitions in our LGP corpus.

Using the calculated duration values in the process previously described, we
created an interpolation between the current sign and the next sign using
dynamic transitions by defining a duration value and an offset value888The
offset was introduced as a workaround due to the limitations of the Unity
animation engine because the animation blending of Unity requires overlap
between the animations. Another way to do it would be by using the UnityEditor
package which provides much more animation resources to manipulate the
avatar’s animation in runtime. However, these scripts cannot be included in
the WebGL build which we needed because we want to have the translator
deployed in a website.. The first keyframe of every sign in the database
starts at 1 second, which is what allows transitions between signs to be
executed without cutting the signs shorter because without it the transition
would overlap the beginning of each sign. Using the offset value, we can
adjust the timing until the first keyframe matches the transition duration
time; therefore, the offset value is 1 second minus the transition duration
value. Transitions must be seen as a continuous stream of motion without being
too paused because co-articulation, similarly to oral languages, also
constitutes an important part of sign languages. To create transitions that
are fluid and not too paused between signs, we decided to define the offset
value as 1.2 seconds minus the transition value rather than 1 second. Thus,
signs will be slightly overlapped and transitions more fluid.

Another aspect taken into consideration was the phonological assimilation
processes of composite utterances. Composite utterances are utterances that
have meanings derived from the composition of multiple signs (e.g., “VERMELHO”
+ “MELÃO” means “MELÂNCIA” (“RED” + “MELON” means “WATERMELON”). Since
multiple signs can be combined for one sole meaning, the transitions between
these must be smaller than transitions between signs that have separate
meanings. This is another reason why dynamic transitions are so important.
These can have an impact on the perception of composite utterances if the
phonological assimilation processes are not taken into consideration. Based on
empirical experiments, we defined 0.2 seconds as the transition duration in-
between all signs that comprise a composite utterance. Using the indices that
define composite utterances obtained from the translation process, we
transition between signs that comprise composite utterances with a transition
value of 0.2 seconds, making the transitions for composite utterances faster
than transitions for other signs.

###  3.2 Mouthing

Mouthing is an essential part of any automatic written-to-sign translation
system and without it, a signing avatar would look unnatural and could omit
important information. The existing translator was extended to create mouthing
animations. Notice that mouthing should be done with words in Portuguese and
not their glosses. For instance, verbs are not conjugated while signing, but
these should be conjugated while mouthing. Therefore, we extended the system
to gather all words in Portuguese and, afterwards, combine them into a
sentence so that we consider the assimilation between words when executing the
phonetic transcription. (Figure 3)

Figure 3: The process of transcribing a sentence phonetically and mapping it
to the corresponding visemes.

The phonetic transcription (Step 1 in Figure 3) is done by employing the
phonemizer tool999https://github.com/bootphon/phonemizer, where the speak
backend is used to produce phoneme sequences described based on the
International Phonetic Alphabet transcription. After this, normalization (Step
2 in Figure 3) is done by encoding non-ASCII to ASCII, words are separated
into their corresponding syllables (Step 3 in Figure 3) using syllabification
rules and, then, each phoneme is mapped into one viseme (Step 4 in Figure 3)
using the phoneme-viseme mapping we created. While mapping visemes, we need to
be careful not to over-articulate as it would generate unnatural mouthing
animations. We prevented the over-articulation problem by removing visemes
that are irrelevant in the visual domain. For instance, we remove visemes that
have equal consecutive visemes, and we remove ’C’ viseme consonants (i.e., in
a visual domain, represent a slight open mouth) that are at the end of a
syllable (e.g., ’r’ is removed from ’per’ syllable in Figure 3).

The avatar contains 7 visemes – A, B, C, E, F, O, and U – to animate the 33
phonemes of the Portuguese language. To create visemes as close as possible to
human visemes, animations for each viseme were created by adjusting the
weights of blend shapes. In the translation process, words are translated into
phonemes, separated into syllables, and then mapped into visemes. In the
animation process, when the manual signs are being animated, mouthing is
animated by using an interpolation scheme that concatenates the visemes
according to the animated signs.

The duration value for the mouthing is defined based on the duration of the
sign it is applied to and based on the number of syllables for that sign. The
reason behind this is that we do not want mouthing to either overlap the
duration of a sign or be too slow if the duration of a sign is too large. The
synchronization between mouthing and signs is extremely important because
studies Kipp et al. (2011) have reported that a mismatch between the duration
of signs and their corresponding mouthings can provoke a disturbing
oscillation of the user’s visual focus from hands to face.

Finally, we would like to highlight that the mouth movement is slightly
anticipated with respect to the hands.

##  4 Evaluation

We have designed and conducted two experimental user studies101010Both studies
were approved by the Ethics Committee of our university, and, before
participating in the studies, each participant was handed an informed consent
that they had to sign to participate.: we analyze the impact of both dynamic
transitions and mouthing on: a) linguistic comprehension, b) naturalness, and
c) preference of LGP animations. In the case of dynamic transitions, speed was
also evaluated. All the signing animations were generated using the previously
described sign language translator.

###  4.1 Evaluating Dynamic Transitions

We recruited 11 participants fluent in LGP. Participants had to fill in a
questionnaire. In the first 10 sections of the questionnaire, participants had
to visualize a video, write the understood content, and describe whether the
sentence contained an error. As we wanted to evaluate the impact transitions
could have on the phonology of signs, particularly on the phonological
assimilation of composite sentences, the created sentences contained one or
more composite sentences. Furthermore, for each sentence, they also had to
evaluate the transitions’ speed on a 1-5 Likert scale with one as too slow and
five as too fast, and evaluate the avatar’s naturalness on a 1-5 Likert scale
with one as robotic and five as natural. We presented both conditions -
dynamic transitions and constant conditions - to all participants in a
counterbalanced order. The order of the first ten sections was randomized.

In the next three sections of the questionnaire, participants had to select
the preferred video between two side-by-side videos (one with dynamic
transitions and one with constant transitions of 0.5 seconds). To mitigate
experimental bias, the video position was randomized. We also asked
participants “How the naturalness of the avatar could be improved”, whether
they think “transitions between signs affect naturalness” and whether they
think “transitions between signs affect comprehension”.

####  4.1.1 Comprehension

For each sentence in the questionnaire, we measured the percentage of content
understood by calculating the number of glosses correctly described with 100%
as all glosses correctly understood by a participant. This process had to be
done manually as synonyms of signs also counted as correct. Overall, the
average comprehension scores for all participants with both conditions was
81.56% ($SD=23.29$).

As shown in Figure 4, 7 participants had higher comprehension results in
sentences with dynamic transitions, 3 participants had higher comprehension
results with constant transitions and 1 participant had equal comprehension
results in both transitions. According to a Shapiro-Wilk test, we retained the
null hypothesis of population normality ($p=0.901,p=0.722$); therefore, we
conducted a Paired samples T-test to compare differences in comprehension
scores between our conditions. Based on the results, there was no significant
difference ($t(10)=-1.379,p=0.198$) in the scores for dynamic transitions
($M=82.97,SD=9.43$) and constant transitions ($M=80.15,SD=11.55$).

Figure 4: Comprehension scores between dynamic transitions and constant
transitions per participant.

In almost all cases, participants would either understand a sign or not,
independently of the transition approach, which could be explained by the
difference between the transition values of both approaches is not
significant. However, there were 4 cases in the two-paired sentences (i.e.,
eight sentences) where the same sign was only perceived correctly with a
dynamic approach. Moreover, there were no cases where a sign was only
perceived correctly with a constant approach. Furthermore, seven participants
believed transitions between signs impact comprehension, whereas only four
believed they do not.

####  4.1.2 Naturalness

For each sentence in the questionnaires, we measured the percentage of
naturalness by using the scores submitted on the Likert scale (i.e., one as
robotic and five as natural), with 5 being 100%. Overall, the average
naturalness scores for all participants with both conditions was 50.73%
($SD=22.78$) and the average overall naturalness111111The first percentage is
the average naturalness scores for all sections in the questionnaire (each
video where they had to write the sentence they comprehended). The second
percentage is the overall naturalness asked at the end of the questionnaire.
given at the end of the questionnaire by all participants was 50.91%
($SD=25.87$). The scores for naturalness were significantly lower than those
for the other two measures, which is unsurprising because naturalness is the
most demanding criterion of all.

Figure 5: Naturalness scores between dynamic transitions and constant
transitions.

As shown in Figure 5, there were large discrepancies between naturalness
scores throughout our participants with 20% as the lowest average score and
100% as the highest score. Furthermore, 3 participants had higher naturalness
results in sentences with dynamic transitions, 2 participants had higher
naturalness results with constant transitions, and 6 participants had equal
naturalness results in both transitions. According to a Shapiro-Wilk test, we
retained the null hypothesis of population normality ($p=0.548,p=0.215$);
therefore, we conducted a Paired samples T-test to compare differences in
naturalness scores between our conditions. Based on the results, there was no
significant difference ($t(10)=-0.820,p=0.432$) in the scores for dynamic
transitions ($M=51.27,SD=22.61$) and constant transitions
($M=50.18,SD=22.51$). However, seven participants believed transitions between
signs impact naturalness, whereas only four believed they do not.

####  4.1.3 Preference

We conducted a Chi-Square test to analyze which transition approach was
preferred. We found a statistically significant relation between participants
and the transition approach ($X^{2}(1,N=33)=6.818,p=.009$), as participants
preferred dynamic transitions ($N=24$) rather than constant transitions
($N=9$).

####  4.1.4 Transitions Speed

For each sentence in the questionnaires, we measured the percentage of optimal
transition speed by using the scores submitted in the Likert scale (i.e., one
as too slow and five as too fast) with 3 being the optimal speed with 100% and
decreasing the percentage value according to the closeness to the limits of
the scale with 2 and 4 as 66.67% and 1 and 5 as 33.33%. Overall, the average
optimal transition speed scores for all participants with both conditions was
83.64% ($SD=17.36$), and the average overall quality of transitions given at
the end of the questionnaire by all participants was 81.82% ($SD=17.41$).

Figure 6: Transition speed scores between dynamic transitions and constant
transitions.

As shown in Figure 6, three participants had higher optimal transition speed
results in sentences with dynamic transitions, three participants had higher
optimal transition speed results with constant transitions, and five
participants had equal optimal transition speed results in both conditions.
According to a Shapiro-Wilk test, we retained the null hypothesis of
population normality ($p=0.283,p=0.064$); therefore, we conducted a Paired
samples T-test to compare differences in optimal transition speed scores
between our conditions. Based on the results, there was no significant
difference ($t(10)=-0.319,p=0.756$) in the scores for dynamic transitions
($M=83.64,SD=11.68$) and constant transitions ($M=83.032,SD=13.45$). However,
three participants commented on the importance of faster transitions in-
between signs that comprise one sole meaning and noted that constant
transitions were too slow for composite utterances, and surprisingly, in
negatives. The latter is one aspect we did not consider, but coincidentally
our dynamic approach produced faster transitions between the negated verb and
the “NÃO” (no) sign because the difference between hand locations of these
signs is quite small. This difference allowed participants to note that
constant transitions were too slow for transitions between the negated verb
and the “NÃO” sign while our dynamic approach was optimal. We conclude that
dynamic transitions might positively impact the optimal speed and that signs
that comprise one sole meaning, as composite utterances and negation of verbs,
should have faster transitions than other signs.

####  4.1.5 Discussion

Based on the previously reported findings, we can conclude that the null
hypothesis could not be rejected in evaluating comprehension, transitions’
speed, and naturalness. Nevertheless, we found particular cases where the same
signs with the dynamic approach were perceived correctly and with the constant
approach perceived incorrectly, but the opposite was not found. Therefore,
dynamic transitions could enhance linguistic comprehension, particularly for
signs that comprise one sole meaning (i.e., composite utterances and
negatives) and require faster transitions. The dynamic transitions approach
was also the most preferred approach by our participants, showing the positive
impact they can have on animations.

Regarding naturalness, neither approach had a significant impact, and this
criterion is still the most demanding of all. It is interesting to note that
participants tend to relate naturalness to the comprehension of animations.
Furthermore, it is also interesting to note that naturalness is not only
linked to comprehension but also to syntax, because sentences that were
completely understood but were not correct in terms of grammar, also scored
lower in naturalness.

###  4.2 Mouthing Evaluation

We recruited 20 participants that are learning LGP. Recruiting beginners for
this user study was essential because we wanted people that had sufficient
knowledge to understand some signs but not all, so that we could evaluate
whether mouthing could indeed have an impact on comprehension.

Again, we recurred to a questionnaire with thirteen sentences. For this user
study, we removed all phonological facial expressions from signs, so that all
signs could execute mouthing. The level of complexity and difficulty in this
user study was lower than the previous one, but not too easy so that we could
see the impact of mouthing. This experiment was similar to the previous one
(questions should evaluate naturalness, comprehension and preference). We also
evaluated general quality, signs quality, and facial expressions quality in
the same Likert scales. Additionally, we also asked participants whether they
think “mouthing affects naturalness", whether they think “mouthing affects
comprehension", and “If yes, in which situations and why?".

####  4.2.1 Comprehension

We evaluated comprehension using a similar procedure to the previous study.
Overall, the average comprehension scores for all participants with both
conditions was 70.94% ($SD=37.88$) which we found surprisingly high
considering that participants were beginners and sentences had a level of
complexity and difficulty higher than beginner level with some sentences
composed by interrogatives, one composite utterance (i.e., sign “IRMÃ") and
dactylology words comprised of numbers with two digits and names with seven
letters.

Figure 7: Comprehension scores between animation with mouthing and without
mouthing.

As shown in Figure 7, there were large discrepancies between comprehension
scores among our participants with 33.33% as the lowest average score and 100%
as the highest score. Furthermore, 10 participants had higher comprehension
results in sentences with mouthing, three participants had higher
comprehension results without mouthing, and seven participants had equal
comprehension results in both. According to a Shapiro-Wilk test, we rejected
the null hypothesis of population normality ($p=0.012,p=0.050$); therefore, we
conducted a Wilcoxon signed-rank test to compare differences in comprehension
scores between our conditions. Based on these results, the comprehension
scores for sentences with mouthing were statistically significantly higher
than for sentences without mouthing ($Z=-2.029,p=0.043$). Furthermore, 16
participants believe mouthing does indeed have an impact on comprehension,
whereas only 4 participants believe it does not. Additionally, many comments
were made by participants throughout the questionnaires noting that mouthing
makes it easier to understand the sentences.

####  4.2.2 Naturalness

Naturalness was also evaluated as in the previous experiment. Overall, the
average naturalness scores for all participants with both conditions was
78.29% ($SD=16.91$) and the average overall naturalness given at the end of
the questionnaire by all participants was 78.95% ($SD=15.60$). The scores for
naturalness were significantly higher than scores given in the previous user
study, which can be explained by the fact that participants in this study are
still beginners and are still not sensible about all subtleties of sign
languages; therefore, they did not notice aspects that might still be missing
in our avatar.

Figure 8: Naturalness scores between animation with mouthing and without
mouthing.

As shown in Figure 8, 11 participants had higher naturalness results in
sentences with mouthing, five participants had higher naturalness results
without mouthing, and four participants had equal naturalness results in both.
According to a Shapiro-Wilk test, we retained the null hypothesis of
population normality ($p=0.160,p=0.793$); therefore, we conducted a Paired
samples T-test to compare differences in naturalness scores between our
conditions. Based on the results, the naturalness scores for sentences with
mouthing ($M=80.40,SD=15.24$) were statistically significantly higher
($t(19)=-2.094,p=0.050$) than for sentences without mouthing
($M=76.10,SD=13.11$). Furthermore, 18 participants believe mouthing has an
impact on naturalness, whereas only 2 participants believe it does not.

####  4.2.3 Preference

We conducted a Chi-Square test to analyze which animations were preferred on
the three trials each participant had; therefore, there were 60 trials
overall. There was a statistically significant relation between participants
and the mouthing approach ($X^{2}(1,N=60)=15,p<0.001$), as participants
preferred more animations with mouthing ($N=45$) than animations without
($N=15$). One participant said that “mouthing can distract the participant
from the signs” as being the reason for not choosing animations with mouthing.

####  4.2.4 Discussion

Based on the previously reported findings, we conclude that sentences that
incorporated mouthing had higher comprehension and naturalness scores than
sentences without mouthing. Therefore, our study suggests that mouthing can
indeed enhance linguistic comprehension and naturalness, and participants
prefer LGP animations with mouthing. Our user study demonstrates not only the
impact mouthing has on signing animations but also that the quality of our
mouthing approach was good enough to improve comprehension.

##  5 Conclusions and Future Work

We used an existing text-to-sign language translator to demonstrate how we
improved LGP animations. We introduced a new way of performing transitions
between signs – the dynamic transitions – and added to the translator’s avatar
the possibility of performing mouthing. The positive results indicate that the
generated animations show great potential in the field of synthetic animation
of signing avatars.

Despite the positive results, some aspects must be improved and extended in
future research to improve perceived naturalness. Suggestions include adding
more facial expressions, corporal movements, appropriate pauses and
accelerations between signs, and creating more fluid movements.

## References

  * Adamo-Villani [2008] Nicoletta Adamo-Villani.  3d rendering of american sign language finger-spelling: a comparative study of two animation techniques.  _International journal of human and social sciences_ , 3(4):24, 2008.
  * Al-khazraji et al. [2018] Sedeeq Al-khazraji, Larwan Berke, Sushant Kafle, Peter Yeung, and Matt Huenerfauth.  Modeling the speed and timing of american sign language to generate realistic animations.  In _Proceedings of the 20th International ACM SIGACCESS Conference on Computers and Accessibility_ , pages 259–270, 2018.
  * Al-khazraji et al. [2020] Sedeeq Al-khazraji, Becca Dingman, and Matt Huenerfauth.  Empirical investigation of users’ preferred timing parameters for american sign language animations.  In _Extended Abstracts of the 2020 CHI Conference on Human Factors in Computing Systems_ , pages 1–7, 2020.
  * Al-khazraji et al. [2021] Sedeeq Al-khazraji, Becca Dingman, Sooyeon Lee, and Matt Huenerfauth.  At a different pace: Evaluating whether users prefer timing parameters in american sign language animations to differ from human signers’ timing.  _The 23rd International ACM SIGACCESS Conference on Computers and Accessibility (ASSETS’21)_ , 2021.
  * Bear et al. [2014] Helen L Bear, Richard W Harvey, Barry-John Theobald, and Yuxuan Lan.  Which phoneme-to-viseme maps best improve visual-only computer lip-reading?  In _International Symposium on Visual Computing_ , pages 230–239. Springer, 2014.
  * Cabral et al. [2020] Pedro Cabral, Matilde Gonçalves, Hugo Nicolau, Luísa Coheur, and Ruben Santos.  PE2LGP animator: A tool to animate a Portuguese Sign Language avatar.  In _Proceedings of the LREC2020 9th Workshop on the Representation and Processing of Sign Languages: Sign Language Resources in the Service of the Language Community, Technological Challenges and Application Perspectives_ , pages 33–38, Marseille, France, May 2020. European Language Resources Association (ELRA).  ISBN 979-10-95546-54-2.  URL https://aclanthology.org/2020.signlang-1.6.
  * Crasborn et al. [2008] Onno A Crasborn, Els Van Der Kooij, Dafydd Waters, Bencie Woll, and Johanna Mesch.  Frequency distribution and spreading behavior of different types of mouth actions in three sign languages.  _Sign Language & Linguistics_, 11(1):45–67, 2008.
  * Elliott et al. [2000] Ralph Elliott, John RW Glauert, JR Kennaway, and Ian Marshall.  The development of language processing support for the visicast project.  In _Proceedings of the fourth international ACM conference on Assistive technologies_ , pages 101–108, 2000.
  * Gibet et al. [2011] Sylvie Gibet, Nicolas Courty, Kyle Duarte, and Thibaut Le Naour.  The signcom system for data-driven animation of interactive virtual signers: Methodology and evaluation.  _ACM Transactions on Interactive Intelligent Systems (TiiS)_ , 1(1):1–23, 2011.
  * Glauert et al. [2004] JRW Glauert, Richard Kennaway, Ralph Elliott, and Barry-John Theobald.  Virtual human signing as expressive animation.  In _Symposium on Language, Speech and Gesture for Expressive Characters, University of Leeds_ , pages 98–106, 2004.
  * Gonçalves et al. [2021] Matilde Gonçalves, Luisa Coheur, Hugo Nicolau, and Ana Mineiro.  Pe2lgp: tradutor de português europeu para língua gestual portuguesa em glosas.  _Linguamática_ , 13(1):3–21, Jul. 2021.  doi: 10.21814/lm.13.1.338.  URL https://linguamatica.com/index.php/linguamatica/article/view/338.
  * Huenerfauth [2009] Matt Huenerfauth.  A linguistically motivated model for speed and pausing in animations of american sign language.  _ACM Transactions on Accessible Computing (TACCESS)_ , 2(2):1–31, 2009.
  * Kipp et al. [2011] Michael Kipp, Quan Nguyen, Alexis Heloir, and Silke Matthes.  Assessing the deaf user perspective on sign language avatars.  In _The proceedings of the 13th international ACM SIGACCESS conference on Computers and accessibility_ , pages 107–114, 2011.
  * Neves et al. [2020] Carolina Neves, Luísa Coheur, and Hugo Nicolau.  HamNoSyS2SiGML: Translating HamNoSys into SiGML.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 6035–6039, Marseille, France, May 2020. European Language Resources Association.  ISBN 979-10-95546-34-4.  URL https://aclanthology.org/2020.lrec-1.739.
  * Serra et al. [2012a] José Serra, Manuel Ribeiro, João Freitas, Verónica Orvalho, and Miguel Sales Dias.  A proposal for a visual speech animation system for european portuguese.  In _Advances in Speech and Language Technologies for Iberian Languages_ , pages 267–276. Springer, 2012a.
  * Serra et al. [2012b] José Serra, Manuel Ribeiro, João Freitas, Veronica Orvalho, and Miguel Dias.  A proposal for a visual speech animation system for european portuguese.  _Communications in Computer and Information Science_ , 328:267–276, 01 2012b.  doi: 10.1007/978-3-642-35292-8_28.
  * Wolfe et al. [2018a] Rosalee Wolfe, Thomas Hanke, Gabriele Langer, Elena Jahn, Satu Worseck, Julian Bleicken, John Mcdonald, and Sarah Johnson.  Exploring localization for mouthings in sign language avatars.  In _Proceedings of the LREC2018 8th Workshop on the Representation and Processing of Sign Languages: Involving the Language Community_ , 05 2018a.
  * Wolfe et al. [2018b] Rosalee Wolfe, Thomas Hanke, Gabriele Langer, Elena Jahn, Satu Worseck, Julian Bleicken, John C McDonald, and Sarah Johnson.  Exploring localization for mouthings in sign language avatars.  In _Proceedings of the International Conference on Language Resources and Evaluation (LREC)_ , 2018b.

  *[LGP]: Portuguese Sign Language
  *[BSL]: British Sign Language
  *[ASL]: American Sign Language
  *[EP]: European Portuguese