\section{\@startsection{section}{1}%
    \z@{.7\linespacing\@plus\linespacing}{.5\linespacing}%
    {\normalfont\bfseries\scshape \centering}}
\makeatother

\usepackage{mathrsfs}

\begin{document}

\title{Nonconvex bundle method with application to a delamination problem}
\author[M.N. Dao, J. Gwinner, D. Noll, and N. Ovcharova]{M.N. Dao$^\dag$, J. Gwinner$^\ast$, D. Noll$^\dag$, and N. Ovcharova$^\ast$}
\thanks{$^\dag$ Institut de Math\'ematiques, Universit\'e de Toulouse, France}
\thanks{$^\ast$ Institute of Mathematics, Department of Aerospace Engineering, Universit\"{a}t der Bundeswehr M\"{u}nchen, Germany}

\maketitle

\begin{abstract}
Delamination is a typical failure mode of composite materials caused by weak bonding.
It arises when a crack initiates and propagates under a destructive loading.
Given the physical law
characterizing the properties
of the interlayer adhesive between the bonded bodies,
we consider the problem of computing the propagation of the
crack  front and the stress field along the contact boundary. This leads to a
hemivariational inequality, which after discretization by finite elements
we solve by a
nonconvex bundle method, where
upper-$C^1$ criteria have to be minimized.  As this is in contrast with other classes
of mechanical problems with non-monotone friction
laws and in other applied fields, where  criteria are typically lower-$C^1$,
we propose a bundle method suited for both types of nonsmoothness.
We prove its global convergence  in the sense of subsequences and test it on a typical
delamination problem of material sciences.

\vspace{.4cm}\noindent
{\bf Key words.}
Composite material $\cdot$
delamination $\cdot$ crack front propagation $\cdot$  hemivariational inequality
$\cdot$ Clarke directional derivative $\cdot$
nonconvex bundle method $\cdot$ lower- and upper-$C^1$ function $\cdot$ convergence.
\end{abstract}

\section{Introduction}
We develop a bundle technique to solve nonconvex
variational problems arising  in contact  mechanics and in other applied fields.
We are specifically  interested in the
delamination of
composite structures with an adhesive bonding under destructive loading, a failure mode
which is studied in the material sciences.
When the properties of the  interlayer adhesive between the bonded bodies
are given in the form of a physical law relating the normal component of the stress vector
to the relative displacement between the upper and lower boundaries at the crack tip,
the challenge is to compute the  displacement and stress fields in order to assess the reactive destructive forces
along the contact boundary, as the latter are difficult to measure in situ.
This leads to minimization  of an energy functional,
where a  specific form of nonsmoothness arises in the
boundary integral at the contact boundary.
After discretization via piecewise linear finite elements using the trapezoidal quadrature rule, this
leads to  a finite-dimensional
nonsmooth  optimization problem of the form
\begin{eqnarray}
\label{program}
\begin{array}{ll}
\mbox{minimize} & f(x) \\
\mbox{subject to}& Ax \leq b
\end{array}
\end{eqnarray}
where $f$ is locally Lipschitz and neither smooth nor convex. Depending
on the nature of the frictional forces,
the criterion $f$ may be upper-$C^1$ or lower-$C^1$,  see e.g.  Figure \ref{dellaw}.
As these two classes of nonsmooth functions behave substantially
differently when minimized, we are  forced to
expand on existing bundle strategies
and develop an
algorithm  general enough to encompass  both
types of nonsmoothness. We prove its convergence to a critical point in the sense of subsequences,
and show that it
provides satisfactory numerical results in a simulation of the double cantilever beam test
\cite{gudladt},
one of the most popular  destructive tests to qualify structural adhesive joints.

The difficulty in nonconvex bundling is to provide a suitable
cutting plane oracle which replaces the no longer available
convex tangent plane.
One of the oldest oracles,
discussed already in Mifflin \cite{miflin}, and used in the bundle codes of Lemar\'echal
and Sagastiz\'abal \cite{le-saga1,le-saga2}, or the BT-codes of Zowe \cite{zowe,schramm},
uses the method of {\em downshifted tangents}.  While these authors use linesearch
with Armijo and Wolfe type conditions, which allows only weak convergence certificates
in the sense that {\em some} accumulation point of the sequence of serious iterates is critical,
we favor proximity control in tandem with a suitable backtracking strategy.
This leads to stronger convergence certificates, where {\em every} accumulation point of the sequence of serious iterates
is critical. For instance,
in \cite{noll,pjo,gabarrou} a strong certificate for
downshifted
tangents with proximity control  was proved within the class of lower-$C^1$ functions,
but its validity for
upper-$C^1$ criteria remained open.
An oracle for upper-$C^1$ functions with
a rigorous convergence theory can be based on
the {\em model approach} of \cite{noll,pjo,flows}, but
the latter is not compatible  with the downshift oracle.

To have two strings to one bow is
unsatisfactory,  as one could hardly expect practitioners to select their strategy
according to such a  distinction, which might not be
easy to make in practice.  In this work we will
resolve this impasse and present a
cutting plane oracle based on downshifted tangents, which leads to a
bundle method with strong convergence certificate
for both types of nonsmoothness. In its principal components
our method agrees with
existing strategies for downshifted tangents,
like \cite{le-saga1,zowe,Makela,Miettinen}, and could therefore be considered as  a justification
of this technique for a wide class of applications. Differences with existing methods
occur in the management of the proximity control
parameter, which in our approach has to respect certain rules to assure
convergence to a critical point,  without impeding good practical
performance.

The structure of the paper is as follows.
Section \ref{C1} gives some preparatory information on
lower- and upper-$C^1$ functions.
Section  \ref{algorithm} presents the algorithm
and comments on its ingredients. Theoretical tools
needed to prove convergence are presented
and employed in sections \ref{modelconcept} and \ref{oracle}.  Section \ref{main}
gives the main convergence result, while section \ref{practical}
discusses practical aspects of the algorithm.
In section \ref{delamination},   we discuss the
delamination problem, which we solve numerically using our bundle algorithm.

Numerical results for contact problem with adhesion based on the bundle-Newton method of  L. Luk\v{s}an and J. Vl\v{c}ek \cite{Luksan}
can be found e.g. in the book of Haslinger et al. \cite{Haslinger},  in  \cite{Makela, Miettinen},
and in the more recent  \cite{ Czepiel,LeoSt}.
Mathematical analysis and numerical results for quasistatic delamination problems can be found in
\cite{Kocvara,Roubicek}.

\section{Lower- and upper-$C^1$ functions}
\label{C1}
Following Spingarn \cite{spingarn}, a locally Lipschitz function
$f:\mathbb  R^n \to \mathbb R$ is  lower-$C^1$ at $x_0$,
if there exists a compact Hausdorff space $K$, a neighborhood $U$
of $x_0$, and
a mapping $F:U \times K \to \mathbb R$
such that both $F$ and $D_xF$ are jointly continuous and
\begin{eqnarray}
\label{lower}
f(x) = \max\{F(x,y): y\in K\}
\end{eqnarray}
is satisfied
for $x\in U$. The function $f$ is upper-$C^1$ at $x_0$ if $-f$ is
lower-$C^1$ at $x_0$.

In a minimization problem (\ref{program}), we expect
lower- and upper-$C^1$ functions to behave completely  differently.
Minimizing a lower-$C^1$ function ought to lead to  real difficulties, as on
descending we  move {\em into} the zone of nonsmoothness, which for lower-$C^1$ goes downward.
In contrast,
upper-$C^1$ functions are generally expected to be well-behaved, as intuitively
on descending we
move {\em away} from the nonsmoothness, which here goes upward. The present application
shows that this
argument is too simplistic.
Minimization of upper-$C^1$
functions  leads to real difficulties, which we explain subsequently.
In
delamination for composite materials
we encounter objective functions
of the form
\begin{eqnarray}
\label{structure}
f(x) = f_s(x) + \int_0^1 \min_{i\in I} f_i(x,t)\, dt,
\end{eqnarray}
where $f_s$ gathers the smooth part, while the integral
term, due to the minimum, is responsible for the nonsmoothness.

\textcolor{black}{
\begin{lemma}
Suppose $f_s$ is of class $C^1$ and
the $f_i$ are jointly of class $C^1$.
Then the function {\rm (\ref{structure})} is upper-$C^1$ and can be represented in the form
\begin{eqnarray}
\label{struct}
f(x) =f_s(x) + \min_{\sigma\in \Sigma} \int_0^1 f_{\sigma(t)}(x,t)\, dt,
\end{eqnarray}
where $\Sigma$ is the set of all measurable
mappings $\sigma: [0,1] \to I$.
\end{lemma}
}

\begin{proof}
Let us first prove (\ref{struct}).
For $\sigma\in \Sigma$ and fixed $x\in \mathbb R^n$ the function
$t\mapsto f_{\sigma(t)}(x,t)$ is measurable, and since
$\min_{i\in I} f_i(x,t) \leq f_{\sigma(t)}(x,t)\leq \max_{i\in I} f_i(x,t)$, it is also
integrable. Hence
$F(x,\sigma)=f_s(x)+\int_0^1 f_{\sigma(t)}(x,t)\, dt$ is well-defined, and clearly
$F(x,\sigma)\geq f(x)$, so we have $\inf_{\sigma\in \Sigma} F(x,\sigma) \geq f(x)$.

To prove the reverse estimate,
fix $x\in \mathbb R^n$ and consider the closed-valued multifunction $\Phi:[0,1] \to 2^I$ defined by
$\Phi(t) = \{i\in I: f_i(x,t) = \min_{i'\in I}f_{i'}(x,t)\}$. Since the $f_i(x,\cdot)$ are measurable and $I$
is finite,  $\Phi$
is a measurable multifunction. Choose a measurable selection $\sigma$, that is, $\sigma\in \Sigma$
satisfying $\sigma(t) \in \Phi(t)$ for every $t\in [0,1]$. Then clearly $F(x,\sigma)=f(x)$.
This proves (\ref{struct}).

Let us now show that $f$ is upper-$C^1$.
We consider
$
\varphi(x,t)=\min_{i\in I} f_i(x,t).
$
In view of \cite{spingarn} $\varphi(\cdot,t)$  is upper-$C^1$ and its Clarke subdifferential $\partial \varphi(\cdot,t)$
is strictly supermonotone uniformly over $t\in [0,1]$.
By Theorem 2 in \cite{georgiev},
$\varphi(\cdot,t)$ is approximately concave uniformly over $t\in [0,1]$. Integration with respect to
$t\in [0,1]$ then yields an approximately concave function with respect to $x$,
which by the equivalences in \cite{georgiev} and \cite{spingarn} is
upper-$C^1$.
\end{proof}

Note that the minimum (\ref{struct})
is  semi-infinite  even though $I$ is finite. Minimization of (\ref{structure})  cannot
be converted into a NLP, as would be possible in the min-max case.
The representation (\ref{struct}) highlights the difficulty in minimizing (\ref{structure}).
Minimizing a minimum has a
disjunctive character,
and due to the large size of $\Sigma$ this could lead to
a combinatorial situation with intrinsic difficulty.

\section{The model concept}
\label{modelconcept}
The model of a nonsmooth function was introduced
in \cite{pjo} and is a key element in understanding the bundle concept.

\begin{definition}
[Compare {\rm \cite{pjo}}]
A function $\phi:\mathbb R^n\times \mathbb R^n \to \mathbb R$
is called a model of the locally Lipschitz function $f:\mathbb R^n\to \mathbb R$
on the set $\Omega \subset \mathbb R^n$ if the following axioms are
satisfied:
\begin{enumerate}
\item[$(M_1)$] For every $x\in \Omega$ the function
$\phi(\cdot,x):\mathbb R^n\to \mathbb R$ is convex,
$\phi(x,x) = f(x)$ and $\partial_1\phi(x,x) \subset \partial f(x)$.
\item[$(M_2)$] For every $x\in \Omega$ and every $\epsilon >0$ there
exists $\delta > 0$ such that $f(y) \leq \phi(y,x) + \epsilon \|y-x\|$
for every $y\in B(x,\delta)$.
\item[$(M_3)$] The function $\phi$ is jointly upper semicontinuous, i.e.,
$(y_j,x_j)\to (y,x)$ on $ \mathbb R^n\times \Omega$ implies $\displaystyle\limsup_{j\to\infty} \phi(y_j,x_j)\leq \phi(y,x)$.
\hfill $\square$
\end{enumerate}
\end{definition}
We recall that every locally Lipschitz function $f$ has the so-called {\em standard model}
\[
\phi^\sharp(y,x) = f(x) + f^0(x,y-x),
\]
where $f^0(x,d)$ is the Clarke directional derivative
of $f$ at $x$ in direction $d$. The same function $f$ may in general have several models $\phi$, and
following \cite{noll,flows}, the standard
$\phi^\sharp$ is the smallest one. Every
model $\phi$ gives rise to a bundle strategy. The question is then whether this bundle strategy
is successful. This depends on
the following property of $\phi$.

\begin{definition}
A model  $\phi$  of $f$ on $\Omega$
is said to be strict at $x_0\in \Omega$ if axiom $(M_2)$ is replaced
by the stronger
\begin{enumerate}
\item[$(\widehat{M}_2)$] For every $\epsilon > 0$ there exists $\delta > 0$
such that $f(y) \leq \phi(y,x) + \epsilon \|y-x\|$ for all $x,y\in B(x_0,\delta)$.
\end{enumerate}
We say that $\phi$ is a strict model on $\Omega$, if it is strict at every
$x_0\in \Omega$. \hfill $\square$
\end{definition}

\begin{remark}
We may write axiom $(M_2)$ in the form
$f(y) \leq \phi(y,x_0) + {\rm o}(\|y-x_0\|)$ for $y\to x_0$, and
$(\widehat{M}_2)$ as $f(y) \leq \phi(y,x) + {\rm o}(\|y-x\|)$
for $x,y\to x_0$. Except for the fact that these concepts are
one-sided, this  is precisely  the difference between differentiability
and strict differentiability. Hence the nomenclature.
\end{remark}

\begin{lemma}
[Compare {\rm \cite{noll,flows}}]
Suppose $f$ is  upper-$C^1$. Then its standard
model $\phi^\sharp$ is strict, and hence every model $\phi$ of $f$ is strict.
\hfill $\square$
\end{lemma}

\begin{remark}
For convex $f$
the standard model $\phi^\sharp$ is in general not strict, but $f$ may be used as its own model $\phi(\cdot,x)=f$.
For nonconvex $f$, a wide range of
applications is covered by composite
functions $f = g \circ F$ with $g$ convex and $F$
differentiable. Here the so-called natural
model $\phi(y,x) = g(F(x) + F'(x)(y-x))$ can be used, because it is strict
as soon as $F$ is class $C^1$. This includes
lower-$C^2$ functions in the sense of \cite{rock}, lower-$C^{1,\alpha}$
functions in the sense of \cite{malick-dani},
or amenable functions in the sense of \cite{amenable},
which allow representations of the form $f=g\circ F$
with $F$ of class $C^{1,1}$.
\end{remark}

We conclude with the remark that lower-$C^1$
functions also admit strict models, even though in
that case the construction is more delicate. The strict model
in that case cannot be exploited algorithmically,
and for lower-$C^1$ functions we prefer the oracle
concept, which will be discussed in section
\ref{oracle}.

\section{Elements of the algorithm}
\label{algorithm}
In this section we briefly explain the main features of the algorithm.
This concerns building the working model, computing
the solution of the tangent program, checking acceptance, updating the working model after null steps,
and the management of the proximity control parameter.

\subsection{Working model}
At the current serious iterate  $x$  the  inner loop
of the algorithm at counter $k$ computes an approximation $\phi_k(\cdot,x)$ of
$f$ in a neighborhood of $x$, called a first-order
working model. The working model is a polyhedral
convex function of the form
\begin{eqnarray}
\label{working}
\phi_k(\cdot,x) = \max_{(a,g)\in \mathcal G_k} a + g^\top (\cdot - x),
\end{eqnarray}
where $\mathcal G_k$ is a finite set of affine functions
$y\mapsto a + g^\top(y-x)$ satisfying $a\leq f(x)$,
referred to as {\em planes}. The set $\mathcal G_k$ is  updated
during the inner loop $k$.
At each step $k$ the following
rules have to be respected when updating
$\mathcal G_{k}$ into $\mathcal G_{k+1}$:
\begin{enumerate}
\item[$(R_1)$] One or several cutting planes at the null step $y^k$,
generated by an abstract  cutting plane oracle,
are added to $\mathcal G_{k+1}$.
\item[($R_2)$] The so-called aggregate plane $(a^*,g^*)$, which consists of convex
combinations of elements of $\mathcal G_{k}$, is added to $\mathcal G_{k+1}$.
\item[$(R_3)$] Some older  planes in $\mathcal G_{k}$, which become obsolete
through the addition of the aggregate
plane, are discarded and not kept in $\mathcal G_{k+1}$.
\item[$(R_4)$] Every $\mathcal G_k$ contains at least one so-called exactness plane  $(a_0,g_0)$, where
exactness plane means $a_0=f(x)$, $g_0\in\partial f(x)$. This assures
$\phi_k(x,x)=f(x)$, hence the name.
\item[$(R_5)$] We have to make sure that each working model $\phi_k$
satisfies $\partial_1 \phi_k(x,x) \subset \partial f(x)$.
\end{enumerate}
Once the first-order working model $\phi_k(\cdot,x)$
has been built, the second-order working model
$\Phi_k(\cdot,x)$ is of the form
\begin{eqnarray}
\label{second}
\Phi_k(\cdot,x)=\phi_k(\cdot,x)
+
\textstyle\frac{1}{2}(\cdot - x)^\top Q(x) (\cdot -x),
\end{eqnarray}
where $Q(x)=Q(x)^\top$ is a possibly indefinite symmetric
matrix, depending only on the current serious iterate $x$, and fixed
during the inner loop $k$.  The second-order term includes curvature information on $f$,
if available.

\subsection{Tangent program and acceptance test}
Once the second-order working model (\ref{second})
is formed and the proximity control parameter
$\tau_{k-1} \to \tau_k$ is updated, we solve the tangent program
\begin{eqnarray}
\label{tangent}
\begin{array}{ll}
\mbox{minimize} & \Phi_k(y,x) + \frac{\tau_k}{2}\|y-x\|^2 \\
\mbox{subject to} & Ay\leq b
\end{array}
\end{eqnarray}
Here the proximity control parameter $\tau_k$
satisfies $Q + \tau_k I \succ 0$, which assures that
(\ref{tangent}) is strictly convex and has a unique solution,
$y^k$, called the {\em trial step}.
The trial step
is a candidate to become the new serious iterate $x^+$.
In order to decide whether $y^k$ is acceptable, we compute the test
\begin{eqnarray}
\label{rho}
\rho_k=\frac{f(x)-f(y^k)}{f(x) - \Phi_k(y^k,x)} \stackrel{?}{\geq} \gamma,
\end{eqnarray}
where $0 < \gamma < 1$ is some fixed parameter.
If $\rho_k \geq \gamma$, then $x^+ = y^k$
is accepted and called a {\em serious step}. In this case the inner loop ends successfully.
On the other hand, if $\rho_k < \gamma$, then $y^k$
is rejected and called a {\em null step}. In this case the inner loop $k$
continues. This means we will update  working model
$\Phi_k(\cdot,x) \to \Phi_{k+1}(\cdot,x)$, adjust the proximity control parameter $\tau_k\to \tau_{k+1}$,
and solve (\ref{tangent}) again.

Note that
the test (\ref{rho}) corresponds to the usual
Armijo descent condition used in linesearches, or to the standard
acceptance test in trust region methods.

\subsection{Updating the working model via aggregation}
Suppose the trial step $y^k$ fails the acceptance test (\ref{rho})
and is declared a null step. Then the inner loop has to continue,
and we have to improve the working model at the next sweep
in order to perform better. Since the second-order part of the working model
$\frac{1}{2}(\cdot - x)^\top Q(x)(\cdot - x)$
remains invariant, we will update the first-order part only.

Concerning rule $(R_2)$,
by the necessary optimality condition for (\ref{tangent}),
there exists a multiplier $\eta^*$ such that
\[
0\in \partial_1 \Phi_k(y^k,x) + \tau_k(y^k-x) + A^\top \eta^*,
\]
or what is the same,
\[
(Q(x)+\tau_k I)(y^k-x) - A^\top \eta^* \in \partial_1 \phi_k(y^k,x).
\]
Since $\phi_k(\cdot,x)$ is by construction a maximum of 	affine
planes,  we use the standard description of the
convex subdifferential of a max-function. Writing $\mathcal G_k
=\{(a_0,g_0),\dots,(a_p,g_p)\}$ for  $p ={\rm card}(\mathcal G_k)+1$,
we find non-negative multipliers $\lambda_0,\dots,\lambda_p$
summing up to 1 such that
\[
(Q(x)+\tau_kI)(y^k-x)-A^\top\eta^* = \sum_{i=0}^p \lambda_i g_i,
\]
and in addition, $a_i + g_i^\top (y^k-x) = \phi_k(y^k,x)$ for all
$i\in \{0,\dots,p\}$ with $\lambda_i > 0$. We say that those
planes which are active at $y^k$ are  {\em called by the aggregate plane}.
In the above rule $(R_3)$ we allow those to be removed  from
$\mathcal G_{k}$.
We now define the aggregate plane as:
\[
a^*_k = \sum_{i=0}^p \lambda_i a_i, \quad g^*_k = \sum_{i=0}^p \lambda_i g_i.
\]
Note that by construction the aggregate plane
$m_k^*(\cdot,x)=a^*_k + g^{*\top}_k(\cdot - x)$ at null step $y^k$ satisfies
$m_k^*(y^k,x)=a^*+g^{*\top}(y^k-x)=\phi_k(y^k,x)$. This construction is standard
and follows the original idea in Kiwiel \cite{kiwiel_aggregate}. It assures in particular that
$\Phi_{k+1}(y^k,x) \geq m_k^*(y^k,x) + \frac{1}{2}(y^k-x)^\top Q(x)(y^k-x) = \Phi_k(y^k,x)$.

\subsection{Updating the working model by cutting planes and exactness planes}
The crucial improvement in the first-order working model is in adding a
cutting plane which cuts away the unsuccessful trial step $y^k$ according to rule $(R_1)$. We shall
denote the cutting plane as $m_k(\cdot,x) = a_k + g^\top(\cdot - x)$. The only requirement
for the time being is that $a_k \leq f(x)$, as this assures $\phi_{k+1}(x,x)\leq f(x)$.
Since we also maintain at least one exactness plane of the form
$m_0(\cdot,x)=f(x) + g_0^\top(\cdot - x)$ with $g_0\in \partial f(x)$, we assure
$\phi_{k+1}(x,x)= \Phi_{k+1}(x,x)=f(x)$.  Later we will also have to check the validity of $(R_5)$.

It is possible to integrate
so-called {\em anticipated cutting planes} in the new working model $\mathcal G_{k+1}$.
Here anticipated designates all planes which are not
based on the rules exactness, aggregation, cutting planes. Naturally,
adding such planes can not be allowed in an arbitrary way, because axioms $(R_1) - (R_5)$ have to be respected.

\begin{remark}
It may be beneficial to choose a new exactness plane $m_0(\cdot,x)= f(x) + g^\top (\cdot-x)$
after each null step $y$, namely the one which satisfies $m_0(y,x) = f^0(x,y-x)$.
If $x$ is a point of differentiability of $f$, then all these exactness planes are identical anyway, so no
extra work occurs. On the other hand, computing $g\in \partial f(x)$
such that $g^\top (y-x) = f^0(x,y-x)$ is usually cheap. Consider for instance
eigenvalue optimization, where $f(x) = \lambda_1\left( F(x)\right)$, $x\in \mathbb R^n$,
$F:\mathbb R^n \to \mathbb S^m$, and $\lambda_1:\mathbb S^m\to \mathbb R$ is
the maximum eigenvalue function of $\mathbb S^m$. Then
$f^0(x,d) = \lambda_1'(X,D) = \lambda_1(Q^\top DQ)$, where $X=F(x)$,  $D=F'(x)d$, and
where $Q$ is a $t \times m$ matrix whose columns form an orthogonal basis
of the maximum eigenspace of $X$ of dimension $t$ \cite{cullum}. Then $G=QQ^\top \in \partial \lambda_1(X)$ attains
$\lambda_1'(X,D)$,  hence
$g = F'(x)^* QQ^\top$ attains $f'(x,d)$. Since usually $t\ll m$, the computation of $g$ is cheap.
\end{remark}

\subsection{Management of proximity control}
The central novelty of the bundle methods developed in
\cite{noll,pjo,anp} is the discovery that in the absence of convexity the proximity
control parameter $\tau$ has to follow certain basic rules
to assure convergence of the sequence $x^j$
of serious iterates. This is in contrast with convex bundle
methods, where
$\tau$ could in principle be frozen once and for all.
More precisely, suppose $\phi_k(\cdot,x)$
has failed and produced only a null step $y^k$. Having built the new
model $\phi_{k+1}(\cdot,x)$,
we compute the secondary
test
\begin{eqnarray}
\label{tilde-rho}
\widetilde{\rho}_k= \frac{f(x)-\Phi_{k+1}(y^k,x)}{f(x)-\Phi_k(y^k,x)}\stackrel{?}{\geq} \widetilde{\gamma},
\end{eqnarray}
where $0 < \gamma < \widetilde{\gamma}<1$ is fixed. Our decision is
\begin{eqnarray}
\label{dec}
\tau_{k+1}=
\left\{
\begin{array}{ll}
2\tau_k &\mbox{if } \widetilde{\rho}_k \geq \widetilde{\gamma} \\
\tau_k & \mbox{if } \widetilde{\rho}_k < \widetilde{\gamma}
\end{array}
\right.
\end{eqnarray}
The rationale of (\ref{tilde-rho})  is to decide whether improving
the model by adding planes will suffice, or
shorter steps have to be forced by increasing $\tau$.

The denominator in (\ref{tilde-rho})
gives the model predicted progress $f(x)-\phi_k(y^k,x)=\phi_k(x,x)-\phi_k(y^k,x)>0$
at $y^k$. On the other hand, the numerator $f(x)-\phi_{k+1}(y^k,x)$
gives the progress over $x$ we would achieve at $y^k$, had we already known
the cutting planes drawn at $y^k$. Due to aggregation we know
that $\phi_{k+1}(y^k,x) \geq \phi_k(y^k,x)$, so that
$\widetilde{\rho}_k \leq 1$, but values
$\widetilde{\rho}_k \approx 1$ indicate that little to no
progress is achieved by adding the cutting plane.
In this case we decide that the $\tau$-parameter must be increased to
force smaller steps, because that reinforces the  agreement
between $f$ and $\phi_{k+1}(\cdot,x)$.

In the test (\ref{dec}) we replace $\widetilde{\rho}_k\approx 1$ by
$\widetilde{\rho}_k\geq \widetilde{\gamma}$ for some fixed $0 < \gamma < \widetilde{\gamma} < 1$.
If $\widetilde{\rho}_k < \widetilde{\gamma}$,
then the quotient if far from 1 and we decide that adding planes has still the potential
to improve the situation. In that event we do not increase
$\tau$.

Let us next consider the management
of $\tau$ in the outer loop. Since $\tau$ can only increase or
stay fixed in the inner loop, we allow $\tau$ to decrease
between serious steps $x\to x^+$, respectively, $x^j \to x^{j+1}$.
This is achieved by the test
\begin{eqnarray}
\label{Gamma}
{\rho}_{k_j} =\frac{f(x^j) - f(x^{j+1})}{f(x^j) - \Phi_{k_j}(x^{j+1},x^j)}
\stackrel{?}{\geq} \Gamma,
\end{eqnarray}
where $0 < \gamma \leq \Gamma < 1$ is fixed. In other words,
if at acceptance we have not only $\rho_{k_j}\geq \gamma$,
but even $\rho_{k_j} \geq \Gamma$, then we decrease
$\tau$ at the beginning of the next inner loop $j+1$, because
we may trust the model. On the other hand, if
$\gamma \leq \rho_{k_j} < \Gamma$ at acceptance, then
we memorize the last $\tau$-parameter used, that is $\tau_{k_j}$ at the end of the
$j$th inner loop.

\begin{remark}
We should compare our management of the proximity control
parameter $\tau$ with other strategies in the literature. For instance
M\"akel\"a {\em et al.} \cite{Makela} consider a very
different management of $\tau$, which is motivated by
the convex case.
\end{remark}

\subsection{Statement of the algorithm}
We are now ready to give our formal statement
of algorithm \ref{algo1}.

\begin{algorithm}
\caption{{\Large $\!\!{\bf  .}$} Proximity control algorithm for (\ref{program}).}\label{algo1}
\begin{algorithmic}[1]
\hrule
\vskip 2pt
\item[\algorithmicparameters] $0<\gamma < \Gamma < 1$, $\gamma < \widetilde{\gamma}<1$,
$0< q <  \infty$,
 $q <  T  <  \infty$.

\STATE {\bf Initialize outer loop}. Choose
initial guess $x^1$ with $Ax^1 \leq b$ and an initial matrix $Q_1=Q_1^\top$
with $-qI\preceq Q_1 \preceq qI$.
Fix memory control parameter $\tau_1^\sharp$ such that $Q_1+\tau_1^\sharp I\succ 0$.
Put $j=1$.
\STATE {\bf Stopping test}. At outer loop counter $j$, stop if $0\in \partial f(x^j) + A^\top \eta^*$
for some multiplier $\eta^*\geq 0$.
Otherwise goto inner loop.
\STATE {\bf Initialize inner loop}. Put inner loop counter $k=1$ and initialize
$\tau$-parameter using the memory element, i.e.,
$\tau_1 = \tau^\sharp_j$. Choose initial convex working model $\phi_1(\cdot,x^j)$,
possibly recycling some planes from previous sweep $j-1$,
and let $\Phi_1(\cdot,x^j)=\phi_1(\cdot,x^j)+\frac{1}{2}(\cdot-x^j)^\top Q_j(\cdot-x^j)$.
\STATE {\bf Trial step generation.} At inner loop counter $k$ solve tangent program
\[
\min_{Ay\leq b} \Phi_k(y,x^j)+\textstyle\frac{\tau_k}{2}\|y-x^j\|^2.
\]
The solution is the new trial step $y^{k}$.
\STATE {\bf Acceptance test.}
Check whether
\[
\rho_k=\frac{f(x^j)-f(y^{k})}{f(x^j)-\Phi_k(y^{k},x^j)} \ge \gamma.
\]
If this is the case put $x^{j+1}=y^{k}$ (serious step), quit inner loop and goto step 8.
If
this is not the case (null step) continue inner loop with step 6.
\STATE {\bf Update working model}.
Build new convex working model $\phi_{k+1}(\cdot,x^j)$ based
on null step $y^{k}$
by adding an exactness plane $m_k^\sharp(\cdot,x^j)$ satisfying $m_k^\sharp(y^k,x^j)=f^0(x^j,y^k-x^j)$,
a downshifted tangent $m_k^\downarrow(\cdot,x^j)$,  and the  aggregate plane $m_k^*(\cdot,x^j)$.
Apply rule $(R_3)$ to avoid overflow. Build $\Phi_{k+1}(\cdot,x^j)$,
and goto step 7.
\STATE {\bf Update proximity parameter}. Compute
\[
\widetilde{\rho}_k = \frac{f(x^j)-\Phi_{k+1}(y^{k},x^j)}{f(x^j)-\Phi_k(y^{k},x^j)}.
\]
Put
\[
\tau_{k+1}= \left\{
\begin{array}{ll}
\vspace{.1cm}
\tau_k, &\mbox{if } \widetilde{\rho}_k  < \widetilde{\gamma} \qquad\mbox{(bad)} \\
\vspace{.1cm}
2\tau_k, &\mbox{if } \widetilde{\rho}_k \ge \widetilde{\gamma}\qquad\mbox{(too bad)}\end{array}
\right.
\
Then increase counter $k$ and continue inner loop with step 4.
\STATE {\bf Update $Q_j$ and memory element}.
Update matrix $Q_j\to Q_{j+1}$,  respecting $Q_{j+1}=Q_{j+1}^\top$ and
$-qI\preceq Q_{j+1}\preceq qI$. Then
store new memory element
$$\tau_{j+1}^\sharp = \left\{
\begin{array}{ll}
\tau_{k}, & \mbox{if } \gamma \leq \rho_k < \Gamma  \qquad\mbox{    (not bad)}\\
&\\
\displaystyle\textstyle\frac{{1}}{2}\tau_{k}, &\mbox{if } \rho_k \ge \Gamma \qquad\qquad \mbox{    (good)}
\end{array}
\right.$$
 Increase $\tau_{j+1}^\sharp$ if necessary to ensure $Q_{j+1}+\tau_{j+1}^\sharp I\succ 0$.
 \STATE {\bf Large multiplier safeguard rule.}
 If  $\tau_{j+1}^\sharp > T$ then re-set $\tau_{j+1}^\sharp = T$.
 Increase outer loop counter $j$  by 1 and loop back to step 2.
\end{algorithmic}
\hrule
\end{algorithm}

\section{Nonconvex cutting plane oracles}
\label{oracle}
In the convex cutting plane method \cite{rudzsinski,hule:93}
unsuccessful trial steps $y^k$ are cut away by adding
a tangent plane to $f$ at $y^k$ into the model.
Due to convexity, the cutting plane is below
$f$ and can therefore be used to
construct an approximation
(\ref{working}) of $f$. For nonconvex $f$, cutting planes are more
difficult to construct, but several ideas have been
discussed. We mention \cite{saga,miflin}.
In \cite{noll} we have proposed an axiomatic approach,
which has the advantage that it covers the applications
we are aware of, and allows a convenient convergence theory.
Here we  use this axiomatic approach in
the convergence proof.

\begin{definition}
[Compare {\rm \cite{noll}}] Let
$f$ be locally Lipschitz. A cutting plane oracle
for $f$ on the set $\Omega$ is an operator $\mathscr O$ which,
with every pair $(x,y)$, $x$ a serious iterate in $\Omega$, $y\in\mathbb R^n$ a null step,
associates an affine function
$m_{y}(\cdot,x)= a + g^\top (\cdot - x)$, called the cutting plane at null step $y$
for serious iterate $x$, so that the following axioms are satisfied:
\begin{enumerate}
\item[$(O_1)$] For $y=x$ we have $a=f(x)$ and $g\in \partial f(x)$.
\item[$(O_2)$] Let $y_j\to x$. Then
there exist $\epsilon_j \to 0^+$ such that $f(y_j)\leq m_{y_j}(y_j,x)+\epsilon_j\|y_j-x\|$.
\item[$(O_3)$] Let $x_j\to x$ and  $y_j,y_j^+\to y$. Then there exists $z\in \mathbb R^n$
such that\\
$\displaystyle\limsup_{j\to\infty} m_{y_j^+}(y_j,x_j)\leq m_{z}(y,x)$.
\hfill $\square$
\end{enumerate}
\end{definition}

As we shall see, these axioms are aligned with
the model axioms $(M_1) - (M_3)$. Not unexpectedly, there is also
a strict version of $(O_2)$.

\begin{definition}
\label{strict-oracle}
A cutting plane oracle $\mathscr O$  for $f$ is called strict
at $x_0$ if the following strict version of $(O_2)$
is satisfied:
\begin{enumerate}
\item[$(\widehat{O}_2)$]
Suppose $y_j,x_j \to x$. Then there exist $\epsilon_j\to 0^+$
such that $f(y_j)\leq m_{y_j}(y_j,x_j)+ \epsilon_j \|y_j-x_j\|$.  \hfill $\square$
\end{enumerate}
\end{definition}

We now discuss two
versions of the oracle
which are of special interest for our applications.

\begin{example}
[Model-based oracle]
Suppose $\phi$ is a model
of $f$. Then we can generate a cutting plane
for serious iterate $x$ and trial step $y$ by taking
$g\in \partial_1 \phi(y,x)$ and putting
\[
m_{y}(\cdot,x) = \phi(y,x) + g^\top (\cdot - y)
= \phi(y,x) + g^\top (x-y) + g^\top( \cdot - x).
\]
Oracles generated by a model $\phi$
in this way will be denoted $\mathscr O_\phi$. Note that $\mathscr O_\phi$
coincides with the standard oracle if $f$ is convex and $\phi(\cdot,x)=f$,
i.e., if the convex $f$ is chosen as its own model. In more general cases, the simple idea of this oracle
is that in the absence of convexity,  where tangents to $f$ at $y$
are not useful, we simply take tangents
of $\phi(\cdot,x)$ at $y$. Note that the model-based oracle $\mathscr O_\phi$
is strict as soon as the model $\phi$ is strict.
\hfill $\square$
\end{example}

\begin{example}
[Standard oracle] A special case of the model-based oracle
is obtained by choosing the standard model $\phi^\sharp$.
Due to its significance for our present work we call this the standard oracle.
The standard cutting plane for serious step
$x$ and null step $y$ is
$m_y^\sharp(\cdot,x) = f(x)+ g^\top (\cdot -x)$, where the Clarke
subgradient $g\in \partial f(x)$ is  one of those that satisfy $g^\top (y-x)=f^0(x,y-x)$.
The standard oracle is strict iff $\phi^\sharp$ is strict. As was
observed before, this is for instance the case  when $f$ is upper-$C^1$.
Note a specificity of the standard oracle: every standard cutting plane $m_y^\sharp(\cdot,x)$
is also an exactness plane at $x$.
\hfill $\square$
\end{example}

\begin{example}
[Downshifted tangents] Probably the oldest oracle used
for nonconvex functions are downshifted tangents, which we
define as follows. For serious iterate $x$ and null step $y$
let $t(\cdot) = f(y) + g^\top (\cdot - y)$ be a tangent of $f$ at $y$.
That is, $g\in \partial f(y)$. Then we shift $t(\cdot)$ down
until it becomes useful for the model (\ref{working}). Fixing a parameter
$c > 0$, this is organized as follows: We define the cutting plane as
$m_{y}^\downarrow(\cdot,x) = t(\cdot) - s$, where the downshift $s \geq 0$
satisfies
\[
s =
[t(x) - f(x) + c\|y-x\|^2]_+ .
\]
In other words,
$m_{y}^\downarrow(\cdot,x) = a + g^\top (\cdot-x)$, where
$a = \min\{ t(x), f(x)-c\|y-x\|^2  \}$. Note that this procedure
aways satisfies axioms $(O_1)$ and $(O_3)$, whereas axioms
$(O_2)$, respectively, $(\widehat{O}_2)$, are satisfied
if $f$ is lower-$C^1$ at $x_0$. In other words, see \cite{noll}, for $f$ lower-$C^1$
this is an oracle, which is automatically strict.
\hfill $\square$
\end{example}

Motivated by the previous examples, we now define
an oracle which works for both lower-$C^1$  and  upper-$C^1$.

\begin{example}
[Modified downshift] \label{modified}
Let $x$ be the current serious iterate, $y$ a null  step
in the inner loop
belonging to $x$. Then we form the downshifted tangent $m_y^\downarrow(\cdot,x):=t(\cdot)-s$,
that is, the cutting plane we would get from the downshift oracle,
and we form the standard oracle plane $m_y^\sharp(\cdot,x)=f(x) + g^\top (\cdot - x)$, where
the Clarke subgradient $g$ satisfies $f^0(x,y-x) = g^\top(y-x)$. Then we define
\[
m_y(\cdot,x) = \left\{
\begin{array}{ll}
m_y^\downarrow(\cdot,x) &\mbox{ if } m_y^\downarrow(y,x) \geq m_y^\sharp(y,x)
\vspace*{.2cm}\\
m_y^\sharp(\cdot,x) &\mbox{ else}
\end{array}
\right.
\]
In other words, among the two candidate cutting planes $m_y^\downarrow(\cdot,x)$
and $m_y^\sharp(\cdot,x)$, we take the one which has the larger value
at the null step $y$.

Note that this is the oracle we use in our algorithm.  Theorem \ref{theorem1}
clarifies when this oracle is strict.
\hfill $\square$
\end{example}

Given an operator $\mathscr O$ which
with every pair $(x,y)$ of serious step $x$ and null step $y$ associates a cutting
plane $m_y(\cdot,x)=a+g^\top (\cdot - x)$, we fix a constant $M>0$ and define
what we call   the upper envelope function of the oracle
\[
\phi^\uparrow(\cdot,x) = \sup\{ m_y(\cdot,x):  \|y-x\| \leq M\}.
\]
The crucial property of $\phi^\uparrow$
is the following
\begin{lemma}
Suppose $\mathscr O: (x,y) \mapsto m_y(\cdot,x)$ is a cutting plane oracle
satisfying axioms $(O_1)-(O_3)$. Then $\phi^\uparrow$ is a model of $f$. Moreover,
if the oracle satisfies $(\widehat{O}_2)$, then $\phi^\uparrow$ is strict.
\hfill $\square$
\end{lemma}

The proof can be found in \cite{noll}. We refer to $\phi^\uparrow$ as the upper envelope
model associated with the oracle $\mathscr O$. Since in turn every model $\phi$ gives rise to a model-based oracle,
$\mathscr O_\phi$,
it follows that having a strict oracle and having a strict model are equivalent properties of $f$.
Note, however, that the model $\phi^\uparrow$ is in general not practically useful. It is a theoretical tool in the convergence proof.

\begin{remark}
If we start with a model $\phi$, then build $\mathscr O_\phi$, and go back to
$\phi^\uparrow$,  we get back to $\phi$, at least locally.

On the other hand, going from an oracle $\mathscr O$ to its envelope model $\phi^\uparrow$,
and then back to the model based oracle $\mathscr O_{\phi^\uparrow}$ does {\em not}
necessarily lead back to the oracle $\mathscr O$.
\end{remark}

We are now in the position to check axiom $(R_5)$.

\begin{corollary}
All working models $\phi_k$ constructed in our algorithm
satisfy $\partial_1\phi_k(x,x)\subset \partial f(x)$. \hfill $\square$
\end{corollary}

\section{Main convergence result}
\label{main}
In this section we state and prove the main result
of this work and give several
consequences.

\begin{theorem}
\label{theorem1}
Let $f$ be locally Lipschitz and suppose for every $x\in \mathbb R^n$, $f$ is either lower-$C^1$ or  upper-$C^1$ at $x$.
Let $x^1$ be  such that $Ax^1 \leq b$ and  $\{x\in \mathbb R^n: f(x)\leq f(x^1), Ax\leq b\}$
is bounded.
Then every accumulation point $x^*$ of the sequence $x^j$ of serious iterates
generated by algorithm {\rm \ref{algo1}}
is a KKT-point of {\rm (\ref{program})}.
\end{theorem}

\begin{proof}
The result will follow
from \cite[Theorem 1]{noll} as soon as we show
that downshifted tangents as modified in Example \ref{modified} and used in the algorithm
is a strict cutting plane oracle in the sense of definition \ref{strict-oracle}.
The remainder of the proof is to verify this.

1)
Let us denote cutting planes arising from the standard model $\phi^\sharp$
by $m_y^\sharp(\cdot,x)$,  cutting planes obtained by downshift as $m_y^\downarrow(\cdot,x)=t(\cdot)-s$,
and the true cutting plane of the oracle as $m_y(\cdot,x)$. Then as we know
$m_y(\cdot,x)=m_y^\downarrow(\cdot,x)$ if $m_y^\downarrow(y,x) \geq m_y^\sharp(y,x)$,
and otherwise $m_y(\cdot,x)=m_y^\sharp(\cdot,x)$. We have to check $(O_1)$, $(\widehat{O}_2)$, $(O_3)$.

2)
The validity of $(O_1)$ is clear, as both oracles provide Clarke tangent planes to $f$ at $x$ for
$y=x$.

3)
Let us now check $(O_3)$. Consider $x_j\to x$, and $y_j,y_j^+ \to y$. Here $y_j^+$ is a null step at serious step $x_j$.
Passing to a subsequence, we may distinguish  case I,
where $m_{y_j^+}(\cdot,x_j) = m_{y_j^+}^\sharp(\cdot,x_j)$ for every $j$,
and case II, where $m_{y_j^+}(\cdot,x_j)=m_{y_j^+}^\downarrow(\cdot,x_j)$ for every $j$.

Consider case I  first. Let $m_{y_j^+}^\sharp(y_j,x_j) = f(x_j) + g_j^\top (y_j-x_j)$, where $g_j\in \partial f(x_j)$
satisfies
$f^0(x_j,y_j^+-x_j)=g_j^\top (y_j^+-x_j)$.
Passing to yet another subsequence, we may assume $g_j\to g$, and
upper semi-continuity of the Clarke subdifferential gives $g\in \partial f(x)$.
Therefore $m_{y_j^+}(y_j,x_j) = f(x_j) + g_j^\top (y_j-x_j)\to
f(x) + g^\top (y-x) \leq m_y^\sharp(y,x)\leq m_y(y,x)$. So here $(O_3)$ is satisfied
with $z=y$.

Newt consider case II. Here we have
$m_{y_j^+}(y_j,x_j) = t_{g_j}(y_j) - s_j$, where $t_{g_j}(\cdot)$ is a tangent to $f$ at $y_j^+$
with subgradient $g_j\in \partial f(y_j^+)$, and $s_j$ is the corresponding downshift
\[
s_j = \left[ t_{g_j}(x_j) -f(x_j) + c\|y_j^+-x_j\|^2   \right]_+.
\]
Passing to a subsequence, we may assume $g_j\to g$, and by upper semi-continuity of $\partial f$ we have
$g\in \partial f(y)$. Therefore $s_j \to \left[ t_g(x) - f(x) + c\|y-x\|^2 \right]_+=:s$, where uniform
convergence $t_{g_j}(y_j)\to t_g(y)$ occurs due to the boundedness of $\partial f$. But now we see that
$s$ is the downshift for the pair $(x,y)$ when $g\in \partial f(y)$ is used.
Hence $m_{y_j^+}(y_j,x_j) \to m_y^\downarrow(y,x)$, and since
$m_y^\downarrow(y,x)\leq m_y(y,x)$, we are done. So again the $z$ in $(O_3)$ equals $y$ here.

4) Let us finally check axiom $(\widehat{O}_2)$.
Let $x_j,y_j\to x$ be given.
We first consider the case when $f$ is upper-$C^1$ at $x$.
We have to find $\epsilon_j\to 0^+$
such that $f(y_j) \leq m_{y_j}(y_j,x_j) + \epsilon_j \|y_j-x_j\|$ as $j\to \infty$, and by the definition of the oracle,
it clearly suffices to show $f(y_j) \leq m_{y_j}^\sharp(y_j,x_j) + \epsilon_j\|y_j-x_j\|$.
By Spingarn \cite{spingarn},  or Daniilidis and Georgiev \cite{georgiev},
$-f$, which is lower-$C^1$ at $x$, has the following property: For every $\epsilon > 0$
there exists $\delta >0$ such that for all $0 < t < 1$ and $y,z\in B(x,\delta)$,
\[
f(y) \leq f(z) + t^{-1} \left( f(z+t(y-z)) -f(z) \right) + \epsilon (1-t) \|z-y\|.
\]
Taking the limit superior $t\to 0^+$ implies
$$
f(y) \leq f(z) + f'(z,y-z) +\epsilon \|y-z\| \leq f(z) + f^0(z,y-z)+\epsilon \|y-z\|.
$$
Choosing $z=x_j$, $y=y_j$, $\delta_j = \|y_j-z_j\|\to 0$, we can find
$\epsilon_j \to 0^+$ such that
$f(y_j)\leq f(x_j) + f^0(x_j,y_j-x_j) + \epsilon_j \|y_j-x_j\|$, hence
$f(y_j) \leq m_{y_j}^\sharp(y_j,x_j) + \epsilon_j\|y_j-x_j\|$ by the definition of $m^\sharp_{y_j}(\cdot,x_j)$.
That settles the upper-$C^1$ case.

Now consider the case where $f$ is lower-$C^1$ at $x$.
We have to find $\epsilon_j\to 0^+$
such that $f(y_j) \leq m_{y_j}(y_j,x_j) + \epsilon_j \|y_j-x_j\|$ as $j\to \infty$, and
it suffices to show $f(y_j) \leq m_{y_j}^\downarrow(y_j,x_j) + \epsilon_j\|y_j-x_j\|$.
Since $m_{y_j}^\downarrow(y_j,x_j) \geq f(y_j) - s_j$, where
$s_j$ is the downshift $s_j = \left[ t(x_j) - f(x_j) + c\|y_j-x_j\|^2 \right]_+$, and
$t(\cdot)=f(y_j) + g_j^\top (\cdot-y_j)$ for some $g_j\in \partial f(y_j)$,
it suffices to exhibit $\epsilon_j\to 0^+$ such that
$f(y_j) \leq f(y_j)-s_j + \epsilon_j \|y_j-x_j\|$, or what is the same,
$s_j \leq \epsilon_j \|y_j-x_j\|$. For that it suffices to
arrange $\left[t(x_j) - f(x_j)\right]_+ \leq \epsilon_j \|y_j-x_j\|$, because once this is verified,
we get $s_j \leq \left[ t(x_j)-f(x_j) \right]_+ + c\|y_j-x_j\|^2
\leq (\epsilon_j + c\|y_j-x_j\|) \|y_j-x_j\| =: \widetilde{\epsilon}_j \|y_j-x_j\|$.
Note again that
by \cite{spingarn,georgiev}
$f$ has the following property at $x$: For every $\epsilon > 0$
there exists $\delta > 0$ such that
$f(tz+(1-t)y) \leq tf(z) + (1-t)f(y) + \epsilon t(1-t)\|z-y\|$ for all $y,z\in B(x,\delta)$.
Dividing by $t>0$  and passing to the limit $t\to 0^+$ gives
$f^0(y,z-y) \leq f(z) - f(y) + \epsilon \|y-z\|$, using the fact that $f$ is locally Lipschitz.
But for every $g\in \partial f(y)$, $g^\top (z-y) \leq f^0(y,z-y)$.
Using $\|y_j-x_j\| =: \delta_j \to 0$ and taking $y=y_j$, $z=x_j$, this allows us to find
$\epsilon_j\to 0^+$ such that
$g_j^\top (x_j-y_j) \leq f(x_j)-f(y_j)+\epsilon_j \|y_j-x_j\|$.
Substituting this above gives
$t(x_j)-f(x_j) = f(y_j)-f(x_j) + g_j^\top (x_j-y_j)\leq \epsilon_j \|y_j-x_j\|$ as desired.
That settles the lower-$C^1$ case.
\end{proof}

\section{Practical aspects of the algorithm}
\label{practical}
In this section we discuss several
technical aspects of the algorithm, which are
important for its performance.

\subsection{Stopping}
The stopping test in step
2 of the algorithm is stated in this form for the sake of the convergence proof. In practice we delegate  stopping
to the inner loop using
the following two-stage procedure.

If the inner loop
at serious iterate $x^j$ finds the new serious step $x^{j+1}$
such that
\[
\frac{\|x^{j+1}-x^j\|}{1+\|x^j\|} < {\rm tol}_1, \quad \frac{|f(x^{j+1})-f(x^j)|}{1+|f(x^j)|} < {\rm tol}_2,
\]
then we decide that $x^{j+1}$ is optimal. In consequence, the $(j+1)$st inner loop will
not be executed. On the other hand, if the inner loop has difficulties  terminating
and  produces five consecutive
null steps $y^k$ where
\[
\frac{\|y^k-x^j\|}{1+\|x^j\|} < {\rm tol}_1, \quad \frac{|f(y^k)-f(x^j)|}{1+|f(x^j)|} < {\rm tol}_2,
\]
or if a maximum number $k_{\rm max}$  of allowed steps in the inner loop is reached, then
we decide that $x^j$ is optimal. In our experiments we use
\textcolor{black}{${\rm tol}_1= 10^{-5}$, ${\rm tol}_2= 10^{-5}$},
and $k_{\rm max}=50$.

\subsection{Recycling of planes}
At the beginning of a new inner loop at serious step $x^{j+1}$,
we do not want to start building the working model $\phi_1(\cdot,x^{j+1})$ from scratch.
It is more efficient to recycle some of the planes $(a,g) \in \mathcal G_{k_j}$
in the latest working model $\phi_{k_j}(\cdot,x^j)$. In the convex cutting plane
method, this is self-understood, as cutting planes are affine minorants of $f$,
and can at leisure stay on in the sets $\mathcal G$ at all times $j,k$. Without convexity,
we need the following recycling procedure:

Given a plane $m(\cdot,x^j) = a + g^\top (\cdot - x^j)$
in the latest set $\mathcal G_{k_j}$, we form the new downshifted plane
\[
m(\cdot,x^{j+1}) = m(\cdot,x^j) - s,
\]
where the downshift is organized as
\[
s = \left[  m(x^{j+1},x^j) - f(x^{j+1}) + c \|x^{j+1}-x^j\|^2\right]_+.
\]
In other words, we treat $m(\cdot,x^j)$ like a tangent to $f$ at null step
$x^j$ with respect to the serious step $x^{j+1}$ in the downshift oracle. We put
\[
m(\cdot,x^{j+1}) = a + g^\top (\cdot - x^j) - s
= a - s + g^\top (x^{j+1}-x^j) + g^\top (\cdot - x^{j+1}),
\]
and
we accomodate $(a-s+g^\top(x^{j+1}-x^j),g)\in \mathcal G_1$
at the beginning of the $(j+1)$st inner loop.
\textcolor{black}{In the modified version we only keep a plane of this type in $\mathcal G_1$ after comparing it to
the exactness plane $m_0(\cdot,x^{j+1})= f(x^{j+1})+g^\top (\cdot - x^{j+1})$, $g\in \partial f(x^{j+1})$, which satisfies
$g^\top (x^{j}-x^{j+1})=f^0(x^{j+1},x^j-x^{j+1})$. Indeed, when $m(x^j,x^{j+1}) \geq m_0(x^j,x^{j+1})$, then we keep
the downshifted plane, otherwise we add $m_0(\cdot,x^{j+1})$ as additional exactness plane.  }

\section {The delamination benchmark problem} \label{delamination}

The interface behavior of laminated composite materials
is modeled by a non-monotone multi-valued function $\partial j$,
characteristic of the  interlayer adhesive  placed at the contact boundary $\Gamma_c$.
In more precise terms, $\partial j$ is the physical law which holds
between the normal component $-S_n(s)|\Gamma_c$
of the  stress vector
and the relative displacement $u_2(s)|\Gamma_c$, or {\em jump},  between the upper and lower boundaries.
A typical law $\partial j$ for an interlayer adhesive is shown in Figure \ref{dellaw} (left).
In the material sciences, the knowledge of $\partial j$ is crucial
for the understanding of the basic failure modes of
the composite material.

The adhesive law $\partial j$ is usually determined experimentally using
the double cantilever beam test \cite{gudladt} or other destructive testing methods. The result of a typical experiment
is shown schematically in Figure \ref{contaminated}  from \cite{gudladt}, where three probes with different levels of
contamination have been exposed.
While the intact material shows stable
propagation of the crack front (dashed curve),
the 10\% contaminated
specimen shows a typical zig-zag profile (bold solid curve), indicating unstable crack front propagation.
Indeed, when reaching the critical load $P=140$N, the crack starts to propagate. Since by the growth
of the  crack-elongation,
the compliance of the structure increases, the crack propagation slows down and the crack is "caught", i.e.,
stops at $u_2=0.25$mm and the load $P$ in the structure drops from $P=140$N to $P=40$N.
Thereafter, due to the continuously increased load,  the crack starts
again to propagate until reaching another critical load
level at $P=90N$ and $u_2=5$mm. This phenomenon occurs five to six times, as seen in Figure \ref{contaminated}.

\begin{figure}[h!]
\centering
\includegraphics{fig_dellaw}
\caption{Left image shows non-monotone delamination law $\partial j$, leading to an upper-$C^1$ objective. Right image
shows non-monotone friction law, leading to a lower-$C^1$ objective.  \label{dellaw}}
\end{figure}

The 50\% contaminated specimens (dotted curve) shows micro-cracks that appear at a finer level  and are
not visible in the Figure \ref{contaminated}. The lower level of the adhesive energy, which is represented by the area below the load-displacement curve, indicates now that this specimen is of minor resistance.

Even though
the displacement $u_2$ in Figure \ref{contaminated} can only be measured
at the crack tip, in order to proceed one now {\em stipulates} the law $\partial j$ all along
$s\in \Gamma_c$  by assuming that the normal stresses
$S_n(s)|\Gamma_c$
follow the  measured behavior
\begin{eqnarray}
\label{law1}
-S_n(s) \in  \partial j(s, u_2(s)), \; s\in \Gamma_c.
\end{eqnarray}
Under this hypothesis one now
solves the variational
inequality for the unknown displacement field ${\bf u}=(u_1,u_2)$,
and then validates
(\ref{law1}).
Note that $S_n(s)|\Gamma_c$ is the {\em truly} relevant information, as it indicates the
action of the destructive forces along $\Gamma_c$,  explaining
eventual failure of the composite.
In current practice in the material sciences,
this information cannot be assessed by direct measurement,
and is therefore estimated by heuristic formulae \cite{gudladt}.  Our approach could  be
interpreted as one such estimation technique based on mathematical modeling.

\begin{figure}[h!]
\centering
\includegraphics[width =\textwidth]{fig_model}
\caption{Schematic view of cantilever beam testing. Under applied traction force $F_2$  the crack front
propagates to the left. In program (\ref{del2})  traction force $F_2$ and crack front length are given, while the corresponding
displacement $u$ and reactive forces $-S_n|\Gamma_c$ along the contact boundary $\Gamma_c$ have to be computed. \label{model}}
\end{figure}

 \subsection{Delamination study}
Within the framework of plane linear elasticity
we consider  a symmetric
laminated structure with
an interlayer adhesive under loading (see Fig. \ref{model}).
Because of the
symmetry of the structure, it suffices to consider only the upper half of the specimen, represented by $\Omega \subset \mathbb R^2$.
The Lipschitz boundary $\Gamma$ of $\Omega $ consists of four disjoint
parts $\Gamma_u$, $\Gamma_c$, $\Gamma_{F_1}$ and $\Gamma_{F_2}$.
The body is fixed on $\Gamma_u$, i.e.,
$$
u_i=0 \; \mbox{on} \; \Gamma_u, \quad i=1,2.
$$
On $\Gamma_{{F_1}} $ the traction forces $\mathbf F$ are constant and given as
$$
\mathbf{F}=(0,F_2) \quad \mbox{on} \; \Gamma _{F_1}.
$$
The part $\Gamma _{F_2}$ is load-free.
We adopt standard notation from linear elasticity and introduce
the bilinear form of  linear elasticity
\begin{equation}\label{elastic}
 a(\mathbf u, \mathbf v) = \int _ \Omega \mathbf
\varepsilon(\mathbf u) \, : \, \mathbf \sigma (\mathbf v) \, dx,
\end{equation}
where $\mathbf u=(u_1,u_2)$ is the displacement vector,
$\mathbf \varepsilon ({\bf u}) = \frac{1}{2}(\nabla \mathbf u + (\nabla \mathbf u )^T)$
the linearized strain tensor,  and
$\mathbf \sigma (\mathbf v) = \mathbf C : \mathbf \varepsilon (\mathbf v)$  the stress tensor.
 Here, $\mathbf C$ is the elasticity tensor with symmetric positive $L^{\infty}$
 coefficients. The bilinear form is symmetric and due to the first Korn inequality,
coercive.
The linear form $\langle \mathbf{g}, \cdot \rangle$ is defined by
$$
\langle \mathbf{g},\mathbf{v}\rangle =F_2\int _{\Gamma_{F_1}}v_2\, ds.
$$
On the contact boundary $\Gamma_c$ we have the unilateral constraint
$$
u_2 \geq 0 \quad \mbox{a.e. on} \; \Gamma_c
$$
and we apply the non-monotone multi-valued adhesive  law
\begin{eqnarray}
\label{law}
 -S_n(s) \in \partial j(s, u_2(s)) \quad  \mbox{for a.a.} \; s\in \Gamma _c.
\end{eqnarray}
Here $S_n=\sigma_{ij} n_j n_i$, where  $\mathbf n=(n_1,n_2)$ is the outward unit normal vector to $\Gamma_c$.

A typical non-monotone law $\partial j(s, \cdot)$ for delamination,
describing the behavior of the adhesive,  is shown in Fig. \ref{dellaw}.
This law is derived from a nonconvex and a nonsmooth locally Lipschitz
super-potential $j$  expressed in terms of a minimum function.
In particular, $j(s,\cdot)$ is a minimum of four convex quadratic  and one linear function.

We also assume that tangental traction can be neglected on $\Gamma_c$, i.e., $S_t(s)=0$.
The weak
formulation of the delamination problem is then given by the following hemivariational
inequality:   Find
$\mathbf{u}\in K$ such that
\begin{equation} \label{del}
a(\mathbf{u},\mathbf{v}-\mathbf{u}) + \displaystyle \int_{\Gamma_c}j^0(s, u_2(s);v_2(s)-
u_2(s)) \, ds \geq \langle \mathbf{g}, \mathbf{v}-\mathbf {u}
\rangle \quad \forall \, \mathbf{v}\in K,
\end{equation}
where
$j^0(s, u;d)$ is the  Clarke  directional derivative of
$j(s,\cdot)$ at ${u}$ in direction $d$,
$K$ is the nonempty, closed  convex set of all admissible displacements defined by
$$
K=\{\mathbf{v} \in V \, : \, v_2 \geq 0  \, \, \;  \mbox{on} \, \, \; \Gamma_c \},
$$
contained in the function space
$$
V=\{ \mathbf{v} \in H^1(\Omega; \mathbb R^2)\;: \; \mathbf{v}=0 \;\, \mbox{on} \;\, \Gamma _u \}.
$$
The potential energy  of the  problem is
$$
\Pi (\mathbf v) =\frac{1}{2} a(\mathbf v, \mathbf v) + J(\mathbf v)  - \langle \mathbf{g}, \mathbf{v} \rangle,
$$
where $J:V\to \mathbb R$ defined by
$$
J(\mathbf v)=\int_{\Gamma_c} j(s, v_2(s)) \, ds
$$
is the term responsible for the nonsmoothness.
Using the potential energy, the hemivariational inequality
  (\ref{del})  can be transformed to  the
following  nonsmooth, nonconvex
constrained optimization problem
of the form (\ref{program})
\begin{eqnarray}
\label{del2}
\begin{array}{ll}
\mbox{minimize} & \Pi(\mathbf u) \\
\mbox{subject to} & {\mathbf u} \in K
\end{array}
\end{eqnarray}
where the objective is upper-$C^1$, because the super-potential $j(s,\cdot)$
is a minimum. In particular, we have an objective of the form (\ref{structure}),
where the smooth part $f_s$ comprises $\frac{1}{2}a({\mathbf v},{\mathbf v})
- \langle \mathbf g,\mathbf v\rangle$, while the nonsmooth
part  $J(\mathbf v)=\int_{\Gamma_c} j(s,v_2(s))\,ds$ has the
form  (\ref{structure}) with a finite
index set $I$ once the boundary integral is suitably parametrized.

According to the existence theory in \cite{Naniewicz}, problem (\ref{del2})
has at least one Clarke critical point ${\mathbf u}^*$ satisfying
the necessary optimality condition
$$
0\in \partial \,\Pi ({\bf u}^*) + N_K({\bf u}^*),
$$
where $N_K({\mathbf u})$ is the normal cone to
$K$ at $\mathbf u$,
and vice versa,
by a result in \cite{Miettinen}  every critical point of
$\Pi$ on $K$ is a solution of (\ref{del}) (see also \cite{Makela}).

\begin{figure}[h!]
\includegraphics{fig_contaminated}
\caption{Load-displacement curve determined by double cantilever beam test. Dashed curve shows stable behavior for
material without contamination. The 10\% contaminated specimen (bold solid curve) shows unstable crack growth.
After initial linear growth, when the critical load $P=140$N is reached,
the crack starts to propagate. But then the propagation speed slows down, since by the crack the compliance of the specimen increases, and the crack is "caught" at $u_2=0.25$mm. The load $P$ drops from $P=140$N to $P=40$N. Then, by the constantly applied traction force, there is a linear growth of the load $P$  from $ P=40$N to the critical load $P=90$N, where the crack propagates again and stops at $u_2=5$mm, with the load now reduced to $P=30$N.
The 50\% contaminated specimen exhibits  micro-cracks not visible at the chosen scale.
\label{contaminated}}

\end{figure}

\subsection{Discrete problem}
We consider a regular triangulation $\{\mathcal T_h\}$ of $\Omega$, where
we first divide $\Omega$ into small squares of  size $h$ and then each
square by its diagonal into two triangles.
To approximate
$V$ and $K$  we use a piecewise linear finite element approximation and set
$$
V_h=\{v_h \in C(\overline{\Omega};\mathbb R^2)\, : \, {v_h}_{|_{T}} \in ({\bf P}_1)^2,
\, \forall \,T \in \mathcal T_h, \, {v_h}_{|_{\Gamma_u}}=0 \},
$$
$$
K_h=\{v_h \in V_h: v_{h2}(s_\nu)\geq 0 \quad \forall \, s_\nu \in \overline{\Gamma}_c\backslash \overline{\Gamma}_u\}.
$$
Similar to low order finite element approximations of nonsmooth convex contact problems \cite{Glowinski1, Gwinner},
we use the trapezoidal quadrature rule to approximate the functional $J$ by
 \begin{eqnarray}
\label{Jh}
J_h(v_h)  =  \frac{1}{2} \displaystyle \sum_{s_\nu\in \overline{\Gamma}_c\setminus\overline{\Gamma}_u}  |s_\nu s_{\nu+1}| \big [
j(s_\nu,v_{h2}(s_\nu)) +

 j(s_{\nu+1},v_{h2}(s_{\nu+1}))
\big ] ,
\end{eqnarray}
where we  are summing over the
nodes  $s_\nu$ on the contact boundary $\overline{\Gamma}_c\backslash  \overline{\Gamma}_u$, with
$s_{\nu+1}$ being the neighbor of node $s_\nu$ on $\Gamma_c$ in the sense of integration.
This can be regrouped as
\[
J_h(v_h)= \sum_{s_\nu\in \overline{\Gamma}_c\setminus\overline{\Gamma}_u} c_\nu
j(s_\nu,v_{h2}(s_\nu)) = \sum_{s_\nu\in \overline{\Gamma}_c\setminus\overline{\Gamma}_u} c_\nu \min_{i\in  I}
j_i(s_\nu,v_{h2}(s_\nu))
\]
with appropriate weights $c_\nu>0$.
Here, $ I$ is the set of zig-zags in the graph of $\partial j$.

The bundle  algorithm is applied to minimize the discrete functional
\begin{equation} \label{discreteJ}
\Pi_h(v_h)= \frac{1}{2} a(v_h,v_h)+J_h(v_h) - \langle g, v_h \rangle \quad \mbox{on} \quad K_h.
\end{equation}
Introducing an index set $N$
for the nodes $s_\nu$ on the contact boundary $\overline{\Gamma}_c$, we may pull out the minimum from
under the sum, which leads to the expression
\[
\Pi_h(v_h)=\frac{1}{2} a(v_h,v_h)+
\min_{i(\cdot) \in I^N} \sum_{\nu\in N} c_\nu j_{i(\nu)}(s_\nu,v_{h2}(s_\nu)) - \langle g,v_h\rangle.
\]
This is the discrete version of  (\ref{struct}), where
$\frac{1}{2}a(v_h,v_h)-\langle g,v_h\rangle$ is the smooth term $f_s$, and $J_h$ the nonsmooth part.

While computation of Clarke subgradients is straightforward here,
we still have to explain how the
matrix $Q=Q(v)$ in the second-order working model (\ref{second}) is chosen.
Discretizing the quadratic form of linear elasticity
as $a(v_h,v_h)=v_h^\top {\bf A} v_h$ with the symmetric stiffness matrix ${\bf A}$,
and observing that $\langle g,v_h\rangle = {\bf g}^\top v_h$ is linear,
we choose $Q(v)  ={\bf A} + \sum_{\nu\in N} \nabla^2 j_{i(\nu)} (s_\nu,v_h(s_\nu))$, where
$i(\nu)\in I$ is one of those indices, where the minimum
$\min_{i\in I} j_i(s_\nu,v_{h2}(s_\nu))$ is attained.

For convergence of the lowest-order finite element approximation used here
we refer to the results in \cite{Ovcharova}. Higher-order approximations with no limitation in the
polynomial degree,
which lead to nonconforming approximation of unilateral constraints,
have only recently been analyzed for monotone contact problems, see \cite{Gwinner_2013}.

\subsection{Numerical results}
We present numerical results obtained in a  delamination simulation
with modulus of elasticity $E=210$ GPa and Poisson ratio $\nu =0.3$ corresponding to a steel specimen. In all examples we use the benchmark model of \cite{Baniotopoulos2} with geometrical characteristics $(0,100) \times (0,10) $ in [mm] and
thickness $5$mm.  We apply our bundle method to
(\ref{del2}) and compare the results to those obtained by
the regularization technique in \cite{Ovcharova, Ovcharova_Gwinner}. All  computations use
piecewise linear functions and the discretization $40 \times 4$ corresponding to $h=0.25$cm.
In this case, the number of the unknowns in the discrete problem (\ref{discreteJ}) is $80$.

\begin{figure}[h!]
\includegraphics[width=7.8cm,height=4.6cm]{fig_1displ}
\includegraphics[width=7.8cm,height=4.6cm]{fig_1reactions}
\includegraphics[width=7.8cm,height=4.7cm]{fig_2displ}
\includegraphics[width=7.8cm,height=4.6cm]{fig_2reactions}
\caption{Upper: regularization method of  \cite{Ovcharova, Ovcharova_Gwinner}. Lower: optimization method. Left image shows vertical displacement $u_2$
for 5 different values of  $F_2$. Right image shows vertical component of reactive force along contact boundary for   same 5
scenarios.}
\end{figure}

\begin{table}[h!]
\caption{Regularization. Vertical displacement [mm] at 4 intermediate points  for  same 5 scenarios.}
\centering
\begin{tabular}{||c||c|c|c|c||}
\hline\hline
$F_2 [N/mm^2]$  & $u_2(x_1)$ & $u_2(x_2)$ & $u_2(x_3)$ & $u_2(x_4)$ \\
\hline\hline
0.2&4.154500e-06&1.394500e-05&2.601700e-05&3.858700e-05\\
0.4&8.308100e-06&2.788800e-05&5.202800e-05&7.716600e-05\\
0.6&1.633200e-05&5.622700e-05&1.080000e-04&1.640000e-04\\
0.8&2.792500e-05&9.663100e-05&1.860000e-04&2.810000e-04\\
1.0&4.600600e-05&1.590000e-04&3.080000e-04&4.660000e-04\\
\hline\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\caption{Optimization. Vertical displacement [mm] at four intermediate  points for  same 5 scenarios.}
\centering
\begin{tabular}{||c||c|c|c|c||}
\hline\hline
$F_2 [N/mm^2]$  & $u_2(x_1)$ & $u_2(x_2)$ & $u_2(x_3)$ & $u_2(x_4)$ \\
\hline\hline
0.2&4.022500e-06&1.345400e-05&2.499300e-05&3.691900e-05\\
0.4&8.069300e-06&2.698800e-05&5.013300e-05&7.404900e-05\\
0.6&1.564800e-05&5.373900e-05&1.030000e-04&1.550000e-04\\
0.8&2.691300e-05&9.297200e-05&1.790000e-04&2.700000e-04\\
1.0&4.414000e-05&1.530000e-04&2.940000e-04&4.470000e-04\\
\hline\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\caption{Regularization. Horizontal displacement [mm] at four intermediate points  for  same 5 scenarios.}
\centering
\begin{tabular}{||c||c|c|c|c||}
\hline\hline
$F_2 [N/mm^2]$  & $u_2(x_1)$ & $u_2(x_2)$ & $u_2(x_3)$ & $u_2(x_4)$ \\
\hline\hline
0.2&1.481900e-06&2.251300e-06&2.474400e-06&2.499500e-06\\
0.4&2.963600e-06&4.502200e-06&4.948300e-06&4.998500e-06\\
0.6&5.918500e-06&9.400600e-06&1.077100e-05&1.097500e-05\\
0.8&1.015200e-05&1.625600e-05&1.866400e-05&1.904000e-05\\
1.0&1.674400e-05&2.690100e-05&3.100500e-05&3.167000e-05\\
\hline\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\caption{Optimization. Horizontal displacement [mm] at four intermediate points  for  same 5 scenarios.}
\centering
\begin{tabular}{||c||c|c|c|c||}
\hline\hline
$F_2 [N/mm^2]$  & $u_2(x_1)$ & $u_2(x_2)$ & $u_2(x_3)$ & $u_2(x_4)$ \\
\hline\hline
0.2&1.432200e-06&2.161500e-06&2.356100e-06&2.368400e-06\\
0.4&2.872700e-06&4.335000e-06&4.724700e-06&4.748800e-06\\
0.6&5.663400e-06&8.957000e-06&1.023200e-05&1.041100e-05\\
0.8&9.777300e-06&1.561000e-05&1.787700e-05&1.822600e-05\\
1.0&1.606400e-05&2.578000e-05&2.970700e-05&3.034700e-05\\
\hline\hline
\end{tabular}
\end{table}

\begin{figure}[ht]
\hspace*{-.4cm}
\includegraphics[width=7.8cm,height=4.7cm]{fig_comp5_n}
\includegraphics[width=7.8cm,height=4.7cm]{fig_comp4_n}
\caption{Comparison of regularization (bold solid curves) and optimization (dashed) for 3 different values of  $F_2$.
Left vertical displacement, right reactive force.}
\end{figure}

\begin{table}[h!]
\caption{Comparison of optimal valued obtained by regularization and optimization}
\centering
\begin{tabular}{||c|c|c||}
\hline\hline
$F_2 [N/m^2] $             &    ${\Pi_h}_{\rm reg} [Nm]$    &     ${\Pi_h}_{\rm opt}$ [Nm] \\
\hline\hline
200000 &	-1.32894	&-1.29271 \\
\hline
400000	&-2.35224&	-2.30025\\
\hline
600000&	-3.83972&	-3.74609 \\
\hline
800000	&-5.08164	&-5.05389	\\
\hline
1000000&	-5.66771	&-5.66770	\\
\hline\hline
\end{tabular}
\end{table}

\section*{Conclusion}
We have presented a bundle method based on the mechanism of
downshifted tangents which is suited to optimize upper- and lower-$C^1$ functions. Our method allows to integrate
second-order information, if available, and gives a convergence certificate in the sense of subsequences. Every accumulation point of the sequence of serious iterates with an arbitrary starting point is critical.
We have successfully applied our method to a delamination problem arising in the material sciences, where upper-$C^1$ functions
have to be minimized.
Results obtained by optimization were compared to results obtained by  the regularization technique of
 \cite{Ovcharova, Ovcharova_Gwinner},  and both methods are in good agreement.

\section*{Acknowledgment}
The authors thank H.-J. Gudladt for many useful discussions.
The authors were  partially supported by Bayerisch-Franz\"osisches Hochschulzentrum (BFHZ).

\begin {thebibliography}{99}
\bibitem{gudladt} M. Wetzel, J. Holtmannsp\"otter, H.-J. Gudladt, J. v. Czarnecki: Sensitivity of double cantilever beam test to
surface contamination and surface pretreatment. International Journal of Adhesion \& Adhesives, Vol. 46, 114-121 (2013)
\bibitem{miflin} R. Mifflin: A modification and an extension of Lemar\'echal's algorithm for nonsmooth
minimization. Math. Progr. Study 17, 77-90 (1982)
\bibitem{le-saga1}
C. Lemar\'echal:  Bundle methods in nonsmooth optimization. In Nonsmooth optimization (Proc. IIASA Workshop, Laxenburg, 1977), pp. 79-102, IIASA Proc. Ser., 3, Pergamon, Oxford-Elmsford, N.Y., 1978.
\bibitem{le-saga2} C. Lemar\'echal, C. Sagastiz\'abal: Variable metric bundle methods: from conceptual to implementable forms. Math. Programming 76 (1997), no. 3, Ser. B, 393-410.
\bibitem{zowe} {J. Zowe}: The BT-Algorithm for minimizing a nonsmooth functional subject to linear constraints, in  Nonsmooth Optimization and Related Topics , F. H. Clarke, V. F. Demyanov, F. Gianessi (eds.), Plenum Press (1989)
\bibitem{schramm} {H. Schramm, J. Zowe}: A version of the bundle idea for
minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Optim. 2,  121 - 152 (1992)
\bibitem{noll} D. Noll: Cutting plane oracles to minimize nonsmooth nonconvex functions. Set-Valued Var. Anal. 18 (3-4), 531-568 (2010)
\bibitem{pjo} D. Noll, O. Prot, A. Rondepierre: A proximity control algorithm to minimize nonsmooth nonconvex functions. Pacific J. Optim. 4 (3), 569-602 (2008)
\bibitem{gabarrou} D. Alazard, M. Gabarrou, D. Noll: Design of a flight control architecture using a nonconvex bundle method.
Math. Control Sign. Syst. 25 (2), 257-290 (2013)
\bibitem{flows} D. Noll: Convergence of nonsmooth descent methods using the Kurdyka-\L ojasiewicz inequality.
J. Optim. Theory Appl. (DOI) 10.1007/s10957-013-0391-8.
\bibitem{Makela} M.M. M\"{a}kel\"{a}, M. Miettinen, L. Luk\v{s}an,  J. Vl\v{c}ek: Comparing nonsmooth nonconvex bundle methods in solving hemivariational inequalities, Journal of Global Optimization 14  (2), 117-135  (1999).
\bibitem{Miettinen} M. Miettinen, M.M. M\"{a}kel\"{a}, J. Haslinger: On numerical solution of hemivariational inequalities by nonsmooth optimization methods, Journal of Global Optimization 6 (4), 401-425 (1995).
\bibitem{Luksan} L. Luk\v{s}an,  J. Vl\v{c}ek:
A  Bundle-Newton method for nonsmooth unconstrained minimization, Math. Progr. 83,  373 - 391 (1998)
\bibitem{Haslinger}  J. Haslinger, M. Miettinen, P.D. Panagiotopoulos:
  Finite Element Methods for Hemivariational Inequalities, Kluwer Academic Publishers (1999)
\bibitem{Czepiel} J. Czepiel: Proximal Bundle Method for a Simplified Unilateral Adhesion Contact Problem of Elasticity, Schedae Informaticae 20, 115-136 (2011)
  \bibitem {LeoSt} L. Nesemann, E.P. Stephan: Numerical solution of an adhesion problem with FEM and BEM, Appl. Numer. Math. 62 (5), 606-619 (2012)
\bibitem{Kocvara} M. Ko\v{c}vara, A. Mielke, T. Roub\'{\i}\v{c}ek: A rate-independent approach to the delamination problem, Math. Mech. Solids 11, No. 4, 423-447 (2006)
\bibitem{Roubicek} T. Roub\'{\i}\v{c}ek, V. Mantic, Panagiotopoulos, C.G.: A quasistatic mixed-mode delamination model, Discrete Contin. Dyn. Syst., Ser. S 6, No. 2, 591-610 (2013)
\bibitem{spingarn} J. E. Spingarn: Submonotone subdifferentials of Lipschitz functions. Trans. Amer. Math. Soc. 264, 77-89 (1981)
\bibitem{georgiev} A. Daniilidis, P. Georgiev: Approximate convexity and submonotonicity. J. Math. Anal. Appl. 291, 117-144 (2004)
\bibitem{rock} R. T. Rockafellar, R. J-B. Wets:
Variational Analysis. Springer Verlag (2004)
\bibitem{malick-dani} A. Daniilidis, J. Malick: Filling the gap between lower-$C^1$ and lower-$C^2$ functions. Journal of Convex Analysis
12(2), 2005, pp. 315 -- 329.
\bibitem{amenable}  R. A. Poliquin, R. T. Rockafellar:  Prox-regular functions in variational analysis, Trans. Amer. Math. Soc. 348 (5), 1805 - 1838 (1996)
\bibitem{kiwiel_aggregate}  K.C. Kiwiel: An aggregate subgradient method for nonsmooth
convex minimization, Math. Programming 27, 320 - 341 (1983)
\bibitem{cullum} J. Cullum, W.E. Donath, P. Wolfe: The minimization of certain nondifferential sums
of eigenvalues of symmetric matrices. Math. Progr. Stud. 3, 35-55 (1975)
\bibitem{anp} P. Apkarian, D. Noll, O. Prot: A trust region spectral bundle method for nonconvex eigenvalue optimization, SIAM J. Optim. 10 (1), 281-306 (2008)
\bibitem{rudzsinski} A. Ruszczy{\'n}ski:  Nonlinear optimization,
Princeton University Press (2006)
\bibitem{hule:93} J.-B. Hiriart-Urruty, C. Lemar\'echal:  Convex Analysis and Minimization Algorithms, vol. I and II: Advanced Theory and Bundle Methods, vol. 306 of Grundlehren der mathematischen Wissenschaften, Springer Verlag, New York, Heidelberg, Berlin (1993)
\bibitem{saga} W. L. Hare, C. Sagastizabal: Computing proximal points of nonconvex functions, Math. Programming series B 116, 221-258 (2009)

\bibitem {Naniewicz} Z. Naniewicz, P.D. Panagiotopoulos: Mathematical Theory of Hemivariational Inequalities and Applications, New York (1995).
\bibitem{Ovcharova} N. Ovcharova: Regularization Methods and Finite Element Approximation of Hemivariational Inequalities with Applications to Nonmonotone Contact Problems, PhD Thesis, Universit\"at der Bundeswehr M\"unchen, Cuvillier Verlag, G\"{o}ttingen (2012).
\bibitem{Ovcharova_Gwinner}  N. Ovcharova, J. Gwinner:
A study of regularization techniques of nondifferentiable optimization in view of application to
hemivariational inequalities, accepted for publication in JOTA, JOTA-D-13-00163
\bibitem{Ovcharova_Gwinner} Ovcharova, N., Gwinner. J: On the regularization method in nondifferentiable optimization applied to hemivariational inequalities, Constructive Nonsmooth Analysis and Related Topics, Springer, 59-70 (2013).
\bibitem{Baniotopoulos1} C.C. Baniotopoulos, J.  Haslinger,   Z. Mor\'{a}vkov\'{a}: Contact problems with nonmonotone friction: discretization and numerical realization, Comput. Mech. 40, 157-165 (2007)
\bibitem{Baniotopoulos2} C.C. Baniotopoulos, J. Haslinger, Z.   Mor\'{a}vkov\'{a}: Mathematical modeling of delamination and nonmonotone friction problems by hemivariational inequalities, Applications of Mathematics 50 (1), 1-25 (2005)
\bibitem {Carl} S. Carl, V.K. Le, D. Motreanu: Nonsmooth Variational Problems and Their Inequalities, Springer (2007)
 \bibitem{Glowinski1} R. Glowinski:
 Numerical Methods for Nonlinear Variational Problems, Springer, New York (1984)

\bibitem {Goeleven} D. Goeleven, D. Motreanu, Y. Dumont, M. Rochdi, M.: Variational and Hemivariational Inequalities: Theory, Methods and Applications,  Vol. I: Unilateral
Analysis and Unilateral Mechanics, Vol. II: Unilateral problems, Kluwer (2003)
\bibitem{Gwinner} J. Gwinner: Finite-element convergence for contact problems in plane linear elastostatics, Quarterly of Applied Mathematics, Vol. 50,  11-25 (1992)
\bibitem{Gwinner_2013} J. Gwinner: hp-FEM convergence for unilateral contact problems with Tresca friction in plane linear elastostatics, J. Comput. Appl. Math., Vol. 254, 175-184 (2013)

      \bibitem{Panagiotopoulos1993} P.D. Panagiotopoulos: Hemivariational
    inequalities. Applications  in mechanics and engineering,
Berlin, Springer (1993)
\bibitem{Panagiotopoulos1998} P.D. Panagiotopoulos:
 Inequality problems in     mechanics and application. Convex  and nonconvex energy functions, Basel, Birkh\"{a}user (1998)

    \bibitem{Sofonea} M. Sofonea, A. Matei:  Variational Inequalities with Applications, Springer (2009)

\end {thebibliography}

\end{document}

The significance of $T < \infty$ in the algorithm
is that if the proximity control parameter
$\tau$ climbs above $T$ in the $j$th inner loop, then before
starting the $(j+1)$st inner loop after acceptance of $x^{j+1}$, we have to re-set
$\tau$ to the value $T$. This is what we call the large multiplier safeguard rule.
Setting $T=\infty$ means that this rule is dispensed with,
in which case the proximity control parameter
is {\em fully memorized} between serious steps. If we want to prove convergence
for this operational mode, we need the concept of strong oracle and strong model.

\begin{definition}
A model $\phi:\mathbb R^n \times \mathbb R^n \to \mathbb R$
for $f$ is called strong at $x_0$, if the following strong version of $(M_2)$
is satisfied:
\begin{enumerate}
\item[$(\widetilde{M}_2)$] There exists $\delta > 0$ and $L > 0$ such that
$f(y) \leq \phi(y,x) + L \|y-x\|^2$ for all $x,y\in B(x_0,\delta)$.
\end{enumerate}
The model is strong if it is strong at every $x_0$. \hfill
$\square$
\end{definition}

\begin{definition}
A cutting plane oracle $\mathscr O$ is strong at $x$ if the following
strong version of $(O_2)$ is satisfied.
\begin{enumerate}
\item[$(\widetilde{O}_2)$] Suppose $y_j,x_j \to x$. Then there exists $L>0$ such that
$f(y_j) \leq m_{y_j}(y_j,x_j) + L \|y_j-x_j\|^2$ for every $j\in \mathbb N$.
\end{enumerate}
\end{definition}

We have the same relationships as before. If $\mathscr O$ is strong, then $\phi^\uparrow$ is
strong, and if $\phi$ is strong, then $\mathscr O_\phi$ is. Strong implies strict for oracles
and models. There are strict models which are not strong, and there are models which are not strict.
For strong oracles we have the following

\begin{theorem}
Suppose $f$ is one-sided-$C^2$. Let $x^1$ be such that $Ax^1 \leq b$ and
$\{x\in\mathbb R^n: f(x) \leq f(x^1), Ax\leq b\}$ bounded. Then every accumulation point of the sequence
of serious iterates generated by the algorithm is a KKT-point of (\ref{program}).
\end{theorem}

\begin{proof}
By hypothesis $f$ is either lower-$C^2$ or upper-$C^2$ at every $x$, and in
consequence the modified downshift oracle is strong.  This is shown in much the same
was as in the proof of Theorem \ref{theorem1}.  Once this is shown,
invoke \cite[Theorem2]{noll} which proves the result.
\end{proof}

\subsection{Initialization of $\tau$}
Another important aspect is the
initialization of the proximity control parameter $\tau$. Unlike the stopping tests,
which are essentially scale-invariant, $\tau$ is a multiplier  which is
more delicate to adjust. What helps is that we are allowed a certain number
of heuristic operations on $\tau$ as long as we respect
certain rules.

Fixing $M_1 > 0$, we could increase
$\tau_k$ in the inner loop for heuristic reasons as long as $\tau_k \leq M_1$. However,
when this barrier is passed, we have to respect the rigorous rule, which says that $\tau_k$ is only
increased when $\widetilde{\rho}_k \geq \widetilde{\gamma}$.
For the outer loop we use  the same idea. Let $M_2 >0$ and
allow a finite number of heuristic corrections of $\tau_j^\sharp$ when passing from serious step
$x^j$ to $x^{j+1}$, authorized as long as  $\tau_j^\sharp \leq M_2$.
Since $\tau$ may decrease in the outer loop, it may happen
that  we get back below $M_2$, which allows to resume these
operations.

In order to exploit this, we propose the following
procedure to initialize $\tau$. Having started the first inner loop at
$\tau_1=1$, say, it may turn out that we have difficulties
finding a serious iterate because $\tau$ is way too small.
In that event  the inner loop based on the test $\widetilde{\rho}_k \geq \widetilde{\gamma}$
may decide that cutting planes alone give progress, and may
keep $\tau$ fixed, leading to a lengthy backtracking
based solely on cutting planes. Here we use the following heuristic to adjust
$\tau$ after $x^2$ has been found. Fixing the direction
$d = x^2 - x^1$ and choosing an exactness plane
$m_0(\cdot,x^1)$ at $x_1$ such that $m_0(x^2,x^1) =f(x^1) + g_0^\top(x^2-x^1) = f(x^1) + f^0(x^1,d)$, we
ask what parabola $t \mapsto f(x^1) + m_0(x^1+td,x^1)+ \frac{\tau}{2} \| td\|^2$
would have allowed to find $x^2$ at $t=1$ in a single step.
The answer is $\tau = -g_0^\top d / \|d\|^2$, and we use this value  to adjust
$\tau$ before the second inner loop. Naturally, this process can be repeated a finite number of times,
until the threshold $M_2$ is reached.


\section{Introduction}
For $i=1,2$, let $X_{i}$ be a noncompact hyperbolic Riemann orbisurface of finite volume $\vx(X_{i})$
with genus $g_{i}\geq 1$, and can be realized as the quotient space $\Gamma_{i}\backslash\mathbb{H}$,
where $\Gamma_{i}\subset \mathrm{PSL}_{2}(\mathbb{R})$ is a Fuchsian subgroup of the first kind acting
on the hyperbolic upper half-plane $\mathbb{H}$, via fractional linear transformations. Let $\mathcal{
E}_{i}$ and $\mathcal{P}_{i}$ denote the finite sets of elliptic fixed points and cusps of $\Gamma_{i}$,
respectively. Put $\overline{X}_{i}=X_{i}\cup \mathcal{P}_{i}$. Then, $\overline{X}_{i}$ admits the structure of
a Riemann surface. Now consider the complex surface $X=X_{1}\times X_{2}$, which admits the structure of a
noncompact K\"ahler-orbifold of dimension two. Put $\overline{X}=\overline{X}_{1}\times \overline{X}_{2}$.

\vspace{0.2cm}
For $i=1,2$, let $\hypi$ denote the (1,1)-form associated to hyperbolic metric, which is
the natural metric on $X_{i}$, and of constant negative curvature minus one. Now $\hypone +\hyptwo$
is the natural metric on $X$, and let $\hypvol$ denote the volume form associated to
$\hypone +\hyptwo$.

\vspace{0.2cm}
For $i=1,2$, the Riemann surface $\overline{X}_{i}$ is embedded in its Jacobian variety $\mathrm{Jac}(
\overline{X}_{i})$ via the Abel-Jacobi map. Then, the pull back of the flat Euclidean metric by the Abel-Jacobi map is called the
canonical metric, and the (1,1)-form associated to it is denoted by $\hatcani$. We denote its restriction
to $X_{i}$ by $\cani$. Now, $\canone+\cantwo$ defines a metric on $X$, which corresponds to the flat
Euclidean metric, and let $\canvol$ denote the volume form associated to $\canone+\cantwo$.

\vspace{0.2cm}
For $i=1,2$, let $\deli$ denote the hyperbolic Laplacian acting on smooth functions on $X_{i}$. The
hyperbolic heat kernel $\khypi(t;z_{i},w_{i})$ on $\mathbb{R}_{>0}\times X_{i}\times X_{i}$ is the unique
solution of the heat equation
\begin{align*}
\bigg(\deli + \frac{\partial}{\partial t}\bigg)\khypi(t;z_{i},w_{i}) =0,
\end{align*}
with the normalization condition
\begin{align*}
\lim_{t\rightarrow 0}\int_{X_{i}}\khypi(t;z_{i},w_{i})f(z_{i})\hypi(z_{i}) = f(w_{i}),
\end{align*}
for any fixed $w\in X_{i}$ and any smooth function $f$ on $X_{i}$. When $z_{i}=w_{i}$, for brevity of
notation, we denote the hyperbolic heat kernel by $\khypi(t;z_{i})$.

\vspace{0.3cm}\textbf{Main result}
With notation as above, for $z=(z_{1},z_{2})\in (X_{1}\backslash \mathcal{E}_{1})\times
(X_{2}\backslash \mathcal{E}_{2})$, we have the relation of differential forms
\begin{align*}
&g_{1}g_{2}\canvol(z)=\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{1})}\bigg)\cdot \bigg(\frac{1}{4\pi}+
\frac{1}{\vx(X_{2})}\bigg)\hypvol(z)+\frac{1}{2}\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{1})}\bigg)\times
\\&\bigg(\int_{0}^{\infty}\deltwo \khyptwo(t;z_{2}) dt\bigg)\hypvol(z)+
\frac{1}{2}\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{2})}\bigg)\cdot\bigg(\int_{0}^{\infty}\delone \khypone(t;z_{1}) dt\bigg)\hypvol(z)+\notag\\&
\frac{1}{4}\bigg(\int_{0}^{\infty}\delone \khypone(t;z_{1}) dt\bigg)\cdot\bigg(\int_{0}^{\infty}\deltwo \khyptwo(t;z_{2}) dt\bigg)\hypvol(z).
\end{align*}
The above relation, which we call the key-identity, relates the two natural metrics defined on a
K\"ahler-orbifold of dimension two. The key-identity is proved for compact hyperbolic Riemann surfaces,
by J.~Jorgenson and J.~Kramer in \cite{jk}. The same authors extended the key-identity to noncompact
hyperbolic Riemann surfaces of finite volume in \cite{bonn}. Following diferent methods, the
key-identity is extended to noncompact hyperbolic Riemann orbisurfaces in \cite{anilpaper}.
\paragraph{Arithmetic significance}
The key-identity is the most significant technical result of \cite{jk}, which transforms a
problem in Arakelov theory into that of hyperbolic geometry. The key-identity has enabled
J.~Jorgenson and J.~Kramer to derive optimal bounds for the canonical Green's function defined on a compact hyperbolic Riemann
surface $X$ in terms of invariants coming from the hyperbolic geometry of $X$.

\vspace{0.2cm}\noindent
Using the key-identity one can relate the holomorphic world of cusp forms with the $C^{\infty}$
world of M\"ass forms, via the spectral expansion of the hyperbolic heat kernel in terms
of M\"ass forms. In fact, J.~Jorgenson and J.~Kramer have derived a Rankin-Selberg $L$-function
relation relating the Fourier coefficients of cusp forms with those of M\"ass forms in \cite{bonn}.

\vspace{0.2cm}\noindent
Our main result is the first instance of an extension of the key-identity to higher dimensions,
relating the cusp forms of the group $\Gamma_{1}\times\Gamma_{2}$ with the M\"ass forms defined on
$X_{1}$ and $X_{2}$ via the spectral expansions of the hyperbolic heat kernels $\khypone(t;z_{1})$ and
$\khyptwo(t;z_{2})$, respectively.
{\small{\paragraph{Acknowledgements}
This article was realized during the author's graduate studies, which was completed under the
supervision of  J.~Kramer at Humboldt Universit\"at zu Berlin. The author would like to express his
gratitude to J.~Jorgenson and J.~Kramer for introducing him to the exciting area of heat kernels and
automorphic forms, and for generously discussing many new scientific ideas, which resulted in the
completion of this project.

The author would also like to extend his gratitude to N.~Walji, who through many interesting scientific
discussions has conveyed the importance of the key-identity. }}
\section{Background material}\label{section1}
For $i=1, 2$, let $\Gamma_{i} \subset \mathrm{PSL}_{2}(\mathbb{R})$ be a Fuchsian subgroup of the first kind acting by
fractional linear transformations on the upper half-plane $\mathbb{H}$. Let $X_{i}$ be the quotient space $\Gamma_{i}\backslash \mathbb{H}$, and let $g_{i}$
denote the genus of $X_{i}$. The quotient space $X_{i}$ admits the structure of a Riemann orbisurface.

\vspace{0.2cm}
Let $\mathcal{E}_{i}$ and $\mathcal{P}_{i}$ be the finite sets of elliptic fixed points and cusps of
$X_{i}$, respectively; put $\mathcal{S}_{i} = \mathcal{E}_{i}\cup\mathcal{P}_{i}$. For
$\mathfrak{e}_{i}\in \mathcal{E}_{i}$, let $m_{\mathfrak{e}_{i}}$ denote the order of $\mathfrak{e}_{i}$; for
$p_{i}\in \mathcal{P}_{i}$, put $m_{p_{i}}=\infty$; for $z_{i}\in X_{i}\backslash \mathcal{E}_{i}$, put $m_{z_{i}}=1.$ Let $\overline{X}_{i}$
denote $\overline{X}_{i}=X_{i}\cup\mathcal{P}_{i}.$

\vspace{0.2cm}
Locally, away from the elliptic fixed points and the cusps, we identify $\overline{X}_{i}$ with its
universal cover $\mathbb{H}$, and hence, denote the points on $\overline{X}_{i}\backslash
\mathcal{S}_{i}$ by the same letter as the points on $\mathbb{H}$.

\vspace{0.2cm}
The quotient space $\overline{X}_{i}$ admits the structure of a compact Riemann surface. We refer the
reader to Section 1.8 in $\cite{miyake}$, for the details regarding the structure of $\overline{X}_{i}$ as a compact Riemann surface.

\vspace{0.2cm}
Let $X$ denote the product of the Riemann orbisurfaces $X_{1}\times X_{2}$. Then, $X$ admits the
structure of a complex K\"ahler-orbifold of dimension two. The boundary of $X$ is given by
$\partial X=\big(X_{1}\times\mathcal{P}_{2}\big)\cup\big(X_{2}\times\mathcal{P}_{1}
\big)$, and the compactification of $X$ is given by $\overline{X}=\overline{X}_{1}\times\overline{X}_{2}$.

\paragraph{Hyperbolic metric}
For $i=1,2$, we denote the (1,1)-form corresponding to the hyperbolic metric of $X_{i}$, which is compatible with the complex structure on $X_{i}$
and has constant negative curvature equal to minus one, by $\hypi(z_{i})$. Locally, for
$z_{i}\in X_{i}\backslash \mathcal{E}_{i}$, it is given by
\begin{equation*}
 \hypi(z_{i})= \frac{i}{2}\cdot\frac{dz_{i}\wedge d\overline{z}_{i}}{{\Im(z_{i})}^{2}}.
\end{equation*}
From the above formula, it follows that the hyperbolic metric $\hypi(z_{i})$ is singular at the elliptic fixed points and at the cusps.

\vspace{0.2cm}
Let $\vx(X_{i})$ be the volume of $X_{i}$ with respect to the hyperbolic metric $\hypi(z_{i})$. It is given by the formula
\begin{equation*}
\vx(X_{i}) = 2\pi\bigg(2g_{i} -2 + |\mathcal{P}_{i}|+\sum_{\mathfrak{e}_{i} \in \mathcal{E}_{i}}\bigg(1-
\frac{1}{m_{\mathfrak{e}_{i}}}\bigg)\bigg).
\end{equation*}
We denote the (1,1)-form corresponding to the hyperbolic metric of $X$, which is compatible with the complex structure on $X$, by $\hyp(z)$
and the corresponding volume form by $\hypvol(z)$. Locally, for
$z=(z_{1},z_{2})\in (X_{1}\backslash \mathcal{E}_{1})\times(X_{2}\backslash \mathcal{E}_{2})$, it is given by
\begin{align*}
\hyp(z)= \hypone(z_{1})+\hyptwo(z_{2})=\frac{i}{2}\cdot\frac{dz_{1}\wedge d\overline{z}_{1}}{{\Im(z_{1})}^{2}}+\frac{i}{2}\cdot\frac{dz_{2}\wedge
d\overline{z}_{2}}{{\Im(z_{2})}^{2}},
\end{align*}
and the corresponding volume form is given by
\begin{align*}
\hypvol(z)=\hypone(z_{i})\wedge\hyptwo(z_{2})=-\frac{dz_{1}\wedge d\overline{z}_{1}\wedge dz_{2}\wedge d\overline{z}_{2}}{2\Im(z_{1})^{2}\Im(z_{2})^{2}}.
\end{align*}
\paragraph{Canonical metric}
For $i=1,2$, let $S_{2}(\Gamma_{i})$ denote the $\mathbb{C}$-vector space of cusp forms of
weight 2 with respect to $\Gamma_{i}$ equipped with the Petersson inner-product. Let
$\lbrace f_{1}^{i},\ldots,f_{g_{i}}^{i}\rbrace $ denote an orthonormal basis of $S_{2}(\Gamma_{i})$
with respect to the Petersson inner-product. Then, the (1,1)-form $\cani(z_{i})$ corresponding to the
canonical metric of $X_{i}$ is given by
\begin{equation*}
\cani(z_{i})=\frac{i}{2g_{i}} \sum_{j=1}^{g_{i}}\left|f_{j}^{i}(z_{i})\right|^{2}dz_{i}\wedge d\overline{z}_{i}.
\end{equation*}
The canonical metric $\cani(z)$ remains smooth at the elliptic fixed points and at the cusps, and measures
the volume of $X$ to be one.

\vspace{0.2cm}
Let $\Omega_{\overline{X}_{i}}^{1}$ denote the cotangent bundle of holomorphic differential forms of degree
one on $\overline{X}_{i}$. Recall that for each $f^{i}\in S_{2}(\Gamma_{i})$, $f^{i}(z_{i})dz_{i}$
defines a holomorphic differential form of degree one on $\overline{X}_{i}$, and every holomorphic
differential form of degree one on $\overline{X}_{i}$ comes from a weight 2 cusp form. So
$\lbrace f_{1}^{i},\ldots,f_{g_{i}}^{i}\rbrace $ the orthonormal basis of $S_{2}(\Gamma_{i})$ with
respect to the Petersson inner-product gives us an orthonormal basis $\lbrace f_{1}^{i}dz_{i},\ldots,f_{g_{i}}^{i}dz_{i}\rbrace $ of $H^{0}(\overline{X}_{i},\Omega_{\overline{X}_{i}}^{1})$
endowed with the $L^{2}$-inner product given by
\begin{align*}
\langle\alpha^{i},\beta^{i} \rangle=\frac{i}{2}\int_{\overline{X}}\alpha^{i}(z_{i})\overline{\beta^{i}(z_{i})},
\end{align*}
where $\alpha^{i},\beta^{i}\in\Omega_{\overline{X}_{i}}^{1}$.

\vspace{0.2cm}
Let $\Omega_{\overline{X}}^{2}$ denote the space of holomorphic differential forms of degree 2, and let $\lbrace \omega_{1}, \ldots, \omega_{n}
\rbrace $ denote an orthonormal basis of $H^{0}(\overline{X},\Omega_{\overline{X}}^{2})$ endowed with the $L^{2}$-inner product given by
\begin{align*}
\langle\alpha,\beta \rangle=-\frac{1}{4}\int_{\overline{X}}\alpha(z)\overline{\beta(z)},
\end{align*}
where $n$ denotes the dimension of $H^{0}(\overline{X},\Omega_{\overline{X}}^{2})$ as a vector space over $\mathbb{C}$, and
$\alpha,\beta\in\Omega_{\overline{X}}^{2}$. Then, the canonical volume form on $X$ is defined as
\begin{align*}
\canvol(z)=-\frac{1}{4n}\sum_{j=1}^{n}\omega_{j}(z)\wedge\overline{\omega_{j}(z)}.
\end{align*}
The canonical volume form $\canvol(z)$ measures the volume of $X$ to be one.
\paragraph{Hyperbolic Laplacian}
For $i=1,2$, the hyperbolic Laplacian acting on smooth functions defined on $X_{i}$ is given by
\begin{align*}
\deli =-y_{i}^{2}\bigg(\frac{\partial^{2}}{\partial x_{i}^{2}}+\frac{\partial^{2}}{\partial y_{i}^{2}}\bigg),
\end{align*}
and the hyperbolic Laplacian acting on smooth functions defined on $X$ is given by
\begin{align*}
\del=\delone+\deltwo= -y_{1}^{2}\bigg(\frac{\partial^{2}}{\partial x_{1}^{2}}+\frac{\partial^{2}}{\partial y_{1}^{2}}\bigg)-
y_{2}^{2}\bigg(\frac{\partial^{2}}{\partial x_{2}^{2}}+\frac{\partial^{2}}{\partial y_{2}^{2}}\bigg).
\end{align*}
\paragraph{Hyperbolic heat kernels}
For $t \in \mathbb{R}_{> 0}$  and $z, w \in \mathbb{H}$, let $K_{\mathbb{H}}(t;z,w)$ denote the hyperbolic heat kernel on $\mathbb{R}_{> 0}
\times\mathbb{H}\times\mathbb{H}$.

\vspace{0.2cm}
For $i=1,2$, $t \in  \mathbb{R}_{> 0}$ and $z_{i}, w_{i} \in X_{i}$, the hyperbolic heat kernel $\khypi(t;z_{i},w_{i})$ on
$\mathbb{R}_{> 0}\times X_{i}\times X_{i}$ is defined as
\begin{equation}\label{defnkhyp}
\khypi(t;z_{i},w_{i})=\sum_{\gamma_{i}\in\Gamma_{i}}K_{\mathbb{H}}(t;z_{i},\gamma_{i} w_{i}).
\end{equation}
For $z_{i},w_{i}\in X_{i}$, the hyperbolic heat kernel $\khypi(t;z_{i},w_{i})$ satisfies the differential equation
\begin{align}\label{diffeqnkhyp}
\bigg(\Delta_{\text{hyp},z}^{i} + \frac{\partial}{\partial t}\bigg)\khypi(t;z,w) &=0,
\end{align}
Furthermore, for a fixed $w_{i}\in X_{i}$, and any smooth function $f^{i}$ on $X_{i}$, the hyperbolic heat kernel $\khypi(t;z_{i},w_{i})$
satisfies the equation
\begin{align}\label{normcondkhyp}
\lim_{t\rightarrow 0}\int_{X_{i}}\khypi(t;z_{i},w_{i})f^{i}(z)\hypi(z_{i}) &= f^{i}(w_{i}).
\end{align}
To simplify notation, we write $\khypi(t;z_{i})$ instead of $\khypi(t;z_{i},z_{i})$, when $z_{i}=w_{i}$.
\paragraph{Key-identity on $X_{i}$}
For $i=1,2$, $z_{i}\in X_{i} \backslash \mathcal{E}_{i}$, we have the relation of differential forms
\begin{align}\label{keyidentityrs}
&g_{i}\cani(z_{i}) =\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{i})}\bigg)\hypi(z_{i})+ \frac{1}{2}\bigg(\int_{0}^{\infty}\deli \khypi(t;z_{i}) dt\bigg)
\hypi(z_{i}).
\end{align}
This relation has been established as Theorem 3.4 in \cite{jk}, when $X_{i}$ is
compact. The proof given in \cite{jk} applies to our case where $X$ does admit elliptic fixed points and
cusps, as long as $z_{i}\in X_{i}\backslash \mathcal{E}_{i}$.

\vspace{0.2cm}
In \cite{anilpaper}, the above identity is extended to elliptic fixed points and cusps at the level of
currents.
\section{Key-identity on $X$}\label{section2}
\begin{lem}\label{lem1}
The dimension of $H^{0}(\overline{X},\Omega_{\overline{X}}^{2})$ as a vector space over $\mathbb{C}$ is $g_{1}g_{2}$, and
for $z=(z_{1},z_{2})\in X$, the canonical volume form is given by
\begin{align}\label{lem1eqn}
\canvol(z)=\canone(z_{1})\wedge\cantwo(z_{2})=-\frac{1}{4g_{1}g_{2}}\sum_{j=1}^{g_{1}}\sum_{k=1}^{g_{2}}|f^{1}_{j}(z_{1})|^{2}\cdot|f^{2}_{k}(z_{2})|^{2}
dz_{1}\wedge d\overline{z}_{1}\wedge dz_{2}\wedge d\overline{z}_{2}.
\end{align}
\begin{proof}
From K\"unneth theorem of algebraic geometry, we have
\begin{align*}
H^{0}\big(\overline{X},\Omega_{\overline{X}}^{2}\big)=H^{0}\big(\overline{X}_{1},\Omega_{\overline{X}_{1}}^{1}\big)\otimes H^{0}\big(\overline{X}_{2},
\Omega_{\overline{X}_{2}}^{1}\big).
\end{align*}
So from the isomorphism $S_{2}(\Gamma_{i})\cong H^{0}(\overline{X}_{i},\Omega_{\overline{X}_{i}}^{1})$, it follows that the
set
\begin{align*}
\big\lbrace f^{1}_{j}f^{2}_{k} \big\rbrace_{\substack{1\leq j\leq g_{1}\\1\leq k\leq g_{2}}}
\end{align*}
forms an orthonormal basis of $H^{0}(\overline{X},\Omega_{\overline{X}}^{2})$, which implies that
\begin{align*}
\canvol(z)=-\frac{1}{4g_{1}g_{2}}\sum_{j=1}^{g_{1}}\sum_{k=1}^{g_{2}}|f^{1}_{j}(z_{1})|^{2}\cdot |f^{2}_{k}(z_{2})|^{2}
dz_{1}\wedge d\overline{z}_{1}\wedge dz_{2}\wedge d\overline{z}_{2}.
\end{align*}
Furthermore, a direct calculation, shows that $\canone(z_{1})\wedge\cantwo (z_{2})=\canvol(z)$, which completes the proof of the lemma.
\end{proof}
\end{lem}
\begin{thm}\label{thm2}
For $z=(z_{1},z_{2})\in (X_{1}\backslash \mathcal{E}_{1})\times (X_{2}\backslash \mathcal{E}_{2})$, we have the relation of differential forms
\begin{align*}
&g_{1}g_{2}\canvol(z)=\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{1})}\bigg)\cdot \bigg(\frac{1}{4\pi}+
\frac{1}{\vx(X_{2})}\bigg)\hypvol(z)+\frac{1}{2}\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{1})}\bigg)\times
\\&\bigg(\int_{0}^{\infty}\deltwo \khyptwo(t;z_{2}) dt\bigg)\hypvol(z)+
\frac{1}{2}\bigg(\frac{1}{4\pi}+ \frac{1}{\vx(X_{2})}\bigg)\cdot\bigg(\int_{0}^{\infty}\delone \khypone(t;z_{1}) dt\bigg)\hypvol(z)+\notag\\&
\frac{1}{4}\bigg(\int_{0}^{\infty}\delone \khypone(t;z_{1}) dt\bigg)\cdot\bigg(\int_{0}^{\infty}\deltwo \khyptwo(t;z_{2}) dt\bigg)\hypvol(z).
\end{align*}
\begin{proof}
The proof of the theorem follows from combining equations \eqref{keyidentityrs} and \eqref{lem1eqn}.
\end{proof}
\end{thm}