#  Radium-containing molecular cations amenable for laser cooling

Timur Isaev<EMAIL_ADDRESS>Chemistry Dept., M. Lomonosov Moscow
State University, Moscow 119991, Russia  Dmitrii Makinskii
<EMAIL_ADDRESS>NRC ”Kurchatov Institute” - PNPI, Orlova Roscha, 1,
188300 Gatchina, Russia
Chemistry Dept., M. Lomonosov Moscow State University, Moscow 119991, Russia
Andrei Zaitsevskii<EMAIL_ADDRESS>NRC ”Kurchatov Institute” -
PNPI, Orlova Roscha, 1, 188300 Gatchina, Russia
Chemistry Dept., M. Lomonosov Moscow State University, Moscow 119991, Russia

###### Abstract

Recently a new wave of interest to spectroscopy of radioactive compounds has
raised due to successful applications of the new experimental ISOL/CRIS
technique to optical spectroscopy of radium monofluoride molecules. This opens
great prospects to searches of the effects connected with “new physics” which
point on deviations of the physical laws from those established by Standard
Model of elementary particles. Considerable advantages in experiments for
search for such effects would be provided by the abilities to trap the working
molecules, their laser-coolability and presence of co-magnitometer molecular
states and also a variety of accessible nuclear isotopes of the elements in
the molecule with different nuclear multipole moments. Laser-coolable
polyatomic molecular ions containing Ra nuclei shall meet the above criteria
and in the present article we are considering a number of prospective
molecular ions and calculating their electronic structure and molecular
properties.

###### pacs:

31.30.-i, 37.10.Mn, 12.15.Mm, 21.10.Ky

##  I Introduction

Molecules containing radium nuclei offer great prospects in a number of
research fields, including search for “new physics” outside of the Standard
Model of elementary particles. These prospects are related, on the one hand,
to the extreme sensitivity of molecules containing heavy nuclei to the effects
of time ($\cal T$-odd ) and space ($\cal P$-odd ) parity violation [1, 2, 3,
4, 5, 6, 7] and on the other hand to a considerable enhancement of nuclear
$\cal P$-odd and $\cal T$-odd moments in octupole-deformed nuclei [8, 9].
Radium isotopes possess a large variety of nuclear properties, including a
wide range of nuclear spins from 0 (226Ra) to 5/2 (e.g. in 221Ra), octupole
deformation (in isotopes 223Ra and 225Ra) and half-live time from 1599 years
for 226Ra to 4.7 seconds for 209Ra. Recently a new direction in molecular
spectroscopy, namely spectroscopy of short-lived radioactive molecules, has
been established [10] and the first vibrational spectra measurements have been
performed on radium monofluoride (RaF) molecule. As experimental information
for this and other molecules containing radioactive nuclei was scarce, _ab
initio_ electronic structure calculations [11, 12, 13] were the main source of
valuable information to design effective experimental scheme. One of the
important predictions following from the electronic structure calculations was
good prospects for laser-coolability of RaF, which paves the way for high-
precision spectroscopic studies. Laser-coolability is also important in
experiments with molecular ions [14], where it allows to perform efficient
compression of population of vibrational and rotational degrees of freedom
[15, 16]. Molecular ions also have an attractive feature, that they can be
easily trapped and then considerable trapping time can be used for optical
manipulations. For example, in experiments on search of permanent electric
dipole moment (EDM) of an electron in HfF+ molecular cation [17] the trapping
time was ca. 1$s$, i.e. sufficient to perform vibrational-rotational cooling
even with optical cooling loop involving highly-forbidden electronic
transitions. In view of considerable progress of molecular spectroscopy of
radioactive species and attractive features of radium-containing compounds for
high-precision spectroscopy (see also [18, 19]) we are considering a number of
radium-containing molecular ions which could possess highly-diagonal Franck-
Condon matrices for transitions between ground and low-lying excited
electronic states. Considered compounds can be produced using the technique
similar to that used in [20]. We analyze electronic structure of suggested
compounds from the point of laser-coolability (which requires quasi-
diagonality of Franck-Condon matrix for cooling vibronic transitions [21]) and
is an essential prerequisite for ultra-precision spectroscopy.

##  II Calculation details and discussion

All calculations reported below employ the relativistic electronic structure
model similar to that used in Ref. [22]. The model is defined by the accurate
two-component shape-consistent pseudopotential of Ra (for discussion on the
theory of RECP employed see [23, 24]) replacing 60 inner core electrons [25].
Light-element atoms are described in all-electron manner; the effects of
relativity are accounted for through so-called empty-core pseudopotentials
[26, 25]. All RECPs are optimized to describe valence (rather than subvalence
and/or core) electronic shells and incorporate implicitly the effects of
finite nuclear size and Breit electron-electron interactions.

Ground-state equilibrium geometries and energetics are determined using two-
component non-collinear density functional theory [27] with the “non-
empirical” PBE0 approximation for the exchange-correlation functional [28].
The components of one-electron (pseudo) spinors are expanded in the Gaussian
basis comprising the primitive $(10s9p9d4f)$ set on the Ra atom and triple
zeta quality sets [29, 30]) extended by double sets of polarization functions
on other atoms; for first-row atoms, single sets of diffuse functions are
added as well (see Supplementary materials). The total basis set sizes were
thus $(12s7p2d)/[6s4p2d]$ for C, N, F and $(5s2p)/[3s2p]$ for H. The
relativistic effects associated with light atoms were neglected at the DFT
stage. The resulting geometries and Ra+ binding energies are listed in Table
1. It is worth noting that the obtained equilibrium parameters for RaNCH+
agree well with those from relativistic CCSD(T) calculations (the Ra–N
equilibrium separation 2.905 Å, dissociation energy $6.89\cdot 10^{3}$ cm-1,
see below).

Table 1: Ground-state equilibrium geometries (bond lengths in Å, angles in
degrees) and dissociation energies of ionic complexes according to the two-
component relativistic DFT / PBE0 calculations.

Complex | Symmetry |  $R_{e}$(Ra–Xa)) | Attached ligand geometry | (deformation) |  $D_{e}$, 103 cm-1
---|---|---|---|---|---
RaNH${}_{3}^{+}$ | $C_{3v}$ | 2.872 |  $R$(N–H)=1.018 | ($+0.005$ ) | 8.13
|  |  | ∠RaNH=113.43∘ |  |
|  |  | ∠HNH=105.24∘ | ($-1.43^{\circ}$) |
RaNCCH${}_{3}^{+}$ | $C_{3v}$ | 2.799 |  $R$(N–C)=1.153 | ($-0.000$) | 9.48
|  |  |  $R$(C–C)=1.443 | ($-0.008$) |
|  |  |  $R$(C–H)=1.091 | ($+0.001$) |
|  |  | ∠CCH=109.65∘ | ($-0.46^{\circ}$) |
RaNCH+ | $C_{\infty v}$ | 2.881 |  $R$(N–C)=1.1470 Å | ($-0.003$) | 7.03
|  |  |  $R$(C–H)=1.0726 Å | ($+0.005$) |
RaCNH+ | $C_{\infty v}$ | 3.073 |  $R$(C–N)=1.157 | ($-0.012$ )b) | 6.68 c)
|  |  |  $R$(N–H)=1.002 | ($+0.006$ )b) |
RaNCCN+ | $C_{\infty v}$ | 2.931 |  $R$(C–NRa)=1.154 | ($-0.001$) | 4.23
|  |  |  $R$(C–C)= 1.374 | ($-0.002$) |
|  |  |  $R$(C–Nterm)=1.156 | ($+0.001$) |
RaFH+ | $C_{\infty v}$ | 2.778 |  $R$(F–H)=0.928 | ($+0.009$) | 4.17

a) neighbor atom b) with respect to HNC, b) with respect to Ra+ \+ HNC

In all cases, the complex formation does not lead to significant deformation
of the ligand in comparison to its free form; for instance, the deformation of
the free HCN molecule from its equilibrium geometry to that found for the
ligand in the RaNCH+ complex increases its energy by less than 40 cm-1. The
Ra+ binding energies are rather moderate (the largest value, 9.48$\cdot
10^{3}$ cm-1, is predicted for RaNCCH${}_{3}^{+}$). The equilibrium structures
of compounds have symmetry of the free ligand.

Excited state calculations for relatively stable complexes are performed
within the standard Fock space relativistic coupled cluster (FS RCC) scheme
[31] using the closed-shell Hartree–Fock determinant of the doubly charged
molecular cation as the Fermi vacuum state and restricting the cluster
operator expansion to single and double excitations (FS RCCSD). For all
systems under study, model spaces are constructed by placing the single
electron on one of 18 lowest-energy molecular spinors corresponding to
$7s_{1/2}$, $6d_{3/2,\,5/2}$, and $7p_{1/2,\,3/2}$ atomic spinors of radium
ion at the dissociation limit. The employed basis for Ra is the
$[10s\,9p\,9d\,7f\,4g\,3h]$ subset of the basis from Ref. [22]; its important
feature consists in using ANO-like high-angular-momentum functions optimised
in scalar relativistic calculations. For hydrogen and first-row atoms we use
correlation-consistent basis sets cc-pVTZ and aug-cc-pVTZ [32, 33],
respectively. The $5s5p$ subshells of Ra as well as $1s$ shells of first-row
atoms are frozen after the Hartree–Fock stage.

Crude estimates for squared vertical transition dipoles are obtained using the
model-space parts of the wavefunctions as
$|\langle\psi_{i}^{\perp\\!\perp}|d_{\eta}|\psi_{f}\rangle|\times|\langle\psi_{f}^{\perp\\!\perp}|d_{\eta}|\psi_{i}\rangle|$,
where $\psi_{i},\;\psi_{f}$ and
$\psi_{i}^{\perp\\!\perp},\;\psi_{f}^{\perp\\!\perp}$ are respectively right
and left eigevectors of the non-Hermitian FS RCC effective Hamiltonian
corresponding to the initial ($i$) and final ($f$) states and $d_{\eta}$
stands for a component of the dipole moment operator. Due to the complete
neglect of contributions to dipole matrix elements from the configurations
outside of the model space, these estimates should be considered only as
semiquantitative [34].

The FS RCC calculations are performed with the EXP-T package [35] which uses
the solutions of spin-orbit-coupled Hartree-Fock equations and transformed
molecular integrals exported by the DIRAC19 program system [36, 37]. The
DIRAC19 code is also employed for relativistic single-reference CCSD(T)
calculations.

Table 2: FS RCC vertical excitation energies $T_{\rm vert}$ and squared
transition dipoles RaNCH+ computed at the RDFT/PBE0 ground state geometries.

| State |  $T_{\rm vert}$, $10^{3}$ cm-1 |  $\sum|d^{2}|\;^{a)}$, a.u.
---|---|---|---
RaNCH+ | ($X$)1/2 | 0 |
| (1)3/2 | 11.36 | 0.02
| (2)1/2 | 11.74 | 0.10
| (2)3/2 | 12.70 | 0.01
| (1)5/2 | 12.89 | 0
| (3)1/2 | 16.10 | 3.45
| (4)1/2 | 20.08 | 7.73
| (3)3/2 | 22.38 | 8.55
| (5)1/2 | 29.82 | 2.07
RaNH${}_{3}^{+}$ | $(X)E_{1/2}$ | 0 |
| $(1)E_{3/2}$ | 11.75 | 0.01
| $(2)E_{1/2}$ | 13.05 | $<\\!\\!10^{-2}$
| $(3)E_{1/2}$ | 13.43 | 0.13
| $(2)E_{3/2}$ | 14.26 | 0.02
| $(4)E_{1/2}$ | 17.07 | 4.16
| $(5)E_{1/2}$ | 20.58 | 7.09
| $(3)E_{3/2}$ | 22.62 | 8.79
| $(6)E_{1/2}$ | 25.12 | 2.88
RaNCCH${}_{3}^{+}$ | $(X)E_{1/2}$ | 0 |
| $(1)E_{3/2}$ | 11.61 | 0.03
| $(2)E_{1/2}$ | 12.26 | 0.23
| $(3)E_{1/2}$ | 13.01 | $<\\!\\!10^{-2}$
| $(2)E_{3/2}$ | 13.15 | 0.05
| $(4)E_{1/2}$ | 16.20 | 3.99
| $(5)E_{1/2}$ | 19.89 | 7.74
| $(3)E_{3/2}$ | 21.93 | 8.73
| $(6)E_{1/2}$ | 28.62 | 1.37

a) sum of squared dipoles for transitions from a single excited state
component to both components of the ground state.

The results are summarized in Table 2. Four lowest vertical excitations of
each molecular anion are localized approximately in the same energy range as
$7s-6d$ excitations of the free atomic ion Ra+ (12.08$\times 10^{3}$ and
13.74$\times 10^{3}$ wavenumbers) and are very weakly allowed or even
effectively forbidden, as it should be for quasi $s-d$ transitions, due to
rather weak bonding of Ra+ with ligands (unlike the cases of RaF [10], RaCl
[22] and RaOH [6] where strong chemical bonding of Ra leads to strong
$s-p$/$p-d$ hybridisation of unpaired-electron spinors of corresponding low-
lying electronic states). The fifth excited state, (3)1/2 or (4)$E_{1/2}$,
also correlating with Ra+ (6d) at the dissociation limit, still lies well
below the area of $7s-7p$ transitions of Ra+ ( 21.35$\times 10^{3}$ and
26.21$\times 10^{3}$ wavenumbers) but the transition dipole matrix element
between this state and the ground one is large, indicating a significant
admixture of $p-$ components. The lack of Ra basis functions with spatial
angular momentum greater than 5 ($i$, $k$ etc.) and the neglect of quantum
electrodynamic corrections [38] lead to a comparable errors having the same
sign and resulting in a systematic overestimation of three lowest excitation
energies of free Ra+ by 220-260 cm-1; one could expect that the corresponding
correction of calculated transition energies for the complex ions would
rectify the estimates (see also [13]).

For the RaNCH+ complex we perform a study on the dependence of FS RCC energies
on the Ra-N internuclear separation and Ra-N-C valence angle, leaving the
ligand geometric parameters at their RDFT equilibrium values in the complex.
In the case of stretching deformation, the results can be affected by basis
set superposition errors (BSSE) and the neglect of higher excitation
contributions in the cluster operator. To reduce the corresponding errors, we
evaluate the excited state energies by adding the geometry-dependent FS RCCSD
excitation energies to the ground-state potential calculated by the single-
reference RCC method with perturbative account of contributions from triple
excitations (RCCSD(T)) and including the counterpoise BSSE corrections (ref.
[22, 39]). The resulting potential functions for lowest electronic states and
equilibrium parameters are displayed in Fig. 1 and Table 3, respectively.

According to the calculations with ground-state equilibrium Ra–N separation
and ligand geometry, the complex in all excited states under study should be
linear.

To estimate prospects for laser-coolability of the proposed compounds we
calculated FC-factors for vibronic transitions between ground and five lowest-
lying excited electronic states for RaNCH+ cation as we would expect that
chemical bonding situation is quite similar to this in other compounds. We
accounted only for stretching mode between Ra and ligand, thus effectively
reducing the vibrational problem to this in diatomic pseudomolecule RaX, where
the pseudoatom X has atomic mass equal to mass of NCH. The calculated points
on PEC are approximated by Morse potential and then FC factors together with
equilibrium distance $R_{e}$ and vibrational quanta $\omega_{\rm stretch}$ are
obtained from the parameters of corresponding approximation. The results are
provided in the Table 4. It can be seen that vibronic transitions from the
ground vibrational state of the state 1(3/2), 2(3/2) and 3(1/2) to the first
three vibrational levels $X$ state posses a sum of the greatest FC-factors
sufficiently close to unity to be prospective for using in quasiclosed optical
cycling loop. At the same time, for vibronic transitions between 2(1/2) and
ground electronic states FC-matrix is clearly non-diagonal, and thus effective
cooling loop for these transitions cannot be established.

An insight into the origin of different dependences of potential energies for
different low-lying states on the Ra-N separation can be gained from an one-
electron picture accounting for correlation effects. Such picture can be
obtained via transforming the model-space projection of $(0h1p)$-sector FS RCC
wavefunctions to a single-determinant form. Unpaired-electron spinors provide
approximations for natural spinors (NS) of the corresponding states, one
spinor per state. To better describe the shape of these spinors, the FS RCC
solutions were obtained in larger model spaces (up to 50 active spinors) using
the determinant-shifting technique to suppress the effect of possible intruder
states [40]; the energy estimates are practically insensitive to this
extension. Fig. 1 provides the plots of absolute values of model natural
spinors (square roots of approximate unpaired electron densities) for several
states.

Non-diagonality of FC-matrix is related to a somewhat different nature of
chemical bonding in the ground and low-lying excited states. In Fig.1 one can
see that the ground-state unpaired electron spinor is strongly locaized on the
radium atom and nearly vanishes in the vicinity of a surface separating Ra and
N domains. In other words, its shape is typical for a non-bonding spinor of
the first type, according to classification of non-bonding MOs/spinors in
[11], and the contribution of the unpaired electron to the Ra-N bonding is
negligible. The corresponding spinors for the first excited (1)3/2 state is
slightly delocalized between the Ra ion and the ligand; the delocalization is
more pronounced for the next (2)1/2 state. For both excited states, these
spinors pass through zero between the nitrogen and carbon atoms and thus can
be interpreted in MO-LCAO approach in terms of admixture of the unoccupied
anti-bonding spinor of the N-C fragment to Ra+ spinors. The unpaired electron
density in the area associated with the Ra-N bond is non-negligible for the
(1)3/2 state and more significant for the (2)1/2. This picture indicates
certain contributions of unpaired electron to Ra-N bond strengthening in these
states, quite weak for (1)3/2 and significant for (2)1/2 and agrees well with
the decrease of equilibrium separations between Ra and N, rather small for the
former state and more significant for the latter one (Table 3).

Figure 1:  FS RCCSD / RCCSD(T) energies for five lowest electronic states of linear RaNCH+ as functions of the Ra–N internuclear separation (left; the zero energy corresponds to the ground-state dissociation limit) and absolute values for unpaired-electron natural spinors for the ground ($X(1)1/2$) and low-energy excited (1)3/2 and (2)1/2 of along the symmetry plane (right; isoline values are separated by 0.02 $a_{0}^{-3/2}$).  Table 3:  RCCSD(T)/FS RCCSD equilibrium parameters of low-lying states of RaNCH+ computed with the frozen ligand geometry.  State |  $R_{e}$, Å |  $T_{e}$, $10^{3}$ cm-1 |  $\omega_{\rm stretch}$, cm-1
---|---|---|---
($X$)1/2 | 2.905 | 0 | 161
(1)3/2 | 2.860 | 11.36 | 136
(2)1/2 | 2.698 | 11.48 | 155
(2)3/2 | 2.777 | 12.57 | 207
(3)1/2 | 3.011 | 15.99 | 144
Table 4:  Franck-Condon factors for vibronic transitions between ground vibrational state (0’) of the excited electronic states and three lowest vibrational states (0, 1 and 2) of the ground electronic state $X$. FC-factors for transition from (1)5/2 are not provided due to zeroing of E1 electronic transition matrix element. State | (1)3/2 | (2)1/2 | (2)3/2 | (1)5/2 | (3)1/2
---|---|---|---|---|---
$0^{\prime}\rightarrow 0$ | 0.830 | 0.078 | 0.364 | – | 0.617
$0^{\prime}\rightarrow 1$ | 0.127 | 0.151 | 0.348 | – | 0.315
$0^{\prime}\rightarrow 2$ | 0.030 | 0.178 | 0.186 | – | 0.062
Sum | 0.987 | 0.407 | 0.898 | – | 0.994

##  III Conclusion

We analyse electronic structure of a series of Ra-containing molecular cations
from the point of laser-coolability. Such cations can be used for a number of
research, including searches for $\cal P$-odd and $\cal T$-odd violating
interactions in molecules. The optical spectroscopic properties of all the
considered molecular cations can be basically described in the framework of
simple physical picture as attachment of Ra+ to light-element ligand. This
point is supported by that the electronic transition spectra of complexes
closely remind weakly perturbed Ra+ spectra, that the binding energies are
very moderate and inferior even to the lowest excitation energies and the
equilibrium symmetry of considered complexes is as high as symmetry of free
ligand. Taking RaNCH+ as example we calculate molecular parameters of the
ground and five lowest-lying excited electronic states and estimate prospects
for creation of optical cycling center in this molecular cation. We found that
the excited states (1)3/2, (2)3/2 and (3)1/2 of RaNCH+ (or possibly analogous
states of some similar systems) can have sufficiently “parallel” surfaces of
potential energy to the ground electronic state (and, thus, almost-diagonal
FC-matrix for vibronic transitions between these states) to organise
quasiclosed optical cycle, while “parallelism” of the state (2) 1/2 is fully
destroyed by a partial unpaired electron transfer to low-lying empty spinors
of ligand, thus strengthening the chemical bond and displacing the equilibrium
Ra$-$ligand distance.

##  IV Acknowledgment

The authors are very grateful to C. Zuelch, K. Gaul and R. Berger for fruitful
discussions in 2021. The calculations have been carried out using computing
resources of the federal collective usage center Complex for Simulation and
Data Processing for Mega-science Facilities at National Research Centre
“Kurchatov Institute”, http://ckp.nrcki.ru/. The work is supported by RSF
grant No. 21-42-04411.

## References

  * Flambaum and Khriplovich [1985] V. V. Flambaum and I. B. Khriplovich, Phys. Lett. A 110, 121 (1985).
  * Kozlov and Labzowsky [1995] M. G. Kozlov and L. N. Labzowsky, J. Phys. B 28, 1933 (1995).
  * Berger [2004] R. Berger, in  _Relativistic Electronic Structure Theory, Part: 2, Applications_ , edited by P. Schwerdtfeger (Elsevier, Netherlands, 2004) Chap. 4, pp. 188–288.
  * Vutha  _et al._ [2011] A. C. Vutha, B. Spaun, Y. V. Gurevich, N. R. Hutzler, E. Kirilov, J. M. Doyle, G. Gabrielse, and D. DeMille, Physical Review A 84, 034502 (2011).
  * Kozyryev and Hutzler [2017] I. Kozyryev and N. Hutzler, Phys. Rev. Lett. 119, 133002 (2017).
  * Isaev  _et al._ [2017] T. A. Isaev, A. V. Zaitsevskii, and E. Eliav, J. Phys. B: At. Mol. Opt. Phys. 50, 225101 (2017).
  * Gaul and Berger [2017] K. Gaul and R. Berger, The Journal of Chemical Physics 147, 014109 (2017).
  * Auerbach  _et al._ [1996] N. Auerbach, V. V. Flambaum, and V. Spevak, Phys. Rev. Lett. 76, 4316 (1996).
  * Spevak  _et al._ [1997] V. Spevak, N. Auerbach, and V. V. Flambaum, Phys. Rev. C 56, 1357 (1997).
  * Garcia Ruiz  _et al._ [2020] R. F. Garcia Ruiz, R. Berger, J. Billowes, C. L. Binnersley, M. L. Bissell, A. A. Breier, A. J. Brinson, K. Chrysalidis, T. E. Cocolios, B. S. Cooper, K. T. Flanagan, T. F. Giesen, R. P. de Groote, S. Franchoo, F. P. Gustafsson, T. A. Isaev, Á. Koszorús, G. Neyens, H. A. Perrett, C. M. Ricketts, S. Rothe, L. Schweikhard, A. R. Vernon, K. D. A. Wendt, F. Wienholtz, S. G. Wilkins, and X. F. Yang, Nature 581, 396 (2020).
  * Isaev  _et al._ [2010] T. A. Isaev, S. Hoekstra, and R. Berger, Phys. Rev. A 82, 052521 (2010).
  * Isaev and Berger [2013] T. A. Isaev and R. Berger, ArXiv e-prints physics.chem-ph:1302.5682 (2013), arXiv:1302.5682 [physics.chem-ph] .
  * Zaitsevskii  _et al._ [2022] A. Zaitsevskii, L. V. Skripnikov, N. S. Mosyagin, T. Isaev, R. Berger, A. A. Breier, and T. F. Giesen, The Journal of Chemical Physics 156, 044306 (2022).
  * Lien  _et al._ [2011] C.-Y. Lien, S. R. Williams, and B. Odom, Physical Chemistry Chemical Physics 13, 18825 (2011).
  * Lien  _et al._ [2014] C.-Y. Lien, C. M. Seck, Y.-W. Lin, J. H. Nguyen, D. A. Tabor, and B. C. Odom, Nature Communications 5, 10.1038/ncomms5783 (2014).
  * Stollenwerk  _et al._ [2020] P. R. Stollenwerk, I. O. Antonov, S. Venkataramanababu, Y.-W. Lin, and B. C. Odom, Physical Review Letters 125, 113201 (2020).
  * Cairncross  _et al._ [2017] W. B. Cairncross, D. N. Gresh, M. Grau, K. C. Cossel, T. S. Roussy, Y. Ni, Y. Zhou, J. Ye, and E. A. Cornell, Physical Review Letters 119, 153001 (2017).
  * Zakharova and Petrov [2021] A. Zakharova and A. Petrov, Physical Review A 103, 032819 (2021).
  * Zakharova [2022] A. Zakharova, Physical Review A 105, 032811 (2022).
  * Fan  _et al._ [2021] M. Fan, C. Holliman, X. Shi, H. Zhang, M. Straus, X. Li, S. Buechele, and A. Jayich, Physical Review Letters 126, 023002 (2021).
  * DiRosa [2004] M. D. DiRosa, Eur. Phys. J. D 31, 395 (2004).
  * Isaev  _et al._ [2021] T. A. Isaev, A. V. Zaitsevskii, A. Oleynichenko, E. Eliav, A. A. Breier, T. F. Giesen, R. F. Garcia Ruiz, and R. Berger, J. Quant. Spectrosc. Radiat. Transfer 269, 107649 (2021).
  * Mosyagin  _et al._ [2010] N. S. Mosyagin, A. Zaitsevskii, and A. V. Titov, Int. Rev. At. Mol. Phys. 1, 63 (2010).
  * Mosyagin  _et al._ [2016] N. S. Mosyagin, A. V. Zaitsevskii, L. V. Skripnikov, and A. V. Titov, Int. J. Quantum Chem. 116, 301 (2016).
  * [25] N. S. Mosyagin and A. V. Titov, Generalized relativistic effective core potentials, http://www.qchem.pnpi.spb.ru/recp.
  * Mosyagin  _et al._ [2021] N. Mosyagin, A. Oleynichenko, A. Zaitsevskii, A. Kudrin, E. Pazyuk, and A. Stolyarov, J. Quant. Spectrosc. Radiat. Transfer 263, 107532 (2021).
  * van Wüllen [2010] C. van Wüllen, Z. Phys. Chem. 224, 413 (2010).
  * Adamo and Barone [1999] C. Adamo and V. Barone, J. Chem. Phys. 110, 6158 (1999).
  * Schäfer  _et al._ [1994] A. Schäfer, C. Huber, and R. Ahlrichs, J. Chem. Phys. 100, 5829 (1994), https://doi.org/10.1063/1.467146 .
  * Pritchard  _et al._ [2019] B. P. Pritchard, D. Altarawy, B. Didier, T. D. Gibson, and T. L. Windus, J. Chem. Inf. Model. 47, 1045 (2019).
  * Visscher  _et al._ [2001] L. Visscher, E. Eliav, and U. Kaldor, J. Chem. Phys. 115, 9720 (2001).
  * Dunning [1989] T. H. Dunning, J. Chem. Phys. 90, 1007 (1989).
  * Kendall  _et al._ [1992] R. A. Kendall, T. H. Dunning Jr., and R. J. Harrison, J. Chem. Phys. 96, 6796 (1992).
  * Zaitsevskii  _et al._ [2020] A. Zaitsevskii, A. V. Oleynichenko, and E. Eliav, Symmetry 12, 1845 (2020).
  * Oleynichenko  _et al._ [2020] A. V. Oleynichenko, A. Zaitsevskii, and E. Eliav, in  _Supercomputing_, Commun. Comput. Inf. Sci., Vol. 1331, edited by V. Voevodin and S. Sobolev (Springer International Publishing, Cham, 2020) pp. 375–386.
  * [36] DIRAC, a relativistic ab initio electronic structure program, Release DIRAC19 (2019), written by A. S. P. Gomes, T. Saue, L. Visscher, H. J. Aa. Jensen, and R. Bast, with contributions from I. A. Aucar, V. Bakken, K. G. Dyall, S. Dubillard, U. Ekström, E. Eliav, T. Enevoldsen, E. Faßhauer, T. Fleig, O. Fossgaard, L. Halbert, E. D. Hedegård, B. Heimlich–Paris, T. Helgaker, J. Henriksson, M. Iliaš, Ch. R. Jacob, S. Knecht, S. Komorovský, O. Kullie, J. K. Lærdahl, C. V. Larsen, Y. S. Lee, H. S. Nataraj, M. K. Nayak, P. Norman, G. Olejniczak, J. Olsen, J. M. H. Olsen, Y. C. Park, J. K. Pedersen, M. Pernpointner, R. di Remigio, K. Ruud, P. Sałek, B. Schimmelpfennig, B. Senjean, A. Shee, J. Sikkema, A. J. Thorvaldsen, J. Thyssen, J. van Stralen, M. L. Vidal, S. Villaume, O. Visser, T. Winther, and S. Yamamoto (available at http://dx.doi.org/10.5281/zenodo.3572669, see also http://www.diracprogram.org).
  * Saue  _et al._ [2020] T. Saue, R. Bast, A. S. P. Gomes, H. J. A. Jensen, L. Visscher, I. A. Aucar, R. Di Remigio, K. G. Dyall, E. Eliav, E. Fasshauer, T. Fleig, L. Halbert, E. D. Hedegård, B. Helmich-Paris, M. Iliaš, C. R. Jacob, S. Knecht, J. K. Laerdahl, M. L. Vidal, M. K. Nayak, M. Olejniczak, J. M. H. Olsen, M. Pernpointner, B. Senjean, A. Shee, A. Sunaga, and J. N. P. van Stralen, J. Chem. Phys. 152, 204104 (2020).
  * Skripnikov [2021] L. V. Skripnikov, The Journal of Chemical Physics 154, 201101 (2021).
  * Pazyuk  _et al._ [2015] E. A. Pazyuk, A. V. Zaitsevskii, A. V. Stolyarov, M. Tamanis, and R. Ferber, Russ. Chem. Rev. 84, 1001 (2015).
  * Zaitsevskii  _et al._ [2017] A. Zaitsevskii, N. S. Mosyagin, A. V. Stolyarov, and E. Eliav, Phys. Rev. A 96, 022516 (2017).


11institutetext: Moscow institute of physics and technology, Dolgoprudny,
Institutskii ave., 9, Russia 11email:
<EMAIL_ADDRESS>22institutetext:
Skolkovo Institute of Science and Technology, Moscow, Russia 22email:
<EMAIL_ADDRESS>Weierstrass Institute for
Applied Analysis and Stochastics, Berlin, Germany 33email:
<EMAIL_ADDRESS>Institute for Information
Transmission Problems of the Russian Academy of Sciences (Kharkevich
Institute), Russia 55institutetext: Caucasus Mathematical Center, Adyghe State
University, Maikop, Russia

# Decentralized convex optimization under affine constraints for power systems
control††thanks: The work of D. Yarmoshik was supported by the program
“Leading Scientific Schools” (grant no. NSh-775.2022.1.1). The work of A.
Rogozin and A. Gasnikov was supported by Russian Science Foundation (project
No. 21-71- 30005).

Demyan Yarmoshik 11 0000-0003-1912-1040 Alexander Rogozin 11
1111-2222-3333-4444 Oleg. O. Khamisov 22 0000-0001-9015-9442 Pavel
Dvurechensky 33 0000-0003-1201-2343 Alexander Gasnikov 114455
0000-0002-7386-039X

###### Abstract

Modern power systems are now in continuous process of massive changes.
Increased penetration of distributed generation, usage of energy storage and
controllable demand require introduction of a new control paradigm that does
not rely on massive information exchange required by centralized approaches.
Distributed algorithms can rely only on limited information from neighbours to
obtain an optimal solution for various optimization problems, such as optimal
power flow, unit commitment etc.

As a generalization of these problems we consider the problem of decentralized
minimization of the smooth and convex partially separable function
$f=\sum_{k=1}^{l}f^{k}(x^{k},{\tilde{x}})$ under the coupled
$\sum_{k=1}^{l}(A^{k}x^{k}-b^{k})\leq 0$ and the shared
$\tilde{A}\tilde{x}-\tilde{b}\leq 0$ affine constraints, where the information
about $A^{k}$ and $b^{k}$ is only available for the $k$-th node of the
computational network.

One way to handle the coupled constraints in a distributed manner is to
rewrite them in a distributed-friendly form using the Laplace matrix of the
communication graph and auxiliary variables (Khamisov, CDC, 2017). Instead of
using this method we reformulate the constrained optimization problem as a
saddle point problem (SPP) and utilize the consensus constraint technique to
make it distributed-friendly. Then we provide a complexity analysis for state-
of-the-art SPP solving algorithms applied to this SPP.

###### Keywords:

Constrained convex optimization Distributed optimization Energy system
Distributed control Saddle point problem

##  1 Introduction

Optimal operation of power systems relies heavily on the ability of system
operator to solve efficiently a number of optimization problems such as
optimal power flow, unit commitment, as well as a number of online problems
such as frequency and voltage control. Traditionally such problems were solved
by System Operators in a centralized way. However, recent developments in
implementation of distributed energy sources, storage systems and possibility
of demand response can be effectively controlled by distributed algorithms.
Such approach has a number of potential benefits, namely reduction of
necessary communications between agents, increased robustness with respect to
malfunction of any agent and possibility to increase cybersecurity and privacy
of each agent.

The detailed surveys on the application of distributed algorithms in power
systems is given in [10, 14]. These applications often lead to the necessity
of solving an optimization problem, which can be formulated as distributed
optimization problem with coupled constraints. Distributed approaches for
optimization problems with coupled constraints can be separated into two main
groups: (i) primal, dual or primal-dual consensus algorithms [2, 9, 19, 8, 11,
12, 13]; (ii) ADMM-based algorithms [1, 16, 3, 18].

In this paper we propose a novel optimization approach for convex optimization
problems with coupled linear equality and inequality constraints. Here
introduction of specially placed Laplace matrices is used to model
communications between neighboring agents in a computational network described
as a connected graph. In the core of our approach lies: 1) the reduction of
the decentralized optimization problem with constraints to decentralized
saddle point problem; 2) applying decentralized Mirror Prox algorithm from
[15] to solve the obtained saddle point problem. We obtain the same rate of
convergence $\sim 1/N$ ($N$ – number of communication steps / oracle calls) as
the best known competitors, like ADMM [7]. The main benefit of our approach is
that the local optimization problem at each node is much simpler than in the
ADMM-based approaches since we use only gradient oracle instead of complicated
proximal mapping which may require a matrix inversion. Compared to the dual
algorithms of [11, 12, 13], we consider a more general setting in which the
objective may be non-separable and there are local linear constraints at each
node of the computational network.

##  2 Problem Statement

Let us consider the following optimization problem:

$\min_{x\in\mathbb{R}^{n}}f({\bf x}),$ (1a) $A^{\prime}{\bf
x}-b^{\prime}=0,\;A^{\prime}\in\mathbb{R}^{m\times
n},\;b^{\prime}\in\mathbb{R}^{m},$ (1b) $C^{\prime}{\bf x}-d^{\prime}\leq
0,\;C^{\prime}\in\mathbb{R}^{h\times n},\;d^{\prime}\in\mathbb{R}^{h},$ (1c)

where $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a differentiable strictly
convex function. It is assumed that constraints (1b) and (1c) are consistent
and there exists a unique solution $x^{*}$. Thus, Karush–Kuhn–Tucker (KKT)
conditions are necessary and sufficient optimality conditions.

Let us now consider the case, when problem (1) must be solved by a multi-agent
network with $l$ agents connected by a graph defined by a Laplacian matrix
$W$. For this case, we assume, that each agent seeks to find its own subvector
$x^{k}\in\mathbb{R}^{n_{k}}$, $k\in\\{1,\dots,l\\}$ ($\sum_{k=1}^{l}n_{k}=n$)
and the shared vector ${\tilde{x}}\in\mathbb{R}^{{\tilde{n}}}$. We denote
vector of private variables by ${\bf x}=(x^{1\top},\dots,x^{l\top})^{\top}$.
Additionally, function $f$ is partially separable:

$f({\bf x},{\tilde{x}})=\sum_{k=1}^{l}f^{k}(x^{k},{\tilde{x}})$

and each $f^{k}$ is known only to agent $k$. Each agent has partial
information $A^{k}\in\mathbb{R}^{m\times n_{k}}$, $b^{k}\in\mathbb{R}^{m}$,
$C^{k}\in\mathbb{R}^{h\times n_{k}}$ and $d^{k}\in\mathbb{R}^{h}$ about
constraints’ parts corresponding only to variables $x^{k}$:
$A\vcentcolon=[A^{1},\dots,A^{l},]$, $b\vcentcolon=\sum_{k=1}^{l}b^{k}$,
$C\vcentcolon=[C^{1},\dots,C^{l}]$ and $n\vcentcolon=\sum_{k=1}^{l}n_{k}$.
Additionally we assume that there are shared constraints with matrices
${\tilde{A}}\in\mathbb{R}^{{\tilde{m}}\times{\tilde{n}}}$,
${\tilde{C}}\in\mathbb{R}^{{\tilde{h}}\times{\tilde{n}}}$ and vectors
${\tilde{b}}\in\mathbb{R}^{{\tilde{m}}}$,
${\tilde{d}}\in\mathbb{R}^{{\tilde{h}}}$ which are known to all agents.

As a result, each agent $k$ has only its own part of the objective function
$f^{k}(x^{k},\tilde{x})$ and parts of the coupled equality and inequality
constraints respectively: $A^{k}x^{k}-b^{k}$ and $C^{k}x^{k}-d^{k}$.

Therefore, we have an optimization problem of the following form:

$\displaystyle\min_{x\in\mathbb{R}^{n+{\tilde{n}}}}~{}$
$\displaystyle\sum_{k=1}^{l}f^{k}(x^{k},{\tilde{x}}),$ (2a) s.t.
$\displaystyle\sum_{k=1}^{l}(A^{k}x^{k}-b^{k})=0,$ (2b)
$\displaystyle\sum_{k=1}^{l}(C^{k}x^{k}-d^{k})\leq 0,$ (2c)
$\displaystyle{\tilde{A}}{\tilde{x}}-{\tilde{b}}=0,$ (2d)
$\displaystyle{\tilde{C}}{\tilde{x}}-{\tilde{d}}\leq 0.$ (2e)

Here ${\tilde{x}}\in\mathbb{R}^{{\tilde{n}}}$ is a subvector of $x$ that
contains global variables used by all agents.

##  3 Mathematical setting

###### Assumption 3.1

For every $k=1,\ldots,l$

  1. 1.

$f^{k}(x^{k},{\tilde{x}})$ is differentiable.

  2. 2.

(Convexity) $\forall x^{k},x^{\prime
k}\in{\mathcal{X}}^{k},\forall{\tilde{x}},{\tilde{x}}^{\prime}\in\tilde{\mathcal{X}}$

$f^{k}(x^{\prime k},{\tilde{x}}^{\prime})\geq
f^{k}(x^{k},{\tilde{x}})+\left\langle\nabla
f^{k}(x^{k},{\tilde{x}}),\begin{pmatrix}x^{\prime k}-x^{k}\\\
{\tilde{x}}^{\prime}-{\tilde{x}}\end{pmatrix}\right\rangle.$

  3. 3.

(Lipschitz smoothness)

$\left\|\nabla f^{k}(x^{\prime k},{\tilde{x}}^{\prime})-\nabla
f^{k}(x^{k},{\tilde{x}})\right\|\leq L_{k}\left\|\begin{pmatrix}x^{\prime
k}-x^{k}\\\ {\tilde{x}}^{\prime}-{\tilde{x}}\end{pmatrix}\right\|.$

###### Assumption 3.2

Variable $x$ is subject to block constraints:
$x^{k}\in\prod_{i=1}^{n_{k}}[\xi^{k,i},\eta^{k,i}]={\mathcal{X}}^{k}$,
$\xi^{k,i},\eta^{k,i}\in\mathbb{R}$ and
${\tilde{x}}\in\prod_{i=1}^{{\tilde{n}}}[\tilde{\xi}^{i},\tilde{\eta}^{i}]=\tilde{\mathcal{X}}$,
$\tilde{\xi}^{i},\tilde{\eta}^{i}\in\mathbb{R}$ .

This is a natural assumption since in a real-world system maximal and minimal
values of every control and auxiliary variable are limited. Let us also denote

  * •

$\lambda_{max}(A),\lambda_{min}^{+}(A)$ — the largest and the smallest
positive eigenvalues of a matrix A.

  * •

$\sigma_{max}(A)=\sqrt{\lambda_{max}(A^{\top}A)}$ and
$\sigma^{+}_{min}(A)=\sqrt{\lambda^{+}_{min}(A^{\top}A)}$ — the largest and
the smallest positive singular value of a matrix A.

  * •

$\chi(A)=\frac{\sigma_{max}(A)}{\sigma^{+}_{min}(A)}$ — condition number of a
matrix $A$ on $\left(\operatorname{Ker}{A}\right)^{\top}$.

  * •

$\operatorname{Proj}_{S}(x)$ — projection of $x$ onto a set $S$.

The key instrument in separating shared variables and coupled constraints is
introducing the consensus constraint with the help of matrix $W$ defined as
follows:

  1. 1.

${W}$ is symmetric positive semi-definite matrix.

  2. 2.

(Network compatibility) For all $i,j=1,\dots,l$ the entry of $W$:
$[{W}]_{ij}=0$ if $i\neq j$ and there is no edge in the communication graph
between nodes $i$ and $j$. This property allows to perform multiplications by
$W$ in a distributed manner (only using information from neighbours in the
communication graph).

  3. 3.

(Kernel property) For any $v=[v_{1},\ldots,v_{m}]^{\top}\in\mathbb{R}^{m}$,
${W}v=0$ if and only if $v_{1}=\ldots=v_{m}$, i.e.
$\operatorname{Ker}{W}=\operatorname{span}\left\\{\mathbf{1}\right\\}$. This
property allows to rewrite pairwise equality constraint in a distributed way.

An example of matrix satisfying this assumption is the graph Laplacian
${W}{\in\mathbb{R}^{m\times m}}$:

$\displaystyle[W]_{ij}\triangleq\begin{cases}-1,&\text{if }(i,j)\in E,\\\
\text{deg}(i),&\text{if }i=j,\\\ 0,&\text{otherwise,}\end{cases}$

where $\text{deg}(i)$ is the degree of the node $i$, i.e., the number of
neighbors of the node.

Matrix $W$ can be used to rewrite pairwise equality of scalars. To rewrite
pairwise equality of vector variables with equal dimesion we will use the
following extension of matrix $W$, called communication matrix:

${\bf W}=W\otimes I_{d},$ (3)

where $\otimes$ denotes the Kronecker product and $d$ is the dimension of the
vector variables.

##  4 Distributed saddle point problem formulation

###  4.1 Saddle point problem and consensus constraints

We reformulate problem (1) as saddle point problem:

$\min_{{\bf x},{\tilde{x}}}\max_{\begin{subarray}{c}\lambda,\tilde{\lambda}\\\
\mu,\tilde{\mu}\geq
0\end{subarray}}\sum_{k=1}^{l}\left[f^{k}(x^{k},{\tilde{x}})+\lambda^{\top}(A^{k}x^{k}-b^{k})+\mu^{\top}(C^{k}x^{k}-d^{k})\right]+\\\
\tilde{\lambda}^{\top}({\tilde{A}}{\tilde{x}}-{\tilde{b}})+\tilde{\mu}^{\top}({\tilde{C}}{\tilde{x}}-{\tilde{d}}).$
(4)

Let us unify the analysis of equality and inequality constraints by stacking
Lagrange multipliers $\lambda$ and $\mu$ in a single dual variable

$y=\begin{pmatrix}\lambda\\\
\mu\end{pmatrix},~{}y\in{\mathcal{Y}}=\mathbb{R}^{m}\times\mathbb{R}^{h}_{+}.$

And similarly we introduce the joined dual variable for the coupled
constraints:

${\tilde{y}}=\begin{pmatrix}\tilde{\lambda}\\\
\tilde{\mu}\end{pmatrix},~{}{\tilde{y}}\in{\tilde{\mathcal{Y}}}=\mathbb{R}^{{\tilde{m}}}\times\mathbb{R}^{{\tilde{h}}}_{+}.$

To solve this saddle point problem in a distributed manner we have to separate
dual variables $y$ by making their copies at each node and introducing
consensus constraint into the saddle point problem, as described in [15]. That
brings us to the following formulation:

$\min_{{\bf x},{\tilde{x}},{\bf z}}\max_{{\bf
y},{\tilde{y}}}\sum_{k=1}^{l}\left[f^{k}(x^{k},{\tilde{x}})+y^{k\top}\begin{pmatrix}A^{k}x^{k}-b^{k}\\\
C^{k}x^{k}-d^{k}\end{pmatrix}\right]+{\bf z}^{\top}{\bf W}{\bf
y}+{\tilde{y}}^{\top}\begin{pmatrix}{\tilde{A}}{\tilde{x}}-{\tilde{b}}\\\
{\tilde{C}}{\tilde{x}}-{\tilde{d}}\end{pmatrix}$ (5)

To separate the terms corresponding to the shared constraints (2d), (2e) we
should go back to the optimization problem (2) and do the same trick with
them: make a copy of ${\tilde{x}}$ at each node and introduce consensus
constraint. So we transform (2d), (2e) into equivalent system

$\displaystyle{\tilde{A}}{\tilde{x}}^{k}+{\tilde{b}}=0,\;k\in\\{1,\ldots,l\\},$
(6a) $\displaystyle{\tilde{C}}{\tilde{x}}^{k}+{\tilde{d}}\leq
0,\;k\in\\{1,\ldots,l\\},$ (6b) $\displaystyle{\tilde{\bf W}}{\tilde{\bf
x}}=0,$ (6c)

where ${\tilde{\bf
x}}=({\tilde{x}}^{1\top},\dots,{\tilde{x}}^{l\top})^{\top},\;{\tilde{\bf
W}}=W\otimes I_{\tilde{n}}$.

Note, that each node can handle constraints (6a) and (6b) independently, so we
don’t have to introduce additional consensus constraints over corresponding
dual variables in the final saddle point problem:

$\min_{{\bf x},{\tilde{\bf x}},{\bf z}}\max_{{\bf y},{\tilde{\bf
y}},{\tilde{\bf
z}}}\sum_{k=1}^{l}\left[f^{k}(x^{k},{\tilde{x}}^{k})+y^{k\top}\begin{pmatrix}A^{k}x^{k}-b^{k}\\\
C^{k}x^{k}-d^{k}\end{pmatrix}+{\tilde{y}}^{k\top}\begin{pmatrix}{\tilde{A}}{\tilde{x}}^{k}-{\tilde{b}}\\\
{\tilde{C}}{\tilde{x}}^{k}-{\tilde{d}}\end{pmatrix}\right]+{\bf z}^{\top}{\bf
W}{\bf y}+{\tilde{\bf z}}^{\top}{\tilde{\bf W}}{\tilde{\bf x}}\\\ =\min_{{\bf
x},{\tilde{\bf x}},{\bf z}}\max_{{\bf y},{\tilde{\bf y}},{\tilde{\bf
z}}}\sum_{k=1}^{l}g^{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k})+{\bf
z}^{\top}{\bf W}{\bf y}+{\tilde{\bf z}}^{\top}{\tilde{\bf W}}{\tilde{\bf x}},$
(7)

where ${\bf y}=(y^{1\top},\ldots,y^{l\top})^{\top}$, ${\bf W}=W\otimes
I_{m+h}$.

We will also use the following notation:

$G({\bf x},{\tilde{\bf x}},{\bf y},{\tilde{\bf
y}})=\sum_{k=1}^{l}g^{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k}),$ (8)

and

$G_{w}({\bf x},{\tilde{\bf x}},{\bf y},{\tilde{\bf y}})=G({\bf x},{\tilde{\bf
x}},{\bf y},{\tilde{\bf y}})+{\bf z}^{\top}{\bf W}{\bf y}+{\tilde{\bf
z}}^{\top}{\tilde{\bf W}}{\tilde{\bf x}}.$ (9)

###  4.2 Comparison with [4], [5]

In this subsection we show the equivalence of our approach and approach from
[4], [5] from the perspective of saddle point problems. Since the shared
variables ${\tilde{x}}$ are handled in the same way in both approaches (by
introducing the constraint ${\tilde{\bf W}}{\tilde{\bf x}}=0$ into the
optimization problem), we consider the case without shared variables and only
with equality-type constraints to simplify the derivations.

Let us introduce a set of new matrices and vectors:

$\begin{gathered}{\bf A}=\operatorname{diag}(A^{1},\dots,A^{l}),{\bf
b}=(b^{1\top},\dots,b^{l\top})^{\top},\\\ \end{gathered}$ (10)
$\begin{gathered}W^{mk}=\operatorname{diag}(W_{k\bullet},\dots,W_{k\bullet})\in\mathbb{R}^{m\times
ml},{\bf W}^{m}=\left[\begin{array}[]{c}W^{m1}\\\ \vdots\\\
W^{ml}\end{array}\right]\in\mathbb{R}^{ml\times ml},\\\ \end{gathered}$ (11)

In [4], [5] the following distributed-friendly reformulation of problem (2) is
proposed, and its equivalence to the original problem is shown:

$\min_{{\bf x}\in\mathbb{R}^{n},{\bf y}\in\mathbb{R}^{ml}}\left\\{f({\bf
x})=\sum_{k=1}^{l}f^{k}(x^{k})\right\\},$ (12a) ${\bf A}{\bf x}-{\bf b}+{\bf
W}^{m}{\bf y}=0.$ (12b)

Here a sort of consensus constraint is integrated directly into the
minimization problem, which differs from our technique of adding consensus
constraint into the corresponding saddle point problem. Note also that ${\bf
W}^{m}$ and ${\bf W}$ differ in their structure (the way of constructing
matrix $W$ for using it with multi-dimensional variables).

The saddle point problem corresponding to the minimization problem (12) is

$\min_{{\bf x},{\bf y}}\max_{{\bf z}}L({\bf x},{\bf y},{\bf z})=\min_{{\bf
x},{\bf y}}\max_{{\bf z}}f({\bf x})+{\bf z}^{\top}\left({\bf A}{\bf x}-{\bf
b}+{\bf W}^{m}{\bf y}\right).$ (13)

Let us now compare this problem with the saddle point problem (7). By
rewriting sum in (7) and using the symmetry of ${\bf W}$ we have

$\displaystyle\min_{{\bf x},{\bf z}}$ $\displaystyle\max_{\bf
y}\sum_{k=1}^{l}\left[f^{k}(x^{k})+y^{k\top}(A^{k}x^{k}-b^{k})\right]+{\bf
z}^{\top}{\bf W}{\bf y}$ $\displaystyle=\min_{{\bf x},{\bf z}}\max_{{\bf
y}}f({\bf x})+{\bf y}^{\top}({\bf A}{\bf x}-{\bf b})+{\bf z}^{\top}{\bf W}{\bf
y}$ $\displaystyle=\min_{{\bf x},{\bf z}}\max_{{\bf y}}f({\bf x})+{\bf
y}^{\top}({\bf A}{\bf x}-{\bf b}+{\bf W}{\bf z}).$ (14)

Since ${\bf W}$ and ${\bf W}^{m}$ differ only in the arrangement of columns,
problems (13) and (4.2) differ only in the arrangement of components of
maximized variables. Therefore, both approaches leads to the same saddle point
problem.

##  5 Algorithm

We use classical Extragradient algorithm from [6]. Being applied to the
problem (7) it converges to the solutions of the primal and the dual problems
as will be shown in the next sections. Here we describe it in an explicit
form, so it is ready to be applied to the problem (2), see Algorithm 1.

Note, that the projection in our case is a simple clipping and can be
performed independently for each component of the variable.

Algorithm 1 Decentralized Extragradient for problem (2)

1: Initialize ${\bf x}_{0}\in{\mathcal{X}},{\bf y}_{0}={\bf
z}_{0}=\vec{0}_{l(m+h)},{\tilde{\bf
x}}_{0}\in{\tilde{\mathcal{X}}}^{l},{\tilde{\bf
y}}=\vec{0}_{l({\tilde{m}}+{\tilde{h}})},{\tilde{\bf
z}}_{0}=\vec{0}_{l{\tilde{n}}}$

2: for $i=0,\ldots,N-1$ do

3: Compute ${\bf z}^{\prime}_{i}={\bf W}{\bf z}_{i}$, ${\bf
y}^{\prime}_{i}={\bf W}{\bf y}_{i}$, ${\tilde{\bf z}}^{\prime}_{i}={\tilde{\bf
W}}{\tilde{\bf z}}_{i}$, ${\tilde{\bf x}}^{\prime}_{i}={\tilde{\bf
W}}{\tilde{\bf x}}_{i}$.

4: Make intermediate gradient step  $\displaystyle
x_{{i+\frac{1}{2}}}^{k}=\operatorname{Proj}_{\mathcal{X}}\left(x^{k}_{i}-h\nabla_{x^{k}}f^{k}(x_{i}^{k},{\tilde{x}}_{i}^{k})-h(A^{k\top},C^{k\top})y^{k}_{i}\right)$
$\displaystyle{\tilde{x}}_{i+\frac{1}{2}}^{k}=\operatorname{Proj}_{\tilde{\mathcal{X}}}\left({\tilde{x}}^{k}_{i}-h\nabla_{{\tilde{x}}^{k}}f^{k}(x_{i}^{k},{\tilde{x}}_{i}^{k})-h{\tilde{z}}^{\prime
k}_{i}\right)$ $\displaystyle
y_{i+\frac{1}{2}}^{k}=\operatorname{Proj}_{\mathcal{Y}}\left(y^{k}_{i}+h\begin{pmatrix}A^{k}x_{i}^{k}-b^{k}\\\
C^{k}x_{i}^{k}-d^{k}\end{pmatrix}+hz^{\prime k}_{i}\right)$
$\displaystyle{\tilde{y}}_{i+\frac{1}{2}}^{k}=\operatorname{Proj}_{\tilde{\mathcal{Y}}}\left({\tilde{y}}^{k}_{i}+h\begin{pmatrix}{\tilde{A}}^{k}{\tilde{x}}_{i}^{k}-{\tilde{b}}^{k}\\\
{\tilde{C}}^{k}{\tilde{x}}_{i}^{k}-{\tilde{d}}^{k}\end{pmatrix}\right)$
$\displaystyle z_{i+\frac{1}{2}}^{k}=z^{k}_{i}-hy^{\prime k}_{i}$
$\displaystyle{\tilde{z}}_{i+\frac{1}{2}}^{k}={\tilde{z}}^{k}_{i}+h{\tilde{x}}^{\prime
k}_{i}$

5: Compute ${\bf z}^{\prime}_{i+\frac{1}{2}}={\bf W}{\bf z}_{i+\frac{1}{2}}$,
${\bf y}^{\prime}_{i+\frac{1}{2}}={\bf W}{\bf y}_{i+\frac{1}{2}}$,
${\tilde{\bf z}}^{\prime}_{i+\frac{1}{2}}={\tilde{\bf W}}{\tilde{\bf
z}}_{i+\frac{1}{2}}$, ${\tilde{\bf x}}^{\prime}_{i+\frac{1}{2}}={\tilde{\bf
W}}{\tilde{\bf x}}_{i+\frac{1}{2}}$.

6: Make gradient step  $\displaystyle
x_{i+1}^{k}=\operatorname{Proj}_{\mathcal{X}}\left(x^{k}_{i}-h\nabla_{x^{k}}f^{k}(x_{i+\frac{1}{2}}^{k},{\tilde{x}}_{i+\frac{1}{2}}^{k})-h(A^{k\top},C^{k\top})y^{k}_{i+\frac{1}{2}}\right)$
$\displaystyle{\tilde{x}}_{i+1}^{k}=\operatorname{Proj}_{\tilde{\mathcal{X}}}\left({\tilde{x}}^{k}_{i}-h\nabla_{{\tilde{x}}^{k}}f^{k}(x_{i+\frac{1}{2}}^{k},{\tilde{x}}_{i+\frac{1}{2}}^{k})-h{\tilde{z}}^{\prime
k}_{i+\frac{1}{2}}\right)$ $\displaystyle
y_{i+1}^{k}=\operatorname{Proj}_{\mathcal{Y}}\left(y^{k}_{i}+h\begin{pmatrix}A^{k}x_{i+\frac{1}{2}}^{k}-b^{k}\\\
C^{k}x_{i+\frac{1}{2}}^{k}-d^{k}\end{pmatrix}+hz^{\prime
k}_{i+\frac{1}{2}}\right)$
$\displaystyle{\tilde{y}}_{i+1}^{k}=\operatorname{Proj}_{\tilde{\mathcal{Y}}}\left({\tilde{y}}^{k}_{i}+h\begin{pmatrix}{\tilde{A}}^{k}{\tilde{x}}_{i+\frac{1}{2}}^{k}-{\tilde{b}}^{k}\\\
{\tilde{C}}^{k}{\tilde{x}}_{i+\frac{1}{2}}^{k}-{\tilde{d}}^{k}\end{pmatrix}\right)$
$\displaystyle z_{i+1}^{k}=z^{k}_{i}-hy^{\prime k}_{i+\frac{1}{2}}$
$\displaystyle{\tilde{z}}_{i+1}^{k}={\tilde{z}}^{k}_{i}+h{\tilde{x}}^{\prime
k}_{i+\frac{1}{2}}$

7: end for

7: For ${\bf t}\in\left\\{{\bf x},{\bf y},{\bf z},{\tilde{\bf x}},{\tilde{\bf
y}},{\tilde{\bf z}}\right\\}$ compute $\displaystyle\widehat{\bf
t}^{N}=\frac{1}{N}\sum_{k=0}^{N-1}{\bf t}^{k+\frac{1}{2}}$.

##  6 Smoothness and domain size analysis

In this section we will perform some technical analysis to obtain the
relations between parameters of the input data to the problem (object
functions and constrains) and parameters of Extragradient’s convergence rate.

###  6.1 Bounds on $\|y^{*}\|$, $\|{\tilde{y}}^{*}\|$

To calculate Lipschitz smoothness constants of the problem we have to localize
$y^{*}$ (dual part of solution of the initial saddle problem (4), which is
also a solution to the dual problem under our assumptions), i.e. find $R_{y}$
such that ${\mathcal{Y}}$ lies in a ball in $\mathbb{R}^{m}$ with center in
$0$ and radius $R_{y}$, and $y^{*}\in{\mathcal{Y}}$. From optimality
conditions for dual problem of (2)

$\nabla_{\bf x}L=\nabla_{\bf x}f+(A^{\top},C^{\top})y^{*}=0$ (15)
$\nabla_{{\tilde{x}}}L=\nabla_{{\tilde{x}}}f+({\tilde{A}}^{\top},{\tilde{C}}^{\top}){\tilde{y}}^{*}=0.$
(16)

Since for any $y\in\ker{A^{T}}$ vector $y^{*}+y$ is also a solution, we
consider only solution with the smallest norm (it’s enough for saddle point
problem solution’s quality criteria and convergence analysis), i. e.
$y^{*}\in\left(\ker{A^{T}}\right)^{\bot}$.

Therefore

$\|y^{*}\|^{2}\leq\frac{\|\nabla_{\bf x}f({\bf
x}^{*},{\tilde{x}}^{*})\|^{2}}{(\sigma_{min}^{+}\left((A^{\top},C^{\top})\right))^{2}},$
$\|{\tilde{y}}^{*}\|^{2}\leq\frac{\|\nabla_{{\tilde{x}}}f({\bf
x}^{*},{\tilde{x}}^{*})\|^{2}}{(\sigma_{min}^{+}(({\tilde{A}}^{\top},{\tilde{C}}^{\top})))^{2}},$

where $\sigma_{min}^{+}(A)=\sqrt{\min\\{\lambda>0:\exists x\neq
0:AA^{T}x=\lambda x\\}}$. Hence we get

###### Lemma 1

Saddle point problem (7), which is unconstrained on variables ${\bf
y},{\tilde{\bf y}}$, is equivalent to the same problem with constraints
$\|{\bf y}\|\leq R_{\bf y}$ and $\|{\tilde{\bf y}}\|\leq R_{{\tilde{\bf y}}}$,
where

$R_{\bf y}=\sqrt{l}~{}\frac{\max\limits_{{\bf
x}\in{\mathcal{X}},{\tilde{x}}\in{\tilde{\mathcal{X}}}}\|\nabla_{\bf x}f({\bf
x},{\tilde{x}})\|}{\sigma_{min}^{+}\left((A^{\top},C^{\top})\right)},R_{{\tilde{\bf
y}}}=\sqrt{l}~{}\frac{\max\limits_{{\bf
x}\in{\mathcal{X}},{\tilde{x}}\in{\tilde{\mathcal{X}}}}\|\nabla_{{\tilde{x}}}f({\bf
x},{\tilde{x}})\|}{\sigma_{min}^{+}\left(({\tilde{A}}^{\top},{\tilde{C}}^{\top})\right)}.$
(17)

###  6.2 Bounds on $\|z^{*}\|$, $\|{\tilde{z}}^{*}\|$

Next we want to find constants for Euclidean-case bounds for Theorem 3.5 [15].
To specify, how the convergence rate depends on problem’s parameters, we need
to find scalars $M_{y},M_{{\tilde{x}}},L_{xx},L_{yx},L_{xy}L_{yy}$, determined
by inequalities

$\displaystyle\|\nabla_{y}g^{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k})\|\leq
M_{y}~{}\forall k,x_{k}\in{\mathcal{X}}_{k},y_{k}\in{\mathcal{Y}}$ (18a)
$\displaystyle\|\nabla_{{\tilde{x}}}g_{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k})\|\leq
M_{{\tilde{x}}}~{}\forall k,x_{k}\in{\mathcal{X}}_{k},y_{k}\in{\mathcal{Y}}$
(18b) $\displaystyle\|\nabla_{x}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{x}G({\overline{\bf x}}^{\prime},{\overline{\bf y}})\|\leq
L_{xx}\|{\overline{\bf x}}-{\overline{\bf
x}}^{\prime}\|~{}\forall{\overline{\bf x}},{\overline{\bf
x}}^{\prime}\in{\overline{\mathcal{X}}},{\overline{\bf
y}}\in{\overline{\mathcal{Y}}}$ (18c)
$\displaystyle\|\nabla_{x}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{x}G({\overline{\bf x}},{\overline{\bf y}}^{\prime})\|\leq
L_{xy}\|{\overline{\bf y}}-{\overline{\bf
y}}^{\prime}\|~{}\forall{\overline{\bf
x}}\in{\overline{\mathcal{X}}},{\overline{\bf y}},{\overline{\bf
y}}^{\prime}\in{\overline{\mathcal{Y}}}$ (18d)
$\displaystyle\|\nabla_{y}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{y}G({\overline{\bf x}}^{\prime},{\overline{\bf y}})\|\leq
L_{yx}\|{\overline{\bf x}}-{\overline{\bf
x}}^{\prime}\|~{}\forall{\overline{\bf x}},{\overline{\bf
x}}^{\prime}\in{\overline{\mathcal{X}}},~{}\forall{\overline{\bf
y}}\in{\overline{\mathcal{Y}}}$ (18e)
$\displaystyle\|\nabla_{y}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{y}G({\overline{\bf x}},{\overline{\bf y}}^{\prime})\|\leq
L_{yy}\|{\overline{\bf y}}-{\overline{\bf
y}}^{\prime}\|~{}\forall{\overline{\bf
x}}\in{\overline{\mathcal{X}}},~{}\forall{\overline{\bf y}},{\overline{\bf
y}}^{\prime}\in{\overline{\mathcal{Y}}},$ (18f)

where ${\overline{\bf x}}=({\bf x}^{\top},{\tilde{\bf x}}^{\top})^{\top}$ and
${\overline{\bf y}}=({\bf y}^{\top},{\tilde{\bf y}}^{\top})^{\top}$

By using the triangle inequality

$\|\nabla_{y^{k}}g^{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k})\|=\|\nabla_{y^{k}}y^{\top}(A^{k}x^{k}-b^{k})\|=\left\|\begin{pmatrix}A^{k}x^{k}-b^{k}\\\
C^{k}x^{k}-d^{k}\end{pmatrix}\right\|\leq\\\
\max_{{k\in\\{1,\ldots,l\\}}}\left\\{\sigma_{max}\left(({A^{k}}^{\top},{C^{k}}^{\top})\right)R_{x^{k}}+\left\|({b^{k}}^{\top},{d^{k}}^{\top})\right\|\right\\}=M_{y},$

and

$\|\nabla_{{\tilde{x}}^{k}}g^{k}(x^{k},{\tilde{x}}^{k},y^{k},{\tilde{y}}^{k})\|=\|\begin{pmatrix}{{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top}\end{pmatrix}{\tilde{y}}^{k}\|\leq\sigma_{max}\left(\begin{pmatrix}{{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top}\;\end{pmatrix}\right)R_{{\tilde{y}}}\\\
=\chi\left(({{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top})\right)\max\limits_{{\bf
x}\in{\mathcal{X}},{\tilde{x}}\in{\tilde{\mathcal{X}}}}\|\nabla_{{\tilde{x}}}f({\bf
x},{\tilde{x}})\|=M_{{\tilde{x}}}.$

Then by directly applying Lemma 4.2 in [15] we have

###### Lemma 2

Saddle point problem (7), which is unconstrained on variables ${\bf
z},{\tilde{\bf z}}$, is equivalent to the same problem with constraints
$\|{\bf z}\|\leq R_{\bf z}$ and $\|{\tilde{\bf z}}\|\leq R_{{\tilde{\bf z}}}$,
where

$R_{\bf z}=\frac{\sqrt{2l}M_{y}}{\lambda_{min}^{+}({\bf W})},R_{{\tilde{\bf
z}}}=\frac{\sqrt{2l}M_{{\tilde{\bf x}}}}{\lambda_{min}^{+}({\tilde{\bf W}})}.$
(19)

###  6.3 Smoothness constants

Let us find smoothness constants of function $G$. From (7) we have

$\nabla_{x}G({\overline{\bf x}},{\overline{\bf y}})-\nabla_{x}G({\overline{\bf
x}}^{\prime},{\overline{\bf y}})=\begin{pmatrix}\nabla
f^{1}(x^{1},{\tilde{x}}^{1})-\nabla
f^{1}(x^{1^{\prime}},{\tilde{x}}^{1^{\prime}})\\\ \vdots\\\ \nabla
f^{l}(x^{l},{\tilde{x}}^{l})-\nabla
f^{l}(x^{l^{\prime}},{\tilde{x}}^{l^{\prime}})\\\ \end{pmatrix}.$

By Assumption 3.1

$\displaystyle\|\nabla_{x}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{x}G({\overline{\bf x}}^{\prime},{\overline{\bf
y}})\|^{2}=\sum_{k=1}^{l}\|\nabla f^{k}(x^{k},{\tilde{x}}^{k})-\nabla
f^{k}(x^{k^{\prime}},{\tilde{x}}^{k^{\prime}})\|^{2}$
$\displaystyle\leq\sum_{k=1}^{l}L_{k}^{2}\left\|\begin{pmatrix}x^{\prime
k}-x^{k}\\\
{\tilde{x}}^{\prime}-{\tilde{x}}\end{pmatrix}\right\|^{2}\leq\max_{k}L_{k}^{2}\|{\overline{\bf
x}}-{\overline{\bf x}}^{\prime}\|^{2}.$

Taking square root from both parts of the inequality we get

$L_{xx}=\max_{k\in\\{1,\ldots,l\\}}L_{k}.$

Similarly, for other variables

$\nabla_{x}G({\overline{\bf x}},{\overline{\bf y}})-\nabla_{x}G({\overline{\bf
x}},{\overline{\bf
y}}^{\prime})=\begin{pmatrix}({A}^{\top},{C}^{\top})\;(y-y^{\prime})\\\
\begin{pmatrix}{{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top}\;\end{pmatrix}({\tilde{y}}^{l}-{\tilde{y}}^{l^{\prime}})\\\
\end{pmatrix},$ $\nabla_{y}G({\overline{\bf x}},{\overline{\bf
y}})-\nabla_{y}G({\overline{\bf x}}^{\prime},{\overline{\bf
y}})=\begin{pmatrix}({A^{1}}^{\top},{C^{1}}^{\top})^{\top}(x^{1}-x^{1^{\prime}})\\\
\vdots\\\ ({A^{l}}^{\top},{C^{l}}^{\top})^{\top}(x^{l}-x^{l^{\prime}})\\\
\begin{pmatrix}{{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top}\;\end{pmatrix}^{\top}({\tilde{x}}^{1}-{\tilde{x}}^{1^{\prime}})\\\
\vdots\\\
\begin{pmatrix}{{\tilde{A}}}^{\top},{{\tilde{C}}}^{\top}\;\end{pmatrix}^{\top}({\tilde{x}}^{l}-{\tilde{x}}^{l^{\prime}})\end{pmatrix}.$

and

$L_{xy}=\max\left\\{\max_{k\in\\{1,\ldots,l\\}}\sigma_{max}\left(({A^{k}}^{\top},{C^{k}}^{\top})\right),\;\sigma_{max}\left(({\tilde{A}}^{\top},{\tilde{C}}^{\top})\right)\right\\}=L_{yx},$

$\displaystyle L_{yy}=0.$

##  7 Main result

Let us denote

$\displaystyle L_{\zeta}=2\cdot\text{max}\\{$ $\displaystyle R^{2}_{{\bf
x}{\tilde{\bf x}}}L_{x{\tilde{x}},x{\tilde{x}}},\;R^{2}_{{\bf y}{\tilde{\bf
y}}}L_{y{\tilde{y}},y{\tilde{y}}},\;$ $\displaystyle\sqrt{2}R_{{\bf
x}{\tilde{\bf x}}}R_{{\bf y}{\tilde{\bf
y}}}L_{x{\tilde{x}},y{\tilde{y}}}+2M_{{\bf x}{\tilde{\bf x}}}R_{{\bf
x}{\tilde{\bf x}}}\frac{\lambda_{\max}(\tilde{\bf
W})}{\lambda_{\min}^{+}(\tilde{\bf W})}+2M_{{\bf y}{\tilde{\bf y}}}R_{{\bf
y}{\tilde{\bf y}}}\frac{\lambda_{\max}({\bf W})}{\lambda_{\min}^{+}({\bf
W})}\\}.$

Then, following the arguments presented in Theorem 3.5 from [15], we introduce
$\zeta=({\bf x}^{\top},{\tilde{\bf x}}^{\top},{\bf y}^{\top},{\tilde{\bf
y}}^{\top},{\bf z}^{\top},{\bf z}^{\top})^{\top}$. We also define a norm for
$\zeta$ as follows:

$\displaystyle\left\|\zeta\right\|^{2}=\frac{\left\|{\bf
x}\right\|^{2}}{R_{\bf x}^{2}}+\frac{\left\|{\tilde{\bf
x}}\right\|^{2}}{R_{\tilde{\bf x}}^{2}}+\frac{\left\|{\bf
y}\right\|^{2}}{R_{\bf y}^{2}}+\frac{\left\|{\tilde{\bf
y}}\right\|^{2}}{R_{\tilde{\bf y}}^{2}}+\frac{\left\|{\bf z}\right\|}{R_{\bf
z}^{2}}+\frac{\left\|{\tilde{\bf z}}\right\|^{2}}{R_{\tilde{\bf z}}^{2}}$

According to the standard analysis of Mirror-Prox algorithm, the duality gap
is bounded as follows:

$G_{w}({\bf x}_{N},{\tilde{\bf x}}_{N},{\bf z}_{N},{\bf y},{\tilde{\bf
y}},{\tilde{\bf z}})-G_{w}({\bf x},{\tilde{\bf x}},{\bf z},{\bf
y}_{N},{\tilde{\bf y}}_{N},{\tilde{\bf
z}}_{N})\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{L_{\zeta}}{2N}\left\|\zeta-\zeta_{0}\right\|^{2}},$
(20)

Substituting ${\bf y}=0,{\tilde{\bf y}}=0,{\tilde{\bf z}}=0,{\bf x}={\bf
x}_{*},{\tilde{\bf x}}={\tilde{\bf x}}_{*},{\bf z}=0$ we get complexity
estimate by function residual:

$\sum_{k=1}^{\ell}f(x_{N}^{k},{\tilde{x}}_{N}^{k})-\sum_{k=1}^{\ell}f(x_{*}^{k},{\tilde{x}}_{*})\leq\frac{3L_{\zeta}}{N}.$
(21)

Analogously, we obtain bounds for affine constraints and consensus constraints

$\displaystyle\left\|Ax_{N}-b\right\|+\left\|Cx_{N}-d\right\|$
$\displaystyle\leq\frac{17\sqrt{2}L_{\zeta}}{N}\min_{k=1,\ldots,l}\sigma_{\min}^{+}({A^{k}}^{\top},{C^{k}}^{\top}),$
$\displaystyle\left\|\tilde{\bf A}{\tilde{\bf x}}-{\bf
b}\right\|+\left\|\tilde{\bf C}{\tilde{\bf x}}-{\bf d}\right\|$
$\displaystyle\leq\frac{17\sqrt{2}L_{\zeta}}{N}\min_{k=1,\ldots,\ell}\sigma_{\min}^{+}({\tilde{\bf
A}}^{\top},{\tilde{\bf C}}^{\top}),$ $\displaystyle\left\|{\bf W}{\bf
y}_{N}\right\|$
$\displaystyle\leq\frac{17\sqrt{2}L_{\zeta}}{2N}\lambda_{\min}^{+}({\bf W}),$
$\displaystyle\left\|{\tilde{\bf W}}{\tilde{\bf x}}_{N}\right\|$
$\displaystyle\leq\frac{17\sqrt{2}L_{\zeta}}{2N}\lambda_{\min}^{+}({\tilde{\bf
W}}).$

###### Remark 1

In the problem formulation (2) we can additionally assume that $x^{k}\in
Q^{k}\subseteq\mathbb{R}^{n_{k}}$,
$\tilde{x}\in\tilde{Q}\subseteq\mathbb{R}^{\tilde{n}}$, where $Q^{k}$ and
$\tilde{Q}$ – simple convex sets, i.e. simplex, ball, half plane e.t.c. In
this case instead of decentralized Extragradient method for saddle point
problem (Mirror Prox with euclidian prox-function) one should use general
decentralized Mirror Prox algorithm [15].

##  8 Numerical experiment

For the purpose of numerical experiment data is taken from [17]. Here 6 bus
system contains 2 generators. DC optimal power flow problem of the following
form is considered:

$\min_{\begin{subarray}{c}p^{G}\in{\mathcal{P}}\\\
\theta\in\Theta,\end{subarray}}\sum_{i\in G}c_{i}(p^{G}_{i})$ (22a)
$p^{G}_{i}-p^{D}_{i}=B_{ij}(\theta_{i}-\theta_{j}),$ (22b)
$\left|(\theta_{i}-\theta_{j})/X_{ij}\right|\leq F^{max}_{ij}.$ (22c)

Optimization variables:

  * •

$p^{G}_{i},\;i\in\\{1,\ldots,l\\}$ — generator power output;

  * •

$\theta_{i},\;i\in\\{1,\ldots,l\\}$ — phase angle of the bus $i$.

Parameters:

  * •

${\mathcal{P}}=\prod_{i=1}^{l}\left[p^{G,\min}_{i},~{}p^{G,\max}_{i}\right]$ —
minimal and maximal generation. For nodes without generation
$p^{G,\min}_{i}=p^{G,\max}_{i}=0$.

  * •

$\Theta=\prod_{i=1}^{l}\left[-\theta^{max}_{i},~{}\theta^{max}_{i}\right]$ —
maximal phase angle

  * •

$p^{D}_{i},\;i\in\\{1,\ldots,l\\}$ — demand;

  * •

$B_{ij}=B_{ji},\;i,j\in\\{1,\ldots,l\\}$ — line susceptances. If no power line
between nodes $i$ and $j$ then $B_{ij}=0$ else $B_{ij}>0$.
$X_{ij}=-B_{ij},\;i,j\in\\{1,\ldots,l\\}$ are line reactances;

  * •

$F^{max}_{ij},\;i,j\in\\{1,\ldots,l\\}$ — maximal power flow on the line
$(i,j)$;

Cost functions:

$c_{i}(\cdot),\;i\in\\{1,\ldots,l\\}$ — convex sufficiently smooth functions,
representing the cost of operating a generator at given power.

The obtained results are consistent with the results in [17]: generation is
equal to 110 MW and 200 MW for the 1-st and 2-nd generators respectively. The
results of numerical experiment are given in Fig. 1. Here the plots of
function value and constraint residual convergence.

Figure 1: Results of the numerical experiment for DC optimal power flow
problem on 6-bus system [17]

## References

  * [1] Erseghe, T.: Distributed optimal power flow using admm. IEEE Transactions on Power Systems 29(5), 2370–2380 (Sep 2014). https://doi.org/10.1109/TPWRS.2014.2306495
  * [2] Falsone, A., Margellos, K., Garatti, S., Prandini, M.: Dual decomposition for multi-agent distributed optimization with coupling constraints. Automatica 84, 149–158 (2017)
  * [3] Falsone, A., Notarnicola, I., Notarstefano, G., Prandini, M.: Tracking-admm for distributed constraint-coupled optimization. Automatica 117, 1–13 (202)
  * [4] Khamisov, O.O.: Direct disturbance based decentralized frequency control for power systems. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC). pp. 3271–3276 (Dec 2017). https://doi.org/10.1109/CDC.2017.8264139
  * [5] Khamisov, O.O., Chernova, T., Bialek, J.W.: Comparison of two schemes for closed-loop decentralized frequency control and overload alleviation. In: 2019 IEEE Milan PowerTech. pp. 1–6 (June 2019). https://doi.org/10.1109/PTC.2019.8810926
  * [6] Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976)
  * [7] Lan, G.: First-order and stochastic optimization methods for machine learning. Springer (2020)
  * [8] Liang, S., Wang, L.Y., Yin, G.: Distributed smooth convex optimization with coupled constraints. IEEE Transactions on Automatic Control 65, 347–353 (Jan 2020)
  * [9] Liang, S., Zheng, X., Y.Hong: Distributed ninsmooth optimization with coupled inequality constraints via modified lagrangian function. IEEE Transaction on Automatic Control 63, 1753–1759 (2018)
  * [10] Molzahn, D.K., Dörfler, F., Sandberg, H., Low, S.H., Chakrabarti, S., Baldick, R., Lavaei, J.: A survey of distributed optimization and control algorithms for electric power systems. IEEE Transactions on Smart Grid 8(6), 2941–2962 (Nov 2017). https://doi.org/10.1109/TSG.2017.2720471
  * [11] Necoara, I., Nedelcu, V.: Distributed dual gradient methods and error bound conditions. arXiv:1401.4398 (2014)
  * [12] Necoara, I., Nedelcu, V.: On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems. Automatica 55, 209–216 (2015). https://doi.org/https://doi.org/10.1016/j.automatica.2015.02.038, https://www.sciencedirect.com/science/article/pii/S0005109815001004
  * [13] Necoara, I., Nedelcu, V., Dumitrache, I.: Parallel and distributed optimization methods for estimation and control in networks. Journal of Process Control 21(5), 756–766 (2011). https://doi.org/https://doi.org/10.1016/j.jprocont.2010.12.010, https://www.sciencedirect.com/science/article/pii/S095915241000257X, special Issue on Hierarchical and Distributed Model Predictive Control
  * [14] Patari, N., Venkataramanan, V., Srivastava, A., Molzahn, D.K., Li, N., Annaswamy, A.: Distributed optimization in distribution systems: Use cases, limitations, and research needs. IEEE Transactions on Power Systems pp. 1–1 (2021). https://doi.org/10.1109/TPWRS.2021.3132348
  * [15] Rogozin, A., Beznosikov, A., Dvinskikh, D., Kovalev, D., Dvurechensky, P., Gasnikov, A.: Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07758 (2021)
  * [16] Rostampour, V., Haar, O.t., Keviczky, T.: Distributed stochastic reserve scheduling in ac power systems with uncertain generation. IEEE Transactions on Power Systems 34(2), 1005–1020 (2019). https://doi.org/10.1109/TPWRS.2018.2878888
  * [17] Wang, Y., Wu, L., Wang, S.: A fully-decentralized consensus-based admm approach for dc-opf with demand response. IEEE Transactions on Smart Grid 8(6), 2637–2647 (2017). https://doi.org/10.1109/TSG.2016.2532467
  * [18] Wnag, Z., Ong, C.J.: Distributed model predictive control of linear descrete-times systems with local and global cosntraints. Automatica 81, 184–195 (2017)
  * [19] Yuan, D., Ho, D.W.C., Jiang, G.P.: An adaptive primal-dual subgradient algorithm for online distributed constrained optimization. IEEE Transactions on Cybernetics 48, 3045–3055 (2018)


# ICCV 2021 Understanding Social Behavior in Dyadic and
Small Group Interactions Challenge
Fact sheet: Automatic self-reported personality recognition Track

Francisca Pessanha1, Gizem Sogancioglu1
1Department of Information and Computing Sciences, Utrecht University,
Utrecht, The Netherlands

This is the fact sheet’s template for the ICCV 2021 Understanding Social
Behavior in Dyadic and Small Group Interactions Challenge [1], “Automatic
self-reported personality recognition Track”. Please fill out the following
sections carefully in a scientific writing style. Then, send the compressed
project (in .zip format), i.e., the generated PDF, .tex, .bib and any
additional files to<EMAIL_ADDRESS>and put in the Subject of the email
“Fact Sheets: ICCV 2021 (DYAD) Challenge”, following the schedule and
instructions provided in the Challenge webpage [1] “Wining solutions (post-
challenge), Fact Sheets”.

##  I Team details

  * •

Team leader name: Francisca Pessanha and Gizem Sogancioglu

  * •

Username on Codalab: fpessanha, gizemsogancioglu

  * •

Team leader affiliation: Utrecht University

  * •

Team leader email<EMAIL_ADDRESS><EMAIL_ADDRESS>
  * •

Name of other team members (and affiliation): Metehan Doyran, Heysem Kaya,
Ronald Poppe, Albert Ali Salah, Almila Akdag Salah

  * •

Team website URL (if any): https://www.uu.nl/en/research/interaction/social-
and-affective-computing/people

##  II Contribution details

###  II-A Title of the contribution

We propose an informed baseline to help disentangle the various contextual
factors of influence in this type of case studies. For this purpose, we
analysed the correlation between the given metadata and the self-assigned
personality trait scores and developed a model based solely on this
information. Further, we compared the performance of this informed baseline
with models based on state-of-the-art visual, linguistic and audio features.
For the present dataset, a model trained solely on simple metadata features
(age, gender and number of sessions) proved to have superior or similar
performance when compared with simple audio, linguistic or visual features
based systems.

###  II-B Representative image / workflow diagram of the method

The pipelines for the informed (metadata based) and combined (acoustic-
linguistic + metadata) systems are shown in Figures 1 and 2, respectively.

Figure 1: Personality prediction informed baseline. Figure 2: Personality
prediction model using linguistic, visual and metadata features. We defined
the best performing models for each personality trait based on their
performance on the development set and applied late fusion to get a final
prediction. The best performing models for both linguistic and audio features
were obtained in the ghost task.

###  II-C Detailed method description

The regressor used for all steps of this section was a multitask Random Forest
regressor. We defined the hyperparameters of each model based on a 3-fold
participant-independent cross-validation. A model was trained for each task to
evaluate what were the most representative interactions. The best performing
model was chosen based on the performance in the development set. We used both
training and development sets for training in the final evaluation phase. Both
per task model and fused models (using task as a feature) experimented.

Firstly, we defined different models based on gender, age, number of sessions,
background and mood dimensions. A simple model using only gender, age and
number of sessions as features outperformed the development baseline in all
dimensions motivating us to explore this matter further (Figure 1). For this
purpose, we explored solutions based on linguistic, audio and video features
and compared them with this informed baseline.

In the linguistic domain, we concatenated the transcriptions of the
participant in the session and extracted state-of-the-art features, namely
Sentence-Bert [2], TFIDF [3], LIWC [4] and VAD [5]. Further, we handcrafted
features to represent the interaction between the two participants: turn rate,
speech rate and speech duration rate. In the audio domain, we sampled the
audio using turn-wise chunks and extracted functionals from geMAPS for these
audio segments [6]. For visual, we obtained i3D features for every 2.5 seconds
of the participant camera video [7]. The final prediction for both audio and
visual models was given by the median of all the predictions for the session
in question.

The best performing models in the development set where then fused as
illustrated in Figure 2.

###  II-D Challenge results

The best performance on the test set was achieved using the simple pipeline
described in Figure 1.

TABLE I: Results from Leaderboard (Test phase) obtained by the proposed approach. Rank position | O | C | E | A | N | MSE
---|---|---|---|---|---|---
3 | 0.752 | 0.687 | 0.917 | 0.671 | 1.098 | 0.825

###  II-E Final remarks

TABLE II: Results obtained by the approaches represented in Figure 1 and Figure 2 on the development set. Method | O | C | E | A | N | MSE
---|---|---|---|---|---|---
Challenge baseline | 0.6589 | 1.3541 | 1.1893 | 0.9651 | 1.1487 | 1.0632
Metadata model | 0.6074 | 1.3285 | 1.2082 | 0.9554 | 1.1029 | 1.0405
Combined model | 0.6074 | 1.3285 | 1.0864 | 0.8476 | 1.0955 | 0.9931

In the development phase, the combined model described in Figure 2 achieved
the best performance (Table II). However, these results were not replicable in
the final evaluation phase, possibly due to differences in trait balance
amongst the splits and the small number of samples for both development and
test sets, leading to overfitting to the development set characteristics.
Therefore, the results presented in Section II were obtained with a metadata
trained model.

A correlation between personality, gender and age has been reported in
previous studies. According to Marsh et al. [8] women have higher latent
scores on all OCEAN traits, except for openness. Further, with age,
individuals become happier, more self-content and self-centred and more
conformed, which leads to less openness, neuroticism, extroversion and
conscientiousness and more agreeability. Further, we hypothesise that,
considering the time investment and social energy required for participation
in a session, the number of sessions for each participant is correlated to
their personality traits, namely openness. For this reason, using metadata for
personality prediction is a relevant experiment.

Despite this information, the three metadata factors referred should not be
sufficient for a strong personality prediction, particularly when compared
with audio-visual-metadata informed systems like the challenge baseline. This
fact may indicate that the dataset includes unwanted bias. Considering the
small size of the dataset and the similarities in backgrounds of the
participants, with a mainly highly educated population, we expect to find
patterns in personality that won’t generalize for a more diverse population.
Further, ”apparent personality” may deviate from the ”real personality”,
particularly for traits low in visibility like emotional stability, which can
then influence the performance of appearance-based models’ performance like
the baseline. In this domain, recent work on ”apparent personality” prediction
also points out the influence of inherent characteristics of the subject such
as age, gender, attractiveness and ethnicity, on the way their personality is
perceived [9].The same is true for the way the participants interact with each
other, expecting different interactions when the participant is paired with
similar or dissimilar personality types [10]. So, we consider the dataset
would benefit from third-person annotation to analyze the correlations between
self-reported and perceived personality traits.

In sum, our goal with the present submission was to propose an informed
baseline to assess the influence of metadata in the performance of models for
multimodal tasks. We argue that understandable baseline models are fundamental
to access the contributions and shortcomings of complex systems in the
affective computing field and contributes to the early detection of dataset
related bias.

##  III Additional method details

Please, reply if your challenge entry considered (or not) the following
strategies and provide a brief explanation. For the non-binary questions, you
can mark multiple options.

  * •

Mark with an X the modalities you have exploited. ( ) Visual, ( ) Acoustic, (
) Transcripts, (x) Metadata, ( ) Landmark annotations, ( ) Eye-gaze vectors.

  * •

In case you used metadata, mark with an X the types of metadata you have
exploited. (x) Age, (x) Gender, ( ) Country of origin, ( ) Max. level of
education, ( ) Pre-session mood, ( ) Post-session mood, ( ) Pre-session
fatigue, ( ) Post-session fatigue, ( ) Relationship among interactants, ( )
Task type, ( ) Task order, ( ) Task difficulty, ( ) Language, (x) Other.
If “other”, or if you have used just a subset of info for a given type of
metadata (e.g., just a subset of mood values), please detail: Number of
sessions

  * •

Mark with an X the tasks you used for training. ( ) Talk, ( ) Lego, ( )
Animals, ( ) Ghost.
The model proposed uses solely age, gender and number of sessions as features
so, no task information is needed. In the training phase, we explored
approaches using all four tasks.

  * •

Mark with an X the tasks you used for evaluation. ( ) Talk, ( ) Lego, ( )
Animals, ( ) Ghost.

  * •

Did you use the provided validation set as part of your training set? (x) Yes,
( ) No
If yes, please detail:
The final model was trained in the combined validation and training set.

  * •

Did you use any fusion strategy of modalities? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use ensemble models? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you follow a multi-task approach or trained each trait individually? (x)
Multi-task, ( ) Trained each trait individually.

  * •

Did you use information from the other interlocutor (e.g., their visual info)
to predict the personality of the target interlocutor? ( ) Yes, (x) No.
If yes, please detail:

  * •

Did you use pre-trained models? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use external data? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use any regularization strategies/terms? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use handcrafted features? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use any pose estimation method? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use any face / hand / body detection, alignment or segmentation
strategy? ( ) Yes, (x) No
If yes, please detail:

  * •

At what level of granularity did your method perform personality inference? (
) Frame-level, ( ) Audio/video chunk-level (i.e., short audio/video snippet),
( ) Task-level, ( ) Session-level, ( ) Other.
If “other”, please detail. If you selected “chunk-level”, please comment on
the chunk length and why you selected it: Participant-level

  * •

Did you use any aggregation method to compute a single personality prediction
per participant? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you use any spatio-temporal feature extraction strategy? ( ) Yes, (x) No
If yes, please detail:

  * •

Did you perform any data augmentation?
( ) Yes, (x) No
If yes, please detail:

  * •

Did you use any bias mitigation technique (e.g., rebalancing training data)?
( ) Yes, (x) No
If yes, please detail:

##  IV Code repository

Link to a code repository with complete and detailed instructions so that the
results obtained on Codalab can be reproduced locally. This includes a list of
requirements, pre-trained models, and so on. Note, training code with
instructions is also required. This is recommended for all participants and
mandatory for winners to claim their prize. Organizers strongly encourage the
use of docker to facilitate reproducibility.

Code repository: https://github.com/gizemsogancioglu/FGM_Utrecht

## References

  * [1] ChaLearn Looking at People. ICCV’2021 Understanding Social Behavior in Dyadic and Small Group Interactions Challenge. [Online]. Available: https://chalearnlap.cvc.uab.cat/challenge/45/description/
  * [2] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [3] L.-P. Jing, H.-K. Huang, and H.-B. Shi, “Improved feature selection approach TFIDF in text mining,” in _Proc. International Conference on Machine Learning and Cybernetics_ , vol. 2. IEEE, 2002, pp. 944–946.
  * [4] J. W. Pennebaker, R. L. Boyd, K. Jordan, and K. Blackburn, “The development and psychometric properties of LIWC2015,” Tech. Rep., 2015.
  * [5] S. M. Mohammad, “Obtaining reliable human ratings of valence, arousal, and dominance for 20,000 english words,” in _Proc. ACL_ , 2018.
  * [6] F. Eyben, K. R. Scherer, B. W. Schuller, J. Sundberg, E. André, C. Busso, L. Y. Devillers, J. Epps, P. Laukka, S. S. Narayanan _et al._ , “The geneva minimalistic acoustic parameter set (gemaps) for voice research and affective computing,” _IEEE transactions on affective computing_ , vol. 7, no. 2, pp. 190–202, 2015.
  * [7] J. Carreira and A. Zisserman, “Quo vadis, action recognition? a new model and the kinetics dataset,” 2018.
  * [8] H. W. Marsh, B. Nagengast, and A. J. Morin, “Measurement invariance of big-five factors over the life span: Esem tests of gender, age, plasticity, maturity, and la dolce vita effects.” _Developmental psychology_ , vol. 49, no. 6, p. 1194, 2013.
  * [9] R. D. P. Principi, C. Palmero, J. C. Junior, and S. Escalera, “On the effect of observed subject biases in apparent personality analysis from audio-visual signals,” _IEEE Transactions on Affective Computing_ , 2019.
  * [10] R. Cuperman and W. Ickes, “Big five predictors of behavior and perceptions in initial dyadic interactions: Personality similarity helps extraverts and introverts, but hurts “disagreeables”.” _Journal of personality and social psychology_ , vol. 97, no. 4, p. 667, 2009.