# Smart cathodic protection system for real-time quantitative assessment of
corrosion of sacrificial anode based on Electro-Mechanical Impedance (EMI)

Durgesh Tamhane  Jeslin Thalapil  Sauvik Banerjee<EMAIL_ADDRESS>Siddharth Tallur<EMAIL_ADDRESS>Department of Electrical Engineering,
Indian Institute of Technology Bombay, Mumbai 400076, MH India  Department of
Civil Engineering, Indian Institute of Technology Bombay, Mumbai 400076, MH
India

###### Abstract

Corrosion of metal structures is often prevented using cathodic protection
systems, that employ sacrificial anodes that corrode more preferentially
relative to the metal to be protected. In-situ monitoring of these sacrificial
anodes during early stages of their useful life could offer several insights
into deterioration of the material surrounding the infrastructure as well as
serve as early warning indicator for preventive maintenance of critical
infrastructure. In this paper, we present an Electro-Mechanical Impedance
(EMI) measurement-based technique to quantify extent of corrosion of a zinc
sacrificial anode without manual intervention. The detection apparatus
consists of a lead zirconate titanate (PZT) transducer affixed onto a circular
zinc disc, with waterproofing epoxy protecting the transducer element when the
assembly is submerged in liquid electrolyte (salt solution) for accelerated
corrosion by means of impressed current. We develop an analytical model for
discerning the extent of corrosion by monitoring shift in resonance frequency
for in-plane radial expansion mode of the disc, that also accurately models
the nonlinearity introduced by partial delamination of the corrosion product
(zinc oxide) from the disc. The analytical model thus developed shows
excellent agreement with Finite Element Analysis (FEA) and experimental
results. Our work establishes the efficacy of the proposed technique for
monitoring the state of health of sacrificial anodes in their early stage of
deterioration and could thus be widely adopted for structural health
monitoring applications within the internet of things.

###### keywords:

Electro-Mechanical Impedance (EMI) , sacrificial anode , cathodic protection
system , corrosion monitoring , smart infrastructure , structural health
monitoring

††journal: Journal of LaTeX Templatesmytitlenotemytitlenotefootnotetext: D.
Tamhane and J. Thalapil have contributed equally to the manuscript.

##  1 Introduction

Longevity of civil infrastructure relies on strength of metals such as steel
for construction of buildings, pipelines, storage tanks etc. These metals are
typically embedded in insulated casings or treated with anti-corrosion
coatings to protect them from damage due to corrosion. Nevertheless, these
metals are susceptible to corrosion as soon as the material in which they are
embedded deteriorates and allows permeation and diffusion of corrosive agents.
The initiation and rate of corrosion depends on several factors e.g. quality
of raw materials used in preparation of concrete for reinforced steel
structures, air quality of the environment where the structure is to be built,
water quality and salinity for marine infrastructure etc. A simple and
commonly used method to protect metals from corrosion is by installing a
cathodic protection system [1, 2, 3]. The cathodic protection system uses a
sacrificial metal that is more electrochemically active (i.e. more negative
electrode potential) relative to the vulnerable metal that requires
protection. In passive cathodic protection systems, the sacrificial metal
(anode) is attached to the vulnerable metal surface prone to corrosion. Being
more electrochemically active, the sacrificial anode is consumed due to
corrosion in place of the metal that it protects, thus prolonging the service
life of the infrastructure. It is necessary to monitor the efficacy of a
passive cathodic protection system to ensure adequate protection against
corrosion. This is often measured indirectly by monitoring the corrosion of
the metal structure that the cathodic system is protecting [4, 5]. Other
direct monitoring methods include half-cell potential measurement [6], open-
circuit potential test [7], DC current density measurement [8] etc. These
tests require three-electrode apparatus and disconnection of the sacrificial
anodes from the cathodic protection system for several hours thus interfering
with their functionality.

The advent of the internet of things has lead to tremendous surge in smart
infrastructure applications within structural health monitoring. Lead
zirconate Titanate (PZT) transducers find a variety of applications in
structural health monitoring such as assessing performance and state of pre-
stressed concrete [9, 10], damage localization and monitoring [11, 12, 13,
14], monitoring debonding in composite structures [15, 16, 17], monitoring of
fatigue damage and curing of adhesives [18, 19] etc. More recently, PZT
transducers embedded within infrastructure are employed as smart sensors for
real-time monitoring [20, 21] for applications such as impact monitoring [22]
and detection of internal damage in concrete and embedded reinforcements [23,
24]. While PZT transducers have also been employed for corrosion monitoring
[25, 26], an analytical and quantitative correlation of change in impedance of
the PZT transducer due to the corrosion of the system under inspection
requires further development. More recently, Electro-Mechanical Impedance
(EMI) measurements of PZT transducers have been explored for monitoring the
performance of concrete including monitoring of chlorine ingress and
carbonation [27, 28, 29, 30] of concrete. EMI measurements conducted with PZT
transducers embedded into stainless steel coupons [31] have also been reported
for studying the effect of corrosion on their conductance spectra. While the
versatility of EMI measurements with PZT transducers is well established in
literature, their application as a tool for health-assessment of cathodic
protection systems has not been investigated.

In this paper, we report a novel EMI-based sensor topology for monitoring the
corrosion of a sacrificial zinc anode with an adhesively bonded PZT
transducer. Experimental measurements are conducted with an impressed-current
based accelerated corrosion system for in-situ evaluation of the susceptance
spectra of the PZT transducer attached to the sacrificial anode. Corrosion-
induced change in frequency for a bulk acoustic resonance mode of the disc-
shaped sacrificial anode is employed as a signature to assess the extent of
corrosion as shown in Figure 1. We observe that the series resonance frequency
of the PZT transducer gradually increases with increasing corrosion time.
Detailed Finite Element (FE) simulations and analytical models are presented
in an effort to examine this shift in frequency, which is attributed to the
formation and partial delamination of the oxide film formed on the surface of
the sacrificial anode. The following sections present details of the
analytical model (with supporting information in appendices), and experimental
results and discussions.

Figure 1: (a) 3D illustration, and (b) photograph of the PZT transducer bonded
to zinc sacrificial anode. (c) Finite element method simulation of susceptance
spectrum of the sensor showing electro-mechanical resonance corresponding to
radial expansion mode of the assembly (inset: mode-shape showing displacement
profile for radial expansion mode). The extent of corrosion of the sacrificial
anode is ascertained by monitoring the shift in series resonance frequency.

##  2 Analytical Model and Finite Element Analysis

###  2.1 Principle of operation

The coupling of the mechanical parameters (mechanical strain: $S_{ij}$,
mechanical stress: $T_{kl}$) and electrical parameters (electrical field:
$E_{kl}$, electrical displacement: $D_{j}$) for a structure excited with
piezoelectric transduction can be described as [32]:

$\begin{split}S_{ij}=s_{ijkl}^{E}T_{kl}+d_{kij}E_{k}\\\
D_{j}=d_{jkl}T_{kl}+\varepsilon_{jk}^{T}E_{k}\end{split}$ (1)

where $s_{ijkl}^{E}$ is the mechanical compliance of the structure material
measured at zero electric field $(E=0)$, $\varepsilon_{jk}^{T}$ is the
dielectric permittivity measured at zero mechanical stress $(T=0)$, and
$d_{kij}$ represents the piezoelectric coupling coefficient. The direct
piezoelectric effect describes conversion of applied stress to electric
charge. Similarly, the converse piezoelectric effect results in generation of
strain under application of an electric field in the piezoelectric material.
At electric resonance, the PZT transducer presents low impedance (i.e. large
admittance) to the excitation source, which results in large mechanical
response when coupled to a mechanical resonance of the structure. The electro-
mechanical resonance frequency and impedance of the piezoelectrically
transduced structure depends on its geometry, mass and stiffness. Corrosion
causes change in these parameters, thereby resulting in shift in the electro-
mechanical resonance frequency as seen in the EMI spectrum. Using an impedance
analyzer/LCR meter, the resonance frequency of the structure can be measured
and used to determine the extent of corrosion. Here we consider a circular
zinc plate as the sacrificial anode, onto which a PZT transducer is bonded
using an adhesive. The resonance mode under study is the radial expansion mode
as shown in Figure 1(c). Corrosion of zinc (Zn) results in formation of a zinc
oxide layer (ZnO) on the anode, which results in change in the series
resonance frequency, corresponding to the peak in the admittance spectrum. We
present below an analytical model for the radial expansion mode of vibration
for the multi-layer (Zn, ZnO) disc.

###  2.2 Mathematical formulation for axial in-plane vibration of circular
plates

The governing equation for in-plane axisymmetric radial expansion mode of a
circular plate in cylindrical coordinates ($r$,$\theta$) is expressed as [32]:

$\frac{E}{1-\nu^{2}}\left(\frac{\partial^{2}u_{r}}{\partial
r^{2}}+\frac{1}{r}\frac{\partial u_{r}}{\partial
r}-\frac{u_{r}}{r^{2}}\right)=\rho\frac{\partial^{2}u_{r}}{\partial t^{2}}$
(2)

where $E$ and $\nu$ are the Young’s modulus and Poisson’s ratio of the
material respectively, $\rho$ is the density and $u_{r}$ is the radial
displacement in cylindrical coordinates ($r$,$\theta$). The general solution
for the radial displacement $u_{r}$ is expressed as (details provided in A):

$u_{r}\left(r,t\right)=\left(C_{1}J_{1}\left(\beta\frac{r}{a}\right)+D_{1}Y_{1}\left(\beta\frac{r}{a}\right)\right)e^{i\omega
t}$ (3)

where $\omega$ denotes the fundamental resonance frequency of the circular
plate of radius $a$ and
$\beta=\omega\sqrt{\frac{\rho\left(1-\nu^{2}\right)a^{2}}{E}}$ denotes
dimensionless frequency parameter, $J_{1}(\beta\frac{r}{a})$ is Bessel
function of first kind of order one, and $Y_{1}(\beta\frac{r}{a})$ is Bessel
function of second kind of order one. The above solution does not consider the
effect of inertia of lateral motion. Thus, similar to Rayleigh’s theory for
the extensional vibration of bars, the modified frequency parameter for a
circular disc can be expressed as:

$\beta=\omega\sqrt{\frac{\rho
a^{2}}{\frac{E}{1-\nu^{2}}-\frac{\rho\omega^{2}\nu^{2}I_{zz}}{A}}}$ (4)

where $I_{zz}$ denotes the area moment of inertia of the disc cross-section
along a direction normal to the circular cross-section, and $A$ denotes area
of the cross-section. The detailed formulation for dimensionless frequency
parameter for a thick circular disc is provided in B.

###  2.3 Equivalent circular-shaped PZT model

We have employed a square-shaped PZT transducer in our experiments, as shown
in Figure 1. To simplify the mathematical formulation, we model the square PZT
transducer as an equivalent circular-shaped PZT transducer so that interface
boundary condition in cylindrical coordinates can be established. For a square
plate undergoing axial vibration with ‘free edge’ boundary condition, the
fundamental frequency is expressed as [32]:

$\omega=\frac{\pi}{L}\sqrt{\frac{E_{T}}{1-\nu_{T}^{2}}}$ (5)

where $L$ denotes the edge length of the square PZT transducer, and $E_{T}$
and $\nu_{T}$ denote the Young’s modulus and Poisson’s ratio of the transducer
material (PZT). Similarly, for a circular plate undergoing axial vibration
with similar boundary conditions, the fundamental frequency is expressed as:

$\omega=\frac{\beta_{T}}{a_{T}}\sqrt{\frac{E_{T}}{1-\nu_{T}^{2}}}$ (6)

where $a_{T}$ is the radius of circular PZT transducer and $\beta_{T}$ is the
dimensionless frequency parameter obtained by solving the characteristic
equation

$\beta_{T}J_{0}(\beta_{T})-(1-\nu_{T})J_{1}(\beta_{T})=0$ (7)

where $J_{0}$ and $J_{1}$ are the Bessel functions of first kind of order $0$
and $1$, respectively [32].

Equating equations (5) and (6), we obtain

$\frac{\pi}{L}=\frac{\beta_{T}}{a_{T}}$ (8)

or,

$a_{T}=L\frac{\beta_{T}}{\pi}$ (9)

Figure 2: Dimensions of (left) square-shaped PZT transducer atop zinc anode
used in our experiment, and (right) equivalent circular-shaped PZT transducer
with dimensions computed using equation (9). All dimensions are in units of
$\text{\,}\mathrm{mm}$.

The value of $\beta_{T}$ obtained by solving the characteristic equation
(equation (7)) for fundamental radial in-plane axisymmetric vibration mode
with free edge boundary condition is equal to $2.0424$. The PZT transducer
used in our experiment is square-shaped with edge length
$20\text{\,}\mathrm{mm}$, that therefore corresponds to an equivalent circular
PZT transducer with radius $13\text{\,}\mathrm{mm}$, as shown in Figure 2.

###  2.4 Mathematical formulation of bi-layer circular plate with equivalent
circular PZT transducer

To derive analytical expression for the resonance frequency of fundamental
axisymmetric radial expansion mode of the corroded zinc plate with the PZT
transducer, we model the structure as a composite of two portions shown in
Figure 3. The layers are considered perfectly ‘bonded’ with each other i.e.
the layers have equal radial displacements and there is no inter-layer slip.
This assumption implies there is no delamination between the layers, and is
consistent with experimental observations during initial corrosion [33]. Thus,
the circular zinc anode with thin corroded layer (zinc oxide) can be divided
into two portions namely: Portion I (two layers: zinc + zinc oxide), and
Portion II (three layers: zinc + zinc oxide + equivalent circular PZT). The
following assumptions are considered for the analysis:

  * 1.

All materials are assumed to be isotropic

  * 2.

Corrosion occurs uniformly across the bottom surface of the zinc anode

Figure 3: (top) Top view and (bottom) cross-section of the circular zinc anode
with equivalent circular PZT transducer on top surface and uniformly formed
zinc oxide layer on bottom surface.

Therefore, the general solutions for axisymmetric in-plane radial expansion of
the circular disc in the two portions are expressed as:

$U(r)=\begin{cases}U_{1}(r)=C_{1}J_{1}\left(\beta_{1}\frac{r}{a}\right)+C_{2}Y_{1}\left(\beta_{1}\frac{r}{a}\right)&\text{Portion
I}\\\ U_{2}(r)=C_{3}J_{1}\left(\beta_{2}\frac{r}{a}\right)&\text{Portion
II}\end{cases}$ (10)

where the dimensionless frequency parameters are given as (subscripts $1$, $2$
and $3$ denote zinc oxide layer, zinc layer and PZT transducer, respectively):

${\beta_{1}}=\sqrt{\frac{\left(\rho_{1}h_{1}+\rho_{2}h_{2}\right)a^{2}}{\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}}}\times\omega$
(11)
${\beta_{2}}=\sqrt{\frac{\left(\rho_{1}h_{1}+\rho_{2}h_{2}+\rho_{3}h_{3}\right)a^{2}}{\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}+\frac{E_{3}h_{3}}{1-\nu_{3}^{2}}}}\times\omega$
(12)

where $h$ is the thickness, $E$ is the Young’s modulus, $\rho$ is the density
and $\nu$ is the Poisson’s ratio of the respective layer. The Young’s modulus
for the PZT transducer is obtained from the compliance coefficients as
$E_{3}=1/S_{11}$ and the Poisson’s ratio as $\nu_{3}=-S_{12}/S_{11}$, wherein
the compliance coefficients $S_{11}$ and $S_{12}$ are obtained from the
compliance matrix of the PZT transducer. The radial force expression for
Portion I and Portion II can be expressed as:

$N_{r}=\begin{cases}N_{r1}=D_{1}\left(\frac{\partial U_{1}}{\partial
r}+\nu_{1eq}\frac{U_{1}}{r}\right)&\text{Portion I}\\\
N_{r2}=D_{2}\left(\frac{\partial U_{2}}{\partial
r}+\nu_{2eq}\frac{U_{2}}{r}\right)&\text{Portion II}\end{cases}$ (13)

where the stiffness coefficients $D_{1}$ and $D_{2}$, and the equivalent
Poisson’s ratio $\nu_{1eq}$ amd $\nu_{1eq}$ for Portions I and II respectively
are expressed as follows:

$D_{1}=\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}$ (14)

$D_{2}=\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}+\frac{E_{3}h_{3}}{1-\nu_{3}^{2}}$
(15)

$\nu_{1eq}=\frac{\frac{\nu_{1}E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{\nu_{2}E_{2}h_{2}}{1-\nu_{2}^{2}}}{\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}}$
(16)
$\nu_{2eq}=\frac{\frac{\nu_{1}E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{\nu_{2}E_{2}h_{2}}{1-\nu_{2}^{2}}+\frac{\nu_{3}E_{3}h_{3}}{1-\nu_{3}^{2}}}{\frac{E_{1}h_{1}}{1-\nu_{1}^{2}}+\frac{E_{2}h_{2}}{1-\nu_{2}^{2}}+\frac{E_{3}h_{3}}{1-\nu_{3}^{2}}}$
(17)

###  2.5 Determination of resonance frequency of fundamental radial expansion
mode

For the two layer (zinc and zinc oxide) circular plate with equivalent
circular PZT patch undergoing axisymmetric in-plane radial vibration, the free
edge boundary condition at $r=a$ is $N_{r1}=0$ (zero radial force) i.e.
$\frac{\partial U_{1}}{\partial
r}\Big{|}_{r=a}+\nu_{1eq}\frac{U_{1}}{r}\Big{|}_{r=a}=0$. At the interface
between Portion I and Portion II at r=b, there exists continuity of radial
displacement and radial forces, i.e. $U_{1}(r=b)=U_{2}(r=b)$ and
$N_{r1}\Big{|}_{r=b}=N_{r2}\Big{|}_{r=b}$. Substituting the expressions for
displacements in the above equations, a $3\times 3$ characteristic determinant
is obtained as below:

$\Delta=\left|\begin{array}[]{ccc}K_{11}&K_{12}&K_{13}\\\
K_{21}&K_{22}&K_{23}\\\ K_{31}&K_{32}&K_{33}\\\ \end{array}\right|$ (18)

where the elements of the determinant are:

$K_{11}=\beta_{1}J_{0}\left(\beta_{1}\right)-J_{1}\left(\beta_{1}\right)\left(1-\nu_{1eq}\right)$
(19)
$K_{12}=\beta_{1}Y_{0}\left(\beta_{1}\right)-Y_{1}\left(\beta_{1}\right)\left(1-\nu_{1eq}\right)$
(20) $K_{13}=0$ (21) $K_{21}=J_{1}\left(\frac{b\beta_{1}}{a}\right)$ (22)
$K_{22}=Y_{1}\left(\frac{b\beta_{1}}{a}\right)$ (23)
$K_{23}=-J_{1}\left(\frac{b\beta_{2}}{a}\right)$ (24)
$K_{31}=\frac{\beta_{1}J_{0}\left(\frac{b\beta_{1}}{a}\right)}{a}-\frac{\left(1-\nu_{1eq}\right)J_{1}\left(\frac{b\beta_{1}}{a}\right)}{b}$
(25)
$K_{32}=\frac{\beta_{1}Y_{0}\left(\frac{b\beta_{1}}{a}\right)}{a}-\frac{\left(1-\nu_{1eq}\right)Y_{1}\left(\frac{b\beta_{1}}{a}\right)}{b}$
(26)
$K_{33}=\frac{D_{2}\left(-\frac{\beta_{2}J_{0}\left(\frac{b\beta_{2}}{a}\right)}{a}+\frac{\left(1-\nu_{2eq}\right)J_{1}\left(\frac{b\beta_{2}}{a}\right)}{b}\right)}{D_{1}}$
(27)

Since the material properties ($E$, $\nu$ and $\rho$) are known for the three
layers, the characteristic determinant $\Delta$ can be expressed as a function
of the natural frequency $\omega$, and thickness of the corroded zinc oxide
layer $h_{1}$ and the uncorroded zinc layer $h_{2}$, i.e.
$\Delta=\Delta(\omega,h_{1},h_{2})$. The natural frequencies of the system
undergoing corrosion can be obtained by setting the characteristic determinant
to zero. The thicknesses $h_{1}$ and $h_{2}$ are obtained using Faraday’s law
of electrolysis. Thus with the values of $h_{1}$ and $h_{2}$ determined, the
characteristic equation can be expressed as $\Delta(\omega)=0$, solving which
gives the natural frequency of the system. The characteristic equation is a
transcendental equation that is solved using MATLAB.

###  2.6 Comparison of solutions of analytical model and FEA

The solution for resonance frequency of fundamental axisymmetric radial
expansion mode obtained from the analytical model described above are
baselined against FEM model of the structure solved using COMSOL Multiphysics.
We solve for a commercially available cylindrical zinc sacrificial anode
(Canode, Krishna Conchem Products Pvt. Ltd.) of diameter
$3.6\text{\,}\mathrm{cm}$ and thickness $0.73\text{\,}\mathrm{cm}$, and PZT-5H
transducer of dimensions
$20\text{\,}$$\times$$20\text{\,}$$\times$$0.4\text{\,}\mathrm{m}\mathrm{m}^{3}$
(SP-5H, Sparkler Ceramics Pvt. Ltd.). A photograph of the assembly, and the
FEM model is shown in Figure 1. The equivalence of the two structures shown in
Figure 2 is validated through Finite Element (FE) simulations performed using
COMSOL Multiphysics, which yields resonance frequencies for the fundamental
axisymmetric radial expansion mode as
$69.42\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ and
$69.44\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ (amounting to
$<$$0.03\text{\,}\%$ error) for the circular zinc plate with square-shaped PZT
and equivalent circular PZT, respectively. The FE simulations are performed
using “Fine” mesh setting in COMSOL Multiphysics, considering the trade-off
between computation time and convergence of the eigenfrequency solution (as
shown in Table 1. The computation time is obtained on a computer with $64$-bit
Intel® Xeon® E5-1650 v4 $3.60\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ CPU and
$32\text{\,}\mathrm{G}\mathrm{B}$ RAM. The computation time is significantly
higher upon introduction of zinc oxide layer as described below.

Table 1: Comparison of impact of mesh settings in COMSOL Multiphysics on eigenfrequency solution Mesh setting |  Number of domain elements |  Computation time [$\text{\,}\mathrm{s}$] |  Eigenfrequency [$\text{\,}\mathrm{kHz}$]
---|---|---|---
Extremely Coarse | 438 | 3 | 69.471
Extra Coarse | 2079 | 3 | 69.431
Coarser | 4522 | 4 | 69.425
Coarse | 10070 | 8 | 69.422
Normal | 18985 | 13 | 69.421
Fine | 29686 | 21 | 69.42
Finer | 48591 | 36 | 69.42

When corrosive agents attack the sacrificial anode, a thin layer of corrosion
products forms on its surface due to the multitude of corrosive reactions
taking place. Thus for simplicity we have assumed that soon after corrosion
initiates the anode is part metal and part metal oxide [33, 34]. The surface
of the anode on which the PZT is attached is assumed to not corrode (this is
ensured using water-proofing sealant in the experiment, as described in the
following section). In the initial stages of accelerated corrosion due to
externally applied impressed current, zinc reacts with oxygen and forms zinc
oxide. By calculating the amount of mass (thickness) loss in the zinc layer
and added mass (thickness) due to formation of zinc oxide using Faraday’s law
of electrolysis, we obtain the resonance frequency for the radial expansion
mode through FE simulations performed in COMSOL Multiphysics and using the
analytical method described in section 2.5. Table 2 lists the material
properties for zinc and zinc oxide used for these calculations.

Table 2: Material properties used for calculating mass conversion of zinc to zinc oxide Material |  Density [$\text{\,}\mathrm{g}\mathrm{/}\mathrm{c}\mathrm{m}^{3}$] |  Molecular mass [$\text{\,}\mathrm{g}\text{\,}{\mathrm{mol}}^{-1}$]
---|---|---
Zinc | 7.14 | 65.38
Zinc oxide | 5.68 | 81.38

The conversion of zinc to zinc oxide is governed by the chemical reaction:

$\ce{Zn+0.5O_{2}\xrightarrow{}ZnO}$ (28)

Thus, $1\text{\,}\mathrm{g}$ of zinc produces $1.24\text{\,}\mathrm{g}$ of
zinc oxide i.e. $1\text{\,}\mathrm{c}\mathrm{m}^{3}$ volume of zinc is
converted to $1.57\text{\,}\mathrm{c}\mathrm{m}^{3}$ of zinc oxide. Since we
consider a cylindrical geometry whose radius does not change due to corrosion
(i.e. zinc oxide only forms on the bottom circular face of the anode due to
waterproofing of top and side walls of the disc in the experiment), reduction
of thickness of the zinc layer by $1\text{\,}\mathrm{cm}$ results in formation
of $1.57\text{\,}\mathrm{cm}$ of zinc oxide. The corresponding thickness
reduction of zinc due to $0.35\text{\,}\mathrm{A}$ impressed current applied
for various time duration values shown in Table 3 are obtained using Faraday’s
law of electrolysis. Figure 4 shows a comparison of the FEM and analytical
model results accounting for Faradaic mass loss of zinc $(\Delta
m_{\ce{Zn}})$, and added mass of the zinc oxide layer formed due to corrosion
$(\Delta m_{\ce{ZnO}})$.

Table 3: Calculated thickness loss of zinc layer and thickness added in zinc oxide layer for $0.35\text{\,}\mathrm{A}$ impressed current applied for various time duration values. The resonance frequencies obtained using FEM simulation and analytical calculations show good agreement with each other. Time [$\text{\,}\mathrm{min}$] |  Zn thickness loss [$\text{\,}\mathrm{cm}$] |  ZnO thickness gain [$\text{\,}\mathrm{cm}$] |  Analytical result [$\text{\,}\mathrm{kHz}$] |  FEM result [$\text{\,}\mathrm{kHz}$]
---|---|---|---|---
0 | 0 | 0 | 69.875 | 69.42
30 | 0.0029 | 0.0045 | 70.194 | 69.717
60 | 0.0058 | 0.0091 | 70.510 | 70.009
90 | 0.0088 | 0.0137 | 70.825 | 70.299
120 | 0.0117 | 0.0183 | 71.137 | 70.585
150 | 0.0146 | 0.0229 | 71.447 | 70.869
180 | 0.0176 | 0.0275 | 71.756 | 71.149
210 | 0.0205 | 0.0321 | 72.062 | 71.427
240 | 0.0234 | 0.0367 | 72.367 | 71.703
270 | 0.0264 | 0.0413 | 72.669 | 71.975
300 | 0.0293 | 0.0459 | 72.970 | 72.246
330 | 0.0323 | 0.0505 | 73.269 | 72.514
360 | 0.0352 | 0.0551 | 73.567 | 72.78
Figure 4: Frequency shift of the radial mode of a zinc anode of diameter
$3.6\text{\,}\mathrm{cm}$ and thickness $0.73\text{\,}\mathrm{cm}$, and PZT-5H
transducer of dimensions
$20\text{\,}$$\times$$20\text{\,}$$\times$$0.4\text{\,}\mathrm{m}\mathrm{m}^{3}$,
due to $0.35\text{\,}\mathrm{A}$ impressed current applied to induce
accelerated corrosion. The shift in resonance frequency relative to the value
at $t=$ $0\text{\,}\mathrm{h}$ (commencement of impressed current application)
is shown at intervals of $30\text{\,}\mathrm{min}$ up to $t=$
$6\text{\,}\mathrm{h}$. The results show good agreement of the analytical
model with Finite Element Method (FEM).

##  3 Experimental Setup

Two samples (A and B) of the sacrificial anode with PZT transducer as
described in section 2.6 are fabricated. One of the circular surfaces of the
zinc anode is gently polished with fine grit sandpaper and the PZT transducer
is affixed on the center of the polished side with Fewikwik® instant adhesive.
Further, a coating of waterproofing epoxy (M-Seal® Clear RTV Silicone Sealant)
is applied over the PZT transducer to protect it from the liquid electrolyte
used in the experiment. This waterproofing sealant also protects the polished
surface of the anode from corroding. The assembly is left undisturbed for
$12\text{\,}\mathrm{h}$ to allow the epoxy to cure. The experimental setup for
accelerated corrosion by means of applied impressed current (shown in Figure
5) consists of an electrolytic cell with a set of two electrodes submerged in
an electrolyte. We use a copper tube as cathode and a $3.5\text{\,}\%$ NaCl
solution as electrolyte. The copper electrode is connected to negative
terminal of a constant current source (Aplab LQ6324T) while positive terminal
of the current source is connected to the zinc anode assembly. The impedance
of the PZT transducer is measured using a precision LCR meter (Agilent
E4980A). The LCR meter is connected to a computer via USB, and is controlled
using a custom-made software designed with LabVIEW for data acquisition. The
constant current source supplies current of magnitude
$0.35\text{\,}\mathrm{A}$. After every $30\text{\,}\mathrm{min}$ interval, the
current source is turned off and impedance of the PZT transducer is recorded,
without disturbing the mechanical arrangement of the apparatus.

Figure 5: (a) Illustration and (b) photograph of the experimental setup used
for accelerated corrosion of sacrificial anode.

##  4 Experimental Results and Discussion

Figure 6: (a) Evolution of susceptance spectra (for sample B) of the PZT
transducer on sacrificial anode system. The series resonance frequency
(corresponding to peak in the susecptance spectra) changes with increasing
corrosion of the anode and is used as a signature for estimating extent of
corrosion. (b) Experimentally measured shift in resonance frequency of radial
expansion mode for samples A and B compared with results obtained from
analytical model (equation (34)).

Figure 6 shows experimentally measured change in series resonance frequency of
the susceptance spectra over duration of the experiment. Both samples show a
change in slope and nonlinearity in the measurements (as indicated by the blue
and red hollow squares in Figure 6(b)) instead of the linear trend as
predicted by Faraday’s law (Figure 4). The assumption made in Figure 4 is that
corrosion products stay on the anode throughout the duration of the
experiment. While performing the experiments, we observe that residue of the
corrosion product separates from the anode into the electrolyte. The
mathematical model of the process of delamination is explained below. The
ideal mass-loss equation as depicted by Faraday’s law is given by:

$\Delta m=\frac{IMt}{Fz}$ (29)

where $\Delta m$ is the mass loss, $I$ is current passing through the cell,
$M$ is molecular weight of the reactive species, $t$ is total time duration
for which current flows in the cell, $F$ is Faraday’s constant, and $z$ is
valency of the reactive species. As per Faraday’s law, the mass of the
sacrificial anode assembly (i.e. circular zinc anode with affixed PZT
transducer and waterproofing epoxy layer) should increase as time progresses,
due to formation of the zinc oxide layer. However, we observe a reduction in
overall mass of the sacrificial anode assembly in the experiment
($2.51\text{\,}\mathrm{g}$ and $2.14\text{\,}\mathrm{g}$ for samples A and B
respectively, measured with a precision weighing scale). The reduction in
overall mass is attributed to partial delamination of zinc oxide from the
anode surface. The change in delamination front of a polymeric coating from
zinc surface in the presence of electrolyte shows a power law dependence with
time [35]:

$a_{del}=k\times t^{A}$ (30)

where $a_{del}$ is the distance of the delamination front from the edge of the
plate, $k$ is the rate constant, $t$ is the exposure time for delamination to
occur, and $A$ is the exponent in the power law. Thus, the volume of the non-
delaminated zinc oxide layer can be expressed as:

$V_{\text{non-delaminated}}=\pi\left(a-a_{\text{del}}\right)^{2}h_{1}$ (31)

To simplify modeling of the disc, we assume that reduction in volume of the
zinc oxide layer happens only due to the reduction of thickness and that the
area remains the same. This assumption is consistent with the experimental
observation that corrosion occurs uniformly over the surface and no
delamination is observed between the formed zinc oxide layer and the zinc
layer in the initial $30\text{\,}\mathrm{min}$ phase of the experiment [33].
Thus, the reduction of overall mass of the sacrificial anode assembly happens
from the dissolution or the delamination of the Zinc oxide layer. Therefore we
define a parameter termed as the non-delaminated factor $\Gamma_{d}$, which is
the ratio of the non-delaminated thickness of zinc oxide layer $h_{1d}$ to the
total thickness of the zinc oxide layer in absence of delamination $h_{1}$:

$\Gamma_{d}=\frac{h_{1d}}{h_{1}}=\frac{V_{\text{non-
delaminated}}}{V}=\frac{\pi\left(a-a_{\text{del}}\right)^{2}}{\pi
a^{2}}=1-\frac{2a_{del}}{a}+\frac{a_{del}^{2}}{a^{2}}$ (32)

Using equations (30) and (32), we can generalize the non-delamination factor
for a circular disc undergoing corrosion as:

$\Gamma_{d}=1-C_{1}t^{A}+C_{2}t^{2A}$ (33)

where $C_{1}$ and $C_{2}$ are reaction dependent constants. According to the
theory of rate-determining step, the value of the exponent $A$ may vary
between $0.5\text{\,}$ and $1.0\text{\,}$ [35]. The constants $C_{1}$, $C_{2}$
and $A$ are estimated for both Sample A and Sample B using MATLAB Curve
Fitting Toolbox, and the non-delamination factors for Sample A and Sample B
thus obtained are:

$\Gamma_{d}=\begin{cases}1-0.4676t^{0.695}+0.06953t^{2\times
0.695}&\text{Sample A}\\\ 1-0.4925t^{0.65}+0.08753t^{2\times
0.65}&\text{Sample B}\end{cases}$ (34)

The overall mass change of the sacrificial anode can be attributed to the mass
loss of zinc ($-\Delta m_{\ce{Zn}}$) due to electrolysis, and mass gain due to
the non-delaminated portion of zinc oxide ($+\Gamma_{d}\times\Delta
m_{\ce{ZnO}}$):

$\text{Overall mass loss}=-\Delta m_{\ce{Zn}}+\Gamma_{d}\times\Delta
m_{\ce{ZnO}}$ (35)

The estimated overall mass loss calculated using the constants obtained from
the curve fitting are $1.87\text{\,}\mathrm{g}$ and $1.54\text{\,}\mathrm{g}$
for sample A and sample B , respectively. We observe a large frequency shift
from $t=$ $0\text{\,}\mathrm{h}$ to $t=$ $0.5\text{\,}\mathrm{h}$ for both
samples, that is not captured by $\Gamma_{d}$. In order to account for this
large initial shift in resonance frequency, we have to introduce an increment
of $0.714\text{\,}\%$ in the resonance frequency at $t=$
$0\text{\,}\mathrm{h}$ for Sample A and $1.41\text{\,}\%$ for Sample B for
best least squares fit. The dramatic variation in the frequency shift in the
first $30\text{\,}\mathrm{min}$ of the experiment is shown in the conductance
and susceptance spectra of sample B in Figures 7(a) and (b), respectively. The
resonance frequency changes drastically in the first few minutes of the
experiment. At $t=$ $20\text{\,}\mathrm{min}$, the resonance frequency for the
anode assembly submerged in the electrolyte attains a value close to the case
where the uncorroded anode is not submerged in the electrolyte. In addition to
the sharp increase in resonance frequency, we also notice significant loading
of the resonance (reduction of peak height and broadening of peak width) at
$t=$ $0\text{\,}\mathrm{min}$ upon submerging the anode in electrolyte. With
progressing time, the impedance spectra show reduction in loading and the
subsequent frequency shift is explained by the delamination model described
above. The origin for the drastic change in loading and initial frequency
shift of the radial expansion mode of the circular zinc disc anode is under
investigation.

Figure 7: (a) Conductance, and (b) susceptance spectra for the sacrificial
anode + PZT assembly (sample B) showing measurements obtained up to $t=$
$90\text{\,}\mathrm{min}$. The resonance frequency changes drastically in the
first few minutes of the experiment, and at $t=$ $20\text{\,}\mathrm{min}$ the
resonance frequency attains a value close to the case where the uncorroded
anode is not submerged in electrolyte (labeled as ‘0 min (no water)’).
Additionally we also see abrupt change in the loading of the resonance (i.e.
reduction of peak height and broadening of peak width) upon submerging the
assembly in electrolyte (labeled ‘0 min’). The loading reduces with
progressing time. The origins of this observation are under investigation.

##  5 Conclusion

In summary, we have demonstrated an electromechanical impedance based method
to detect early corrosion of zinc sacrficial anodes (used in cathodic
protection systems). The experiments are conducted by connecting the
sacrificial anode assembly in an electrochemical half-cell comprising of
copper cathode and $3.5\text{\,}\%$ NaCl electrolyte solution. A constant
current source is used to generate impressed current for accelerated corrosion
of the anode, and a precision LCR meter is used to measure the electro-
mechanical impedance of the PZT transducer. The electro-mechanical resonance
frequency is obtained from the susceptance spectra recorded using a LabVIEW
program running on a computer connected to the LCR meter. We have chosen a
commercially available circular zinc plate for our experiments, with PZT-5H
transducer affixed in the center of one of the circular faces of the plate. We
present an analytical model to calculate change in resonance frequency of the
radial expansion vibration mode of the assembly due to corrosion of zinc and
resultant formation of zinc oxide.

To the best of our knowledge, this is the first reported realization of a
smart-cathodic protection system with built-in sensing of extent of
degradation of the sacrificial anode. The analytical model presented in our
work accounts for nonlinearity due to partial delamination of the zinc oxide
film, as was observed in our experiments conducted with two such sacrificial
anode samples. The analytical model and FEA framework presented in this work
can be adapted to study the variation of any desired bulk acoustic vibration
modes of sacrificial anodes of any arbitrary geometry. Future work will focus
on understanding the origins of the sharp change observed in resonance
frequency in first $30\text{\,}\mathrm{min}$ of the experiment as well as
drastic change in loading of the resonance. The technique proposed in this
paper can be used for in-situ monitoring of sacrificial anodes and detecting
early signs of cover deterioration due to corrosive agents in marine
infrastructure prone to corrosion. This technique is cost-effective and can be
equipped with portable impedance analyzers (e.g. Analog Devices AD5933) and
remote monitoring capabilities and thus has a wide application potential in
structural health monitoring. This technique could also be adapted for real-
time monitoring of degradation of electrodes in batteries and fuel cells.

## CRediT authorship contribution statement

Durgesh Tamhane: Conceptualization, Methodology, Investigation, Software,
Validation, Visualization, Writing - Original Draft. Jeslin Thalapil: Formal
analysis, Investigation, Software, Validation, Visualization, Writing -
Original Draft. Sauvik Banerjee: Conceptualization, Methodology,
Investigation, Resources, Funding acquisition, Supervision, Writing - Original
Draft, Writing - Review & Editing. Siddharth Tallur: Conceptualization,
Methodology, Investigation, Resources, Funding acquisition, Supervision,
Writing - Original Draft, Writing - Review & Editing.

## Declaration of Competing Interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgments

This work was supported by IMPRINT-2A by Department of Science & Technology,
Government of India [grant IMP/2018/001442] with additional financial support
from Sanrachana Structural Strengthening Pvt. Ltd. [grant
RD/0119-SSIMPQ2-001]. The authors thank Krishna Conchem Products Pvt. Ltd. for
providing the zinc sacrificial anodes used for performing the experiments. The
authors also thank Mr. Hrishikesh Belatikar at IIT Bombay for assistance with
developing the LabVIEW based data acquisition software, Dr. Rajeshwara Chary
Sriramadasu at IIT Bombay for preliminary discussions, and Wadhwani
Electronics Lab (WEL) at IIT Bombay for providing Agilent E4980A precision LCR
meter.

##  Appendix A General solution for axisymmetric in-plane radial vibration of
a circular plate

In case of axisymmetric radial vibration of a circular plate, the displacement
$u_{r}$ is independent of the angular position $\theta$ i.e. $\frac{\partial
u_{r}}{\partial\theta}=0$. Additionally, tangential displacement
$u_{\theta}=0$, since motion is only along the radial direction. The mode
shape of the radial expansion mode is shown as an inset in Figure 1(c). Thus,
strain-displacement relations for axisymmetric motion can be expressed as:

$\epsilon_{r}=\frac{\partial u_{r}}{\partial r}$ (36)
$\epsilon_{\theta}=\frac{u_{r}}{r}$ (37)

The stress-strain relationship for case of plane stress in cylindrical
coordinates can be expressed as:

$\sigma_{r}=\frac{E}{1-\nu^{2}}\left(\epsilon_{r}+\nu\epsilon_{\theta}\right)$
(38)
$\sigma_{\theta}=\frac{E}{1-\nu^{2}}\left(\nu\epsilon_{r}+\epsilon_{\theta}\right)$
(39) $\sigma_{r\theta}=0$ (40)

where $E$ and $\nu$ denote Young’s modulus and Poisson’s ratio for the
material of the plate, respectively. Using equations (36)$-$(40), we can
express stress-displacement relations for case of axisymmetric plane stress
as:

$\sigma_{r}=\frac{E}{1-\nu^{2}}\left(\frac{\partial u_{r}}{\partial
r}+\nu\frac{u_{r}}{r}\right)$ (41)
$\sigma_{\theta}=\frac{E}{1-\nu^{2}}\left(\nu\frac{\partial u_{r}}{\partial
r}+\frac{u_{r}}{r}\right)$ (42)

Further, we can express radial and circumferential forces in the plate as:

$N_{r}=\frac{Eh}{1-\nu^{2}}\left(\frac{\partial u_{r}}{\partial
r}+\nu\frac{u_{r}}{r}\right)$ (43)
$N_{\theta}=\frac{Eh}{1-\nu^{2}}\left(\nu\frac{\partial u_{r}}{\partial
r}+\frac{u_{r}}{r}\right)$ (44) $N_{r\theta}=0$ (45)

Figure 8: Infinitesimal plate element for analysis of in-plane plate vibration
in polar coordinates for a circular plate undergoing axisymmetric radial
vibrations.)

Considering force equilibrium condition along the radial direction $(r)$ in
the infinitesimal plate element as shown in Figure 8, we obtain:

$\frac{\partial N_{r}}{\partial r}+\frac{1}{r}\frac{\partial
N_{r\theta}}{r}+\frac{N_{r}-N_{\theta}}{r}=\rho
h\frac{\partial^{2}u_{r}}{\partial t^{2}}$ (46)

For axisymmetric case, the equilibrium equation can be written as:

$\frac{\partial N_{r}}{\partial r}+\frac{N_{r}-N_{\theta}}{r}=\rho
h\frac{\partial^{2}u_{r}}{\partial t^{2}}$ (47)

From the expressions of radial and circumferential forces obtained in
equations (43) and (44) respectively, we obtain the following expression for
governing equation of axisymmetric radial in-plane vibration:

$\frac{E}{1-\nu^{2}}\left(\frac{\partial^{2}u_{r}}{\partial
r^{2}}+\frac{1}{r}\frac{\partial u_{r}}{\partial
r}-\frac{u_{r}}{r^{2}}\right)=\rho\frac{\partial^{2}u_{r}}{\partial t^{2}}$
(48)

Considering harmonic motion, we can express $u_{r}(r,t)=U_{r}(r)e^{i\omega
t}$, and re-write the governing equation of motion (upon dividing all terms in
the equation by $e^{i\omega t}$):

$\frac{E}{\rho\left(1-\nu^{2}\right)}\left(\frac{d^{2}U_{r}}{dr^{2}}+\frac{1}{r}\frac{dU_{r}}{dr}-\frac{U_{r}}{r^{2}}\right)+\omega^{2}U_{r}=0$
(49)

The general solution for equation (49) is of the form:

$U_{r}(r)=A_{1}J_{1}\left(\beta\frac{r}{a}\right)+A_{2}Y_{1}\left(\beta\frac{r}{a}\right)$
(50)

where,

$\beta=\sqrt{\frac{\rho a^{2}\left(1-\nu^{2}\right)}{E}}\times\omega$ (51)

and $J_{1}(\frac{\beta r}{a})$ is Bessel function of first kind of order one
and $Y_{1}(\frac{\beta r}{a})$ is Bessel function of second kind of order one.
The constants $A_{1}$ and $A_{2}$ are determined from appropriate boundary
conditions.

##  Appendix B Effect of inertia of lateral motion on axisymmetric vibration
of thick plates

For modeling the effect of inertia of lateral motion on axisymmetric
vibration, a thick rectangular plate undergoing axisymmetric extensional
vibration is analyzed and the solution is then extended to circular plates.
The displacement field along $x$, $y$ and $z$ for a rectangular plate
undergoing axisymmetric radial vibration with lateral displacement in the
$z-$direction are expressed as:

$\displaystyle u_{x}(t)=u(x,t)$ (52) $\displaystyle u_{y}(t)=0$ (53)
$\displaystyle u_{z}(t)=-\nu z\frac{\partial u(x,t)}{\partial x}$ (54)

The kinetic energy of the plate can be expressed as:

$\begin{split}T&=\frac{1}{2}\int_{0}^{L}{\rho A(\frac{\partial u}{\partial
t})^{2}}dx+\frac{1}{2}\int_{0}^{L}{\rho\nu^{2}\iint{z^{2}dA\left(\frac{\partial^{2}u}{\partial
x\partial t}\right)^{2}}}dx\\\ &=\frac{1}{2}\int_{0}^{L}{\rho A(\frac{\partial
u}{\partial
t})^{2}}dx+\frac{1}{2}\int_{0}^{L}{\rho\nu^{2}I_{zz}\left(\frac{\partial^{2}u}{\partial
x\partial t}\right)^{2}}dx\end{split}$ (55)

where $\rho$ denotes the material density, $A$ denotes area of cross-section,
and $I_{zz}$ is the area moment of inertia of the plate along the
$z-$direction (thickness). By extended Hamilton’s principle, we obtain the
governing equation for radial vibration including the effect of lateral
displacement as:

$\rho\nu^{2}I_{zz}\frac{\partial^{4}u(x,t)}{\partial x^{2}\partial
t^{2}}+\frac{EA}{1-\nu^{2}}\frac{\partial^{2}u}{\partial x^{2}}=\rho
A\frac{\partial^{2}u(x,t)}{\partial t^{2}}$ (56)

Assuming harmonic vibrations, with solution for displacement of form
$u(x,t)=U(x)\cos(\omega t)$, we can re-write the governing equation as:

$\left(\frac{EA}{1-\nu^{2}}-\rho\omega^{2}\nu^{2}I_{zz}\right)U"(x)+\rho
A\omega^{2}U(x)=0$ (57)

Thus, we obtain the modified dimensionless frequency parameter as:

$\beta=\sqrt{\frac{\rho L^{2}}{\frac{E}{1-\nu^{2}}-\frac{\rho\\\
\omega^{2}\nu^{2}I_{zz}}{A}}}\times\omega$ (58)

Extending this solution to circular thick plates, the modified dimensionless
frequency parameter is expressed as:

$\beta=\sqrt{\frac{\rho
a^{2}}{\frac{E}{1-\nu^{2}}-\frac{\rho\omega^{2}\nu^{2}I_{zz}}{A}}}\times\omega$
(59)

Re-arranging the above equation, we obtain the relation:

$\displaystyle\frac{E}{\rho
a^{2}(1-\nu^{2})}=\left(\frac{1}{\beta^{2}}+\frac{\nu^{2}I_{zz}}{Aa^{2}}\right)\omega^{2}$
(60) $\displaystyle\frac{E}{\rho
a^{2}(1-\nu^{2})}=\frac{\omega^{2}}{\beta_{m}^{2}}$ (61)

where

$\frac{1}{\beta_{m}^{2}}=\frac{1}{\beta^{2}}+\frac{\nu^{2}I_{zz}}{Aa^{2}}$
(62)

For a circular disc, the area moment of inertia along the z-axis $(I_{zz})$ is
not constant. Therefore an optimal solution was calculated by minimizing the
error between analytically obtained and FEM simulation result for resonance
frequency of a solid disc with increasing thickness to radius ratio. Using the
optimized moment of inertia factor, the modified dimensionless frequency
parameter incorporating lateral displacement is expressed as:

$\frac{1}{\beta_{m}^{2}}=\frac{1}{\beta^{2}}+\frac{\nu^{2}\times 3.93568\times
h^{2}}{12\times a^{2}}$ (63)

This relation is used for the calculation of natural frequencies for a thick
circular disc with a square PZT transducer affixed on one of the circular
faces.

## References

  * [1] L. Bertolini, M. Gastaldi, M. Pedeferri, E. Redaelli, Prevention of steel corrosion in concrete exposed to seawater with submerged sacrificial anodes, Corrosion Science 44 (7) (2002) 1497–1513.
  * [2] S. Szabo, I. Bakos, Cathodic protection with sacrificial anodes, Corrosion Reviews 24 (3-4) (2006) 231–280.
  * [3] V. Cicek, Cathodic protection: Industrial solutions for protecting against corrosion, John Wiley & Sons, 2013.
  * [4] R. Brousseau, B. Baldock, Laboratory study of sacrificial anodes for reinforced concrete, Corrosion 54 (3) (1998) 241–245.
  * [5] J.-A. Jeong, W.-S. Chung, Y.-H. Kim, Electrochemical measurements of cathodic protection for reinforced concrete piles in a marine environment using embedded corrosion monitoring sensors, Metals and Materials International 19 (3) (2013) 445–452.
  * [6] P. Astuti, R. Rafdinal, H. Hamada, Y. Sagawa, D. Yamamoto, K. Kamarulzaman, Effectiveness of rusted and non-rusted reinforcing bar protected by sacrificial anode cathodic protection in repaired patch concrete, in: IOP Conference Series: Earth and Environmental Science, Vol. 366, IOP Publishing, 2019, p. 012013.
  * [7] U. M. Angst, A critical review of the science and engineering of cathodic protection of steel in soil and concrete, Corrosion 75 (12) (2019) 1420–1433.
  * [8] A. Farooq, M. Hamza, Q. Ahmed, K. M. Deen, Evaluating the performance of zinc and aluminum sacrificial anodes in artificial seawater, Electrochimica Acta 314 (2019) 135–141.
  * [9] D. Ai, H. Luo, H. Zhu, Numerical and experimental investigation of flexural performance on pre-stressed concrete structures using electromechanical admittance, Mechanical Systems and Signal Processing 128 (2019) 244–265.
  * [10] N. Kaur, S. Goyal, K. Anand, G. K. Sahu, A cost-effective approach for assessment of pre-stressing force in bridges using piezoelectric transducers, Measurement 168 108324.
  * [11] W. Ostachowicz, P. Kudela, P. Malinowski, T. Wandowski, Damage localisation in plate-like structures based on PZT sensors, Mechanical Systems and Signal Processing 23 (6) (2009) 1805–1829.
  * [12] T.-C. Huynh, S.-Y. Lee, N.-L. Dang, J.-T. Kim, Sensing region characteristics of smart piezoelectric interface for damage monitoring in plate-like structures, Sensors 19 (6) (2019) 1377.
  * [13] J. Zhu, X. Qing, X. Liu, Y. Wang, Electromechanical impedance-based damage localization with novel signatures extraction methodology and modified probability-weighted algorithm, Mechanical Systems and Signal Processing 146 107001\.
  * [14] D. D. Mandal, S. Banerjee, Identification of breathing type disbonds in stiffened panels using non-linear lamb waves and built-in circular PWT array, Mechanical Systems and Signal Processing 117 (2019) 33–51.
  * [15] H. Chen, B. Xu, T. Zhou, Y.-L. Mo, Debonding detection for rectangular cfst using surface wave measurement: Test and multi-physical fields numerical simulation, Mechanical Systems and Signal Processing 117 (2019) 238–254.
  * [16] B. Xu, H. Chen, Y.-L. Mo, T. Zhou, Dominance of debonding defect of CFST on PZT sensor response considering the meso-scale structure of concrete with multi-scale simulation, Mechanical Systems and Signal Processing 107 (2018) 515–528.
  * [17] M. Aslam, P. Nagarajan, M. Remanan, Dynamic response of piezoelectric smart beam with adhesive debonding, Material Design & Processing Communications 2 (4) (2020) e159.
  * [18] Z. S. Tang, Y. Y. Lim, S. T. Smith, I. Izadgoshasb, Development of analytical and numerical models for predicting the mechanical properties of structural adhesives under curing using the PZT-based wave propagation technique, Mechanical Systems and Signal Processing 128 (2019) 172–190.
  * [19] M. Haq, S. Bhalla, T. Naqvi, Fatigue damage and residual fatigue life assessment in reinforced concrete frames using PZT-impedance transducers, Cement and Concrete Composites (2020) 103771.
  * [20] K. K. Maurya, A. Rawat, G. Jha, Smart materials and electro-mechanical impedance technique: A review, Materials Today: Proceedings (2020).
  * [21] P. Jiao, K.-J. I. Egbe, Y. Xie, A. Matin Nazar, A. H. Alavi, Piezoelectric sensing techniques in structural health monitoring: A state-of-the-art review, Sensors 20 (13) (2020) 3730.
  * [22] L. Qiu, X. Lin, Y. Wang, S. Yuan, W. Shi, A mechatronic smart skin of flight vehicle structures for impact monitoring of light weight and low-power consumption, Mechanical Systems and Signal Processing 144 (2020) 106829.
  * [23] R. C. Sriramadasu, Y. Lu, S. Banerjee, Identification of incipient pitting corrosion in reinforced concrete structures using guided waves and piezoelectric wafer transducers, Structural Health Monitoring 18 (1) (2019) 164–171.
  * [24] A. Kocherla, K. V. Subramaniam, Embedded Smart PZT-based Sensor for Internal Damage Detection in Concrete under Applied Compression, Measurement (2020) 108018\.
  * [25] J. Wang, W. Li, C. Lan, P. Wei, W. Luo, Electromechanical impedance instrumented piezoelectric ring for pipe corrosion and bearing wear monitoring: A proof-of-concept study, Sensors and Actuators A: Physical (2020) 112276.
  * [26] W. Shi, Y. Chen, P. Liu, D. Xu, Corrosion investigation of reinforced concrete based on piezoelectric smart materials, Materials 12 (3) (2019) 519.
  * [27] V. Talakokula, S. Bhalla, A. Gupta, Monitoring early hydration of reinforced concrete structures using structural parameters identified by piezo sensors via electromechanical impedance technique, Mechanical Systems and Signal Processing 99 (2018) 129–141.
  * [28] C. Zhang, G. P. Panda, Q. Yan, W. Zhang, C. Vipulanandan, G. Song, Monitoring early-age hydration and setting of portland cement paste by piezoelectric transducers via electromechanical impedance method, Construction and Building Materials 258 (2020) 120348.
  * [29] V. Talakokula, S. Bhalla, Reinforcement corrosion assessment capability of surface bonded and embedded piezo sensors for reinforced concrete structures, Journal of Intelligent Material Systems and Structures 26 (17) (2015) 2304–2313.
  * [30] V. Talakokula, S. Bhalla, R. Ball, C. Bowen, G. Pesce, R. Kurchania, B. Bhattacharjee, A. Gupta, K. Paine, Diagnosis of carbonation induced corrosion initiation and progression in reinforced concrete structures using piezo-impedance transducers, Sensors and Actuators A: Physical 242 (2016) 79–91.
  * [31] W. Li, T. Liu, D. Zou, J. Wang, T.-H. Yi, PZT based smart corrosion coupon using electromechanical impedance, Mechanical Systems and Signal Processing 129 (2019) 455–469.
  * [32] V. Giurgiutiu, Structural Health Monitoring with Piezoelectric Wafer Active Sensors (Second Edition), Academic Press, 2014.
  * [33] Y. Meng, L. Liu, D. Zhang, C. Dong, Y. Yan, A. A. Volinsky, L.-N. Wang, Initial formation of corrosion products on pure zinc in saline solution, Bioactive materials 4 (2019) 87–96.
  * [34] J. Perkins, W. Luebke, K. Graham, J. Todd, Anodic corrosion of zinc alloys in seawater, Journal of the Electrochemical Society 124 (6) (1977) 819.
  * [35] W. Fürbeth, M. Stratmann, The delamination of polymeric coatings from electrogalvanized steel–a mechanistic approach.: Part 3: delamination kinetics and influence of CO2, Corrosion Science 43 (2) (2001) 243–254.


# On the Optimal Combination of Tensor Optimization Methods

Dmitry Kamzolov a Alexander Gasnikova,b,c and Pavel Dvurechenskyc,d.
aMoscow Institute of Physics and Technology, Moscow, Russia;
b National Research University Higher School of Economics, Moscow, Russia;
cInstitute for Information Transmission Problems RAS, Moscow, Russia;
d Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany

###### Abstract

We consider the minimization problem of a sum of a number of functions having
Lipshitz $p$-th order derivatives with different Lipschitz constants. In this
case, to accelerate optimization, we propose a general framework allowing to
obtain near-optimal oracle complexity for each function in the sum separately,
meaning, in particular, that the oracle for a function with lower Lipschitz
constant is called a smaller number of times. As a building block, we extend
the current theory of tensor methods and show how to generalize near-optimal
tensor methods to work with inexact tensor step. Further, we investigate the
situation when the functions in the sum have Lipschitz derivatives of a
different order. For this situation, we propose a generic way to separate the
oracle complexity between the parts of the sum. Our method is not optimal,
which leads to an open problem of the optimal combination of oracles of a
different order.

##  1 Introduction

Higher-order (tensor) methods, which use the derivatives of the objective up
to order $p$, recently have become an area of intensive research effort in
optimization, despite the idea is quite old and goes back to the works of P.
Chebyshev and L. Kantorovich ([5] and [18]). One of the reasons is that the
lower complexity bounds were obtained in [2, 1, 26], which opened a question
of optimal methods, and it was shown in [26] that Taylor expansion of a convex
function can be made convex by appropriate regularization, leading to
tractable tensor step implementable in practice. Recently nearly optimal
methods were obtained in [26, 13], and extensions for Hölder continuous
higher-order derivatives were proposed in [16, 28]. In this paper, we consider
an interesting question that is still open in the theory of tensor methods.
Namely, if a tensor method minimizes a function $f$ up to accuracy
$\varepsilon$ in $N_{f}(\varepsilon)$ oracle calls and possibly another tensor
method minimizes a function $g$ in $N_{g}(\varepsilon)$ oracle calls, is it
possible to combine these two methods to minimize $f+g$ up to accuracy
$\varepsilon$ in $\tilde{O}(N_{f}(\varepsilon))$ oracle calls for $f$ and
$\tilde{O}(N_{g}(\varepsilon))$ oracle calls for $g$? To say more, we would
like to have a generic approach which can take as an input different
particular algorithms for each component. For simplicity, we consider a sum of
two functions, but we believe that the approach can be generalized for an
arbitrary number of functions. Note that in the last few years, the answer to
this question plays a crucial role in the development of optimal algorithms
for convex decentralized distributed optimization [21, 19, 9, 14, 3, 27].

Some results in this direction are known for the first-order methods $p=1$
[20, 22, 19, 3, 10] and for the case of the sum of two functions with the
second being so simple that it can be incorporated directly in the tensor step
[17] like in composite first-order methods [24]. Yet, the general theory on
how to combine different methods to obtain optimal complexity for tensor
methods is not yet developed for $p\geq 2$.

First, we consider uniformly convex sum of two functions $f+g$, each having
Lipschitz derivatives of the same order $p$. Our approach is based on the
recent framework of near-optimal tensor methods [13], which extends the
algorithm of [23] to tensor methods. Our idea is to apply the near-optimal
tensor method to the sum, considering $g$ as a composite and including it into
the tensor step without its Taylor approximation. Then each tensor step
requires to solve properly regularized uniformly convex auxiliary problem.
This is again done by the nearly optimal tensor method. Since the auxiliary
problem turns out to be very well conditioned, it is possible to solve it very
fast, and we only need to call the oracle for $g(x)$. The careful analysis
allows to separate the oracle complexity as we call the oracle for $f(x)$ only
on outer iterations and oracle for $g(x)$ only on the inner, resulting in the
optimal number of oracle calls for $f$ and for $g$ separately. As a building
block, we explain how to extend near-optimal tensor methods to work with
inexact tensor step, extending the current theory since existing near-optimal
methods assume that the tensor step is exact. If the function is not uniformly
convex, one can use a standard regularization technique with a small
regularization parameter.

Note, there exist several accelerated envelopes that allow accelerating tensor
methods: Monteiro–Svaiter envelop [23, 25, 12, 17, 4], Doikov–Nesterov
envelope [7] envelope. Further, we will use Monteiro–Svaiter envelope. Note
that it seems that Doikov–Nesterov envelop and standard direct Nesterov’s
tensor acceleration [26] does not well suited for our purposes. Note also that
for all envelopes for the moment, it’s not known with what accuracy we should
solve the auxiliary problem. In Monteiro–Svaiter envelop we working on this in
Appendix B. Among different variants of Monteiro–Svaiter envelop, we preferred
variant from [4], but we generalize (see Appendixes) [4] on the composite case
[17] and uniformly convex problem target functions [12].

Second, we consider the case when $f$ and $g$ have Lipshitz derivatives of
different orders $p_{f}$ and $p_{g}$, respectively. We apply a similar
technique as above, but using non-accelerated tensor methods as building
blocks. We demonstrate that in this case, complexities can also be separated,
but they turn out to be not optimal. This states an open problem of an optimal
combination of optimal methods that use oracles of a different order.

As far as we know for the moment, there exists only one optimal result
concerns the methods of different orders. This is the result from [3], where
authors considered sliding of optimal $0$-order and $1$-order methods.

##  2 Problem Statement and Preliminaries

In what follows, we work in a finite-dimensional linear vector space $E$. Its
dual space, the space of all linear functions on $E$, is denoted by
$E^{\ast}$. For $x\in E$ and $s\in E^{\ast}$, we denote by $\left\langle
s,x\right\rangle$ the value of a linear function $s$ at $x$. For the (primal)
space $E$, we introduce a norm $\|\,\cdot\,\|_{E}$. Then the dual norm is
defined in the standard way:

$\|s\|_{E^{\ast}}=\max\limits_{x\in E}\left\\{\left\langle
s,x\right\rangle:\,\|x\|_{E}\leq 1\right\\}.$

Finally, for a convex function $f:\textbf{dom }f\rightarrow R$ with
$\textbf{dom }f\subseteq E$ we denote by $\nabla f(x)\in E^{\ast}$ one of its
subgradients.

We consider the following convex optimization problem:

$\min\limits_{x\in E}F(x)=f(x)+g(x),$ (1)

where $f(x)$ and $g(x)$ are convex functions with Lipschitz $p$-th derivative,
it means that

$\|D^{p}f(x)-D^{p}f(y)\|\leq L_{p,f}\|x-y\|.$ (2)

Then Taylor approximation of function $f(x)$ can be written as follows:

$\Omega_{p}(f,x;y)=f(x)+\sum_{k=1}^{p}\frac{1}{k!}D^{k}f(x)\left[y-x\right]^{k},y\in
E$ (3)

By (2) and the standard integration we can get next inequality

$|f(y)-\Omega_{p}(f,x;y)|\leq\frac{L_{p,f}}{(p+1)!}\|y-x\|^{p+1}.$ (4)

Now we introduce an additional condition for the functions.

######  Definition 1.

Function $F(x)$ is $r$-uniformly convex ($r\geq 2$) if

$F(y)\geq F(x)+\left\langle\nabla
F(x),y-x\right\rangle+\frac{\sigma_{r}}{r}\|y-x\|^{r},\quad\forall x,y\in E$

with constant $\sigma_{r}$

One of the main examples of $r$-uniformly convex functions is
$\frac{1}{r}\|x\|^{r}$ from Lemma 5 [7].

######  Lemma 1.

For fixed $r\geq 2$, consider the following function:

$f_{r}(x)=\frac{1}{r}\|x\|^{r},\quad x\in\mathbb{E}.$

Function $f_{r}(x)$ is uniformly convex of degree $r$ with
$\sigma_{r}=2^{2-r}$.

Problem (1) can be solved by tensor methods [26] or its accelerated versions
[25], [4], [17], [13] . This methods have next basic step:

$T_{H}(x)=\operatornamewithlimits{argmin}_{y}\left\\{\Omega_{p}(f+g,x;y)+\frac{H_{p}}{p!}\|y-x\|^{p+1}\right\\}.$

For $H_{p}\geq L_{p}$ this subproblem is convex and hence implementable. Note
that this method does not use information about sum type problem and compute
their derivatives the same number of times. We want to separate computation
complexity of high-order derivatives for sum of two functions. In next section
we will describe this idea in more details.

As an accelerated optimal method, we introduce Accelerated Taylor Descent
(ATD) from [4]. But for our paper we need to get a composite variant of ATD.

Algorithm 1 Composite Accelerated Taylor Descent

1: Input: convex function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ such that
$\nabla^{p}f$ is $L_{p}$-Lipschitz, proper closed convex
$g:\mathbb{R}^{d}\rightarrow\mathbb{R}$.

2: Set $A_{0}=0,x_{0}=y_{0}$

3: for $k=0$ to $k=K-1$ do

4: Compute a pair $\lambda_{k+1}>0$ and $y_{k+1}\in\mathbb{R}^{d}$ such that
$\frac{1}{2}\leq\lambda_{k+1}\frac{H_{p,f}\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}{(p-1)!}\leq\frac{p}{p+1}\,,$
where
$y_{k+1}=\operatornamewithlimits{argmin}_{y}\left\\{\Omega_{p}(f,\tilde{x}_{k};y)+\frac{H_{p,f}}{p!}\|y-\tilde{x}_{k}\|^{p+1}+g(y)\right\\}\,,$
(5) and
$a_{k+1}=\frac{\lambda_{k+1}+\sqrt{\lambda_{k+1}^{2}+4\lambda_{k+1}A_{k}}}{2}\text{
, }A_{k+1}=A_{k}+a_{k+1}\text{ , and
}\tilde{x}_{k}=\frac{A_{k}}{A_{k+1}}y_{k}+\frac{a_{k+1}}{A_{k+1}}x_{k}\,.$

5: Update $x_{k+1}:=x_{k}-a_{k+1}\nabla f(y_{k+1})-a_{k+1}g^{\prime}(y_{k+1})$

6: return $y_{K}$

Algorithm 1 is a generalization of ATD from [4] for composite optimization
problem. It means, that we try to minimize sum of two functions
$F(x)=f(x)+g(x)$, where $g(x)$ is a proper closed convex function and
subproblem (5) with $g(x)$ is easy to solve. Note that if $g(x)$ smooth and
has a gradient, so $g^{\prime}(y_{k+1})=\nabla g(y_{k+1})$, but if $g(x)$ has
only subgradient, we should introduce $g^{\prime}(y_{k+1})$. Similarly to
(2.9) from [6] by using optimality condition for (5) we define

$g^{\prime}(y_{k+1})=-\nabla\Omega_{p}(f,\tilde{x}_{k};y_{k+1})-\frac{(p+1)H_{p,f}}{p!}\|y_{k+1}-\tilde{x}_{k}\|^{p-1}(y_{k+1}-\tilde{x}_{k})$

######  Theorem 1.

Let $F(x)=f(x)+g(x)$, where $f$ denote a convex function whose $p^{th}$
derivative is $L_{p}$-Lipschitz, $g(x)$ is a proper closed convex function and
let $x_{\ast}$ denote a minimizer of $F$. Then CATD satisfies, with
$c_{p}=2^{p-1}(p+1)^{\frac{3p+1}{2}}/(p-1)!$,

$F(y_{k})-F(x_{\ast})\leq\frac{c_{p}L_{p}R^{p+1}}{k^{\frac{3p+1}{2}}}\,,$ (6)

where

$R=\|x_{0}-x^{\ast}\|$ (7)

is the maximal radius of the initial set. Furthermore each iteration of ATD
can be implemented in $\tilde{O}(1)$ calls to a $p^{th}$-order Taylor
expansion oracle, where $\tilde{O}$ means up to logarithmic factors.

We prove this theorem similarly to the proof of [4] in Appendix A.

Now we assume that function $F(x)$ is additionally $r$-uniformly convex, hence
we may get a speed up by using restarts. We formulate method and theorem for
CATD with restarts.

Algorithm 2 CATD with restarts

1: Input: $r$-unformly convex function $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$
with constant $\sigma_{r}$ and CATD conditions.

2: Set $z_{0}=x_{0}=0$ and $R_{0}=\|z_{0}-x_{\ast}\|$.

3: for $k=0,$ to $K$ do

4: Set $R_{k}=R_{0}\cdot 2^{-k}$ and
$N_{k}=\max\left\\{\left\lceil\left(\frac{rc_{p}L_{p}2^{r}}{\sigma_{r}}R_{k}^{p+1-r}\right)^{\frac{2}{3p+1}}\right\rceil,1\right\\}.$
(8)

5: Set $z_{k+1}:=y_{N_{k}}$ as the output of CATD started from $z_{k}$ and run
for $N_{k}$ steps.

6: return $z_{K}$

######  Theorem 2.

CATD with restarts for $r$-uniformly convex function $F$ with constant
$\sigma_{r}$ converges with $N_{r}$ steps of CATD per restart and with $N_{F}$
total number of CATD steps, where

$N_{F}=\tilde{O}\left[\left(\frac{L_{p,f}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right].$
(9)

We prove this theorem similarly to [12] in Appendix C.

##  3 Uniformly convex functions

We consider similar to (1) problem.

$\min F(x)=f(x)+g(x),$ (10)

where additionally $F(x)$ is $r$-uniformly convex function. We also assume,
that $p+1\geq r$.

If we will use Algorithm 2 for problem (10) we get next convergence speed. To
reach $F(x_{N})-F(x^{\ast})\leq\varepsilon$, we need $N_{f}+N_{g}$ iterations,
where

$\displaystyle
N_{f}=\tilde{O}\left[\left(\frac{L_{p,f}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right],$
(11) $\displaystyle
N_{g}=\tilde{O}\left[\left(\frac{L_{p,g}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right].$
(12)

Note that for this method we compute $N_{f}+N_{g}$ derivatives for both $f(x)$
and $g(x)$ functions. We want to separate this computations and compute
$N_{f}$ derivatives for the function $f$ and $N_{g}$ derivatives for the
function $g$.

Next we will describe the our framework. We assume that $L_{p,f}<L_{p,g}$, it
means that $N_{f}<N_{g}$. For that case we consider problem 10 as a composite
problem with $g(x)$ as a composite part. We solve this problem by Algorithm 2.
In this algorithm we have tensor subproblem (5). To solve this subproblem we
run another Algorithm 2 with objective function
$\Omega_{p}(f,\tilde{x}_{k};y)+\frac{H_{p,f}}{p!}\|y-\tilde{x}_{k}\|^{p+1}+g(y)$
up to the desired accuracy. As we will prove next, this subproblem may be
solved linearly by the desired accuracy, so we should not worry too much about
the level of the desired accuracy. We write more details about the correctness
of this part and the more precise level of desired accuracy in Appendix B. As
a result we get Algorithm 3.

Algorithm 3 Tensor Methods Combination

1: Input: $r$-unformly convex function $F(x)=f(x)+g(x)$ with constant
$\sigma_{r}$, convex functions $f(x)$ and $g(x)$ such that $\nabla^{p}f$ is
$L_{p,f}$-Lipschitz and $\nabla^{p}g$ is $L_{p,g}$-Lipschitz.

2: Set $z_{0}=y_{0}=x_{0}$

3: for $k=0,$ to $K-1$ do

4: Run Algorithm 2 for problem $f(x)+g(x)$, where $g(x)$ is a composite part.

5: for $m=0,$ to $M-1$ do

6: Run Algorithm 2 up to desired accuracy for subproblem
$\min\limits_{y}\left(\Omega_{p}(f,\tilde{x}_{k};y)+\frac{H_{p,f}}{p!}\|y-\tilde{x}_{k}\|^{p+1}+g(y)\right)$

7: return $z_{K}$

Now we prove that this framework split computation’s complexities.

######  Theorem 3.

Assume $F(x)$ is $r$-uniformly convex function ($r\geq 2$), $f(x)$ and $g(x)$
are convex functions with Lipshitz $p$-th derivative ($p\geq 1$, $p+1\geq r$)
and $L_{p,f}<L_{p,g}$. Then by using our framework with $H_{p,f}=2L_{p,f}$,
method converges to $F(x_{N})-F(x^{\ast})\leq\varepsilon$ with $N_{f}$ as (11)
computations of derivatives $f(x)$ and $N_{g}$ as (12) computation of
derivatives $g(x)$.

###### Proof.

As we prove in 2 for the outer composite method with constant
$H_{p,f}=2L_{p,f}$ we need to make

$N_{out}=\tilde{O}\left[\left(\frac{2pL_{p,f}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right]$

outer steps, it means that we need to compute $N_{out}=N_{f}$ derivatives of
$f(x)$. Now we compute how much steps of inner method we need. Note that inner
function has Lipshitz $p$-th derivative $H_{p,f}+L_{g}$. Also it is
$(p+1)$-uniformly convex with $\sigma_{p+1}$. To compute $\sigma_{p+1}$ we
need to split $H_{p,f}$ into two parts $H_{p,f}=H_{1}+H_{2}$, where the first
part needs to make $\Omega_{p}(f,x;y)+\frac{H_{1}}{p!}\|y-x\|^{p+1}$ a convex
function and the second part needs to make $\frac{H_{2}}{p!}\|y-x\|^{p+1}$ a
uniformly convex term. Hence, from Lemma 1 we have
$\sigma_{p+1}=\frac{H_{2}(p+1)2^{2-p}}{p!}$. We take $H_{1}=H_{2}=L_{p,f}$. As
a result, the number of inner iterations equal to

$\displaystyle N_{inn}$
$\displaystyle=\tilde{O}\left[\left(\frac{2L_{p,f}+L_{p,g}}{\frac{(p+1)L_{p,f}2^{2-p}}{p!}}\right)^{\frac{2}{3p+1}}\log\left(\frac{F(x_{0})-F(x^{\ast})+H_{p,f}R^{p+1}}{\varepsilon}\right)\right]$
(13)
$\displaystyle=\tilde{O}\left[\left(\frac{2L_{p,f}+L_{p,g}}{\frac{(p+1)L_{p,f}2^{2-p}}{p!}}\right)^{\frac{2}{3p+1}}\right]\overset{L_{p,f}<L_{p,g}}{=}\tilde{O}\left[\left(\frac{L_{p,g}}{L_{p,f}}\right)^{\frac{2}{3p+1}}\right]$

Hence the total number of inner iterations and total number of derivative’s
computations of $g(x)$ is

$\displaystyle N_{g}$ $\displaystyle=N_{out}\cdot
N_{inn}=\tilde{O}\left[\left(\frac{L_{p,f}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right]\cdot\tilde{O}\left[\left(\frac{L_{p,g}}{L_{p,f}}\right)^{\frac{2}{3p+1}}\right]$
$\displaystyle=\tilde{O}\left[\left(\frac{L_{p,g}R^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\right].$

So we prove the theorem and split computation complexities. ∎

Note, that this framework also easily adapts to methods without accelerating
like [26], [6]. But, unfortunately, it is much harder to adapt for other
acceleration schemes. As we know, it is possible to adapt this framework for
speed ups from [12] and [17] for $p\geq 2$, but for $p=1$ it may arise some
troubles because of adaptive inner regularisation and hence hard subproblem.
As for [26] acceleration it also hard to adapt, because the inner subproblem
is much harder with increasing complexity.

Also note that this framework can be generalized to the problem of the sum of
$m$ functions.

##  4 General convex functions

We consider (1) problem for convex functions.

If we will use Algorithm 1 for problem (1) we get next convergence speed. To
reach $F(x_{N})-F(x^{\ast})\leq\varepsilon$, we need $N_{f}+N_{g}$ iterations,
where

$\displaystyle
N_{f}=\tilde{O}\left[\left(\frac{L_{p,f}R^{p+1}}{\varepsilon}\right)^{\frac{2}{3p+1}}\right],$
(14) $\displaystyle
N_{g}=\tilde{O}\left[\left(\frac{L_{p,g}R^{p+1}}{\varepsilon}\right)^{\frac{2}{3p+1}}\right].$
(15)

Now we prove that the our framework split computation’s complexities for
convex functions.

######  Theorem 4.

Assume $f(x)$ and $g(x)$ are convex functions with Lipshitz $p$-th derivative
($p\geq 1$, $p+1\geq q$) and $L_{p,f}<L_{p,g}$. Then by using our framework
with $H_{p,f}=2L_{p,f}$, method converges to
$F(x_{N})-F(x^{\ast})\leq\varepsilon$ with $N_{f}$ as (14) computations of
derivatives $f(x)$ and $N_{g}$ as (15) computation of derivatives $g(x)$.

###### Proof.

For the outer method 1 with constant $H_{p,f}=2L_{p,f}$, we make

$N_{out}=\tilde{O}\left[\left(\frac{2L_{p,f}R^{p+1}}{\varepsilon}\right)^{\frac{2}{3p+1}}\right]$

outer steps, it means that we need to compute $N_{out}=N_{f}$ derivatives of
$f(x)$. For inner method 1 to solve subproblem (5) similarly we has the same
rate as (13) Hence the total number of inner iterations and total number of
derivative’s computations of $g(x)$ is

$\displaystyle N_{g}$ $\displaystyle=N_{out}\cdot
N_{inn}=\tilde{O}\left[\left(\frac{2L_{p,f}R^{p+1}}{\varepsilon}\right)^{\frac{2}{3p+1}}\right]\cdot\tilde{O}\left[\left(\frac{L_{p,g}}{L_{p,f}}\right)^{\frac{2}{3p+1}}\right]$
$\displaystyle=\tilde{O}\left[\left(\frac{L_{p,g}R^{p+1}}{\varepsilon}\right)^{\frac{2}{3p+1}}\right].$

So for convex function computation complexities are also splitting. ∎

##  5 Multi-Composite Tensor Method

The natural generalization of framework 3 is to use for the sum of two
functions with different smoothness and hence different order of methods. But
as we know, in the literature there is no method that works with the sum of
two functions with different smoothness. We need to use tensor methods for the
smallest order. To improve this situation we we introduce the new type of
problem, where $f(x)$ and $g(x)$ have different smoothness order. Similar idea
for the first and second order was in the paper [8]. Next we propose a tensor
method to solve such problem with splitting the complexities.

We introduce a multi-composite tensor optimization problem.

$F(x)=f(x)+g(x)+h(x),$ (16)

where $h(x)$ is a simple proper closed convex function, $f(x)$ is a convex
functions with Lipschitz $q$-th derivative and $g(x)$ is a convex functions
with Lipschitz $p$-th derivative. By using Theorem 1 from [26] we can get for
$f(x)$ if $H_{q,f}\geq qL_{q,f}$, that

$\Omega_{q}(f,x;y)+\frac{H_{q,f}}{(q+1)!}\|y-x\|^{q+1}$

is convex and

$f(y)\leq\Omega_{q}(f,x;y)+\frac{H_{q,f}}{(q+1)!}\|y-x\|^{q+1}$ (17)

Now we propose our method

$\displaystyle
T_{H_{q,f},H_{p,g}}(x)\in\operatornamewithlimits{Argmin}\limits_{y}\left\\{\Omega_{q}(f,x;y)+\frac{H_{q,f}}{(q+1)!}\|y-x\|^{q+1}\right.$
(18)
$\displaystyle+\left.\Omega_{p}(g,x;y)+\frac{H_{p,g}}{(p+1)!}\|y-x\|^{p+1}+h(y)\right\\}$
(19)

Then

$x_{t+1}=T_{H_{q,f},H_{p,g}}(x_{t})$ (20)

One can see that our method based on method [26] and combine models of two
functions. Next we start to prove, that our method converges and split the
complexities.

We assume that exists at least one solution $x_{\ast}$ of problem (1) and the
level sets of $F$ are bounded. By the first-order optimality condition for
$T=T_{H_{q,f},H_{p,g}}(x)$ we get:

$\displaystyle\nabla\Omega_{q}(f,x;T)+\frac{H_{q,f}(T-x)}{q!}\|T-x\|^{q-1}$
(21) $\displaystyle+$
$\displaystyle\nabla\Omega_{p}(g,x;T)+\frac{H_{p,g}(T-x)}{p!}\|T-x\|^{p-1}+\partial
h(T)=0$

For the proof we need next small lemma.

######  Lemma 2.

For any $x\in E$, $H_{q,f}\geq qL_{q,f}$ and $H_{p,g}\geq pL_{p,g}$, we have

$F(T_{H_{q,f},H_{p,g}}(x))\leq\min\limits_{y}\left\\{F(y)+\frac{H_{q,f}+L_{q,f}}{(q+1)!}\|y-x\|^{q+1}+\frac{H_{p,g}+L_{p,g}}{(p+1)!}\|y-x\|^{p+1}\right\\}$
(22)

###### Proof.

$\displaystyle F(T_{H_{q,f},H_{p,g}}(x))$
$\displaystyle\leq\min\limits_{y}\left\\{\Omega_{q}(f,x;y)+\frac{H_{q,f}}{(q+1)!}\|y-x\|^{q+1}\right.$
$\displaystyle+\Omega_{p}(g,x;y)+\frac{H_{p,g}}{(p+1)!}\|y-x\|^{p+1}+h(y)\left.\right\\}$
$\displaystyle\overset{\eqref{eq_sumup}}{\leq}\min\limits_{y}\left\\{F(y)+\frac{H_{q,f}+L_{q,f}}{(q+1)!}\|y-x\|^{q+1}+\frac{H_{p,g}+L_{p,g}}{(p+1)!}\|y-x\|^{p+1}\right\\}$

∎

This leads us to the main theorem, that proves the convergence speed of our
method.

######  Theorem 5.

If $f_{q}(x)$ is convex functions with Lipshitz constant $L_{q,f}$ for $q$-th
derivative, $f_{p}(x)$ is convex functions with Lipshitz constant $L_{p,g}$
for $p$-th derivative; $H_{q,f}\geq qL_{q,f}$ and $H_{p,g}\geq pL_{p,g}$.
$\alpha_{t}$ is chosen such that $\alpha_{0}=1$ and
$\alpha_{t}\in\left[0;1\right]\,t\geq 1$, then for any $t\geq 0$ for method
(20) we have

$F(x_{t+1})-F(x_{\ast})\leq
A_{t}\sum\limits_{i=0}^{t}\left[C_{f}\frac{\alpha_{i}^{q+1}}{A_{i}}\|x_{i}-x_{\ast}\|^{q+1}+C_{g}\frac{\alpha_{i}^{p+1}}{A_{i}}\|x_{i}-x_{\ast}\|^{p+1}\right]$
(23)

where

$C_{f}=\frac{H_{q,f}+L_{q,f}}{(q+1)!},\quad
C_{g}=\frac{H_{p,g}+L_{p,g}}{(p+1)!};$ $A_{t}=\begin{cases}1,\quad t=0\\\
\prod\limits_{i=1}^{t}(1-\alpha_{i}),\quad t\geq 1\end{cases}$ (24)

###### Proof.

From (22)

$\displaystyle F(x_{t+1})$
$\displaystyle\leq\min\limits_{y}\left\\{F(y)+\frac{H_{q,f}+L_{q,f}}{(q+1)!}\|y-x_{t}\|^{q+1}+\frac{H_{p,g}+L_{p,g}}{(p+1)!}\|y-x_{t}\|^{p+1}\right\\}$
$\displaystyle\leq F(y)+C_{f}\|y-x_{t}\|^{q+1}+C_{g}\|y-x_{t}\|^{p+1}$

If we take $y=x_{t}+\alpha_{t}(x_{\ast}-x_{t})$, then by convexity

$\displaystyle F(x_{t+1})\leq
F(y)+C_{f}\alpha_{t}^{q+1}\|x_{\ast}-x_{t}\|^{q+1}+C_{g}\alpha_{t}^{p+1}\|x_{\ast}-x_{t}\|^{p+1}$
$\displaystyle\leq(1-\alpha_{t})F(x_{t})+\alpha_{t}F(x_{\ast})+C_{f}\alpha_{t}^{q+1}\|x_{\ast}-x_{t}\|^{q+1}+C_{g}\alpha_{t}^{p+1}\|x_{\ast}-x_{t}\|^{p+1}.$

Hence

$\displaystyle F(x_{t+1})-F(x_{\ast})$
$\displaystyle\leq(1-\alpha_{t})\left(F(x_{t})-F(x_{\ast})\right)$
$\displaystyle+C_{f}\alpha_{t}^{q+1}\|x_{\ast}-x_{t}\|^{q+1}+C_{g}\alpha_{t}^{p+1}\|x_{\ast}-x_{t}\|^{p+1}$

For $t=0$ and $\alpha_{0}=1$ we get

$\displaystyle F(x_{1})-F(x_{\ast})$ $\displaystyle\leq
C_{f}\|x_{\ast}-x_{0}\|^{q+1}+C_{g}\|x_{\ast}-x_{0}\|^{p+1}$

For $t>0$ we divide both sides by $A_{t}$:

$\displaystyle\frac{1}{A_{t}}(F(x_{t+1})-F(x_{\ast}))$
$\displaystyle\leq\frac{(1-\alpha_{t})}{A_{t}}\left(F(x_{t})-F(x_{\ast})\right)$
$\displaystyle+C_{f}\frac{\alpha_{t}^{q+1}}{A_{t}}\|x_{\ast}-x_{t}\|^{q+1}+C_{g}\frac{\alpha_{t}^{p+1}}{A_{t}}\|x_{\ast}-x_{t}\|^{p+1}$
$\displaystyle\overset{\eqref{eq_A}}{\leq}\frac{1}{A_{t-1}}\left(F(x_{t})-F(x_{\ast})\right)$
$\displaystyle+C_{f}\frac{\alpha_{t}^{q+1}}{A_{t}}\|x_{\ast}-x_{t}\|^{q+1}+C_{g}\frac{\alpha_{t}^{p+1}}{A_{t}}\|x_{\ast}-x_{t}\|^{p+1}$

By summarising both sides we obtain (22) ∎

Next we can fix parameters of this theorem and get next corollary.

######  Corollary 1.

For method (20) and $\alpha_{t}=\frac{p+1}{t+p+1}$ we have

$F(x_{t+1})-F(x_{\ast})\leq
E_{q}\frac{(H_{q,f}+L_{q,f})R^{q+1}}{(t+p+1)^{q}}+E_{p}\frac{(H_{p,g}+L_{p,g})R^{p+1}}{(t+p+1)^{p}}$
(25)

where

$E_{k}=\frac{(p+1)^{k+1}}{(k+1)!},\quad k=\left\\{q,p\right\\}$

###### Proof.

We use

$\displaystyle F(x_{t+1})-F(x_{\ast})$ $\displaystyle\leq
A_{t}\sum\limits_{i=0}^{t}\left[C_{f}\frac{\alpha_{i}^{q+1}}{A_{i}}\|x_{i}-x_{\ast}\|^{q+1}+C_{g}\frac{\alpha_{i}^{p+1}}{A_{i}}\|x_{i}-x_{\ast}\|^{p+1}\right]$
$\displaystyle\overset{\eqref{def_diameter}}{\leq}C_{f}R^{q+1}\sum\limits_{i=0}^{t}\frac{A_{t}\alpha_{i}^{q+1}}{A_{i}}+C_{g}R^{p+1}\sum\limits_{i=0}^{t}\frac{A_{t}\alpha_{i}^{p+1}}{A_{i}}$

Now we compute these sums for $\alpha_{t}=\frac{p+1}{t+p+1}$:

$\displaystyle A_{t}$
$\displaystyle=\prod\limits_{i=1}^{t}(1-\alpha_{i})=\prod\limits_{i=1}^{t}\frac{i}{i+p+1}=\frac{t!\,(p+1)!}{(t+p+1)!}=(p+1)!\prod\limits_{i=1}^{p+1}\frac{1}{t+i}$
$\displaystyle\geq\frac{(p+1)!}{(t+1)^{p+1}}$

For the second sum we get

$\displaystyle\sum\limits_{i=1}^{t}\frac{A_{t}\alpha_{i}^{p+1}}{A_{i}}$
$\displaystyle=\sum\limits_{i=1}^{t}\frac{(p+1)^{p+1}\prod_{j=1}^{p+1}(i+j)}{(i+p+1)^{p+1}(p+1)!}\cdot(p+1)!\prod\limits_{i=1}^{p+1}\frac{1}{t+i}$
$\displaystyle=(p+1)^{p+1}\sum\limits_{i=1}^{t}\prod_{j=1}^{p+1}\frac{i+j}{i+p+1}\prod\limits_{i=1}^{p+1}\frac{1}{t+i}$
$\displaystyle\leq\frac{(p+1)^{p+1}}{(t+p+1)^{p}}$

For the first sum we get For second sum we have

$\displaystyle\sum\limits_{i=1}^{t}\frac{A_{t}\alpha_{i}^{q+1}}{A_{i}}$
$\displaystyle=\sum\limits_{i=1}^{t}\frac{(p+1)^{q+1}\prod_{j=1}^{p+1}(i+j)}{(i+p+1)^{q+1}(p+1)!}\cdot(p+1)!\prod\limits_{i=1}^{p+1}\frac{1}{t+i}$
$\displaystyle=(p+1)^{q+1}\sum\limits_{i=1}^{t}\frac{\prod_{j=1}^{p+1}(i+j)}{(i+p+1)^{q+1}}\cdot\prod\limits_{i=1}^{p+1}\frac{1}{t+i}$
$\displaystyle\leq\frac{(p+1)^{q+1}}{(t+p+1)^{q}}.$

From this two formulas for sums we get (25) ∎

Finally, we prove that our method converges with the desired speed and split
the complexities. Note that this algorithm can be generalized for the sum of
$m$ functions.

##  6 Conclusion

In this paper, we consider the minimization of the sum of two functions $f+g$,
each having Lipshitz $p$-th order derivatives with different Lipschitz
constants. We propose a general framework to accelerate tensor methods by
splitting computational complexities. As a result, we get near-optimal oracle
complexity for each function in the sum separately for any $p\geq 1$,
including the first-order methods. To be more precise, if the near optimal
complexity to minimize $f$ is $N_{f}(\varepsilon)$ iterations and to minimize
$g$ is $N_{g}(\varepsilon)$, then our method requires no more than
$N_{f}(\varepsilon)$ oracle calls for $f$ and $\tilde{O}(N_{f}(\varepsilon))$
oracle calls for $g$ to minimze $f+g$. We prove, that our framework works with
both convex and uniformly convex functions. To get this result, we
additionally generalize near-optimal tensor methods for composite problems
with inexact inner tensor step.

Further, we investigate the situation when the functions in the sum have
Lipschitz derivatives of a different order. For this situation, we propose a
generic way to separate the oracle complexity between the parts of the sum. It
is the first tensor method that works with functions with different
smoothness. Our method is not optimal, which leads to an open problem of the
optimal combination of oracles of a different order.

###  6.1 Acknowledgements

We would like to thank Yu. Nesterov for fruitful discussions on inexact
solution of tensor subproblem.

###  6.2 Funding

The work of D. Kamzolov was funded by RFBR, project number 19-31-27001. The
work of A.V. Gasnikov and P.E. Dvurechensky in the first part of the paper was
supported by RFBR grant 18-29-03071 mk. The work of A.V. Gasnikov in Appendix
was prepared within the framework of the HSE University Basic Research Program
and funded by the Russian Academic Excellence Project ’5-100’.

## References

  * [1] Naman Agarwal and Elad Hazan.  Lower bounds for higher-order convex optimization.  arXiv preprint arXiv:1710.10329, 2017.
  * [2] Yossi Arjevani, Ohad Shamir, and Ron Shiff.  Oracle complexity of second-order methods for smooth convex optimization.  Mathematical Programming, 178(1-2):327–360, 2019.
  * [3] Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov.  Derivative-free method for decentralized distributed non-smooth optimization.  arXiv preprint arXiv:1911.10645, 2019.
  * [4] Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford.  Near-optimal method for highly smooth convex optimization.  In Conference on Learning Theory, pages 492–507, 2019.
  * [5] Pafnuty Chebyshev.  collected works. Vol 5.  Strelbytskyy Multimedia Publishing, 2018.
  * [6] Nikita Doikov and Yurii Nesterov.  Local convergence of tensor methods.  arXiv preprint arXiv:1912.02516, 2019.
  * [7] Nikita Doikov and Yurii Nesterov.  Minimizing uniformly convex functions by cubic regularization of newton method.  arXiv preprint arXiv:1905.02671, 2019.
  * [8] Nikita Doikov and Peter Richtárik.  Randomized block cubic newton method.  arXiv preprint arXiv:1802.04084, 2018.
  * [9] Darina Dvinskikh and Alexander Gasnikov.  Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems.  arXiv preprint arXiv:1904.09015, 2019.
  * [10] Darina Dvinskikh, Sergey Omelchenko, Alexander Tiurin, and Alexander Gasnikov.  Accelerated gradient sliding and variance reduction.  arXiv preprint arXiv:1912.11632, 2019.
  * [11] Pavel Dvurechensky, Alexander Gasnikov, Petr Ostroukhov, César A Uribe, and Anastasiya Ivanova.  Near-optimal tensor methods for minimizing the gradient norm of convex function.  arXiv preprint arXiv:1912.03381, 2019.
  * [12] Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A Uribe.  Optimal tensor methods in smooth convex and uniformly convexoptimization.  In Conference on Learning Theory, pages 1374–1391, 2019.
  * [13] Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, et al.  Near optimal methods for minimizing convex functions with lipschitz $p$-th derivatives.  In Conference on Learning Theory, pages 1392–1393, 2019.
  * [14] Eduard Gorbunov, Darina Dvinskikh, and Alexander Gasnikov.  Optimal decentralized distributed algorithms for stochastic convex optimization.  arXiv preprint arXiv:1911.07363, 2019.
  * [15] Geovani Nunes Grapiglia and Yurii Nesterov.  On inexact solution of auxiliary problems in tensor methods for convex optimization.  arXiv preprint arXiv:1907.13023, 2019.
  * [16] Geovani Nunes Grapiglia and Yurii Nesterov.  Tensor methods for minimizing functions with h$\backslash$"$\\{$o$\\}$ lder continuous higher-order derivatives.  arXiv preprint arXiv:1904.12559, 2019.
  * [17] Bo Jiang, Haoyue Wang, and Shuzhong Zhang.  An optimal high-order tensor method for convex optimization.  In Conference on Learning Theory, pages 1799–1801, 2019.
  * [18] Leonid Vital’evich Kantorovich.  On newton’s method.  Trudy Matematicheskogo Instituta imeni VA Steklova, 28:104–144, 1949.
  * [19] George Lan.  Lectures on optimization methods for machine learning.  e-print, 2019.
  * [20] Guanghui Lan.  Gradient sliding for composite optimization.  Mathematical Programming, 159(1-2):201–235, 2016.
  * [21] Guanghui Lan, Soomin Lee, and Yi Zhou.  Communication-efficient algorithms for decentralized and stochastic optimization.  Mathematical Programming, pages 1–48, 2018.
  * [22] Guanghui Lan and Yuyuan Ouyang.  Accelerated gradient sliding for structured convex optimization.  arXiv preprint arXiv:1609.04905, 2016.
  * [23] Renato DC Monteiro and Benar Fux Svaiter.  An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.  SIAM Journal on Optimization, 23(2):1092–1125, 2013.
  * [24] Yu Nesterov.  Gradient methods for minimizing composite functions.  Mathematical Programming, 140(1):125–161, 2013.
  * [25] Yurii Nesterov.  Lectures on convex optimization, volume 137.  Springer, 2018.
  * [26] Yurii Nesterov.  Implementable tensor methods in unconstrained convex optimization.  Mathematical Programming, pages 1–27, 2019.
  * [27] Alexander Rogozin and Alexander Gasnikov.  Projected gradient method for decentralized optimization over time-varying networks.  arXiv preprint arXiv:1911.08527, 2019.
  * [28] Chaobing Song and Yi Ma.  Towards unified acceleration of high-order algorithms under hölder continuity and uniform convexity.  arXiv preprint arXiv:1906.00582, 2019.

##  Appendix A Proof of Composite Accelerated Taylor Descent

This section is a rewriting of proof from [4], with adding composite part into
the proof. Next theorem based on Theorem 2.1 from [4]

######  Theorem 6.

Let $(y_{k})_{k\geq 1}$ be a sequence of points in $\mathbb{R}^{d}$ and
$(\lambda_{k})_{k\geq 1}$ a sequence in $\mathbb{R}_{+}$. Define
$(a_{k})_{k\geq 1}$ such that $\lambda_{k}A_{k}=a_{k}^{2}$ where
$A_{k}=\sum_{i=1}^{k}a_{i}$. Define also for any $k\geq 0$,
$x_{k}=x_{0}-\sum_{i=1}^{k}a_{i}(\nabla f(y_{i})+g^{\prime}(y_{i}))$ and
$\tilde{x}_{k}:=\frac{a_{k+1}}{A_{k+1}}x_{k}+\frac{A_{k}}{A_{k+1}}y_{k}$.
Finally assume if for some $\sigma\in[0,1]$

$\|y_{k+1}-(\tilde{x}_{k}-\lambda_{k+1}\nabla
f(y_{k+1}))\|\leq\sigma\cdot\|y_{k+1}-\tilde{x}_{k}\|\,,$ (26)

then one has for any $x\in\mathbb{R}^{d}$,

$F(y_{k})-F(x)\leq\frac{2\|x\|^{2}}{\left(\sum_{i=1}^{k}\sqrt{\lambda_{i}}\right)^{2}}\,,$
(27)

and

$\sum_{i=1}^{k}\frac{A_{i}}{\lambda_{i}}\|y_{i}-\tilde{x}_{i-1}\|^{2}\leq\frac{\|x^{*}\|^{2}}{1-\sigma^{2}}\,.$
(28)

To prove this theorem we introduce auxiliaries lemmas based on lemmas 2.2-2.5
and 3.1 , lemmas 2.6 and 3.3 one can take directly from [4] without any
changes.

######  Lemma 3.

Let $\psi_{0}(x)=\frac{1}{2}\|x-x_{0}\|^{2}$ and define by induction
$\psi_{k}(x)=\psi_{k-1}(x)+a_{k}\Omega_{1}(F,y_{k},x)$. Then
$x_{k}=x_{0}-\sum_{i=1}^{k}a_{i}(\nabla f(y_{i})+g^{\prime}(y_{i}))$ is the
minimizer of $\psi_{k}$, and $\psi_{k}(x)\leq
A_{k}F(x)+\frac{1}{2}\|x-x_{0}\|^{2}$ where $A_{k}=\sum_{i=1}^{k}a_{i}$.

######  Lemma 4.

Let $(z_{k})$ be a sequence such that

$\psi_{k}(x_{k})-A_{k}F(z_{k})\geq 0\,.$ (29)

Then one has for any $x$,

$F(z_{k})\leq F(x)+\frac{\|x-x_{0}\|^{2}}{2A_{k}}\,.$ (30)

###### Proof.

One has (recall Lemma 3):

$A_{k}F(z_{k})\leq\psi_{k}(x_{k})\leq\psi_{k}(x)\leq
A_{k}F(x)+\frac{1}{2}\|x-x_{0}\|^{2}\,.$

∎

######  Lemma 5.

One has for any $x$,

$\displaystyle\psi_{k+1}(x)-A_{k+1}F(y_{k+1})-(\psi_{k}(x_{k})-A_{k}F(z_{k}))$
$\displaystyle\geq A_{k+1}(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot\left(\frac{a_{k+1}}{A_{k+1}}x+\frac{A_{k}}{A_{k+1}}z_{k}-y_{k+1}\right)+\frac{1}{2}\|x-x_{k}\|^{2}\,.$

###### Proof.

Firstly, by simple calculation we note that:

$\psi_{k}(x)=\psi_{k}(x_{k})+\frac{1}{2}\|x-x_{k}\|^{2},\text{ and
}\psi_{k+1}(x)=\psi_{k}(x_{k})+\frac{1}{2}\|x-x_{k}\|^{2}+a_{k+1}\Omega_{1}(f,y_{k+1},x)\,,$

so that

$\psi_{k+1}(x)-\psi_{k}(x_{k})=a_{k+1}\Omega_{1}(F,y_{k+1},x)+\frac{1}{2}\|x-x_{k}\|^{2}\,.$
(31)

Now we want to make appear the term $A_{k+1}F(z_{k+1})-A_{k}F(z_{k})$ as a
lower bound on the right hand side of (31) when evaluated at $x=x_{k+1}$.
Using the inequality $\Omega_{1}(F,y_{k+1},z_{k})\leq f(z_{k})$ we have:

$\displaystyle a_{k+1}\Omega_{1}(F,y_{k+1},x)$ $\displaystyle=$ $\displaystyle
A_{k+1}\Omega_{1}(F,y_{k+1},x)-A_{k}\Omega_{1}(F,y_{k+1},x)$ $\displaystyle=$
$\displaystyle A_{k+1}\Omega_{1}(F,y_{k+1},x)-A_{k}\nabla
F(y_{k+1})\cdot(x-z_{k})-A_{k}\Omega_{1}(F,y_{k+1},z_{k})$ $\displaystyle=$
$\displaystyle
A_{k+1}\Omega_{1}\left(F,y_{k+1},x-\frac{A_{k}}{A_{k+1}}(x-z_{k})\right)-A_{k}\Omega_{1}(F,y_{k+1},z_{k})$
$\displaystyle\geq$ $\displaystyle A_{k+1}F(y_{k+1})-A_{k}F(z_{k})$
$\displaystyle+$ $\displaystyle A_{k+1}(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot\left(\frac{a_{k+1}}{A_{k+1}}x+\frac{A_{k}}{A_{k+1}}z_{k}-y_{k+1}\right)\,,$

which concludes the proof. ∎

######  Lemma 6.

Denoting $\lambda_{k+1}:=\frac{a_{k+1}^{2}}{A_{k+1}}$ and
$\tilde{x}_{k}:=\frac{a_{k+1}}{A_{k+1}}x_{k}+\frac{A_{k}}{A_{k+1}}y_{k}$ one
has:

$\displaystyle\psi_{k+1}(x_{k+1})-A_{k+1}F(y_{k+1})-(\psi_{k}(x_{k})-A_{k}F(y_{k}))$
$\displaystyle\geq\frac{A_{k+1}}{2\lambda_{k+1}}\bigg{(}\|y_{k+1}-\tilde{x}_{k}\|^{2}-\|y_{k+1}-(\tilde{x}_{k}-\lambda_{k+1}(\nabla
f(y_{k+1}))+g^{\prime}(y_{k+1}))\|^{2}\bigg{)}\,.$

In particular, we have in light of (26)

$\psi_{k}(x_{k})-A_{k}F(y_{k})\geq\frac{1-\sigma^{2}}{2}\sum_{i=1}^{k}\frac{A_{i}}{\lambda_{i}}\|y_{i}-\tilde{x}_{i-1}\|^{2}.$

###### Proof.

We apply Lemma 5 with $z_{k}=y_{k}$ and $x=x_{k+1}$, and note that (with
$\tilde{x}:=\frac{a_{k+1}}{A_{k+1}}x+\frac{A_{k}}{A_{k+1}}y_{k}$):

$\displaystyle(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot\left(\frac{a_{k+1}}{A_{k+1}}x+\frac{A_{k}}{A_{k+1}}y_{k}-y_{k+1}\right)+\frac{1}{2A_{k+1}}\|x-x_{k}\|^{2}$
$\displaystyle=(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot(\tilde{x}-y_{k+1})+\frac{1}{2A_{k+1}}\left\|\frac{A_{k+1}}{a_{k+1}}\left(\tilde{x}-\frac{A_{k}}{A_{k+1}}y_{k}\right)-x_{k}\right\|^{2}$
$\displaystyle=(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot(\tilde{x}-y_{k+1})+\frac{A_{k+1}}{2a_{k+1}^{2}}\left\|\tilde{x}-\left(\frac{a_{k+1}}{A_{k}}x_{k}+\frac{A_{k}}{A_{k+1}}y_{k}\right)\right\|^{2}\,.$

This yields:

$\displaystyle\psi_{k+1}(x_{k+1})-A_{k+1}F(y_{k+1})-(\psi_{k}(x_{k})-A_{k}F(y_{k}))$
$\displaystyle\geq A_{k+1}\cdot\min_{x\in\mathbb{R}^{d}}\left\\{(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))\cdot(x-y_{k+1})+\frac{1}{2\lambda_{k+1}}\|x-\tilde{x}_{k}\|^{2}\right\\}\,.$

The value of the minimum is easy to compute. ∎

For the first conclusion in Theorem 6, it suffices to combine Lemma 6 with
Lemma 4, and Lemma 2.5 from [4]. The second conclusion in Theorem 6 follows
from Lemma 6 and Lemma 3.

The following lemma shows that minimizing the $p^{th}$ order Taylor expansion
(5) can be viewed as an implicit gradient step for some ‘‘large’’ step size:

######  Lemma 7.

Equation (26) holds true with $\sigma=1/2$ for (5), provided that one has:

$\frac{1}{2}\leq\lambda_{k+1}\frac{L_{p}\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}{(p-1)!}\leq\frac{p}{p+1}\,.$
(32)

###### Proof.

Observe that the optimality condition gives:

$\nabla_{y}f_{p}(y_{k+1},\tilde{x}_{k})+\frac{L_{p}\cdot(p+1)}{p!}(y_{k+1}-\tilde{x}_{k})\|y_{k+1}-\tilde{x}_{k}\|^{p-1}+g^{\prime}(y_{k+1})=0\,.$
(33)

In particular we get:

$\displaystyle y_{k+1}-(\tilde{x}_{k}-\lambda_{k+1}(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1})))=\lambda_{k+1}(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1}))$
$\displaystyle-\frac{p!}{L_{p}\cdot(p+1)\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}(\nabla_{y}f_{p}(y_{k+1},\tilde{x}_{k})+g^{\prime}(y_{k+1}))\,.$

By doing a Taylor expansion of the gradient function one obtains:

$\|\nabla f(y)-\nabla_{y}f_{p}(y,x)\|\leq\frac{L_{p}}{p!}\|y-x\|^{p}\,,$

so that we find:

$\displaystyle\|y_{k+1}-(\tilde{x}_{k}-\lambda_{k+1}(\nabla
f(y_{k+1})+g^{\prime}(y_{k+1})))\|$
$\displaystyle\leq\lambda_{k+1}\frac{L_{p}}{p!}\|y_{k+1}-\tilde{x}_{k}\|^{p}+\left|\lambda_{k+1}-\frac{p!}{L_{p}\cdot(p+1)\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}\right|\cdot\|\nabla_{y}f_{p}(y_{k+1},\tilde{x}_{k})+g^{\prime}(y_{k+1})\|$
$\displaystyle\leq\|y_{k+1}-\tilde{x}_{k}\|\left(\lambda_{k+1}\frac{L_{p}}{p!}\|y_{k+1}-\tilde{x}_{k}\|^{p-1}+\left|\lambda_{k+1}\frac{L_{p}\cdot(p+1)\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}{p!}-1\right|\right)$
$\displaystyle=\|y_{k+1}-\tilde{x}_{k}\|\left(\frac{\eta}{p}+\left|\eta\cdot\frac{p+1}{p}-1\right|\right)$

where we used (33) in the second last equation and we let
$\eta:=\lambda_{k+1}\frac{L_{p}\cdot\|y_{k+1}-\tilde{x}_{k}\|^{p-1}}{(p-1)!}$
in the last equation. The result follows from the assumption $1/2\leq\eta\leq
p/(p+1)$ in (32). ∎

Finally, if we replace $\|x^{\ast}\|$ by $\|x_{0}-x^{\ast}\|$ in Lemma 3.3 and
use Lemma 3.4 from [4] we prove Theorem 6.

##  Appendix B Inexact solution of the subproblem

Suppose that (5) can not be solved exactly. Assume that we can find only
inexact solution $\tilde{y}_{k+1}$ satisfies

$\left\|\nabla\left(f_{p}(\tilde{y}_{k+1},\tilde{x}_{k})+\frac{L_{p}}{p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p+1}+g(\tilde{y}_{k+1})\right)\right\|\leq\frac{L_{p}}{2p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p}.$
(34)

In this case Lemma 7 should be corrected.

######  Lemma 8.

Equation (26) holds true with $\sigma=3/4$ for (34), provided that one has:

$\frac{1}{2}\leq\lambda_{k+1}\frac{L_{p}\cdot\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p-1}}{(p-1)!}\leq\frac{p}{p+1}\,.$

###### Proof.

Let’s introduce

$\Xi_{k+1}=\nabla\left(f_{p}(\tilde{y}_{k+1},\tilde{x}_{k})+\frac{L_{p}}{p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p+1}+g(\tilde{y}_{k+1})\right).$

The main difference with the proof of Lemma 7 is in the following line

$\displaystyle\|\tilde{y}_{k+1}-(\tilde{x}_{k}-\lambda_{k+1}(\nabla
f(\tilde{y}_{k+1})+g^{\prime}(\tilde{y}_{k+1})))\|$
$\displaystyle\leq\lambda_{k+1}\frac{L_{p}}{p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p}+$
$\displaystyle\left|\lambda_{k+1}-\frac{p!}{L_{p}\cdot(p+1)\cdot\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p-1}}\right|\cdot\|\nabla_{y}f_{p}(\tilde{y}_{k+1},\tilde{x}_{k})+g^{\prime}(\tilde{y}_{k+1})\|+\lambda_{k+1}\Xi_{k+1}$
$\displaystyle\leq\|\tilde{y}_{k+1}-\tilde{x}_{k}\|\left(\lambda_{k+1}\frac{L_{p}}{p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p-1}+\left|\lambda_{k+1}\frac{L_{p}\cdot(p+1)\cdot\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p-1}}{p!}-1\right|\right)$
$\displaystyle+\|\tilde{y}_{k+1}-\tilde{x}_{k}\|\cdot\frac{1}{2p}\cdot\lambda_{k+1}\frac{L_{p}\cdot\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p-1}}{(p-1)!}.$

To complete the proof it’s left to notice that due to the (34)

$\|\Xi_{k+1}\|\leq\frac{L_{p}}{2p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p}.$

∎

Based on (34) we try to relate the accuracy $\tilde{\varepsilon}$ we need to
solve auxiliary problem to the desired accuracy $\varepsilon$ for the problem
(1). For this we use Lemma 2.1 from [15]. This Lemma guarantee that if

$\left\|\nabla\left(f_{p}(\tilde{y}_{k+1},\tilde{x}_{k})+\frac{L_{p}}{p!}\|\tilde{y}_{k+1}-\tilde{x}_{k}\|^{p+1}+g(\tilde{y}_{k+1})\right)\right\|\leq\frac{1}{4p(p+1)}\|\nabla
F(\tilde{y}_{k+1})\|,$ (35)

then (34) holds true. So it’s sufficient to solve auxiliary problem in terms
of (35).

Assume that $F(x)$ is $r$-uniformly convex function with constant $\sigma_{r}$
($r\geq 2$, $\sigma_{r}>0$, see Definition 1), then from Lemma 2 [7] we have

$F(\tilde{y}_{k+1})-\min\limits_{x\in
E}F(x)\leq\frac{r-1}{r}\left(\frac{1}{\sigma_{r}}\right)^{\frac{1}{r-1}}\|\nabla
F(\tilde{y}_{k+1})\|^{\frac{r}{r-1}}.$ (36)

Inequalities (35), (36) give us guarantees that it’s sufficient to solve
auxiliary problem with the accuracy

$\tilde{\varepsilon}=O\left(\left(\epsilon^{r-1}\sigma_{r}\right)^{\frac{1}{r}}\right)$

in terms of criteria (35). Since auxiliary problem is every time $r$-uniformly
convex we can apply (36) to auxiliary problem to estimate the accuracy in
terms of function discrepancy. Anyway we will have that there is no need to
think about it since the dependence of this accuracy are logarithmic. The only
restrictive assumption we made is that $F(x)$ is $r$-uniformly convex. If this
is not a case, like in Section 4, we may use regularisation tricks [11]. This
lead us to $\sigma_{2}\sim\varepsilon$. So the dependence
$\tilde{\varepsilon}$ becomes worthier, but this doesn’t change the main
conclusion about possibility to skip the details concern the accuracy of the
solution of auxiliary problem.

##  Appendix C CATD with restarts

The proof of the theorem 2.

###### Proof.

As $F$ is $r$-uniformly convex function we get

$\displaystyle R_{k+1}$
$\displaystyle=\|z_{k+1}-x_{\ast}\|\leq\left(\frac{r\left(F(z_{k+1})-F(x_{\ast})\right)}{\sigma_{r}}\right)^{\frac{1}{r}}\overset{\eqref{speedCATD}}{\leq}\left(\frac{r\left(\frac{c_{p}L_{p}R_{k}^{p+1}}{N_{k}^{\frac{3p+1}{2}}}\right)}{\sigma_{r}}\right)^{\frac{1}{r}}$
$\displaystyle=\left(\frac{rc_{p}L_{p}R_{k}^{p+1}}{\sigma_{r}N_{k}^{\frac{3p+1}{2}}}\right)^{\frac{1}{r}}\overset{\eqref{numberofrestarts}}{\leq}\left(\frac{R_{k}^{p+1}}{2^{r}R_{k}^{p+1-r}}\right)^{\frac{1}{r}}=\frac{R_{k}}{2}.$

Now we compute the total number of CATD steps.

$\displaystyle\sum\limits_{k=0}^{K}N_{k}$
$\displaystyle\leq\sum\limits_{k=0}^{K}\left(\frac{rc_{p}L_{p}2^{r}}{\sigma_{r}}R_{k}^{p+1-r}\right)^{\frac{2}{3p+1}}+K=\sum\limits_{k=0}^{K}\left(\frac{rc_{p}L_{p}2^{r}}{\sigma_{r}}(R_{0}2^{-k})^{p+1-r}\right)^{\frac{2}{3p+1}}+K$
$\displaystyle=\left(\frac{rc_{p}L_{p}2^{r}R_{0}^{p+1-r}}{\sigma_{r}}\right)^{\frac{2}{3p+1}}\sum\limits_{k=0}^{K}2^{\frac{-2(p+1-r)k}{3p+1}}+K$

∎