$\displaystyle\leq\frac{8D_{X}\left(\sum\limits_{i=0}^{m+1}z_{i}\|B_{i}\|D_{U_{i}}\right)}{3\sqrt{t+1}}+\frac{4D_{X}\sum\limits_{i=0}^{m+1}\|B_{i}\|^{2}D_{U_{i}}^{2}}{3M_{B,U}t(t+1)}+\frac{8M_{B,U}D_{X}}{9\sqrt{t+1}}$
$\displaystyle\quad+\frac{4M_{B,U}D_{X}}{3(t+1)\sqrt{t}}+\frac{2D_{X}\sum\limits_{i=0}^{m+1}\|B_{i}\|^{2}D^{2}_{U_{i}}}{3t^{2}(t+1)\sqrt{t}M_{B,U}}+\frac{18M_{B,U}D_{X}{V}}{\sqrt{t+1}}+\frac{D_{X}\left(\sum\limits_{i=0}^{m+1}z_{i}\|B_{i}\|D_{U_{i}}\right)}{\sqrt{t}},$
$\displaystyle\|H(x_{T},{f}^{*})\|_{\infty}$
$\displaystyle\leq\frac{8D_{X}\left(\max\limits_{i=0,\cdots,m+1}\|B_{i}\|D_{U_{i}}\right)}{3\sqrt{t+1}}+\frac{4D_{X}\sum\limits_{i=0}^{m+1}\|B_{i}\|^{2}D_{U_{i}}^{2}}{3M_{B,U}t(t+1)}+\frac{8M_{B,U}D_{X}}{9\sqrt{t+1}}$
$\displaystyle\quad+\frac{4M_{B,U}D_{X}}{3(t+1)\sqrt{t}}+\frac{2D_{X}\sum\limits_{i=0}^{m}\|B_{i}\|^{2}D^{2}_{U_{i}}}{3t^{2}(t+1)\sqrt{t}M_{B,U}}+\frac{18M_{B,U}D_{X}{V^{\prime}}}{\sqrt{t+1}}+\frac{D_{X}\left(\max\limits_{i=0\cdots,m+1}\|B_{i}\|D_{U_{i}}\right)}{\sqrt{t}}.$

##  7 Convergence Analysis of LCG

[Lemma 2.1] At iteration $k$, if Algorithm 1 does not terminate, then
$L_{k}>0$. Moreover, the sequence of the level estimates satisfies
$l_{1}<\cdots<l_{k}<l_{k+1}<\cdots\leq f^{*}$, $k\geq 1$. Consequently,
$\phi(l_{k+1})\geq\phi(l_{k})\geq\cdots\geq\phi(f^{*})=0$.

###### Proof.

Proof. We first show that at iteration $k$, if the algorithm does not
terminate, then $L_{k}>0$. Indeed, if, on the opposite, $L_{k}\leq 0$, since
CGO stops at $U_{k}-L_{k}\leq(1-\mu)\epsilon$, then
$U_{k}\leq(1-\mu)\epsilon+L_{k}\leq(1-\mu)\epsilon\leq\epsilon$, leading to
the termination of the algorithm. Therefore, together by the requirement that
$\gamma_{k}>0$ returned by CGO, at each update of $l$, we have
$l_{k+1}-l_{k}\geq\frac{1}{\gamma_{k}}L_{k}>0.$ In addition, noting that
$\mathcal{L}_{k}(l_{k+1})=0$ by the origin of $l_{k+1}$ in (2.3), and that
$\phi(l_{k+1})\geq\mathcal{L}_{k}(l_{k+1})$ since $\mathcal{L}$ underestimates
$\phi$, we have $\phi(l_{k+1})\geq\mathcal{L}_{k}(l_{k+1})=0=\phi(f^{*})$,
which, in view of the fact that $\phi$ is nonincreasing, implies that
$l_{k+1}\leq f^{*}$, $k\geq 1$. By the definition of $l_{1}$, we have
$l_{1}\leq f^{*}$. Finally by the monotonicity non-increasing property of
$\phi$ and $\phi(f^{*})$, we have
$\phi(l_{k+1})\geq\phi(l_{k})\geq\cdots\geq\phi(f^{*})=0$. ∎

[Theorem 2.1] For all $k\geq 1$, we have

$U_{k}\leq\left(f^{*}-l_{1}\right)\frac{1}{\mu}\left(\frac{1}{2\mu}\right)^{k},$
(7.1)

where $\mu\in(\frac{1}{2},1)$, $l_{1}$ is the initial estimate of the optimal
value of (1.1) such that $l_{1}\leq f^{*}$. Moreover, given precision
$\epsilon$, at the termination of LCG when $U_{k}\leq\epsilon$, the algorithm
yields an $\epsilon$-optimal and $\epsilon$-feasible solution $x_{k}$ of
problem (1.1).

###### Proof.

Proof. By the linearity of $\mathcal{L}_{k}(\cdot)$ and the relation that
$l_{k-1}<l_{k}<l_{k+1}$ according to Lemma 2.1, we have

$\frac{\mathcal{L}_{k}(l_{k-1})-\mathcal{L}_{k}(l_{k})}{l_{k}-l_{k-1}}=\frac{\mathcal{L}_{k}(l_{k})-\mathcal{L}_{k}(l_{k+1})}{l_{k+1}-l_{k}},$

which together with the fact $\mathcal{L}_{k}(l_{k+1})=0$ and the simple
relation $a+b\geq 2\sqrt{ab},\ a,b\in\mathbb{R}^{+}$ imply that

$\displaystyle(l_{k+1}-l_{k})\mathcal{L}_{k}(l_{k-1})$
$\displaystyle\geq(l_{k+1}-l_{k}+l_{k}-l_{k-1})\mathcal{L}_{k}(l_{k})$
$\displaystyle\geq
2\sqrt{l_{k+1}-l_{k}}\sqrt{l_{k}-l_{k-1}}\mathcal{L}_{k}(l_{k}).$

Rearranging the terms, we obtain

$\frac{\mathcal{L}_{k}(l_{k-1})}{\sqrt{l_{k}-l_{k-1}}}\geq\frac{2\mathcal{L}_{k}(l_{k})}{\sqrt{l_{k+1}-l_{k}}}.$
(7.2)

Observe that ${U}_{k}-{L}_{k}\leq(1-\mu)\epsilon$ and $U_{k}>\epsilon$ when
the algorithm does not terminate at iteration $k$. Therefore, we have
${U}_{k}-{L}_{k}\leq(1-\mu){U}_{k}$, and thus ${L}_{k}/{U}_{k}\geq\mu$. Using
this observation and the fact $\mathcal{L}_{k}(l_{k})=L_{k}$, we obtain
$\mathcal{L}_{k}(l_{k})\geq\mu{U}_{k}$. Note also
${U}_{k-1}\geq\phi(l_{k-1})\geq\mathcal{L}_{k}(l_{k-1})$. Using this bound and
the one in (7.2), we have

$\frac{{U}_{k-1}}{\sqrt{l_{k}-l_{k-1}}}\geq\frac{2\mu{U}_{k}}{\sqrt{l_{k+1}-l_{k}}}.$
(7.3)

Applying the above relation recursively and the facts that
${U}_{1}\leq\frac{1}{\mu}{L}_{1}$, ${L}_{1}\leq\phi(l_{1})$,
$l_{k+1}-l_{k}\leq f^{*}-l_{1}$ yields

$\displaystyle\begin{split}{U}_{k}&\leq\frac{1}{2\mu}\sqrt{\frac{l_{k+1}-l_{k}}{l_{k}-l_{k-1}}}\
{U}_{k-1}\\\
&\leq\left(\frac{1}{2\mu}\right)^{k-1}\sqrt{\frac{l_{k+1}-l_{k}}{l_{2}-l_{1}}}\
{U}_{1}\\\
&\leq\frac{1}{\mu}\left(\frac{1}{2\mu}\right)^{k-1}\sqrt{(f^{*}-l_{1})\phi(l_{1})}\sqrt{\frac{{L}_{1}}{l_{2}-l_{1}}}.\end{split}$
(7.4)

Note also it can be easily verified that: $\phi(l)-\phi(l+\delta)\leq\delta,\
l\in\mathbb{R},$ for any $\delta\geq 0$ (same for $\mathcal{L}_{1}(\cdot)$),
which leads to $\phi(l_{1})\leq f^{*}-l_{1}$ and $\mathcal{L}_{1}(l_{1})\leq
l_{2}-l_{1}$ as $\mathcal{L}_{1}(l_{2})=0$ and $\phi(f^{*})=0$. Consequently,
following from the relation in (7.4), we attain

${U}_{k}\leq\frac{1}{\mu}\left(\frac{1}{2\mu}\right)^{k-1}(f^{*}-l_{1}).$

At the termination of LCG when $U_{k}\leq\epsilon$, the algorithm yields an
$\epsilon$-optimal and $\epsilon$-feasible solution $x_{k}$ of problem (1.1)
since $f(x_{k})-f^{*}\leq f(x_{k})-l_{k}\leq U_{k}\leq\epsilon$ and
$\max\limits_{i=1,\cdots,m}\\{h_{i}(x_{k})\\}\leq U_{k}\leq\epsilon$. ∎

[Lemma 2.3] When LCG does not terminate at iteration $k$, the output
$(\gamma_{k},L_{k},U_{k})$ of CGO satisfies (2.4)-(2.6).

###### Proof.

Proof. First define the sequence $\\{\beta^{t}\\}$, across inner iteration
(CGO iteration) $t\geq 1$ as follow:
$\beta^{t}:=(\beta^{t}_{1},\cdots,\beta^{t}_{t})$, where
$\beta^{t}_{j}=\begin{cases}\alpha_{t},\ \text{if}\ j=t,\\\
(1-\alpha_{t})\beta^{t-1}_{j},\ \text{if}\ j\neq t,\end{cases}$ with
$\beta^{1}_{1}=\alpha_{1}$. Denote $r_{j}:=(r_{j,0},\cdots,r_{j,m})$, where
$r_{j,i}$ is the $i$-th element of vector $r_{j}$ at iteration $j$, $j\leq t$.
According to Algorithm 2, $\underline{h}_{t}(x;l)$ can be explicitly written
as:

$\underline{h}_{t}(x;l)=-\gamma_{t}l+\sum\limits_{j=1}^{t}\beta^{t}_{j}\left[r_{j,0}\ell_{f}(x_{j-1},x)+\sum\limits_{i=1}^{m}r_{j,i}\ell_{h_{i}}(x_{j-1},x)\right],$
(7.5)

where $\gamma_{t}=\sum\limits_{j=1}^{t}\beta^{t}_{j}r_{j,0}$ and we have
$z_{t,i}=\sum\limits_{j=1}^{t}\beta^{t}_{j}r_{j,i}$, $z_{t,i}$ is the $i$-th
element of vector $z_{t}$ at iteration $t$.

At each CGO iteration under outer iteration $k$, by the definition in (2.2),
we have $\mathcal{L}_{t}(l)=L_{t}-\gamma_{t}(l-l_{k})$. Arranging the terms
and using the relation in (2.16) and (7.5), for each $l\in\mathbb{R}$, we have

$\displaystyle\mathcal{L}_{t}(l)$
$\displaystyle=-\gamma_{t}l+(L_{t}+\gamma_{t}l_{k})$
$\displaystyle=-\gamma_{t}l+\min\limits_{x\in
X}\underline{h}_{t}(x;l_{k})+\gamma_{t}l_{k}$ $\displaystyle=\min\limits_{x\in
X}\underline{h}_{t}(x;l).$

Moreover, according to Lemma 2.2, it can be shown that
$\underline{h}_{t}(x;l)\leq\gamma_{t}[f(x)-l]+\langle
h(x),z_{t}\rangle,\forall x\in X$. Hence,
$\mathcal{L}_{t}(l)=\min\limits_{x\in
X}\underline{h}_{t}(x;l)\leq\min\limits_{x\in X}\gamma_{t}[f(x)-l]+\langle
h(x),z_{t}\rangle\leq\min\limits_{x\in X}\max\limits_{(\gamma,z)\in
Z}\gamma[f(x)-l]+\langle h(x),z\rangle\equiv\phi(l)$. Immediately, we obtain
the relation in (2.6). In view of Lemma 2.2 and the relation in (2.6), for a
given level estimate $l\in\mathbb{R}$, $L_{k},U_{k}$ are the lower bound and
upper bound of $\phi(l)$, respectively. Therefore, (2.5) is satisfied.

Now, we show (2.4). By (7.5), we have

$\mathcal{L}_{t}(l)=-\gamma_{t}l+\min\limits_{x\in
X}\sum\limits_{j=1}^{t}\beta^{t}_{j}\left[r_{j,0}\ell_{f}(x_{j-1},x)+\sum\limits_{i=1}^{m}r_{j,i}\ell_{h_{i}}(x_{j-1},x)\right].$

In the case where LCG is not terminated at outer iteration $k$, suppose CGO
runs $t(k)$ iterations. According to Lemma 2.1, it produces a lower bound such
that ${L}_{t(k)}>0$. Here $\gamma_{k}\equiv\gamma_{t(k)},z_{k}\equiv
z_{t(k)},L_{k}\equiv L_{t(k)}$ and
$\mathcal{L}_{k}(l_{k})\equiv\mathcal{L}_{t(k)}(l_{k})$. If $\gamma_{k}=0$,
recall that $\gamma_{k}=\sum\limits_{j=1}^{t(k)}\beta^{t}_{j}r_{j,0}$, then we
must have $r_{j,0}=0,\forall j\leq t(k)$. This implies that
$L_{k}=\mathcal{L}_{k}(l_{k})=\min\limits_{x\in
X}\sum\limits_{j=1}^{t(k)}\beta^{t(k)}_{j}\left[\sum\limits_{i=1}^{m}r_{j,i}\ell_{h_{i}}(x_{j-1},x)\right]\leq\min\limits_{x\in
X}\ \langle z_{k},h(x)\rangle\leq 0$, which leads to contradiction. This shows
that CGO returns $\gamma_{k}$ such that $\gamma_{k}>0$. ∎

###### Corollary 7.1

Suppose the algorithmic parameters of CGO are set to (2.22). Then for any
$t\geq 1$ and $\forall w\in(X,Z)$,

$\displaystyle Q_{t}(w_{t},w)$
$\displaystyle\leq\frac{2z^{\top}L_{\bar{h}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right],$
$\displaystyle f(x_{t})-f^{*}$
$\displaystyle\leq\frac{2\max\limits_{i=1,\cdots,{m}+1}L_{\bar{h}_{i}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right],$
$\displaystyle\|{h}(x_{t})\|_{\infty}$
$\displaystyle\leq\frac{2\max\limits_{i=1,\cdots,{m}+1}L_{\bar{h}_{i}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right].$

###### Proof.

Proof. The convergence analysis on the gap function $Q_{t}(w_{t},w)$ is
similar to the one on the general case when treating $\bar{f}(\cdot)=0$ (see
Theorem 2.2). We conclude that

$Q_{t}(w_{t},w)\leq\frac{2z^{\top}L_{\bar{h}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right],\forall
w:=(x,z)\in X\times Z.$

Now we analyze the bound of $\|\bar{h}(x_{t};{f}^{*})\|_{\infty}$, thus the
bounds of $f(x_{t})-f^{*}$ and of $\|{h}(x_{t})\|_{*}$. Suppose there exists
at least one element of $\bar{h}(x_{t};{f}^{*})$ is positive, otherwise, we
arrive trivially at $\|\bar{h}(x_{t};{f}^{*})\|_{*}\leq 0$. Define
$w^{\prime}:=(x^{*},z^{\prime})$, where $x^{*}$ is the optimal primal
solution. $z^{\prime}$ is defined as follows: $z^{\prime}\in{Z}$,
$z^{\prime}_{j}=1$ if $j$ is one of the indices such that
$j\in\operatornamewithlimits{argmax}\limits_{i=1,\cdots,{m}}\bar{h}_{i}(x_{t};{f}^{*})$
and $z^{\prime}_{i}=0$ otherwise. By the definition of $z^{\prime}$ and the
relation
$\underline{h}_{t}(x^{*};f^{*})\leq\langle\bar{h}(x^{*};f^{*}),z_{t}\rangle\leq
0$, we have

$\displaystyle\begin{split}Q_{t}(w_{t},w^{\prime})&=\langle\bar{h}(x_{t};f^{*}),{z^{\prime}}\rangle-\underline{h}_{t}(x^{*};f^{*})\\\
&\geq\|\bar{h}(x_{t};f^{*})\|_{\infty}.\end{split}$ (7.6)

Note also,

$\displaystyle\begin{split}\|\bar{h}(x_{t};f^{*})\|_{\infty}=\max\\{f(x_{t})-f^{*},h(x_{t})\\}\end{split}$

Then we have $\forall w\in(X,Z)$,

$\displaystyle f(x_{t})-f^{*}$
$\displaystyle\leq\frac{2\max\limits_{i=1,\cdots,{m}+1}L_{\bar{h}_{i}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right],$
$\displaystyle\|{h}(x_{t})\|_{\infty}$
$\displaystyle\leq\frac{2\max\limits_{i=1,\cdots,{m}+1}L_{\bar{h}_{i}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right].$

∎

[Theorem 2.3] Suppose that the algorithmic parameters of CGO are set to
(2.22). Then the total number of CGO iterations required to find an
$\epsilon$-solution $\bar{x}\in X$ of (1.1) can be bounded by
$\mathcal{O}\left(\frac{1}{\epsilon^{2}}\log(\frac{1}{\epsilon})\right)$.

###### Proof.

Proof. Using the result in Corollary 7.1 and the fact that
$U_{t}-L_{t}=\max\limits_{w\in X\times Z}Q_{t}(w_{t},w)$, we immediately
obtain

$U_{t}-L_{t}\leq\frac{2\max\limits_{i=1,\cdots,{m}+1}L_{\bar{h}_{i}}D_{X}^{2}}{t+1}+\frac{\bar{M}D_{X}}{\sqrt{t+1}}\left[18{\bar{V}}+\frac{7}{6}\right].$

Consequently, given precision $\epsilon>0$, to attain
$U_{k}-L_{k}\leq\epsilon$ at each call of CGO, the number of iterations is
bounded by $\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$. Furthermore, in
view of Theorem 2.1, the required number of outer loop iterations to obtain
$U_{k}\leq\epsilon$ and thus $f(x_{k})-f^{*}\leq\epsilon$,
$\|{h}(x_{k})\|_{\infty}\leq\epsilon$ is bounded by
$\mathcal{O}\left(\log\frac{1}{\epsilon}\right)$. Combining these two results,
the overall iteration complexity of LCG solving the convex constrained problem
(1.1) is
$\mathcal{O}\left(\frac{1}{\epsilon^{2}}\log(\frac{1}{\epsilon})\right)$. ∎

##  8 Modified Level Conditional Gradient Method

In this section, we focus on the modified version of LCG (MLCG), which
generates a sequence of decreasing level estimates that approximate from above
the optimal value of the problem. More specifically, we present the
algorithmic framework of the MLCG method and convergence analysis of the outer
loop. Remarkably, CGO requires no change in MLCG and remains as what it is in
LCG.

To approximate the optimal value $f^{*}$ by a sequence of decreasing level
estimate from above, the original LCG (Algorithm 1, Section 2) mainly takes
changes in the following steps: (1) In the initialization step, $l_{1}$ is
required to overestimate $f^{*}$. One plausible option is letting
$l_{1}=f(x_{0}),\ \operatornamewithlimits{s.t.}x_{0}\in X,h_{i}(x_{0})\leq
0,i=1,\cdots,m$; (2) The update rule of the level estimate is changed to
$l_{k+1}=l_{k}+U_{k}$; (3) The algorithm terminal condition is changed to
$L_{k}\geq-\epsilon\tilde{\kappa}$. Here $\tilde{\kappa}$ is a lower
approximation of the condition number $\kappa$, where

$\kappa:=-\frac{\phi(l_{1})}{l_{1}-f^{*}}.$

It can be easily verified that $\kappa\leq 1$. We can choose
$\tilde{\kappa}=-\frac{U_{1}}{l_{1}-\tilde{f}}$, where
$\tilde{f}:=\min\\{f(x_{0})+\langle\nabla f(x_{0}),x-x_{0}\rangle:x\in X\\}$.
In this way, $\tilde{f}\leq f^{*}$ and $\tilde{\kappa}\leq\kappa$. Similar to
(Lin et al. 2018), the outer loop iteration complexity relies on $\kappa$ and
we will demonstrate later how the terminal condition
$L_{k}\geq-\epsilon\tilde{\kappa}$ implies the convergence of the outer loop.
The MLCG method is summarized in Algorithm 6.

Algorithm 6 Modified Level Conditional Gradient Method (MLCG)

1: Inputs: $\epsilon>0,\mu\in(0,1)$.

2:Initialization: $x_{0}\in X,h_{i}(x_{0})\leq 0,i=1,\cdots,m$,
$l_{1}=f(x_{0})$.

3:for $k=1,2,\ldots$ do

4: Call CGO with input $l_{k}$ and obtain approximate solutions
$(x_{k};(\gamma_{k},z_{k}))\in X\times Z$, lower bound $L_{k}$, upper bound
$U_{k}$ and if $k=1$, obtain $\tilde{\kappa}=-\frac{U_{1}}{l_{1}-\tilde{f}}$
such that $U_{k}-L_{k}\leq(1-\mu)\tilde{\kappa}\epsilon$.

5: if $L_{k}\geq-\epsilon\tilde{\kappa}$ then

6: Terminate and return $x_{k}$.

7: end if

8: $l_{k+1}=l_{k}+U_{k}$.

9:end for

###### Remark 8.1

There is one edge case such that $l_{1}=f^{*}$ leading to termination of the
algorithm at iteration $k=1$, thus we will not consider this situation in the
convergence analysis. In this case, $U_{1}\geq\phi(l_{1})=\phi(f^{*})=0$. Let
$\tilde{\kappa}=\epsilon$ (instead of $-\frac{U_{1}}{l_{1}-\tilde{f}}$). In
view of CGO terminal condition, we have $L_{1}\geq
U_{1}-(1-\mu)\tilde{\kappa}\epsilon\geq-(1-\mu)\tilde{\kappa}\epsilon\geq-\tilde{\kappa}\epsilon$
and the algorithm terminates. Since $l_{1}=f^{*}$, the condition number
$\kappa$ does not exist. In fact, the algorithm terminates at $k=1$, thus the
iteration complexity in this case will not be affected by $\kappa$.

###  8.1 Outer Loop Iteration Complexity of MLCG

We start with several lemmas that are of important use in the outer loop
convergence analysis.

###### Lemma 8.1

When MLCG is not terminated at iteration $k$ ($k\geq 1$), then $U_{k}\leq\mu
L_{k}$.

###### Proof.

Proof. We first demonstrate that $U_{k}\geq 0$ then the algorithm terminates
at iteration $k$. Indeed, at $k>1$, if $U_{k}\geq 0$, then by the stopping
criteria of CGO, $L_{k}\geq
U_{k}-(1-\mu)\tilde{\kappa}\epsilon\geq-(1-\mu)\tilde{\kappa}\epsilon\geq-\tilde{\kappa}\epsilon$.
Consequently, the algorithm terminates. At iteration $k$, since the algorithm
is not terminated, then $L_{k}<-\epsilon\tilde{\kappa}$. By the stopping
criteria of CGO such as $U_{k}-L_{k}\leq(1-\mu)\tilde{\kappa}\epsilon$, we
have
$U_{k}-L_{k}\leq(1-\mu)\tilde{\kappa}(-L_{k}/\tilde{\kappa})=(1-\mu)(-L_{k})$.
Rearranging the terms in the above inequality, we arrive at $U_{k}\leq\mu
L_{k}$. ∎

###### Lemma 8.2

$l_{1}>\cdots>l_{k}>\cdots\geq f^{*}$.

###### Proof.

Proof. We have discussed the case when $l_{1}=f^{*}$ in Remark 8.1. We will
focus on the case where $l_{1}>f^{*}$. We show $l_{k+1}-f^{*}\geq 0$ by
induction. Suppose $l_{k}-f^{*}\geq 0$, then

$\displaystyle l_{k+1}-f^{*}$ $\displaystyle=l_{k}+U_{k}-f^{*}$
$\displaystyle\geq l_{k}+\phi(l_{k})-f^{*}$ $\displaystyle\geq
l_{k}-f^{*}-(l_{k}-f^{*})$ $\displaystyle=0.$

where the last inequality is due to $\phi(f^{*})-\phi(l_{k})\leq l_{k}-f^{*}$
with $l_{k}-f^{*}\geq 0$ (induction assumption) and $\phi(f^{*})=0$. Next, we
show that $l_{k+1}<l_{k}$. By Lemma 8.1, we have $U_{k}\leq\mu L_{k}<0$ when
the algorithm does not terminate, then $l_{k+1}-l_{k}=U_{k}<0$. ∎

The theorem below shows the outer iteration complexity of MLCG and
demonstrates that when it terminates it outputs an $\epsilon$-optimal and
$\epsilon$-feasible solution.

###### Theorem 8.1

For $k\geq 1$, Algorithm 6 generates $l_{k}$ that satisfies

$l_{k}-f^{*}\leq(1-\kappa\mu)^{k-1}(l_{1}-f^{*}),$

where $\mu\in(0,1),\kappa\in(0,1]$ and $l_{1}$ is the initial level estimate
of $f^{*}$ such that $l_{1}>f^{*}$. Moreover, at the termination of Algorithm
6, it returns an $\epsilon$-optimal and $\epsilon$-feasible solution.

###### Proof.

Proof. We have the following relation

$\displaystyle l_{k+1}-f^{*}$ $\displaystyle=l_{k}+U_{k}-f^{*}$
$\displaystyle\leq l_{k}-f^{*}+\mu L_{k}$ $\displaystyle\leq
l_{k}-f^{*}+\mu\phi(l_{k})$ $\displaystyle\leq
l_{k}-f^{*}-\mu\kappa(l_{k}-f^{*})$
$\displaystyle=(1-\mu\kappa)(l_{k}-f^{*}).$

The first inequality follows from Lemma 8.1, the second inequality from
$L_{k}\leq\phi(l_{k})$, the third is due to
$\frac{\phi(l_{k})-\phi(f^{*})}{l_{k}-f^{*}}\leq\frac{\phi(l_{1})-\phi(f^{*})}{l_{1}-f^{*}}\equiv-\kappa$,
which holds because of the convexity of $\phi(\cdot)$ and the relation that
$l_{k}\leq l_{1},k\geq 1$. Using induction on $k$, we have
$l_{k+1}-f^{*}\leq(1-\kappa\mu)^{k}(l_{1}-f^{*})$.

Next, we will show that given precision $\epsilon$, the terminal condition
$L_{k}\geq-\epsilon\tilde{\kappa}$ implies $l_{k}-f^{*}\leq\epsilon$. Note
first $-\phi(l_{k})\leq-L_{k}$ and $-\phi(l_{k})\geq\kappa(l_{k}-f^{*})$.
Using these inequalities and the relation that $\tilde{\kappa}\leq\kappa$, we
obtain $l_{k}-f^{*}\leq-
L_{k}/\kappa\leq\frac{\tilde{\kappa}}{\kappa}\epsilon\leq\epsilon$. Moreover,
in view of Lemma 8.2, we have $L_{k}\leq\phi(l_{k})\leq\phi(f^{*})=0$, then
$U_{k}\leq
L_{k}+(1-\mu)\tilde{\kappa}\epsilon\leq(1-\mu)\tilde{\kappa}\epsilon$. This
implies that $f(x_{k})-f^{*}=(f(x_{k})-l_{k})+(l_{k}-f^{*})\leq
U_{k}+\frac{\tilde{\kappa}}{\kappa}\epsilon\leq\left((1-\mu)\tilde{\kappa}+\frac{\tilde{\kappa}}{\kappa}\right)\epsilon$
and $\max\limits_{i=1,\cdots,m}h_{i}(x_{k})\leq
U_{k}\leq(1-\mu)\tilde{\kappa}\epsilon\leq\epsilon$. ∎

##  9 Convergence Analysis of Nonconvex Conditional Gradient Method

###  9.1 IPP-LCG for Nonconvex Problem

The following two lemmas serve as building blocks for establishing the
convergence rate of IPP-LCG. In particular, Lemma 9.1 characterizes an
important property of the optimal solution of the subproblem (3.2) and Lemma
9.2 states that the Slater condition enforces uniform boundness on
$y_{j}^{*}$.

###### Lemma 9.1

If $x_{j}^{*}$ is a KKT point (paired with $y_{j}^{*}$) of the subproblem
(3.2), then $\forall x\in X$,

$f(x;x_{j-1})-f(x_{j}^{*};x_{j-1})+\langle
y_{j}^{*},h(x)\rangle\geq\frac{\underline{L}_{f}}{2}\|x_{j}^{*}-x\|^{2}.$

###### Proof.

Proof. By (3.1), we have that that $f(\cdot;x^{\prime})$ is strongly convex.
Together by the strong convexity of $f(\cdot;x_{j-1})$ and convexity of
$h_{i}(\cdot)$ as well as the fact that $y^{*}_{j}\geq 0$, we have

$\displaystyle\begin{split}f(x;x_{j-1})+\langle y_{j}^{*},h(x)\rangle&\geq
f(x_{j}^{*};x_{j-1})+\langle\nabla f(x^{*}_{j};x_{j-1}),x-x^{*}_{j}\rangle\\\
&\quad+\frac{\underline{L}_{f}}{2}\|x-x_{j}^{*}\|^{2}+\sum\limits_{i=1}^{m}y_{j,i}^{*}\left(h_{i}(x_{j}^{*})+\langle\nabla
h_{i}(x_{j}^{*}),x-x^{*}_{j}\rangle\right)\\\ &\geq
f(x_{j}^{*};x_{j-1})+\frac{\underline{L}_{f}}{2}\|x-x_{j}^{*}\|^{2},\forall
x\in X,\end{split}$ (9.1)

where the last inequality follows from properties of the KKT point that
$\sum\limits_{i=1}^{m}y_{j,i}^{*}h_{i}(x_{j}^{*})=0$ and $\nabla
f(x_{j}^{*};x_{j-1})+\sum\limits_{i=1}^{m}y_{j,i}^{*}\nabla h_{i}(x_{j}^{*})$
belongs to the normal cone of $X$. ∎

###### Lemma 9.2

Suppose there exists $\tilde{x}\in X$ such that $h_{i}(\tilde{x})<0,\
i=1,\cdots,m$, then the dual solution $y^{*}_{j}$ is uniformly bounded such
that

$\|y^{*}_{j}\|_{1}\leq\frac{f(\tilde{x})-f^{*}+\underline{L}_{f}\overline{V}}{\|h(\tilde{x})\|_{\infty}},$
(9.2)

where $\|\cdot\|_{1}$ denote the $\ell_{1}$ norm and
$\overline{V}:=\max\limits_{x,y\in X}\frac{1}{2}\|x-y\|^{2}$.

###### Proof.

Proof. Using Lemma 9.1 and replacing $x$ with $\tilde{x}$, we have

$\displaystyle\begin{split}-\langle y_{j}^{*},h(\tilde{x})\rangle&\leq
f(\tilde{x};x_{j-1})-f(x_{j}^{*};x_{j-1})-\frac{\underline{L}_{f}}{2}\|\tilde{x}-x_{j}^{*}\|^{2}\\\
&=f(\tilde{x})-f(x^{*}_{j})+\underline{L}_{f}\left[\|\tilde{x}-x_{j-1}\|^{2}-\|x_{j}^{*}-x_{j-1}\|^{2}\right]-\frac{\underline{L}_{f}}{2}\|\tilde{x}-x_{j}^{*}\|^{2}\\\
&\leq
f(\tilde{x})-f(x^{*}_{j})+\frac{\underline{L}_{f}}{2}\|\tilde{x}-x_{j-1}\|^{2}\\\
&\leq f(\tilde{x})-f(x^{*}_{j})+\underline{L}_{f}\overline{V}.\end{split}$
(9.3)

Note that $h_{i}(\tilde{x})\leq-\|h(\tilde{x})\|_{\infty},i=1,\cdots,m$, then
$-\langle
y_{j}^{*},h(\tilde{x})\rangle\geq\|y_{j}^{*}\|_{1}\|h(\tilde{x})\|_{\infty}$.
∎

[Theorem 3.1] The total number of CGO iterations performed by the IPP-LCG
method to compute an $(\epsilon,\epsilon)$-KKT point of problem (1.1) is
bounded by
$\mathcal{O}\left(\frac{1}{\epsilon^{3}}\log(\frac{1}{\epsilon})\right)$.

###### Proof.

Proof. From Algorithm 3, we have $\delta^{f}\geq
f(x_{j};x_{j-1})-f(x^{*}_{j};x_{j-1})$ and
$\delta^{h}\geq\|h(x_{j})\|_{\infty}$. Define
$B:=\frac{f(\tilde{x})-f^{*}+\underline{L}_{f}\overline{V}}{\|h(\tilde{x})\|_{\infty}}$,
$\epsilon_{J}:=\frac{2}{\underline{L}_{f}}(\delta^{f}+B\delta^{h})$,
$\epsilon^{\prime}_{J}:=\frac{8\underline{L}_{f}}{J}\left[f(x_{0})-f(x_{J})\right]+\delta^{f}+B\delta^{h}$.
Note first, since $(x^{*}_{\hat{j}},y^{*}_{\hat{j}})$ is a pair of optimal
solution of subproblem (3.2), then the complementary slackness condition in
(3.1) automatically holds, i.e.
$\sum\limits_{i=1}^{m}|y_{\hat{j},i}^{*}h_{i}(x^{*}_{\hat{j}})|=0$, where
$y_{\hat{j},i}^{*}$ is the $i$-th element of $y_{\hat{j}}^{*}$.

By Lemma 9.1 (replace $x$ with $x_{\hat{j}}$), we have

$\displaystyle\begin{split}\|x_{\hat{j}}^{*}-x_{\hat{j}}\|^{2}&\leq\frac{2}{\underline{L}_{f}}\left[f(x_{\hat{j}};x_{\hat{j}-1})-f(x_{\hat{j}}^{*};x_{\hat{j}-1})+\langle
y_{\hat{j}}^{*},h(x_{\hat{j}})\rangle\right]\\\
&\leq\frac{2}{\underline{L}_{f}}(\delta^{f}+B\delta^{h}).\end{split}$ (9.4)

Replacing $x$ with $x_{\hat{j}-1}$ in Lemma 9.1 and using the relations that
$f(x_{\hat{j}};x_{\hat{j}-1})-f(x_{\hat{j}}^{*};x_{\hat{j}-1})\leq\delta^{f}$
as well as $h(x_{\hat{j}})\leq\delta^{h}$, we obtain

$\displaystyle\begin{split}\frac{\underline{L}_{f}}{2}\|x_{\hat{j}}^{*}-x_{\hat{j}-1}\|^{2}&\leq
f(x_{\hat{j}-1})-f(x^{*}_{\hat{j}};x_{\hat{j}-1})+\langle
y_{\hat{j}}^{*},h(x_{\hat{j}-1})\rangle\\\
&=f(x_{\hat{j}-1})-f(x_{\hat{j}})-\underline{L}_{f}\|x_{\hat{j}}-x_{\hat{j}-1}\|^{2}+\delta^{f}+B\delta^{h}\\\
&\leq f(x_{\hat{j}-1})-f(x_{\hat{j}})+\delta^{f}+B\delta^{h}\\\
&\leq\frac{1}{J}\sum\limits_{j=1,\cdots,J}f(x_{j-1})-f(x_{j})+\delta^{f}+B\delta^{h}\\\
&=\frac{1}{J}[f(x_{0})-f(x_{J})]+\delta^{f}+B\delta^{h},\\\ \end{split}$ (9.5)

where the third inequality follows from the selection of $\hat{j}$ in
Algorithm 3. Using the above equality, and the KKT condition applied for
(3.2), we arrive at

$\displaystyle\begin{split}\left[d\left(\nabla
f(x^{*}_{\hat{j}})+\sum\limits_{i=1}^{m}{y_{\hat{j}}^{*}}^{i}\nabla
h_{i}(x_{\hat{j}}^{*}),-N_{X}(x_{\hat{j}}^{*})\right)\right]^{2}&=4\underline{L}_{f}^{2}\|x_{\hat{j}}^{*}-x_{\hat{j}-1}\|^{2}\\\
&\leq\frac{8\underline{L}_{f}}{J}\left[f(x_{0})-f(x_{J})\right]+\delta^{f}+B\delta^{h}.\\\
\end{split}$ (9.6)

Combining (9.4) and (9.6), we reach the conclusion that $x_{\hat{j}}$ is an
$(\epsilon^{\prime}_{J},\epsilon_{J})$-KKT point of problem (1.1).
Consequently, given precision $\epsilon$, combining the result in Theorem 2.3,
the overall iteration complexity of IPP-LCG solving for an
$(\epsilon,\epsilon)$-KKT point is bounded by
$\mathcal{O}\left(\frac{1}{\epsilon^{3}}\log(\frac{1}{\epsilon})\right)$. ∎

###  9.2 DNCG for Nonconvex Problem

[Lemma 3.1] $\tilde{F}(\cdot)$ is a smooth function such that
$\|\nabla\tilde{F}(x_{1})-\nabla\tilde{F}(x_{2})\|\leq
L_{c}\|x_{1}-x_{2}\|,\forall x_{1},x_{2}\in X$, where
$L_{c}:=L_{f}+\frac{\|M_{h}\|\|L_{h}\|D_{X}}{c}+\frac{\|M_{h}\|^{2}}{c}$,
$L_{h}:=(L_{h_{1}},\cdots,L_{h_{m}})$, $M_{h}:=(M_{h_{1}},\cdots,M_{h_{m}})$
and $c>0$.

###### Proof.

Proof. Applying the first order optimality on
$\max\limits_{y\in\mathbb{R}^{m}_{+}}f(x)+\langle
h(x),y\rangle-\frac{c}{2}\|y\|^{2}$ at $y_{k-1}$ and $y_{k}$, respectively, we
obtain $\forall y\in\mathbb{R}^{m}_{+}$,

$\displaystyle\langle h(x_{k-1})-cy_{k-1},y-y_{k-1}\rangle$ $\displaystyle\leq
0,$ (9.7) $\displaystyle\langle h(x_{k})-cy_{k},y-y_{k}\rangle$
$\displaystyle\leq 0.$ (9.8)

Furthermore,

$c\|y_{k-1}-y_{k}\|^{2}\leq\langle
h(x_{k-1})-h(x_{k}),y_{k-1}-y_{k}\rangle\leq\|h(x_{k-1})-h(x_{k})\|\|y_{k-1}-y_{k}\|\leq\|M_{h}\|\|x_{k-1}-x_{k}\|\|y_{k-1}-y_{k}\|,$

where the first inequality is by summing up the two inequalities above with
$y$ replaced by $y_{k}$ in (9.7) and $y_{k-1}$ in (9.8); the second inequality
follows from the Cauchy Schwarz inequality; the third one follows by the
Lipschitz continuity of $h$. This gives

$\|y_{k-1}-y_{k}\|\leq\frac{1}{c}\|M_{h}\|\|x_{k-1}-x_{k}\|.$

Next, we derive a bound for $\|y_{k}\|$. Suppose $x^{*}$ is an optimal
solution of (1.1), then $h(x^{*})\leq 0.$ By (3.9) and the Lipschitz
continuity of $h(\cdot)$, we have

$\|y_{k}\|\leq\|\max\left\\{\frac{h(x_{k})-h(x^{*})}{c},0\right\\}\|\leq\frac{\|h(x_{k})-h(x^{*})\|}{c}\leq\frac{\|M_{h}\|\|x_{k}-x^{*}\|}{c}\leq\frac{\|M_{h}\|D_{X}}{c}.$

Using the above inequality, the smoothness of $f$ and $h$, we arrive at

$\displaystyle\begin{split}&\|\nabla\tilde{F}(x_{k})-\nabla\tilde{F}(x_{k-1})\|\\\
=&\|\nabla f(x_{k})-\nabla f(x_{k-1})+\langle y_{k},\nabla
h(x_{k})\rangle-\langle y_{k},\nabla h(x_{k-1})\rangle+\langle
y_{k}-y_{k-1},\nabla h(x_{k-1})\rangle\|\\\
\leq&\left(L_{f}+y_{k}^{\top}L_{h}+\frac{\|M_{h}\|^{2}}{c}\right)\|x_{k-1}-x_{k}\|\\\
\leq&\left(L_{f}+\frac{\|M_{h}\|\|L_{h}\|D_{X}}{c}+\frac{\|M_{h}\|^{2}}{c}\right)\|x_{k-1}-x_{k}\|.\end{split}$

∎

[Theorem 3.2] The total number of iterations required to compute an
approximate solution $\bar{x}$ such that $Q(\bar{x})\leq\epsilon$ and
$\|[h(\bar{x})]_{+}\|^{2}\leq\epsilon$ is bounded by
$\mathcal{O}\left(1/\epsilon^{4}\right)$.

###### Proof.

Proof. Suppose $\\{x_{k}\\}$ is generated by Algorithm 4. Let
$\tilde{F}^{*}:=\min\limits_{x\in X}\tilde{F}(x)$,
$\hat{k}:=\operatornamewithlimits{argmin}\limits_{0\leq k\leq K-1}Q(x_{k})$,
$c=\frac{1}{K^{1/4}}$ and $\alpha_{k}=\frac{1}{\sqrt{K}}$, where $K$ is a
known priori. By Lemma 3.1, we have

$\tilde{F}(x_{k})-\tilde{F}(x_{k-1})\leq\langle\nabla\tilde{F}(x_{k-1}),x_{k}-x_{k-1}\rangle+\left(L_{f}+\frac{\|M_{h}\|\|L_{h}\|D_{X}}{c}+\frac{\|M_{h}\|^{2}}{c}\right)\|x_{k-1}-x_{k}\|^{2}.$

Since by the definition of $Q(\cdot)$ and (3.8),

$\langle\nabla\tilde{F}(x_{k-1}),x_{k}-x_{k-1}\rangle=\alpha_{k}\langle\nabla\tilde{F}(x_{k-1}),p_{k}-x_{k-1}\rangle=-\alpha_{k}Q(x_{k-1}),$

then we have

$\alpha_{k}Q(x_{k-1})\leq-\tilde{F}(x_{k})+\tilde{F}(x_{k-1})+\left(L_{f}+\frac{\|M_{h}\|\|L_{h}\|D_{X}}{c}+\frac{\|M_{h}\|^{2}}{c}\right)\alpha_{k}^{2}\|x_{k-1}-p_{k}\|^{2}.$

Summing up the above inequality from $k=1$ to $K$ and using the fact that
$\tilde{F}^{*}\leq\tilde{F}(x_{K})$ result in

$\displaystyle\begin{split}\left(\sum\limits_{k=1}^{K}\alpha_{k}\right)\min\limits_{1\leq
k\leq
K}Q(x_{k-1})\leq\tilde{F}(x_{0})-\tilde{F}^{*}+\left(L_{f}+\frac{\|M_{h}\|\|L_{h}\|D_{X}}{c}+\frac{\|M_{h}\|^{2}}{c}\right)D_{X}^{2}\sum\limits_{1\leq
k\leq K}\alpha_{k}^{2}.\end{split}$ (9.9)

Dividing both sides of (9.9) by $\sum\limits_{k=1}^{K}\alpha_{k}$, we obtain

$Q(x_{\hat{k}})\leq\frac{1}{\sqrt{K}}\left[\tilde{F}(x_{0})-\tilde{F}^{*}+\frac{L_{f}}{2}D_{X}^{2}\right]+\frac{1}{K^{1/4}}\left(\frac{\|M_{h}\|^{2}D_{X}^{2}}{2}+\frac{\|M_{h}\|\|L_{h}\|D_{X}^{3}}{2}\right).$
(9.10)

Next, we derive a bound for $\|[h(x_{\hat{k}})]_{+}\|^{2}$. Let $y_{ki}$ be
the $i$-th element of the vector $y_{k}$ at iteration $k=1,\cdots,K$. Note
first, if $h(x_{\hat{k}})\leq 0$, then $\|[h(x_{\hat{k}})]_{+}\|^{2}=0$. The
analysis below focuses on the case where $h(x_{\hat{k}})>0$. Consequently, by
(3.9), we have $y_{\hat{k}i}=\frac{h(x_{\hat{k}})}{c},\ i=1,\cdots,m$ and

$\sum\limits_{i=1}^{m}y_{\hat{k}i}h_{i}(x_{\hat{k}})=\sum\limits_{i=1}^{m}\frac{1}{c}\left(h_{i}(x_{\hat{k}})\right)^{2}.$
(9.11)

Note also, using the Lipschitz continuity and the lower curvature property of
$f$, it can be easily verified that

$\langle\nabla
f(y),x-y\rangle\leq\frac{\underline{L}_{f}}{2}D_{X}^{2}+M_{f}D_{X},\forall
x,y\in X.$ (9.12)

Suppose $x^{*}$ is the optimal solution of (1.1), then $h(x^{*})\leq 0$. By
convexity of $h(\cdot)$ and the definition of $Q(x_{\hat{k}})$ in (3.10), we
obtain

$\displaystyle\begin{split}\sum\limits_{i=1}^{m}y_{\hat{k}i}h_{i}(x_{\hat{k}})&\leq\sum\limits_{i=1}^{m}y_{\hat{k}i}\left(h_{i}(x^{*})+\langle\nabla
h_{i}(x_{\hat{k}}),x_{\hat{k}}-x^{*}\rangle\right)\\\
&\leq\sum\limits_{i=1}^{m}y_{\hat{k}i}\langle\nabla
h_{i}(x_{\hat{k}}),x_{\hat{k}}-x^{*}\rangle\\\ &\leq
Q(x_{\hat{k}})+\langle\nabla f(x_{\hat{k}}),x^{*}-x_{\hat{k}}\rangle\\\ &\leq
Q(x_{\hat{k}})+\frac{\underline{L}_{f}}{2}D_{X}^{2}+M_{f}D_{X},\end{split}$
(9.13)

where the first inequality is because of the convexity of $h(\cdot)$, the
second inequality is due to $h(x^{*})\leq 0$ and $y_{\hat{k}}\geq 0$, the
third inequality is by the definition of $Q(x_{\hat{k}})$ and the last
inequality follows from (9.12). Combining (9.11) and (9.13), we have

$\displaystyle\begin{split}\|[h(x_{\hat{k}})]_{+}\|^{2}&\leq
c\left(Q(x_{\hat{k}})+\frac{\underline{L}_{f}}{2}\|x^{*}-x_{\hat{k}}\|^{2}+f(x^{*})-f(x_{\hat{k}})\right)\\\
&\leq\frac{1}{{K^{1/4}}}\left(Q(x_{\hat{k}})+\frac{\underline{L}_{f}}{2}D_{X}^{2}+M_{f}D_{X}\right),\end{split}$

which implies

$\|[h(x_{\hat{k}})]_{+}\|^{2}\leq\frac{1}{K^{3/4}}\left[\tilde{F}(x_{0})-\tilde{F}^{*}+\frac{L_{f}}{2}D_{X}^{2}\right]+\frac{1}{\sqrt{K}}\left(\frac{\|M_{h}\|^{2}D_{X}^{2}}{2}+\frac{\|M_{h}\|\|L_{h}\|D_{X}^{3}}{2}\right)+\frac{1}{K^{1/4}}\frac{\underline{L}_{f}}{2}D_{X}^{2}.$
(9.14)

Combining (9.10) and (9.14), given target accuracy $\epsilon>0$, the iteration
complexity of DNCG of solving for $\bar{x}$ such that $Q(\bar{x})\leq\epsilon$
and $\|[h(\bar{x})]_{+}\|^{2}\leq\epsilon$ is bounded by
$\mathcal{O}\left(1/\epsilon^{4}\right)$. ∎

###### Remark 9.1

In establishing the convergence rate of the DNCG method, we assume that
$h(\cdot)$ is a smooth function. Consider now when $h(\cdot)$ is nonsmooth and
inherits special structure as described in (6.17). Similar to Appendix 6.3, we
can apply Nesterov smoothing scheme and construct $\\{h_{i,\eta_{i}}\\}$ such
as

${h}_{i,\eta_{i}}(x):=\max\limits_{z\in Z_{i}}\ \left\\{\langle
B_{i}x,z\rangle-\hat{h}_{i}(z)-\eta_{i}U_{i}(z)\right\\},i=1,\cdots,\bar{m}.$
(9.15)

In this way, ${h}_{i,\eta_{i}}(x)$ is a $L_{h_{i},\eta_{i}}$-smooth function
with $L_{h_{i},\eta_{i}}=\frac{\|B_{i}\|^{2}}{\omega_{i}+\eta_{i}}$. We
thereby define the gap function as $Q_{\eta}(\bar{x}):=\max\limits_{x\in
X}\langle\nabla\tilde{F}_{\eta}(\bar{x}),\bar{x}-x\rangle$, where
$\tilde{F}_{\eta}(x)=f(x)+\sum\limits_{i=1}^{m}y_{i}h_{i,\eta_{i}}(x)-\frac{c}{2}\|y\|^{2}$.
Let $\eta_{i}=\frac{\|M_{h}\|D^{3}_{X}}{K^{1/8}},\ \forall i=1,\cdots,m.$ Then
by Theorem 3.2, we have that $Q_{\eta}(\bar{x})$ is upper bounded by
$\mathcal{O}\big{(}1/K^{8}\big{)}$. By the second relation in (6.18) , we have
that $\|[h(x_{\hat{k}})]_{+}\|^{2}$ is upper bounded by
$\mathcal{O}\big{(}1/K^{4}\big{)}$.

##  10 Auxiliary Numerical Studies

###  10.1 Portfolio Selection Models

##### Cardinality-free Models.

The objective function in model (Card-Free-Nonconvex) is a step function,
which is discontinuous and nonconvex. To implement the proposed algorithms
solving the model (Card-Free-Nonconvex), we employ a nonconvex smooth
approximation of $f(x)$ parameterized with $\theta$ such as
$\tilde{f}_{\theta}(x)=\frac{1}{K}\sum\limits_{k=1}^{K}\frac{1}{1+\exp\\{(-R_{k}+\sum\limits_{i\in
I}r_{ik}z_{i})/\theta\\}}.$ Clearly, $\tilde{f}_{\theta}\rightarrow f$ when
$\theta\rightarrow 0$.

Now we discuss how to approximate the nonconvex model (Card-Free-Nonconvex)
using the convex formulation. Define $\phi(x):=[1+x]_{+}$. Since for some
$t>0$, $\phi(tx)\geq 1$, then for a random variable $X$, we have

$\inf\limits_{t>0}\mathbb{E}[\phi(tX)]\geq\mathbb{E}\left[\mathbbm{1}_{\\{X>0\\}}\right].$
(10.1)

Consequently, instead of minimizing
$\mathbb{E}\left[\mathbbm{1}_{\\{X>0\\}}\right]$, we minimize its upper bound
$\inf\limits_{t>0}\mathbb{E}[\phi(tX)]$, which is equivalent to minimizing
$\inf\limits_{t>0}\mathbb{E}[\phi(tX)]-\alpha$, where $\alpha$ can be regarded
as some confidence level such that $\alpha>0$. Note that

$\inf\limits_{t>0}\mathbb{E}[\phi(tX)]-\alpha=\inf\limits_{u\in\mathbb{R}}\\{u+\alpha^{-1}\mathbb{E}[X-u]_{+}\\}$

and the minimum of the right-hand-side of the above inequality falls in
$[\underline{u},\bar{u}]$, where where $\underline{u}$ and $\bar{u}$ are the
respective left and right side $1-\alpha$ quantile of the distribution of $X$.
Coincidentally,
$\inf\limits_{u\in\mathbb{R}}\\{u+\alpha^{-1}\mathbb{E}[X-u]_{+}\\}$ is the
Conditional-Value-at-Risk (CVaR) measure that is convex. Leveraging such
approximation, we arrive at the convex approximation of the nonconvex model in
(Card-Free-Convex).

##### Cardinality-constrained Models.

In model (Card-Nonconvex-2), to make the objective function continuous, we use
the smooth approximation function
$\frac{1}{\Psi}\sum\limits_{i=1}^{N}\frac{1}{1+\exp\\{(-x_{i})/\theta\\}}$ to
replace the step function in implementation.

###  10.2 IMRT Models

We provide more details in modeling the IMRT problem in this subsection. To
elaborate, for each patients, the target body structures are discretized into
small voxels $v$ and the collection of all voxels is denoted by $\mathcal{V}$.
In the linac, each angle $a\in A$ contains rectangular grids of beamlet
$(l,r),l=1,\cdots,m,r=1,\cdots,n$, which can stay active or blocked. An
aperture $e\in E_{a}$ of an angle $a$ is then determined by the status of the
beamlets. A set of binary variables $\\{x^{a,e}_{l,r}\\}$ are created to
decide the shape of the aperture $e$ from angle $a$. Specifically,
$x^{a,e}_{l,r}=1$ if beamlet $(l,r)$ is active, and $x^{a,e}_{l,r}=0$ if
beamlet $(l,r)$ is blocked. An additional set of variables $\\{y_{a,e}\\}$ are
created to decide the intensity rate of the selected aperture $e$, where $e\in
E_{a}$. The unit intensity delivered to voxel $v$ from beamlet $(l,r)$ is
denoted by $D_{(l,r)}v$ in Gy. Then the total amount of radiation received by
voxel $v$ is

$z_{v}=\sum\limits_{a\in A}\sum\limits_{e\in
E_{a}}\sum\limits_{l=1}^{m}\sum\limits_{r=1}^{n}RD_{(l,r)v}x^{a,e}_{lr}y_{a,e},\
\forall v\in\mathcal{V}.$

We use $k$ to index the underdose/overdose clinical criteria, where $k\in
K_{u}(k\in K_{o})$ denote the underdose (overdose) criterion and $S_{k}$ to
denote the set of structures in criterion $k$, where
$S_{k}\subset\mathcal{V},k\in K_{u}\bigcup K_{o}$. Additionally, we denote the
number of voxels in $\mathcal{V}$ by $N_{v}$, the number of voxel in $S_{k}$
by $N_{k}$ and the required quantile of criterion $k$ by $p_{k}$.

##### Convex Formulation.

Note that the left hand side in both (4.4) and (4.5) are nonconvex and we use
CVaR for approximation in the convex formulation stated below. Follow the
description in (Lan et al. 2021), the convex model is adapted as follow:

$\displaystyle\min\ f(z):=\frac{1}{N_{v}}$
$\displaystyle\sum\limits_{v\in\mathcal{V}}\underline{w}_{v}\left[\underline{T}_{v}-z_{v}\right]^{2}_{+}+\bar{w}_{v}\left[z_{v}-\bar{T}_{v}\right]^{2}_{+}$
(10.2) $\displaystyle\operatornamewithlimits{s.t.}\
-\tau_{k}+\frac{1}{p_{k}N_{k}}\sum\limits_{v\in
S_{k}}\left[\tau_{k}-z_{v}\right]_{+}\leq-b_{k},\ \forall k\in K_{u},$ (10.3)
$\displaystyle\tau_{k}+\frac{1}{p_{k}N_{k}}\sum\limits_{v\in
S_{k}}\left[z_{v}-\tau_{k}\right]_{+}\leq b_{k},\ \forall k\in K_{o},$ (10.4)
$\displaystyle z_{v}=\sum\limits_{a\in A}\sum\limits_{e\in
E_{a}}\sum\limits_{l=1}^{m}\sum\limits_{r=1}^{n}RD_{(l,r)v}x^{a,e}_{lr}y_{a,e},\
\forall v\in S_{k},k\in K_{u}\cup K_{o},$ (10.5)
$\displaystyle\sum\limits_{a\in A}\max_{e\in E_{a}}y_{a,e}\leq\Phi,$ (10.6)
$\displaystyle\sum\limits_{a\in A}\sum\limits_{e\in E_{a}}y_{a,e}\leq 1,$
(10.7) $\displaystyle y^{a,t}\geq 0,$ (10.8)
$\displaystyle\tau_{k}\leq\bar{\tau}_{k},\ k\in K_{u}\cup K_{o},$ (10.9)
$\displaystyle\tau_{k}\geq\underline{\tau}_{k},\ k\in K_{u}\cup K_{o}.$
(10.10)

The objective function $f(z)$ in (10.2), serving as a convex surrogate of the
clinical criteria, penalizes underage and overage dose of a voxel with pre-
defined threshold $\underline{T_{v}},\bar{T}_{v}$ and weights
$\underline{w}_{v}$, $\bar{w}_{v}$, where $[\cdot]_{+}$ denotes
$\max(\cdot,0)$. To reinforce the clinical criteria, constraints (10.3) and
(10.4) are added. To solve the convex model by the LCG method, smoothing
scheme (with entropy distance generating function) is applied on all nonsmooth
functionals ((10.3),(10.4) and (10.6)), which includes construction of
$\\{h_{i,\eta_{i}}\\}$ as indicated in Algorithm 5 for nonsmooth
underdose/overdose constraints and the group sparsity constraint.

##### Nonconvex Formulation.

The exact nonconvex formulation is described as follow.

$\displaystyle\begin{split}\min\ &f(z):=\sum\limits_{k\in
K_{u}}\frac{w_{k}}{N_{k}}\sum\limits_{v\in
S_{k}}\mathbbm{1}_{\\{z_{v}<\tau_{k}\\}}+\sum\limits_{k\in
K_{o}}\frac{w_{k}}{N_{k}}\sum\limits_{v\in
S_{k}}\mathbbm{1}_{\\{z_{v}>\tau_{k}\\}}\\\ \operatornamewithlimits{s.t.}\
&z_{v}=\sum\limits_{a\in A}\sum\limits_{e\in
E_{a}}\sum\limits_{l=1}^{m}\sum\limits_{r=1}^{n}RD_{(l,r)v}x^{a,e}_{lr}y_{a,e},\
\forall v\in S_{k},k\in K_{u}\cup K_{o},\\\ &\sum\limits_{a\in A}\max_{e\in
E_{a}}y_{a,e}\leq\Phi,\\\ &\sum\limits_{a\in A}\sum\limits_{e\in
E_{a}}y_{a,e}\leq 1,\\\ &y_{a,e}\geq 0.\end{split}$ (10.11)

Here $\\{w_{k}\\}$ is a set of weights for underdose and overdose objective
terms; $f(\cdot)$ is a step function which is nonconvex and discontinuous;
$\\{\tau_{k}\\}$ are parameters given by the clinical criteria, instead of
decision variables to calibrate the approximation in the case of the convex
formulation. To solve the model by the proposed algorithm, we employ a sigmoid
function (parameterized on $\theta$) to approximate the original function.
Specifically, for $k\in K_{u}$, the approximation reads

$\tilde{f}^{k}_{\theta}(x)=\frac{1}{N_{k}}\sum\limits_{v\in
S_{k}}\frac{1}{1+\exp\\{(z_{v}-\tau_{k})/\theta\\}}.$ (10.12)

Similarly, for $k\in K_{o}$,

$\tilde{f}^{k}_{\theta}(x)=\frac{1}{N_{k}}\sum\limits_{v\in
S_{k}}\frac{1}{1+\exp\\{(-z_{v}+\tau_{k})/\theta\\}}.$ (10.13)

Note that when $\theta\rightarrow 0$, $\tilde{f}_{\theta}\rightarrow f$ and
$\tilde{f}_{\theta}$ is nonconvex.

###  10.3 IMRT Synthetic Dataset

The synthetic dataset used in Section 4 mimics the IMRT dataset of a real
patient, with each containing information of (discretized) voxels, beamlet
coodinates and corresponding unit intensity ($D$ matrix) received by each
voxel. In particular, each angle pairs with a $D$ matrix with dimension of
$\\#$ of voxels $\times$ $\\#$ of beamlets, and there are $180$ $D$ matrices
in total. In particular, the number of beamlets is determined by the
discretization granularity (beamlet unit length).

Table 13 describes main features of each dataset, where “Granularity” stands
for beamlet unit length. Instance 1 and 2 (resp. instance 3 and 4) are
featured in lower (resp. higher) beamlet granularity and have the same set of
$D$ matrices and voxels. Higher discretization accuracy (e.g. $0.25$) results
in larger number of beamlets, thus in higher dimension of $D$ matrix.
Therefore, instance 3 and 4 are in larger scale than instance 1 and 2. Among
all the voxels, we randomly select two sets of tumor tissues that require
radiation therapy and treat the rest as the healthy ones. For the tumor
issues, we consider two underdose and one overdose constraints.

Table 13: Features of the synthetic dataset Instance |  $\\#$ of angels |  $\\#$ of voxels |  $\\#$ of beamlets | Accuracy | $b_{k}$ | $p_{k}$
---|---|---|---|---|---|---
1 | 180 | $4096$ | 100 | 1.0 | $[40,50,100]$ | $[0.01,0.01,0.05]$
2 | 180 | $4096$ | 100 | 1.0 | $[50,60,80]$ | $[0.01,0.01,0.01]$
3 | 180 | $262144$ | 2000 | 0.25 | $[40,50,100]$ | $[0.01,0.01,0.05]$
4 | 180 | $262144$ | 2000 | 0.25 | $[50,60,80]$ | $[0.01,0.01,0.01]$

###  10.4 Auxiliary Results on IMRT Synthetic Dataset

Table 14 displays the results of applying LCG to solve the convex formulation
(10.2) - (10.10) with various $\Phi$. From the table, we observe that
regardless of the large difference in scale among the instances, the proposed
algorithm LCG exhibits comparable performance in solving all instances in view
of the objective value and constraint violation at iteration $1000$. By
comparing instance 1 and instance 2 (namely, instance 3 and instance 4), we
see that the values of $\|h(x_{N})\|_{2}$ in instance 1 (resp. instance 3)
remain lower than those in instance 2 (resp. instance 4). Such results
indicate that the satisfaction of the constraints are sensitive to the choice
of $(b_{k},p_{k})$ thus to the decision variable $\tau_{k}$, which jointly
determine the CVaR approximation. An additional observation is that when
$\Phi$ decreases (i.e. sparsity requirement is more stringent), the violation
of the group sparsity constraint increases, which is an expected effect of
$\Phi$.

Table 14: Results of applying LCG on the synthetic dataset at iteration $1000$.  Instance | $\Phi$ | LCG |
---|---|---|---
$f(x_{N})$ | $\|h(x_{N})\|_{2}$ | $\|h_{s}\|_{2}$ | $\|h_{c}\|_{2}$ | Time (s)
1 | 1.0 | 0.0136 | 0.319 | 0 | 0.319 | 901
0.5 | 0.0142 | 0.326 | 0 | 0.326 | 914
0.05 | 0.0156 | 0.449 | 0.302 | 0.332 | 948
0.005 | 0.0193 | 0.528 | 0.421 | 0.319 | 924
| 0.0005 | 0.0174 | 0.576 | 0.499 | 0.288 | 938
2 | 1.0 | 0.0156 | 0.626 | 0 | 0.626 | 916
0.5 | 0.0161 | 0.628 | 0 | 0.628 | 923
0.05 | 0.0197 | 0.702 | 0.291 | 0.639 | 942
0.005 | 0.019 | 0.763 | 0.402 | 0.649 | 908
| 0.0005 | 0.0142 | 0.815 | 0.476 | 0.662 | 949
3 | 1.0 | 0.0479 | 0.434 | 0 | 0.434 | 4678
0.5 | 0.0466 | 0.436 | 0 | 0.436 | 4726
0.05 | 0.0514 | 0.451 | 0.087 | 0.442 | 4685
0.005 | 0.047 | 0.476 | 0.169 | 0.445 | 4834
| 0.0005 | 0.048 | 0.493 | 0.188 | 0.456 | 4842
4 | 1.0 | 0.0421 | 0.919 | 0 | 0.919 | 4766
0.5 | 0.0441 | 0.943 | 0 | 0.943 | 4762
0.05 | 0.0498 | 0.969 | 0.068 | 0.967 | 4813
0.005 | 0.0435 | 0.984 | 0.175 | 0.968 | 4871
| 0.0005 | 0.0433 | 0.975 | 0.201 | 0.954 | 4772