A conditional gradient homotopy method with applications to Semidefinite Programming

Let $\mathsf{Q}$ be an open and convex subset of $\mathsf{E}$. A function $f:\mathsf{E}\to(-\infty,\infty]$ is self-concordant (SC) on $\mathsf{Q}$ if $f\in{\mathbf{C}}^{3}(\mathsf{Q})$ and for all $x\in\mathsf{Q},h\in\mathsf{E}$, we have $\lvert f^{\prime\prime\prime}(x)[h,h,h]\rvert\leq 2(f^{\prime\prime}(x)[h,h])^{3/2}.$ In case where $\operatorname{cl}(\mathsf{Q})$ is a closed, convex, and pointed (i.e., contains no line) cone, we have more structure. We call $f$ a $\nu$-canonical barrier for $\mathsf{Q}$, denoted by $f\in\mathcal{B}_{\nu}(\mathsf{Q})$, if it is SC and

$$\forall(x,t)\in\mathsf{Q}\times(0,\infty):\quad f(tx)=f(x)-\nu\log(t).$$

From [30, Prop. 2.3.4], the following properties are satisfied by a $\nu$-canonical barrier for each $x\in\mathsf{Q},h\in\mathsf{E},t>0$:

	$\displaystyle f^{\prime}(tx)=t^{-1}f^{\prime}(x),$		(2.1)
	$\displaystyle f^{\prime}(x)[h]=-f^{\prime\prime}(x)[x,h],$		(2.2)
	$\displaystyle f^{\prime}(x)[x]=-\nu,$		(2.3)
	$\displaystyle f^{\prime\prime}(x)[x,x]=\nu.$		(2.4)

We define the local norm $\lVert h\rVert_{f^{\prime\prime}(x)}:=(f^{\prime\prime}(x)[h,h])^{1/2}$ for all $x\in\operatorname{dom}(f)$ and $h\in\mathsf{E}$. SC functions are in general not Lipschitz smooth. Still, we have access to a version of a descent lemma of the following form [29, Thm. 5.1.9]:

$$f(x+h)\leq f(x)+f^{\prime}(x)[h]+\omega_{\ast}(\lVert h\rVert_{f^{\prime\prime}(x)})$$

(2.5)

for all $x\in\operatorname{dom}(f)$ and $h\in\mathsf{E}$ such that $\lVert h\rVert_{f^{\prime\prime}(x)}<1$, where $\omega_{\ast}(t)=-t-\log(1-t)$. It also holds true that [29, Thm. 5.1.8]

$$f(x+h)\geq f(x)+f^{\prime}(x)[h]+\omega(\lVert h\rVert_{f^{\prime\prime}(x)})$$

(2.6)

for all $x\in\operatorname{dom}(f)$ and $h\in\mathsf{E}$ such that $x+h\in\operatorname{dom}(f)$, where $\omega(t)=t-\log(1+t)$ for $t\geq 0$.

A classical and useful bound is [29, Lemma 5.1.5]:

$$\frac{t^{2}}{2-t}\leq\omega_{\ast}(t)\leq\frac{t^{2}}{2(1-t)}\quad\forall t\in[0,1).$$

(2.7)

The following assumptions are made for the rest of this paper.

The next assumption transports the barrier setup from the codomain $\mathsf{K}$ to the domain $\mathcal{P}^{-1}(\mathsf{K})$. This is a common operation in the framework of the "barrier calculus" developed in [30, Section 5.1].

Note that $\operatorname{dom}(F)=\operatorname{int}\mathcal{P}^{-1}(\mathsf{K})$.

Let $\operatorname{Opt}:=\min\{g(x)|x\in\mathsf{X},\mathcal{P}(x)\in\mathsf{K}\}$. Thanks to assumptions 2 and 4, $\operatorname{Opt}$ is attained. Our goal is to find an $\varepsilon$-solution of problem (P), defined as follows.

Given $t>0$, define

$$\operatorname{Opt}(t):=\min_{x\in\mathsf{X}}\{V_{t}(x)=\frac{1}{t}F(x)+g(x)\},\text{ and }z^{\ast}(t)\in\{x\in\mathsf{X}|V_{t}(x)=\operatorname{Opt}(t)\}.$$

(2.8)

The following Lemma shows that the path $t\mapsto z^{\ast}(t)$ traces a trajectory in the interior of the feasible set which can be used to approximate a solution of the original problem (P), provided the penalty parameter $t$ is chosen large enough.

The computational efficiency of our approach relies on the availability of a suitably defined minimisation oracle:

We can compute the gradient and Hessian of $F$ as

$$F^{\prime}(x)=f^{\prime}(\mathcal{P}(x))\mathcal{P}^{\prime}(x),\quad F^{\prime\prime}(x)[s,t]=f^{\prime\prime}(\mathcal{P}(x))[\mathcal{P}(s),\mathcal{P}(t)]\quad\forall x\in\operatorname{int}\mathcal{P}^{-1}(\mathsf{K}).$$

This means that we obtain a local norm on $\mathsf{H}$ given by

$$\lVert w\rVert_{x}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}:=}F^{\prime\prime}(x)[w,w]^{1/2}\qquad\forall(x,w)\in\operatorname{int}\mathcal{P}^{-1}(\mathsf{K})\times\mathsf{H}.$$

Note that in order to evaluate the local norm we do not need to compute the full Hessian $F^{\prime\prime}(x)$. It only requires a directional derivative, which is potentially easy to do numerically.

A Linear Mnimization Oracle (LMO) is defined as an oracle producing the vector field

$$s_{t}(x)\in\mathcal{L}_{g}(t^{-1}F^{\prime}(x)).$$

(3.2)

Note that our analysis does not rely on a specific tie-breaking rule, so any member of the set $\mathcal{L}_{g}(t^{-1}F^{\prime}(x))$ will be acceptable.

To measure solution accuracy and overall algorithmic progress, we introduce two merit functions:

	$\displaystyle\operatorname{\mathsf{Gap}}_{t}(x)$	$\displaystyle:=t^{-1}F^{\prime}(x)[x-s_{t}(x)]+g(x)-g(s_{t}(x)),\text{ and }$		(3.3)
	$\displaystyle\Delta_{t}(x)$	$\displaystyle:=V_{t}(x)-V_{t}(z^{\ast}(t)).$		(3.4)

Note that $\operatorname{\mathsf{Gap}}_{t}(x)\geq 0$ and $\Delta_{t}(x)\geq 0$ for all $x\in\operatorname{dom}(F)$. Moreover, convexity together with the definition of the point $z^{\ast}(t)$, gives

	$\displaystyle 0$	$\displaystyle\leq\Delta_{t}(x)=t^{-1}[F(x)-F(z^{\ast}(t))]+g(x)-g(z^{\ast}(t))$
		$\displaystyle\leq t^{-1}F^{\prime}(x)[x-z^{\ast}(t)]+g(x)-g(z^{\ast}(t))$
		$\displaystyle\leq t^{-1}F^{\prime}(x)[x-s_{t}(x)]+g(x)-g(s_{t}(x))=\operatorname{\mathsf{Gap}}_{t}(x).$

Hence,

$$\operatorname{\mathsf{Gap}}_{t}(x)\geq\Delta_{t}(x)\qquad\forall x\in\operatorname{dom}(F)\cap\operatorname{dom}(g).$$

(3.5)

Define

$$\mathtt{e}_{t}(x):=\lVert s_{t}(x)-x\rVert_{x}.$$

(3.6)

Then, for $\alpha\in[0,\min\{1,1/\mathtt{e}_{t}(x)\})$, we get from (2.5)

$$F(x+\alpha(s_{t}(x)-x))\leq F(x)+\alpha F^{\prime}(x)[s_{t}(x)-x]+\omega_{\ast}(\alpha\mathtt{e}_{t}(x)).$$

Together with the convexity of $g$, this implies

$$V_{t}(x+\alpha(s_{t}(x)-x))\leq V_{t}(x)-\alpha\operatorname{\mathsf{Gap}}_{t}(x)+t^{-1}\omega_{\ast}(\alpha\mathtt{e}_{t}(x))={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}V_{t}(x)-\eta_{t,x}(\alpha)},$$

(3.7)

where

$$\eta_{t,x}(\alpha):=\alpha\operatorname{\mathsf{Gap}}_{t}(x)-t^{-1}\omega_{\ast}(\alpha\mathtt{e}_{t}(x))=\alpha\operatorname{\mathsf{Gap}}_{t}(x)+t^{-1}\left(\alpha\mathtt{e}_{t}(x)+\log(1-\alpha\mathtt{e}_{t}(x))\right).$$

Optimising this expression w.r.t $\alpha\in[0,1]$, we obtain the analytic step-size policy

$$\alpha_{t}(x):=\min\left\{1,\frac{t\operatorname{\mathsf{Gap}}_{t}(x)}{\mathtt{e}_{t}(x)(\mathtt{e}_{t}(x)+t\operatorname{\mathsf{Gap}}_{t}(x))}\right\}\in[0,1/\mathtt{e}_{t}(x)).$$

(3.8)

Equipped with this step strategy, procedure $\operatorname{\texttt{CG}}(x^{0},\varepsilon,t)$, described in Algorithm 1, constructs a sequence $\{x^{k}_{t}\}_{k\geq 0}$ which produces an approximately-optimal solution in terms of the merit function $\operatorname{\mathsf{Gap}}_{t}(\cdot)$ and the potential function gap $\Delta_{t}$. Specifically, our main results on the performance of Algorithm 1 are the following iteration complexity estimates, which are proven in Section 5.

Our analysis so far focuses on minimisation of the potential function $V_{t}(x)$ for a fixed $t>0$. However, in order to solve the initial problem (P), one must trace the sequence of approximate solutions $\{z^{\ast}(t)\}_{t\geq 0}$ as $t\uparrow\infty$. The construction of such an increasing sequence of homotopy parameters is the purpose of this section.

Let $\{\eta_{i}\}_{i\geq 0},\{t_{i}\}_{i\geq 0}$ be a sequence of approximation errors and homotopy parameters. For each run $i$, we activate procedure $\operatorname{\texttt{CG}}(x^{0}_{t_{i}},\eta_{i},t_{i})$ with the given configuration $(\eta_{i},t_{i})$. For $i=0$, we assume to have an admissible initial point $x^{0}_{t_{0}}=x^{0}$ available. For $i\geq 1$, we restart Algorithm 1 using a kind of warm-start strategy by choosing $x^{0}_{t_{i}}=x^{R_{i-1}}_{t_{i-1}}$, where $R_{i-1}\leq R(x^{0}_{t_{i-1}},\eta_{i-1},t_{i-1})$ denotes the first iterate $k$ of Algorithm $\operatorname{\texttt{CG}}(x^{0}_{t_{i-1}},\eta_{i-1},t_{i-1})$ satisfying $\operatorname{\mathsf{Gap}}_{t_{i-1}}(x^{k}_{t_{i-1}})\leq\eta_{i-1}$. Note that $R_{i-1}$ is upper bounded by the constant $R(x^{0}_{t_{i-1}},\eta_{i-1},t_{i-1})$ defined in Proposition 3.1. After the $i$-th restart, let us call the obtained iterate $\hat{x}_{i}:=x^{R_{i}}_{t_{i}}$. In this way we obtain a sequence $\{\hat{x}_{i}\}_{i\geq 0}$, consisting of candidates for approximately following the central path, as they are $\eta_{i}$-close in terms of the gap $\operatorname{\mathsf{Gap}}_{t_{i}}$ (and, hence, in terms of the function gap) to the stage $t_{i}$’s optimal point $z^{\ast}(t_{i})$. We update the parameters $(\eta_{i},t_{i})$ as follows:

• •

  The sequence of homotopy parameters is determined as $t_{i}=t_{0}\sigma^{-i}$ for $\sigma\in(0,1)$ until the last round of $\texttt{Homotopy}(x^{0},\varepsilon,f)$ is reached.

• •

  The sequence of accuracies requested in the algorithm $\operatorname{\texttt{CG}}(x^{0}_{t_{i}},\eta_{i},t_{i})$ is updated by $\eta_{i}=\eta_{0}\sigma^{i}$.

• •

  The Algorithm stops after $I\equiv I(\sigma,\eta_{0},\varepsilon)=\lceil\frac{\log(2\eta_{0}/\varepsilon)}{\log(1/\sigma)}\rceil$ updates of the accuracy and homotopy parameters and yields an $\varepsilon$-approximate solution of problem (P).

Our updating strategy for the parameters ensures ”detailed balance” $t_{i}\eta_{i}=t_{0}\eta_{0}$. This equilibrating choice between the increasing homotopy parameter and the decreasing accuracy parameter is sensible, because the iteration complexity of the CndG solver is inversely proportional to $t_{i}\eta_{i}$ (cf. Proposition 3.1). Making the judicious choice $\eta_{0}t_{0}=2\nu$, yields a compact assessment of the total complexity of method $\texttt{Homotopy}(x^{0},\varepsilon,f)$.

The step size policy employed in Algorithm 1 is inversely proportional to the local norm $\mathtt{e}_{t}(x)$. In particular, its derivation is based on the a-priori restriction that we force our iterates to stay within a trust-region defined by the Dikin ellipsoid. This restriction may force the method to take very small steps, and as a result display bad performance in practice. A simple remedy would be to employ a line search. Given $(x,t)\in\operatorname{dom}(F)\times(0,+\infty)$, let

$$\gamma_{t}(x)=\operatorname*{argmin}_{\gamma\in[0,1]\text{ s.t. }x+\gamma(s_{t}(x)-x)\in\operatorname{dom}(F)}V_{t}(x+\gamma(s_{t}(x)-x)).$$

(4.1)

Thanks to the barrier structure of the potential function $V_{t}$, some useful consequences can be drawn from the definition of $\gamma_{t}(x)$. First, $\gamma_{t}(x)\in\{\gamma\geq 0|x+\gamma(s_{t}(x)-x)\in\operatorname{dom}(F)\}$. This implies $x+\gamma_{t}(x)(s_{t}(x)-x)\in\mathsf{X}\cap\operatorname{dom}(F)\cap\operatorname{dom}(g)$. Second, since $\alpha_{t}(x)$ is also contained in the latter set, we have

$$V_{t}(x+\gamma_{t}(x)(s_{t}(x)-x))\leq V_{t}(x+\alpha_{t}(x)(s_{t}(x)-x))\qquad\forall(x,t)\in\operatorname{dom}(F)\times(0,+\infty).$$

Via a comparison principle, this allows us to deduce the analysis of the sequence produced by $\operatorname{\texttt{LCG}}(x^{0},\varepsilon,t)$ from the analysis of the sequence induced by $\operatorname{\texttt{CG}}(x^{0},\varepsilon,t)$. Indeed, if $\{\xi^{k}_{t}\}_{k\geq 0}$ is the sequence constructed by the line search procedure $\operatorname{\texttt{LCG}}(x^{0},\eta,t)$, then we have $V_{t}(\xi^{k+1}_{t})\leq V_{t}(\xi_{t}^{k}+\alpha_{t}(\xi^{k}_{t})(s_{t}(\xi^{k}_{t})-x^{k}_{t}))$ for all $k$. Hence, we can perform the complexity analysis on the majorising function as in the analysis of procedure $\operatorname{\texttt{CG}}(x^{0},\varepsilon,t)$. Consequently, all the complexity-related estimates for the method $\operatorname{\texttt{CG}}(x^{0},\eta,t)$ apply verbatim to the sequence $\{\xi^{k}_{t}\}_{k\geq 0}$ induced by the method $\operatorname{\texttt{LCG}}(x^{0},\eta,t)$.