# Examples of ill-behaved central paths in convex optimization

Jean Charles Gilbert, Clóvis C. Gonzaga, Elizabeth Karas

► To cite this version:

Jean Charles Gilbert, Clóvis C. Gonzaga, Elizabeth Karas. Examples of ill-behaved central paths in convex optimization. Mathematical Programming, 2005, 103, pp.63-94. 10.1007/s10107-003-0460-0 . inria-00072443

HAL Id: inria-00072443

https://inria.hal.science/inria-00072443

Submitted on 24 May 2006

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE

*Examples of ill-behaved central paths in convex optimization*

Jean Charles GILBERT — Clóvis C. GONZAGA — Elizabeth KARAS

N° 4179

3 mai 2001

THÈME 4

Rapport
de recherche
<figure><img src="image_2.png" /></figure>
# Examples of ill-behaved central paths in convex optimization

Jean Charles GILBERT*, Clóvis C. GONZAGA†, Elizabeth KARAS‡

Thème 4 — Simulation et optimisation
de systèmes complexes
Projet Estime

Rapport de recherche n° 4179 — 3 mai 2001 — 31 pages

**Abstract:** This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data.

**Key-words:** Central path – convex optimization – interior point algorithm – nonlinear programming – penalty function methods.

<footnote>* INRIA Rocquencourt, projet Estime, BP 105, 78153 Le Chesnay Cedex (France); e-mail: Jean-Charles.Gilbert@inria.fr.</footnote>

<footnote>† Department of Mathematics, Federal University of Santa Catarina, Florianópolis, Brazil, e-mail: clovis@mtm.ufsc.br. Research partially supported by CAPES, Brazil.</footnote>

<footnote>‡ Department of Mathematics, Federal University of Paraná, Curitiba, Brazil, e-mail: karas@mat.ufpr.br. Research partially supported by CAPES and CNPq, Brazil.</footnote>
Exemples de chemins centraux mouvementés en
optimisation convexe

**Résumé** : Cet article présente quelques exemples de chemins centraux à l'allure mou-
vementée en optimisation convexe. Certains d'entre eux sont formés d'un nombre infini
de segments centraux de longueur fixe; d'autres manifestent des oscillations avec une
variation infinie. Ces chemins peuvent se rencontrer même si les données du problème
sont indéfiniment différentiables.

**Mots-clés :** Algorithme de points intérieurs – chemin central – méthodes de pénali-
sation – optimisation convexe – programmation non linéaire.
# 1 Introduction

Penalization approaches have been central in the whole evolution of optimization techniques. Constrained problems are often solved by a sequence of resolutions of penalized problems, which depend on a single penalization parameter $\mu$. The optimizers associated with each value of $\mu$ define a “path of optimizers”, which should be well-behaved and lead to a solution to the original problem.

This approach is developed in the classical book by Fiacco and McCormick [11], who describe external, internal, and mixed penalty methods for nonlinear programming. Internal penalty methods, also known as barrier methods, had an explosive development in the last fifteen years, due to the success of interior point methods for linear programming and for linear complementarity problems (see the monographs [18, 9, 23, 26, 17, 25, 30]; see also the extensions to nonlinear programming in [10, 27, 13, 14, 8, 3]). The first deep study of the path of optimizers, now known as central path, is due to Bayer and Lagarias [2] and to Megiddo [20], who gave a definitive characterization of the primal-dual central path. An introduction to path-following methods is given by Gonzaga [15].

We know that for linear programming the path is well defined, infinitely differentiable and has a bounded length, associated with the complexity of path-following methods. The limiting behavior of the path derivatives is described by Monteiro and Tsuchiya [21], who show that the path approaches the optimal face with a well-defined inclination. Similar results are obtained for convex problems by McLinden [19]: he shows that under reasonable hypotheses, which include strict complementarity, the central path converges to the “analytic center” of the optimal set for the problem. Vavasis and Ye [28] show that for linear programs in $\mathbb{R}^n$ the central path is composed of a sequence of no more than $n^2$ alternated curved and “almost straight” sectors.

From these results, it seems reasonable to expect smooth and calm sets of optimizers in convex programming problems. In this paper, however, we show that this is not necessarily true. We give examples of convex problems for which the path associated with any penalty function is undesirably weird.

We shall work with an extremely simple region in $\mathbb{R}^2$ and construct increasingly complex objective functions. First, we exhibit a continuous convex function giving rise to an “antenna-like” central path, containing an infinite number of horizontal segments of constant length. The second example is obtained by slightly perturbing the first one and results in a zig-zagging central path with infinite variation. We proceed by smoothing both functions, and produce the same behaviors as before for a differentiable objective function, and finally for a $C^\infty$ function.

We conclude that convexity, even when added to differentiability of any degree, is not a sufficiently strong property to ensure reasonably attractive central paths.
## 2 Background

We are interested in nonlinear programming problems with the shape

$$ \begin{array}{ll} \text{minimize} & f(x) \\ \text{subject to} & c_i(x) \ge 0, \quad i = 1, \dots, m, \end{array} $$

where $f: \mathbb{R}^n \to \mathbb{R}$ and $(-c_i): \mathbb{R}^n \to \mathbb{R}$ are closed proper convex functions.

A penalty method is based on some penalty function $p: \mathbb{R}^m \to \mathbb{R} \cup \{+\infty\}$ and proceeds by solving problems of the form

$$ \min f(x) + \mu p(c(x)), \quad (1) $$

for some penalty parameter $\mu > 0$. If these problems are well-defined, the image of the set-valued map $(\mathbb{R}_{++})$ denotes the set of positive real numbers)

$$ \mu \in \mathbb{R}_{++} \mapsto \chi(\mu) := \operatorname{argmin} \{f(x) + \mu p(c(x))\} $$

is called the central path. There is also a dual central path, but this paper only deals with the primal central path defined above. Interior point methods use the logarithmic barrier function, defined for $y \in \mathbb{R}_{++}^m$ (the set of $m$-vectors with positive components) by

$$ p(y) = -\sum_{i=1}^{m} \log y_i. $$

In that case $\chi(\mu) = \operatorname{argmin} \left\{ f(x) - \mu \sum_{i=1}^{m} \log(c_i(x)) \mid c(x) > 0 \right\}$.

A simple way of visualizing the central path is the following. Assume that $\bar{x} \in \chi(\mu)$ for some $\mu > 0$. Then $\bar{x}$ also solves

$$ \begin{array}{ll} \text{minimize} & f(x) + \mu p(c(x)) \\ \text{subject to} & p(c(x)) = p(c(\bar{x})), \end{array} $$

or equivalently

$$ \text{minimize} \quad \{f(x) \mid p(c(x)) = p(c(\bar{x}))\}. $$

Pictorially, this means that central points are points where $f$ and $(p \circ c)$ have tangent level curves.

Let us particularize this to a very simple 2-dimensional problem. Let $F: z = (x, y) \in \mathbb{R}^2 \to \mathbb{R}$ be a closed proper convex function. We study problems like

$$ \begin{array}{ll} \text{minimize} & F(x, y) \\ \text{subject to} & y \ge 0, \end{array} \quad (2) $$

and assume that its solutions are on the $x$-axis $\{(x, 0) : x \in \mathbb{R}\}$. For this extremely simple feasible set, most penalty functions (e.g., those studied in [1]) give the same sets of optimizers, those described by

$$ \operatorname{argmin}\{F(x, y) \mid y = \text{constant}\}. \quad (3) $$
Depending on whether the penalties are internal or external, $y$ will assume positive or negative values. We consider here the case of interior point methods and parameterize the central path by $y > 0$:

$$y \in \mathbb{R}_{++} \mapsto \chi(y) = \underset{x \in \mathbb{R}}{\operatorname{argmin}} F(x, y). \qquad (4)$$

We denote by {$e^1, e^2$} the canonical basis of $\mathbb{R}^2$.

### 3 Examples with continuous objectives

Let us start with two simple examples of problems with obvious central paths.

**Example 1** The function $F$ is defined by $(x, y) \in \mathbb{R}^2 \mapsto F(x, y) = ay + b$, where $a > 0$ and $b \in \mathbb{R}$. In this case, $\chi(y) = \mathbb{R}$ for any $y > 0$. □

**Example 2** The function $F$ is defined by $(x, y) \in \mathbb{R}^2 \mapsto F(x, y) = ay + b + \varepsilon x$, where $a > 0$, $b$ and $\varepsilon \in \mathbb{R}$, with $\varepsilon \neq 0$. Now, $\chi(y) = \emptyset$ for any $y > 0$. □

We now perturb the functions in Examples 1 and 2 to obtain the first non-trivial example. Let $y_k > 0$ be a given number (the index $k \in \mathbb{N}$ will be useful in a moment) and define the function $g_k^0$ by

$$z = (x, y) \in \mathbb{R}^2 \mapsto g_k^0(x, y) = \frac{1}{2} (\|z - z_k^-\| + \|z - z_k^+\| - 2), \qquad (5)$$

where $\| \cdot \|$ denotes the 2-norm, and

$$z_k^- = (-1, y_k) \quad \text{and} \quad z_k^+ = (1, y_k).$$

Function $g_k^0$ is convex. Its set of minimizers is the segment

$$[z_k^-, z_k^+] = \{(1-t)z_k^- + tz_k^+ : t \in [0, 1]\},$$

on which $g_k^0$ takes the value 0. This function is also differentiable everywhere but at the points $z_k^-$ and $z_k^+$. Note that, since $\| \cdot \| \le \| \cdot \|_1$ (the 1-norm), $g_k^0(x, y) \le \frac{1}{2}(|x - 1| + |x + 1| + 2|y - y_k| - 2)$, so that

$$g_k^0(x, y) \le \begin{cases} |y - y_k| & \text{if } |x| \le 1, \\ |x| + |y - y_k| - 1 & \text{otherwise.} \end{cases} \qquad (6)$$

In our constructions, we use convex functions $g_k$ that are smoothings of $g_k^0$, satisfying

$$0 \le g_k(z) \le g_k^0(z), \qquad (7)$$

for $z$ in a large region.

We can now give our first non trivial example, the function $f_k$. It is obtained by adding to the function of Example 2 (with $a$, $b$, and $\varepsilon$ indexed by $k$), the convex perturbation function $g_k$ just described, multiplied by a positive constant $c_k$, and the constant $-a_k y_k$.
**Example 3** Let $a_k, b_k, c_k$, and $y_k$ be positive parameters and $\varepsilon_k \in \mathbb{R}$. Then, function $f_k$ is defined by

$$z \in \mathbb{R}^2 \mapsto f_k(z) = a_k(y - y_k) + b_k + c_k g_k(z) + \varepsilon_k x. \quad (8)$$

where the convex function $g_k : \mathbb{R}^2 \to \mathbb{R}$ satisfies (7) with $g_k^0$ given by (5). □

To get familiar with function $f_k$, which will be used continually, consider two particular cases with $g_k \equiv g_k^0$.

* If $\varepsilon_k = 0$, we have Example 1 with an added perturbation $c_k g_k^0(\cdot)$. Let $c_k$ be positive, but small enough such that problem (2) has its solutions on the x-axis. We easily see using (4) that for any $y > 0$, $\chi(y) = \{0\}$ if $y \neq y_k$, and $\chi(y_k) = [-1, +1]$. The central path is the cross, depicted on the left in Figure 1.

* Suppose now that $\varepsilon_k$ is nonzero, but small in module, $|\varepsilon_k| < c_k$ say. For $y \neq y_k$, $x \mapsto f_k(x, y)$ is strictly convex with compact level sets, so that $\chi(y)$ is a singleton. Suppose now that $y = y_k$. Observe that $f'_k(z_k^-; -e^1) = c_k - \varepsilon_k$, $f'_k(z_k^-; e^1) = \varepsilon_k$, $f'_k(z_k^+; -e^1) = -\varepsilon_k$, and $f'_k(z_k^+; e^1) = c_k + \varepsilon_k$. Therefore, the inequality $|\varepsilon_k| < c_k$ implies that $\chi(y_k) = \{-1\}$ if $\varepsilon_k > 0$ and $\chi(y_k) = \{+1\}$ if $\varepsilon_k < 0$. The central path is perturbed sideways, like on the right in Figure 1: the path deviates to the left or to the right respectively if $\varepsilon_k > 0$ or $\varepsilon_k < 0$.

<figure><img src="image_3.png" /><figcaption>Figure 1: The central path for Example 3 with $g_k = g_k^0$, and $\varepsilon_k = 0$ (left) or $\varepsilon_k > 0$ (right)</figcaption></figure>

The remarkable examples of this paper are constructed with infinitely many copies of the function $f_k$, defined in Example 3, with various coordinates $y_k$ and coefficients $a_k$, $b_k$, $c_k$, and $\varepsilon_k$. These functions are tangent to a support function $(x, y) \in \mathbb{R} \times [-0.5, 1] \mapsto \psi(y)$, where $\psi : [-0.5, 1] \to \mathbb{R}$ has the following properties:

$$\left\{ \begin{array}{l} \psi \text{ is continuously differentiable,} \\ \psi(y) = 0, \text{ for } y \in [-0.5, 0], \\ y \in [0, 1] \mapsto \psi(y) \text{ is strictly convex.} \end{array} \right. \quad (9)$$
Clearly, these properties imply that $\psi(y) > 0$ and $\psi'(y) > 0$ for all $y \in (0,1]$. The functions $f_k$ are tangent to the support function $\psi$ in the sense that the coefficients $a_k$ and $b_k$ are chosen using the slope and value of $\psi$ at $y_k$, as below:

$$y_k = 2^{-k}, \quad a_k = \psi'(y_k), \quad \text{and} \quad b_k = \psi(y_k). \qquad (10)$$

From the assumptions (9) made on $\psi$, the sequences $\{y_k\}$, $\{a_k\}$, and $\{b_k\}$ are positive, decreasing, and converge to zero, when $k \to \infty$.

We still have some freedom for the determination of each $f_k$, due to the unspecified parameters $c_k > 0$ and $\varepsilon_k$, and the function $g_k$. The parameters $c_k$ and $\varepsilon_k$ will be fixed to control the overlapping of two consecutive functions $f_k$ and $f_{k-1}$, in order to get particular properties of the central path; while the function $g_k$ will be an appropriate modification of $g_k^0$ to get smoothness properties.

The fine control of the objective function in the next examples need only to be done in the closed rectangle of $\mathbb{R}^2$ defined by

$$\Omega = \{(x, y) \in \mathbb{R}^2 \mid |x| \le 1.5, \ -0.5 \le y \le 1\}. \qquad (11)$$

For example, smoothness results will be proved for points in $\Omega$ only. These properties can easily be extended to the whole $\mathbb{R}^2$, by a procedure shown at the end of the paper (in Section 7). At places, we shall pay attention to particular properties satisfied in the horizontal strips of $\Omega$, defined for $k = 1, 2, \dots$ by

$$\Omega_k = \{(x, y) \in \Omega \mid y \in [y_k, y_{k-1}]\}. \qquad (12)$$

Our main concern now is to define the perturbation parameters $c_k$, and next $\varepsilon_k$. Let us examine two consecutive functions $f_{k-1}$ and $f_k$, for some index $k \ge 1$ (see Figure 2).

<figure><img src="image_4.png" /><figcaption>Figure 2: Choice of the coefficients of function $f_k$</figcaption></figure>
We want the functions $f_{k-1}$ and $f_k$ to “cross” in the strip $\Omega_k$, with a positive slack $r_k$ at $y_k$ and $y_{k-1}$ between the linearized models (see Figure 2). The slack $r_k$ must satisfy

$$ 
\begin{aligned}
r_k &\le b_k - (b_{k-1} + a_{k-1}(y_k - y_{k-1})), \\
r_k &\le b_{k-1} - (b_k + a_k(y_{k-1} - y_k)).
\end{aligned}
$$

These inequalities are compatible with the positivity of $r_k$, since the right hand sides are positive by the strict convexity of $\psi$ on $[0, 1]$. Our choice for $r_k$, $k \ge 1$, is:

$$ r_k = \frac{1}{2} \min \{b_k - (b_{k-1} + a_{k-1}(y_k - y_{k-1})), b_{k-1} - (b_k + a_k(y_{k-1} - y_k))\}. \quad (13) $$

Therefore, $\{r_k\}$ is positive and tends to zero, when $k \to \infty$. Now, one sets for $k \ge 0$ (to start the induction, set $r_0 = +\infty$ and $\varepsilon_{-1} = +\infty$):

$$ c_k = \frac{1}{4} \min\{r_k, r_{k+1}\} \quad (14) $$

either $\varepsilon_k = 0$ or $\varepsilon_k = (-1)^k |\varepsilon_k|$, with $0 < |\varepsilon_k| \le \min\{c_k/4, |\varepsilon_{k-1}|\}$.

Therefore, either the sequence $\{|\varepsilon_k|\}$ is identically zero or it is positive and nonincreasing. Note that $r_k \le b_{k-1}/2$. Hence $r_{k+1} \le b_k/2$ and

$$ |\varepsilon_k| \le \frac{c_k}{4} \le \frac{r_{k+1}}{16} \le \frac{b_k}{32}. \quad (15) $$

We can now specify our 4th example of objective function.

**Example 4** Let $\psi: [-0.5, 1] \to \mathbb{R}$ be a function satisfying (9) and let the functions $f_k$, $k \in \mathbb{N}$, be defined as in Example 3, with $y_k$ and the coefficients $a_k$, $b_k$, $c_k$, $\varepsilon_k$ satisfying (10), (13), and (14). The convex functions $g_k$ are unspecified, but must satisfy (7) on $\Omega$. The objective function $F$ is then defined for $z \in \Omega$ by

$$ F(z) = \sup_{k \in \mathbb{N}} f_k(z). \quad (16) $$

<figure><img src="image_5.png" /></figure>

In the rest of this section, we highlight some interesting features of the objective function $F$ introduced in Example 4, including the shape of its central path. We start with an overlapping property of two successive functions $f_{k-1}$ and $f_k$, which implies that these functions cross in the strip $\Omega_k$.

**Lemma 1** Let the functions $f_k$ and the parameters $r_k$ be as in Example 4. Then, for $k \ge 1$ and $(x, y) \in \Omega$:

$$ f_{k-1}(x, y) \le f_k(x, y) - r_k \quad \text{if} \quad y \le y_k \quad (17) $$

and

$$ f_k(x, y) \le f_{k-1}(x, y) - r_k \quad \text{if} \quad y \ge y_{k-1}. \quad (18) $$
Proof. Let $(x, y) \in \Omega$, with $y \le y_k$. Since $g_{k-1} \le g_{k-1}^0$, $|x| \le 1.5$ and $|y - y_{k-1}| \le 1.5$, (6) gives us $g_{k-1}(z) \le 2$, so that

$$f_{k-1}(x, y) \le a_{k-1}(y - y_{k-1}) + b_{k-1} + 2c_{k-1} + 1.5|\varepsilon_{k-1}|. \quad (19)$$

On the other hand,

$$\begin{aligned} f_k(x, y) &\ge a_k(y - y_k) + b_k - |\varepsilon_k| |x| \\ &\ge a_{k-1}(y - y_k) + b_{k-1} - 1.5 |\varepsilon_k|, \end{aligned} \quad (20)$$

because $a_k \le a_{k-1}$, $y \le y_k$ and $g_k(\cdot) \ge 0$. Grouping (19) and (20):

$$\begin{aligned} f_k(x, y) - f_{k-1}(x, y) &\ge a_{k-1}(y_{k-1} - y_k) + b_k - b_{k-1} - 2c_{k-1} - 1.5|\varepsilon_k| - 1.5|\varepsilon_{k-1}|. \end{aligned}$$

We have $|\varepsilon_k| \le |\varepsilon_{k-1}| \le \frac{r_k}{16}$ and $c_{k-1} \le \frac{r_k}{4}$. Hence, using (13),

$$f_k(x, y) - f_{k-1}(x, y) \ge 2r_k - \frac{1}{2}r_k - \frac{3}{16}r_k \ge r_k.$$

This completes the proof of (17). The proof of (18) is similar. □

**Lemma 2** Let the functions $f_k$ and $F$ be defined as in Example 4, and $z = (x, y) \in \Omega$. Then $\lim_{k \to \infty} f_k(z) = 0$. In addition:

(i) $F(x, y) = 0$, if $y \le 0$;

(ii) $F(z) = \max\{f_{k-1}(z), f_k(z)\}$, if $z \in \Omega_k$;

(iii) $F(x, y_k) = f_k(x, y_k)$, if $(x, y_k) \in \Omega$.

Proof. Let $z = (x, y) \in \Omega$. Then $\lim_{k \to \infty} f_k(z) = 0$, since $g_k$ satisfies (7) on $\Omega$, $g_k^0$ is bounded by 2 on $\Omega$, and all the coefficients of $f_k$ converge to 0.

(i) If $y \le 0$, from Lemma 1, $f_k(z)$ increases with $k$. Hence $F(z) = \sup_k f_k(z) = \lim_{k \to \infty} f_k(z) = 0$.

(ii) and (iii) follow immediately from Lemma 1. □

**Lemma 3** The objective function $F$ defined in Example 4 is convex and continuous on $\Omega$. Let $k \ge 1$ and assume that $g_k \equiv g_k^0$. Then

$$\underset{|x| \le 1.5}{\operatorname{argmin}} F(x, y_k) = \begin{cases} [-1, 1] & \text{if } \varepsilon_k = 0, \\ \{(-1)^{k+1}\} & \text{otherwise.} \end{cases} \quad (21)$$

Furthermore, for $y \in (y_k, y_{k-1})$, $\underset{|x| \le 1.5}{\operatorname{argmin}} F(x, y)$ is reduced to a single point. This point is $x = 0$ when $\varepsilon_k = \varepsilon_{k-1} = 0$.

Proof. Function $F$ is clearly convex, since it is the supremum of the convex functions $f_k$. On the other hand, the functions $f_k$ are bounded on $\Omega$ (by $1.5 a_0 + b_0 + 2 \bar{c} + 1.5 \varepsilon_0$, where $\bar{c}$ is a bound on $\{c_k\}$), hence so is $F$. As a bounded convex function, $F$ is continuous.
When $g_k \equiv g_k^0$ and $y = y_k$, we can use the properties of the function $f_k$ given after Example 3 (note that $|\epsilon_k| < c_k$). If $\epsilon_k = 0$, $\chi(y_k) = [-1, +1]$; if $\epsilon_k > 0$, $\chi(y_k) = \{-1\}$; and if $\epsilon_k < 0$, $\chi(y_k) = \{+1\}$. This leads to formula (21).

Consider now the case when $g_k \equiv g_k^0$ and $y \in (y_k, y_{k-1})$. If $\epsilon_k = \epsilon_{k-1} = 0$, $f_k(\cdot, y)$ and $f_{k-1}(\cdot, y)$ are both minimized at $x = 0$, hence so is $F(\cdot, y)$. If $\epsilon_k \neq 0$, since $F(\cdot, y)$ is strictly convex (maximum of two strictly convex functions), it has still a unique minimizer at some $x \in (-1.5, 1.5)$. $\square$

Suppose that $g_k \equiv g_k^0$ in Example 4. We deduce from Lemma 3 the behavior of the central path, shown in Figure 3. If $\epsilon_k = 0$, the path looks like an antenna with an infinity of branches (left picture). Otherwise, the path visits alternately the points $z_k^-$, when $k$ is even, and $z_k^+$, when $k$ is odd (right picture). This results in a zig-zag with infinite variation. In this case, the path is a continuous curve for $\mu > 0$. This is because the set-valued map $\mu \in \mathbb{R}_{++} \mapsto \chi(\mu)$ is always outer semicontinuous (in the sense of Rockafellar and Wets [24, Section 5.B]): if $\mu \to \bar{\mu} > 0$ and some $x_\mu \in \chi(\mu) \to \bar{x}$ then $\bar{x} \in \chi(\bar{\mu})$ (to see this, just take the limit in $f(x_\mu) + \mu p(x_\mu) \le f(x) + \mu p(x)$, for an arbitrary $x$). The continuity of the central path now results from the fact that $\chi(\mu)$ is a singleton and that the central path is in a bounded set, $\Omega$ actually.

<figure><img src="image_6.png" /><figcaption>Figure 3: Central paths for a $C^0$ objective function: the antenna and the zig-zag patterns</figcaption></figure>

# 4 Smoothing operations

Our aim now is to smooth the objective function $F$ introduced in Example 4, without modifying the layout of the central paths obtained for $\epsilon_k = 0$ (antenna) and $\epsilon_k \neq 0$ (zig-zag). A close examination of the construction of $F$ shows that to reach this goal, it is necessary to smooth the elementary functions $f_k$ introduced in (8), which in turn requires the smoothing of $g_k^0$, and the “sup” operator appearing in (16).

Let us first consider the smoothing of the elementary functions $f_k$. For this, we construct $g_k$ in formula (8) as a smooth approximation of the only continuous function $g_k^0$ given by (5). The analysis of Section 3 has shown that the lemmas involving $g_k$ remain true if that function takes nonnegative values not exceeding those of $g_k^0$; see condition (7). In other words, this smoothing operation has to be done from below,
by decreasing $g_k^0$. The reason is that for $\varepsilon_k = 0$ the horizontal segment of the central path will remain central, while for $\varepsilon_k \neq 0$ the central path will do even larger loops. Therefore, the weird pattern of the previous central paths will be preserved.

The second smoothing operation deals with the “sup” appearing in (16). Lemma 3 has shown us that the sup-operator, which takes a priori all the functions $f_k$ into account, involves in fact only two successive elementary functions in each strip $\Omega_k: f_k$ and $f_{k-1}$. Therefore if we smooth the maximum of two convex functions, by modifying the result of the max-operator only when these two functions have close values, the function $F$ will be again evaluated strip by strip and its smoothness will be ensured for $y > 0$ (its smoothness near $y = 0$ will result from a direct argument). In order to make this strategy successful, the smoothing of the sup-operator needs to be done from above, by increasing the values of $\max\{f_1, f_2\}$.

## 4.1 Smoothing the maximum of two functions

Let us start by introducing a procedure to smooth the maximum of two real-valued convex functions $f_1$ and $f_2$ defined on $\mathbb{R}^n$, both of class $C^q$. Here and below, $q$ is either a nonnegative integer or $q = \infty$. The maximum of $f_1$ and $f_2$ is denoted by $f_{\max}$:

$$z \in \mathbb{R}^n \mapsto f_{\max}(z) = \max\{f_1(z), f_2(z)\}.$$

This function is in general only continuous but it can be smoothed in a simple way, by rounding it around its kinks, with no changes far from it, as required by the discussion above. Since, for $t_1$ and $t_2 \in \mathbb{R}$, $\max\{t_1, t_2\} = \frac{1}{2}(t_1 + t_2 + |t_1 - t_2|)$, the max-function can be smoothed by introducing a smooth approximation of the absolute value. This is the track we follow.

Let $\varphi: \mathbb{R} \to \mathbb{R}$ be a convex function of class $C^q$, with the following property:

$$\varphi(w) = |w|, \quad \text{for } |w| \ge 1. \qquad (22)$$

An example of such a function is given in the left picture in Figure 4 and a concrete construction is detailed in Section 4.2. Function $\varphi$ is a $C^q$ version of the absolute value that does not modify it for $|w| \ge 1$. It will be necessary to make this approximation more and more precise. Let $r > 0$ be a scalar measuring the precision of the approximation, which increases when $r \to 0$, and consider the convex function $\varphi_r: \mathbb{R} \to \mathbb{R}$ defined by

$$\varphi_r(w) = r \varphi\left(\frac{w}{r}\right), \quad \text{for all } w \in \mathbb{R}. \qquad (23)$$

Of course $\varphi_r$ is convex and $\varphi_r(w) = |w|$ for $|w| \ge r$. It follows from the convexity of $\varphi_r$ that, for any $w$ and $w' \in \mathbb{R}$:

$$|w| \le \varphi_r(w) \le \varphi_r(w') + |w - w'|. \qquad (24)$$

Given $r > 0$, we introduce the function $M_r: \mathbb{R}^2 \to \mathbb{R}$

$$M_r(t_1, t_2) = \frac{1}{2}(t_1 + t_2 + \varphi_r(t_1 - t_2)), \qquad (25)$$
which is a smooth version of the max-function. It is therefore natural to approximate the function $f_{\max}$ by (see the picture on the right in Figure 4):

$$z \in \mathbb{R}^n \mapsto f(z) = M_r(f_1(z), f_2(z)). \qquad (26)$$

<figure><img src="image_7.png" /><figcaption>Figure 4: Smoothing of the absolute value and of the maximum of two convex functions</figcaption></figure>

The next lemma claims that $M_r$ is convex and increasing, while Lemma 5 shows in what sense the function $f$ defined by (26) is a convex smoothing of the maximum function.

**Lemma 4** The function $M_r$ defined by (25) is convex and increasing: if $t_1 \le t'_1$ and $t_2 \le t'_2$, then $M_r(t_1, t_2) \le M_r(t'_1, t'_2)$.

*Proof.* The convexity of $M_r$ is a clear consequence of that of $\varphi_r$. For the monotonicity, use (24):

$$ \begin{aligned} M_r(t'_1, t'_2) &= \frac{1}{2}(t'_1 + t'_2 + \varphi_r(t'_1 - t'_2)) \\ &\ge \frac{1}{2}(t'_1 + t'_2 + \varphi_r(t_1 - t_2) - |(t'_1 - t'_2) - (t_1 - t_2)|) \\ &\ge \frac{1}{2}(t'_1 + t'_2 + \varphi_r(t_1 - t_2) - (t'_1 - t'_1) - (t'_2 - t_2)) \\ &= M_r(t_1, t_2). \end{aligned} $$

<figure><img src="image_8.png" /></figure>

**Lemma 5** Let $f_1$ and $f_2$ be two convex functions of class $C^q$, with $0 \le q \le \infty$, and $f_{\max} = \max\{f_1, f_2\}$. Consider the function $f$ defined by (26), where $M_r$ is constructed as above, with a function $\varphi$ of class $C^q$. Then

(i) $f$ is convex,

(ii) $f$ is of class $C^q$,

(iii) $z \in \mathbb{R}^n$, $|f_1(z) - f_2(z)| \ge r \implies f(z) = f_{\max}(z)$,

(iv) for any $z \in \mathbb{R}^n$, $f_{\max}(z) \le f(z) \le f_{\max}(z) + r/2$.
Proof. (i) The convexity of $f$ follows from that of $f_1$ and $f_2$ and from the convexity and monotonicity of $M_r$ provided by Lemma 4.

(ii) This follows from the fact that $f_1, f_2, \varphi, \varphi_r$, and $M_r$ are all of class $C^q$.

(iii) Let $z \in \mathbb{R}^n$ and set $\Delta f = f_1(z) - f_2(z)$. If $|\Delta f| \ge r$, then from the definition of $\varphi_r$, one has $\varphi_r(\Delta f) = |\Delta f|$. Hence

$$f(z) = \frac{1}{2} (f_1(z) + f_2(z) + |f_1(z) - f_2(z)|) = f_{\max}(z).$$

(iv) From (24) with $w' = 0$ and $w \in \mathbb{R}$, $|w| \le \varphi_r(w) \le |w| + r$. Then, according to (26):

$$\frac{1}{2} (f_1(z) + f_2(z) + |\Delta f|) \le f(z) \le \frac{1}{2} (f_1(z) + f_2(z) + |\Delta f| + r),$$

which is (iv).

<figure><img src="image_9.png" /></figure>

## 4.2 Examples of $C^1$ and $C^\infty$ smoothing

In this section, we discuss the construction of a class of smoothing functions by integrating twice a probability density function. This smoothing technique is proposed by Chen and Mangasarian in [5] and [6]. We start with a probability density function $w \in \mathbb{R} \mapsto \sigma(w) \in \mathbb{R}$ with compact support:

$$\sigma(w) \ge 0, \quad \int_{-\infty}^{+\infty} \sigma(w) dw = 1, \quad \text{and} \quad \sigma(w) = 0, \text{ for } w \notin (0, 1).$$

Define $\bar{\varphi}$ by integrating $\sigma$ twice:

$$w \in \mathbb{R} \mapsto \bar{\varphi}(w) = \int_{-\infty}^{w} \int_{-\infty}^{t} \sigma(\tau) d\tau dt.$$

Let $c = 1 - \bar{\varphi}(1)$. Since $\bar{\varphi}'(w) = 0$ for $w \le 0$, and $\bar{\varphi}'(w) \le 1$ for all $w \in [0, 1]$, then $\bar{\varphi}(1) \le 1$ and $c \ge 0$. The smoothing function $\varphi: \mathbb{R} \to \mathbb{R}$ is the symmetrization of $\bar{\varphi}$, defined by

$$\varphi(w) = \bar{\varphi}(|w|) + c. \qquad (27)$$

This function is convex and satisfies (22). Its smoothness depends on that of $\sigma$.

We now provide two examples. The first one is based on the pulse function defined below and will be used in Section 5:

$$\sigma(w) = \begin{cases} 1 & \text{if } w \in [0, 1], \\ 0 & \text{otherwise.} \end{cases}$$

Integrating twice this pulse function, we obtain a continuously differentiable smoothing function

$$\varphi(w) = \begin{cases} \frac{1}{2}w^2 + \frac{1}{2} & \text{if } w \in [-1, 1], \\ |w| & \text{otherwise.} \end{cases} \qquad (28)$$
<figure><img src="image_10.png" /><figcaption>Figure 5: Smoothing function obtained by twice integrating the pulse function</figcaption></figure>

The second example, used in Section 6, is a smoothing function of class $C^\infty$ but not analytic. To obtain this example, consider initially a classical example of a non-analytic function of class $C^\infty$ (see [12, page 51]) defined by

$$ w \in \mathbb{R} \mapsto \theta(w) = \begin{cases} e^{-1/w^2} & \text{if } w > 0, \\ 0 & \text{if } w \le 0. \end{cases} \qquad (29) $$

For $w \neq 0$ and $q \in \mathbb{N}$, the $q$th order derivatives $\theta^{(q)}(w)$ can be computed by elementary calculus. For $w < 0$, $\theta^{(q)}(w) = 0$; while for $w > 0$, $\theta^{(q)}(w)$ is a polynomial of degree $3q$ in $w^{-1}$, times $\theta(w)$. It is known that

$$ \lim_{w \to 0} \frac{1}{w^p} \theta(w) = 0, \quad \forall p \in \mathbb{N}, \qquad (30) $$

so that $\theta^{(q)}(0) = 0$, for any $q \in \mathbb{N}$. Now, define

$$ w \in \mathbb{R} \mapsto \sigma(w) = \beta\theta(w)\theta(1-w) \qquad (31) $$

where $\beta > 0$ is such that

$$ \int_{-\infty}^{+\infty} \sigma(w) dw = 1. $$

This is a probability density function, with derivatives of any order that vanish out of $[0, 1]$. Finally the non-analytic smoothing function $\varphi$ of class $C^\infty$ is obtained by twice integrating this density function.

# 5 A continuously differentiable example

Our 5th example is constructed by specifying some of the parameters that remained free in Example 4, with the aim at making the resulting function $F$ of class $C^1$. Let us
first specify the functions $g_k : \Omega \to \mathbb{R}$, for $k \in \mathbb{N}$, obtained by smoothing the functions $g_k^0$ defined in (5): for $z = (x, y) \in \Omega$,

$$g_k(z) = \frac{1}{4} (g_k^0(z))^2. \qquad (32)$$

**Lemma 6** The function $g_k$ defined by (32), with $g_k^0$ given in (5), is convex, continuously differentiable, and satisfies (7) on $\Omega$.

*Proof.* The function $g_k^0$ is convex and takes nonnegative values, and $t \in \mathbb{R}_+ \mapsto t^2/4$ is convex and increasing. Therefore, $g_k$ is convex.

On the other hand, $g_k^0$ is of class $C^\infty$ near any $z \in \Omega \setminus \{z_k^-, z_k^+\}$. Hence, the same is true for $g_k$. We now analyze the smoothness of $g_k$ at $z_k^+$, knowing that the argument is similar at $z_k^-$. The function $g_k$ is differentiable at $z_k^+$ if its subdifferential is reduced to a singleton (see [16, Section VI.2.1]). From [16, theorem VI.6.3.1], we know that $\partial g(z_k^+)$ is the convex hull of the set of limits of convergent sequences $\nabla g(z^j)$ for $z^j \to z_k^+$, $z^j \notin \{z_k^-, z_k^+\}$. Consider such a sequence $(z^j) \subset \Omega$. We have $\nabla g_k(z^j) = \frac{1}{2}g_k^0(z^j)\nabla g_k^0(z^j)$. Since $\|\nabla g_k^0(z^j)\|$ is bounded by 1 and $g_k^0(z^j) \to 0$, we deduce that $\lim_{j \to \infty} \nabla g_k(z^j) = 0$. Hence $\partial g_k(z_k^+) = \{0\}$.

To conclude, note that $g_k$ satisfies (7) on $\Omega$, since by (6), $g_k^0(z) \le 2$ on that set. $\square$

We now describe our 5th example.

**Example 5** Function $F: \Omega \to \mathbb{R}$ is made from the following ingredients.

* The support function $\psi: [-0.5, 1] \to \mathbb{R}$ is defined for $y \in [-0.5, 1]$ by

$$\psi(y) = \frac{1}{2} (\max \{0, y\})^2. \qquad (33)$$

Conditions in (9) are satisfied.

* For $k \in \mathbb{N}$, $g_k$ is the function defined by (32), where $g_k^0$ is given by (5). According to Lemma 6, $g_k$ is a convex $C^1$ function satisfying (7).

* The elementary functions $f_k$, $k \in \mathbb{N}$, are then defined by (8) (as in Example 3), with coordinate $y_k$ and coefficients $a_k$, $b_k$, $c_k$, and $\varepsilon_k$ satisfying (10), (13), and (14).

* The smoothing function $\varphi$ is given by (28).

The objective function $F$ is now constructed by a recursive process.

* Set $F_0(z) = f_0(z)$, for all $z \in \Omega$.

* For $k = 1, 2, \dots$, set

$$F_k(z) = M_{r_k} (f_k(z), F_{k-1}(z)), \quad \text{for all } z \in \Omega, \qquad (34)$$

where $r_k$ is defined by (13), and $M_{r_k}$ is defined by (23) and (25).
Then $F$ is obtained as the pointwise limit of the functions $F_k$:

$$F(z) = \lim_{k \to \infty} F_k(z), \quad \forall z \in \Omega. \qquad (35)$$

<figure><img src="image_11.png" /></figure>

The next lemma gives some elementary properties of the functions $F_k$ and $F$. We denote by $\text{int} \Omega = \{(x, y) \in \mathbb{R}^2 : |x| < 1.5, -0.5 < y < 1\}$ the interior of the set $\Omega$.

**Lemma 7** Let $k \in \mathbb{N}$. The function $F_k$ defined in Example 5 is convex and continuously differentiable on $\text{int} \Omega$. Furthermore:

(i) $F(z) = F_{k+i}(z)$, if $i \in \mathbb{N}$ and $z = (x, y) \in \Omega$ with $y \ge y_k$;

(ii) $F_k(z) = f_k(z)$, if $z = (x, y) \in \Omega$ and $y \le y_k$;

(iii) $F(z) = 0$, if $z = (x, y) \in \Omega$ and $y \le 0$;

(iv) $F(z) = F_k(z) = M_{r_k}(f_k(z), f_{k-1}(z))$, if $z \in \Omega_k$.

*Proof.* Convexity and differentiability are proven by induction. According to (8) and Lemma 6, $F_0 = f_0$ is convex and $C^1$. Suppose now that $k \ge 1$ and that $F_{k-1}$ is convex and $C^1$. Since $f_k$ is convex and $C^1$ (like $f_0$), then (34), the fact that $\varphi$ is $C^1$, and Lemma 5 show that $F_k$ is also convex and $C^1$.

(i) From Lemma 5(iv) and definition (34): $F_k \ge f_k$. For $z \in \Omega$ with $y \ge y_k$, Lemma 1 gives us

$$F_k(z) \ge f_k(z) \ge f_{k+1}(z) + r_{k+1}.$$

Based on Lemma 5(iii) and definition (34), we have $F_{k+1}(z) = F_k(z)$.

For the same $z \in \Omega$, one has $y \ge y_k \ge y_{k+1}$, so that the result just proven shows that $F_{k+2}(z) = F_{k+1}(z) = F_k(z)$. By induction, $F_{k+i}(z) = F_k(z)$, for any $i \in \mathbb{N}$. The definition (35) of $F$ now leads to the result.

(ii) By induction: by definition $F_0 = f_0$. Assume now that (ii) holds for $k-1$, with $k \ge 1$, and let $z \in \Omega$ be such that $y \le y_k$. By induction and Lemma 1:

$$F_{k-1}(z) = f_{k-1}(z) \le f_k(z) - r_k.$$

Hence, according to Lemma 5(iii) and the definition (34), we have $F_k(z) = f_k(z)$.

(iii) For $z = (x, y) \in \Omega$ with $y \le 0$, $F(z) = \lim_{k \to \infty} F_k(z)$ [by (35)] = $\lim_{k \to \infty} f_k(z)$ [by point (ii)] = 0 [by Lemma 2].

(iv) Consider $z \in \Omega_k$; hence $y \in [y_k, y_{k-1}]$. From point (ii) and $y \le y_{k-1}$, $F_{k-1}(z) = f_{k-1}(z)$, so that the definition (34) leads to

$$F_k(z) = M_{r_k}(f_k(z), f_{k-1}(z)).$$

On the other hand, $F(z) = F_k(z)$ by point (i).

<figure><img src="image_12.png" /></figure>

The lemma above shows that the recursive construction is in fact not needed. The function $F$ can be defined simply by applying (iv) for $k \in \mathbb{N}$. Denote by $\bar{f} = \sup_{k \in \mathbb{N}} f_k$
the objective function of Example 4 with the data of Example 5. Then Lemma 7(iv) and Lemma 5(iv) yield

$$ \bar{f}(z) \leq F(z) \leq \bar{f}(z) + r_k/2, \quad \text{for } z \in \Omega_k. \qquad (36) $$

This shows that function F is a smoothing of $\bar{f}$. The smoothing process rounds up the kinks within each strip $\Omega_k$, and the smoothing of each kink does not affect the others.

**Lemma 8** The function F constructed in Example 5 is convex and continuously differentiable on $\text{int}\,\Omega$.

*Proof.* We know from Lemma 7(iii) that $F(x, y) = 0$ if $y \le 0$. Hence F is convex and $C^1$ on $\Omega_-= \{(x, y) \in \text{int}\,\Omega \mid y < 0\}$.

Let us now show that F is convex and $C^1$ on $\Omega_+ = \{(x, y) \in \text{int}\,\Omega \mid y > 0\}$. Let $k \in \mathbb{N}$. By Lemma 7, $F(z) = F_k(z)$ in the open set $O_k = \{(x, y) \in \text{int}\,\Omega \mid y > y_k\}$, so that F is convex and smooth on this set. Since k is arbitrary and $\Omega_+ = \cup_{k \in \mathbb{N}} O_k$, F is convex and smooth on $\Omega_+$.

Note that F is continuous on $\Omega$. Indeed by Lemmas 2 and 3, $\bar{f}$ vanishes on $\Omega_-$ and is continuous on $\Omega$, so that (36) implies the continuity of F at any point $(x, 0) \in \Omega$. To show the convexity of F, consider two points $z \in \Omega_-$ and $z' \in \Omega_+$, and a scalar $t \in [0, 1]$. Since F vanishes on $\Omega_-$, it is enough to show that $F((1-t)z + tz') \le tF(z')$. This inequality clearly holds if $(1-t)z + tz' \in \Omega_-$, since then the left hand side vanishes and $F(z') \ge 0$ (use (36) and the non-negativity of $\bar{f}$ on $\Omega_+$). Otherwise, let $z''$ be the point in $[z, z']$ such that $(z'')^\top e^2 = 0$. Then $(1-t)z + tz' = (1-t')z'' + t'z'$ for some $t' \in [0, t]$. Since F is nonnegative and convex on the closure of $\Omega_+$ [16, proposition IV.1.2.6] and $F(z'') = 0$, one deduces $F((1-t)z + tz') = F((1-t')z'' + t'z') \le t'F(z') \le tF(z')$.

We still have to prove that F is $C^1$ at an arbitrary point $z = (x, 0)$ with $-1.5 < x < 1.5$. It is enough to show that $\partial F(z) = \{0\}$. Let $\delta \in \partial F(z)$. Along any direction $h = (h_1, h_2)$ such that $h_2 \le 0$ we must have $F'(z, h) = 0$, because F vanishes on the closure of $\Omega_-$. For $h = (0, -1)$, $0 = F'(z, h) \ge \delta^\top h = -\delta_2$. Hence $\delta_2 \ge 0$. For $h = (\pm 1, 0)$, $0 = F'(z, h) \ge \delta^\top h = \pm \delta_1$. Hence $\delta_1 = 0$. We conclude that $\delta = (0, \delta_2)$, with $\delta_2 \ge 0$. By convexity,

$$ F(x, y_k) \geq F'((x, 0); (0, y_k)) \geq \delta_2 y_k. \qquad (37) $$

According to Lemma 7, $F(x, y_k) = f_k(x, y_k) \le b_k + c_k g_k(x, y_k) + 1.5 |\varepsilon_k|$. From (15) and the fact that $g_k(x, y_k) \le 0.5$, it follows immediately that $F(x, y_k) \le 2b_k = y_k^2$. Then the limit in (37) implies that $\delta = 0$. $\square$

Lemma 8 shows that the function F constructed in Example 5 is indeed convex and smooth. Let us examine its central path.

For $\varepsilon_k = 0$, the antenna pattern of the central path is preserved, like in example 4. This is essentially a consequence of Lemma 7. Indeed, each segment $[z_k^-, z_k^+]$ belongs to the central path because $F(z) = f_k(z)$ when $z = (x, y_k) \in \Omega$. For $y \in (y_k, y_{k-1})$, we know that both $f_k(\cdot, y)$ and $f_{k-1}(\cdot, y)$ are uniquely minimized at $x = 0$. Then, this is
also the case for $F(\cdot, y) = M_{r_k}(f_k(\cdot, y), f_{k-1}(\cdot, y))$ by the monotonicity property of $M_{r_k}$ (Lemma 4).

Consider now the case when $\varepsilon_k \neq 0$ is computed like in (14). For $y \in (y_k, y_{k-1})$, $F(\cdot, y)$ has a unique minimizer (for the same reasons as above). For $y = y_k$, $F(\cdot, y_k) = f_k(\cdot, y_k)$, and an easy calculation using (8) and (32) yields

$$ \underset{x \in \mathbb{R}}{\operatorname{argmin}} F(x, y_k) = \{(-1)^{k+1}(1 + \tau_k)\}, $$

where $0 < \tau_k = 2|\varepsilon_k|/c_k \le 0.5$. Like in Example 4, the central path is a continuous curve (for $y > 0$) forming a zig-zag with even larger loops.

The antenna and zig-zag central paths for the $C^1$ objective function of example 5 are given in Figure 6 (the zig-zag is the dashed curve).

<figure><img src="image_13.png" /><figcaption>Figure 6: The zig-zag central path for a $C^1$ and a $C^2$ objective functions.</figcaption></figure>

It is possible to modify the ingredients determining the function $F$ in Example 5 to get a smoother objective function. Let $q \ge 2$ be an integer specifying the required degree of smoothness ($q = 1$ in Example 5). The modifications to bring are the following. First, instead of defining $g_k$ by (32), set

$$ g_k(z) = \left( \frac{g_k^0(z)}{2} \right)^{q+1}, \quad \text{for } z \in \Omega. \qquad (38) $$

The support function $\psi: [-0.5, 1] \to \mathbb{R}$ in (33) is now defined by

$$ \psi(y) = \frac{1}{q+1} (\max\{0, y\})^{q+1}, \quad \text{for } y \in [-0.5, 1], \qquad (39) $$

and the smoothing function $\varphi: \mathbb{R} \to \mathbb{R}_+$ in (28) is now obtained as in Section 4.2, starting with the probability density function

$$ \sigma(w) = \begin{cases} \beta w^{q-2} (1-w)^{q-1} & \text{if } w \in [0, 1], \\ 0 & \text{otherwise,} \end{cases} \qquad (40) $$

where $\beta > 0$ is set to have $\int \sigma(w) dw = 1$. It can be shown, using arguments similar to those of Sections 5 and 6 that, with these modifications, the objective function in Example 5 is convex and of class $C^q$.
The next lemma gives conditions ensuring the smoothness of the zig-zag central path. The one corresponding to the $C^2$ objective function, obtained with $q = 2$ in the data above, is the continuous curve in Figure 6.

**Lemma 9** Consider Example 5, in which $g_k = \gamma \circ g_k^0$, where $\gamma: \mathbb{R} \to \mathbb{R}$ is twice differentiable and satisfies $\gamma'(0) = 0$, as well as $\gamma'(t) > 0$ and $\gamma''(t) > 0$ when $t > 0$. Suppose also that the smoothing function $\varphi$ is twice differentiable and that the objective function $F$ is convex and of class $C^q$, with $q \ge 2$. Then, the zig-zag central path is a function of class $C^{q-1}$ of $y > 0$.

*Proof.* The central path is defined by (4), where $\chi$ is a priori multivalued. Since $F$ is convex and differentiable, a point $z = (x, y)$ is on the central path if and only if it satisfies the optimality condition

$$ \nabla_x F(x, y) = 0. $$

We want to show that $\chi$ is single valued and of class $C^{q-1}$. Since $\nabla F$ is $C^{q-1}$, this is a clear consequence of the implicit function theorem, if $\nabla_{xx}^2 F(x, y)$ is nonzero along the zig-zag central path. Actually, we are going to show that $\nabla_{xx}^2 F(x, y) > 0$, which will conclude the proof.

Let $z = (x, y)$, with $y > 0$, be an arbitrary point on the zig-zag central path. Observe that when $\varepsilon_k > 0$:

$$ F'(z_k^-; -e^1) = f_k'(z_k^-; -e^1) = c_k \gamma'(0) (g_k^0)'(z_k^-; -e^1) - \varepsilon_k = -\varepsilon_k < 0. $$

Similarly, when $\varepsilon_k < 0$: $F'(z_k^+; e^1) = \varepsilon_k < 0$. Therefore, $z \notin [z_k^-, z_k^+]$, $g_k^0(z) > 0$, and $g_k^0$ is $C^\infty$ around $z$.

Let us now show that $\nabla_{xx}^2 f_k(z) > 0$ or equivalently, since $c_k > 0$, that $\nabla_{xx}^2 g_k(z) > 0$. By the assumptions and the smoothness of $g_k^0$ around $z$:

$$ \nabla_{xx}^2 g_k(z) = \gamma'(g_k^0(z)) \nabla_{xx}^2 g_k^0(z) + \gamma''(g_k^0(z)) (\nabla_x g_k^0(z))^2. $$

Because $g_k^0(z) > 0$, one has $\gamma'(g_k^0(z)) > 0$ and $\gamma''(g_k^0(z)) > 0$. Also, since $z \notin \{z_k^-, z_k^+\}$:

$$ \nabla_x g_k^0(z) = \frac{1}{2} \left( \frac{x+1}{\|z-z_k^-\|} + \frac{x-1}{\|z-z_k^+\|} \right). $$

This derivative vanishes only if $x = 0$. On the other hand, for $x = 0$:

$$ \nabla_{xx}^2 g_k^0(z) = \frac{(y - y_k)^2}{\|(1, y - y_k)\|^3} $$

This quantity vanishes only if $y = y_k$. Since $(0, y_k)$ is not on the zig-zag central path, one deduces that $\nabla_{xx}^2 g_k(z) > 0$, hence $\nabla_{xx}^2 f_k(z) > 0$.

If $y = y_k$, $F(z) = f_k(z)$ and $\nabla_{xx}^2 F(x, y) = \nabla_{xx}^2 f_k(z) > 0$.

Suppose now that $y \in (y_k, y_{k-1})$. Then, according to Lemma 7(iv)

$$ F(z) = M_{r_k}(f_k(z), f_{k-1}(z)) = \frac{1}{2} \left( f_k(z) + f_{k-1}(z) + \varphi_{r_k}(f_k(z) - f_{k-1}(z)) \right). $$
Therefore

$$ \nabla_{xx}^2 F(x, y) = \frac{1}{2} \left( \begin{aligned} & [1 + \varphi'_{r_k}(f_k(z) - f_{k-1}(z))] \nabla_{xx}^2 f_k(z) + \\ & [1 - \varphi'_{r_k}(f_k(z) - f_{k-1}(z))] \nabla_{xx}^2 f_{k-1}(z) + \\ & \varphi''_{r_k}(f_k(z) - f_{k-1}(z)) [\nabla_x f_k(z) - \nabla_x f_{k-1}(z)]^2 \end{aligned} \right). $$

By construction of $\varphi_r$ in (22)-(23), $|\varphi'_r(t)| \le 1$ for any $t \in \mathbb{R}$. Hence, the three terms in the main parenthesis above are all nonnegative. On the other hand, we have shown that $\nabla_{xx}^2 f_k(z) > 0$ and $\nabla_{xx}^2 f_{k-1}(z) > 0$, and since the factor of each of these two quantities cannot both vanish, one deduces that $\nabla_{xx}^2 F(x, y) > 0$. $\square$

# 6 An example of class $C^\infty$

The construction developed in the previous section is now extended to the case of a $C^\infty$ smoothing, by providing a new specification of the functions $\psi$, $g_k$, and $\varphi$.

**Example 6** Function $F: \Omega \to \mathbb{R}$ is constructed in the same way as in Example 5, with the following modifications.

* The support function $\psi: [-0.5, 1] \to \mathbb{R}$ is now defined for $y \in [-0.5, 1]$ by

$$ \psi(y) = \theta\left(\frac{y}{2}\right), \qquad (41) $$

where $\theta$ is the $C^\infty$ function given in (29)

* The perturbation functions $g_k: \Omega \to \mathbb{R}$, for $k \in \mathbb{N}$, are now obtained by smoothing with $\theta$ the functions $g_k^0$ defined in (5): for $z = (x, y) \in \Omega$,

$$ g_k(z) = g_k^\infty(z) := \theta\left(\frac{1}{3}g_k^0(z)\right). \qquad (42) $$

* The smoothing function $\varphi$ is now the $C^\infty$ function given at the end of Section 4, using function $\theta$ and the probability density function defined by (31).

<figure><img src="image_14.png" /></figure>

Let us motivate the choices made in Example 6. It is easy to check (calculating second derivatives), that $\theta$ is strictly convex on $(0, \sqrt{2/3})$. Therefore, the support function $\psi$ satisfies the conditions in (9). On the other hand, we know by (6) that, for $z \in \Omega$, $0 \le g_k^0(z) \le 2$. Hence, $g_k^\infty$ is convex in $\Omega$, as a composition of a convex nondecreasing function and a convex function. It is easy to check that for $w \ge 0$, $0 \le \theta(w) \le w$. Hence, for $z \in \Omega$, we have $0 \le g_k^\infty(z) \le g_k^0(z)$ and (7) is satisfied.

Our main work in this section is to prove that $F$ is of class $C^\infty$ (its convexity and the behavior of the central paths will result from arguments similar to those in Section 5). For this, we use the following result quoted by Fleming [12, page 50] as a special case of a theorem of Whitney [29].
**Lemma 10** Let $\Omega$ be the closure of an open set $\Omega_0$, and assume that $\Omega$ is convex. Let $\phi$ be of class $C^q$ on $\Omega_0$, for some $q \in \mathbb{N}$, and continuous on $\Omega$. Moreover, assume that for each $m \ge 0$ and $n \ge 0$ with $m+n=q$, there is a function $\bar{\phi}_{m,n}$ continuous on $\Omega$ such that

$$ \bar{\phi}_{m,n}(z) = \frac{\partial^q \phi}{\partial x^m \partial y^n}(z), \quad \text{for all } z \in \Omega_0. $$

Then there exists a function $\bar{\phi}$ of class $C^q$ on $\mathbb{R}^2$ such that $\bar{\phi}(z) = \phi(z)$ for every $z \in \Omega$. In particular, $\phi$ is of class $C^q$ on $\Omega$.

In plain words, this lemma ensures that if any partial derivative of order $q$ of $\phi$ on $\Omega_0$ can be continuously extended to $\Omega$, then $\phi$ is of class $C^q$ on $\Omega$.

According to Lemma 10, we have to look at the partial derivatives of the functions involved in the definition of $F$, and to control their behavior near possible singular points. We do so in sequence for $g_k^0$, $\theta$, $g_k^\infty$, $f_k$, $\varphi$, and finally $F$.

Derivatives of $g_k^0$. The next lemma establishes a bound for these derivatives.

**Lemma 11** For any $q \in \mathbb{N}$, there exists a positive constant $N_q$ such that, for all $k, m, n \in \mathbb{N}$ with $m+n=q$ and all $z \in \Omega$ with $g_k^0(z) > 0$, there holds

$$ \left| \frac{\partial^q g_k^0}{\partial x^m \partial y^n}(z) \right| \le \frac{N_q}{(g_k^0(z))^{q-1}}. \quad (43) $$

*Proof.* When $q=0$, the result is true with $N_0=1$. Now let us fix $k, m, n \in \mathbb{N}$ with $m+n=q>0$. For $z \in \Omega$ with $g_k^0(z) > 0$,

$$ \frac{\partial^q g_k^0}{\partial x^m \partial y^n}(z) = \frac{1}{2} \left( \frac{\partial^q}{\partial x^m \partial y^n} \|z - z_k^-\| + \frac{\partial^q}{\partial x^m \partial y^n} \|z - z_k^+\| \right). $$

Calculating these derivatives, we obtain

$$ \frac{\partial^q g_k^0}{\partial x^m \partial y^n}(z) = \frac{Q_{q,k}^{-}(z)}{\|z - z_k^{-}\|^{2q-1}} + \frac{Q_{q,k}^{+}(z)}{\|z - z_k^{+}\|^{2q-1}}, $$

where $Q_{q,k}^{\mp}$ (in this sentence, the order of the superscripts + and - matters) is a sum of products of a constant (depending on $m$ and $n$) times $q$ factors chosen among $(x \pm 1)$ and $(y - y_k)$. Because $|x \pm 1|$ and $|y - y_k|$ are bounded by $\|z - z_k^{\mp}\|$, there is a constant $N_{m,n}$ independent of $k$ such that

$$ \left| \frac{\partial^q g_k^0}{\partial x^m \partial y^n}(z) \right| \le N_{m,n} \left( \frac{1}{\|z - z_k^-\|^q} + \frac{1}{\|z - z_k^+\|^q} \right). $$

Using the triangle inequality and $\|z_k^- - z_k^+\| = 2$, we have

$$ g_k^0(z) = \frac{1}{2} (\|z - z_k^-\| + \|z - z_k^- + z_k^- - z_k^+\| - 2) \le \|z - z_k^-\|. $$
Similarly, $g_k^0(z) \le \|z - z_k^+\|$. It follows that

$$ \left| \frac{\partial^q g_k^0}{\partial x^m \partial y^n}(z) \right| \le \frac{2N_{m,n}}{(g_k^0(z))^{q-1}}. $$

The result follows with $N_q := \max\{2N_{m,n} | m+n=q, m, n \in \mathbb{N}\}$. $\square$

<figure><img src="image_15.png" /></figure>

*Derivatives of a composite function.* Consider the composite function $\phi = \gamma \circ \eta$, where $\gamma: \mathbb{R} \to \mathbb{R}$ and $\eta: \mathbb{R}^2 \to \mathbb{R}$ are functions of class $C^q$. Let $m, n \in \mathbb{N}$ be such that $q := m + n > 0$. The partial derivative of $\phi$ can be written as a finite sum of the form

$$ \frac{\partial^q \phi}{\partial x^m \partial y^n}(z) = \sum_j \alpha_j \gamma^{(l_j)}(\eta(z)) P_j, \quad (44) $$

where $\alpha_j$ are integers, $l_j \in \{1, 2, \dots, q\}$, and $P_j$ are products of $l_j$ partial derivatives of $\eta$ at $z$, with sum of orders equal to $q$.

*Derivatives of $\theta$.* The derivative of order $l \in \mathbb{N}$ of $\theta$ defined in (29) at $w$ is given by

$$ \theta^{(l)}(w) = \begin{cases} \theta(w) P_{3l} \left(\frac{1}{w}\right) & \text{if } w > 0 \\ 0 & \text{if } w \le 0, \end{cases} \quad (45) $$

where $P_{3l}: \mathbb{R} \to \mathbb{R}$ is a polynomial of degree $3l$.

*Derivatives of $g_k^\infty$.* We now apply the results above to obtain a bound on the derivatives of $g_k^\infty$ defined in (42). The next lemma also shows that $g_k^\infty$ is of class $C^\infty$, which extends Lemma 6 to Example 6.

**Lemma 12** *The functions $g_k^\infty$, $k \ge 0$, are convex and of class $C^\infty$ on $\Omega$. Furthermore, for any $q \in \mathbb{N}$, there exists a positive constant $K_q$ such that, for all $k, m, n \in \mathbb{N}$ with $m+n=q$ and for all $z \in \Omega$, there holds*

$$ \left| \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) \right| \le K_q. \quad (46) $$

*Proof.* Let $k, m, n \in \mathbb{N}$ be fixed, $q = n + m$. For $q = 0$, the fact that $g_k^0$ is bounded by 2 on $\Omega$ readily implies (46) with $K_0 = \theta(2)$. On the other hand $g_k^\infty$ is clearly continuous on $\Omega$. Therefore, we can assume $q > 0$. To simplify the notation we set $g(\cdot) \equiv g_k^0(\cdot)/3$; hence $g_k^\infty = \theta \circ g$.

We know that $g_k^0$ is $C^\infty$, except at the points $z_k^-$ and $z_k^+$, where it is nondifferentiable. Therefore, $g_k^\infty$ is $C^\infty$ at any point $z \in \Omega \setminus \{z_k^-, z_k^+\}$. To show its smoothness at $z_k^\pm$, we prove that any partial derivative of order $q$ of $g^\infty$ converges to zero when $z \to z_k^\pm$ and apply Lemma 10.

Let us compute the derivatives of $g_k^\infty$ at a point $z \in \Omega \setminus \{z_k^-, z_k^+\}$. As above:

$$ \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) = \sum_j \alpha_j \theta^{(l_j)}(g(z)) P_j, \quad (47) $$
where $\alpha_j$ are integers, $l_j \in \{1, 2, \dots, q\}$, and $P_j$ are products of $l_j$ partial derivatives of $g$, with sum of orders equal to $q$.

We know from (45) that, if $g_k^0(z) = 0$, then $\theta^{(l_j)}(g(z)) = 0$ for all $j$, so that $\frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) = 0$. Consider now the case when $g_k^0(z) \neq 0$. Then from (45) again

$$ \theta^{(l_j)}(g(z)) = \theta(g(z)) P_{3l_j} \left( \frac{1}{g(z)} \right), \quad (48) $$

where $P_{3l_j}: \mathbb{R} \to \mathbb{R}$ is a polynomial of degree $3l_j$. On the other hand, each derivative of $g$ satisfies (43); hence

$$ |\mathcal{P}_j| \le \prod_{l=1}^{l_j} \frac{N_{q_l}}{(g(z))^{q_l-1}} \le \frac{\bar{N}_q^q}{(g(z))^{r_j}}, $$

where $\bar{N}_q := \max\{1, N_1, \dots, N_q\}$ and $r_j \le q$. Combining this with (48) and (47) yields

$$ \left| \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) \right| \le \theta(g(z)) \sum_j \alpha_j P_{3l_j} \left( \frac{1}{g(z)} \right) \frac{\bar{N}_q^q}{(g(z))^{r_j}} = \theta(g(z)) \tilde{P}_{4q} \left( \frac{1}{g(z)} \right), $$

where $\tilde{P}_{4q}: \mathbb{R} \to \mathbb{R}$ is a polynomial of degree $\le 4q$. We have shown that for $z \in \Omega \setminus \{z_k^-, z_k^+\}$:

$$ \left\{ \begin{array}{ll} \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) = 0 & \text{if } g_k^0(z) = 0, \\ \\ \left| \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) \right| \le \theta \left( \frac{g_k^0(z)}{3} \right) \tilde{P}_{4q} \left( \frac{3}{g_k^0(z)} \right) & \text{otherwise.} \end{array} \right. \quad (49) $$

Let us now prove that $g_k^\infty$ is $C^\infty$ at $z_k^+$ (the proof is similar at $z_k^-$). By Lemma 10, it is enough to show that

$$ \lim_{z \to z_k^+} \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) = 0. $$

Consider a sequence $\{z_i\}$ in $\Omega \setminus \{z_k^-, z_k^+\}$ such that $z_i \to z_k^+$. Then $g_k^0(z_i) \to 0$ and the limit above follows from (49) and (30).

We still have to prove (46). From (30), the function

$$ w \in \mathbb{R} \mapsto \begin{cases} \theta(w) \tilde{P}_{4q}(1/w) & \text{if } w > 0 \\ 0 & \text{if } w \le 0 \end{cases} $$

is continuous and $g_k^0$ takes its values in the compact set $[0, 2]$. Therefore, from (49), there exists a positive constant $K_q$ dependent only on $q$, such that for any $z \in \Omega$:

$$ \left| \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z) \right| \le K_q. $$

<figure><img src="image_16.png" /></figure>

Recall that $f_k$ is defined by (8), in which $g_k = g_k^\infty$ is now given by (42). Since $g_k^\infty$ is convex and of class $C^\infty$ on $\Omega$ (Lemma 12), so is $f_k$. Also, the smoothing function $\varphi$ is convex and $C^\infty$. It is then possible to extend Lemma 7.
**Lemma 13** For any $k \in \mathbb{N}$, the function $F_k$ of Example 6 is convex and of class $C^\infty$ and all the properties (i)-(iv) in Lemma 7 hold.

*Proof.* The proof is similar to that of Lemma 7.

<figure><img src="image_17.png" /></figure>

To proceed, we need a technical result.

**Lemma 14** For $k$ sufficiently large,

$$2 \le \frac{\psi(y_{k-1})}{r_k} \le 3 \quad \text{and} \quad \frac{2}{y_k^3} \le \frac{a_{k-1}}{r_k} \le \frac{3}{y_k^3}.$$

*Proof.* We simplify the notation by setting

$$\begin{align}
\alpha_k &:= \psi(y_k) - [\psi(y_{k-1}) + \psi'(y_{k-1})(y_k - y_{k-1})] \tag{50} \\
\beta_k &:= \psi(y_{k-1}) - [\psi(y_k) + \psi'(y_k)(y_{k-1} - y_k)]. \nonumber
\end{align}$$

By (10) and (13), $r_k = \frac{1}{2} \min\{\alpha_k, \beta_k\}$.

Let us first prove that, $\beta_k \le \alpha_k$, for $k \ge 1$. Since $\psi$ is positive and increasing on $(0,1)$, we have from (41):

$$\beta_k \le \psi(y_{k-1}) = \theta(y_k).$$

Now consider (50) and use the following facts: $\psi(y_k) \ge 0$, $y_k - y_{k-1} = -y_k$, $\psi'(y_{k-1}) = \psi(y_{k-1})/y_k^3$, $\psi(y_{k-1}) = \theta(y_k)$, and $y_k \le 1/2$. We get

$$\alpha_k > \psi'(y_{k-1})y_k - \psi(y_{k-1}) = \left(\frac{1}{y_k^2} - 1\right) \theta(y_k) \ge \theta(y_k).$$

Hence $\beta_k \le \alpha_k$.

As a result $r_k = \beta_k/2$. Then, using again $y_k - y_{k-1} = -y_k$ and $\psi(y_k) = e^{-3/y_k^2} \psi(y_{k-1})$, we obtain

$$\begin{align*}
r_k &= \frac{1}{2} \left( \psi(y_{k-1}) - \psi(y_k) - \psi'(y_k)y_k \right) \\
&= \frac{1}{2} \left( \psi(y_{k-1}) - \left( 1 + \frac{8}{y_k^2} \right) \psi(y_k) \right) \\
&= \frac{1}{2} \left( 1 - e^{-3/y_k^2} \left( 1 + \frac{8}{y_k^2} \right) \right) \psi(y_{k-1}).
\end{align*}$$

Since $e^{-3/y_k^2}(1+8/y_k^2)$ is positive and tends to zero (by (30)), we have for $k$ large enough

$$2 \le \frac{\psi(y_{k-1})}{r_k} = \frac{2}{1 - e^{-3/y_k^2} \left( 1 + \frac{8}{y_k^2} \right)} \le 3,$$

proving the first bracketing. For the second one, just observe that, by (10) and (41), $a_{k-1} = \psi'(y_{k-1}) = \psi(y_{k-1})/y_k^3$. □

<figure><img src="image_18.png" /></figure>

Derivatives of $f_k$. The first derivatives at $z \in \Omega$ are

$$\frac{\partial f_k}{\partial x}(z) = c_k \frac{\partial g_k^\infty}{\partial x}(z) + \varepsilon_k \quad \text{and} \quad \frac{\partial f_k}{\partial y}(z) = a_k + c_k \frac{\partial g_k^\infty}{\partial y}(z). \tag{51}$$
Its higher order derivatives for $m, n, q \in \mathbb{N}$ such that $m + n = q \ge 2$ are

$$ \frac{\partial^q f_k}{\partial x^m \partial y^n}(z) = c_k \frac{\partial^q g_k^\infty}{\partial x^m \partial y^n}(z). \qquad (52) $$

**Lemma 15** Let $m, n \in \mathbb{N}$, such that $q := m + n \ge 1$. For any $k \ge 0$:

$$ \lim_{k \to \infty} \frac{\partial^q f_k}{\partial x^m \partial y^n}(z) = 0, \quad \text{uniformly for } z \in \Omega. \qquad (53) $$

Furthermore, there is a positive constant $R_q$, such that for $z \in \Omega$ and $k$ sufficiently large:

$$ \left| \frac{\partial^q f_k}{\partial x^m \partial y^n}(z) - \frac{\partial^q f_{k-1}}{\partial x^m \partial y^n}(z) \right| \le R_q \frac{r_k}{y_k^3}. \qquad (54) $$

*Proof.* The first claim of the lemma follows immediately from the formulas of $f_k$ and its derivatives (see (51) and (52)), from the bound (46) obtained in Lemma 12, and the fact that $a_k, b_k, c_k$, and $\varepsilon_k$ tend to zero.

The second result is proven by examining three cases, depending on the values of $q$, $m$, and $n$.

* Case 1: $q \ge 2$. Using (52), the bound (46), and the fact that both $c_{k-1}$ and $c_k$ do not exceed $r_k/4$ (see (14)), we obtain for any $k \ge 1$:

$$ \left| \frac{\partial^q f_k}{\partial x^m \partial y^n}(z) - \frac{\partial^q f_{k-1}}{\partial x^m \partial y^n}(z) \right| \le (c_k + c_{k-1}) K_q \le \frac{r_k}{2} K_q. $$

Hence, (54) follows with $R_q = K_q/2$, because $y_k \le 1$.

* Case 2: $q = m = 1$. Using (51), the bound (46), the fact that both $c_{k-1}$ and $c_k$ do not exceed $r_k/4$, and $|\varepsilon_k| \le |\varepsilon_{k-1}| \le r_k/16$ (see (15)), we have for any $k \ge 1$:

$$ \left| \frac{\partial f_k}{\partial x}(z) - \frac{\partial f_{k-1}}{\partial x}(z) \right| \le \frac{r_k}{2} K_1 + 2|\varepsilon_{k-1}| \le \frac{r_k}{2} \left( K_1 + \frac{1}{4} \right). $$

Inequality (54) follows as in case 1.

* Case 3: $q = n = 1$. Using (51), the bound (46), the fact that both $c_{k-1}$ and $c_k$ do not exceed $r_k/4$, and $a_k \le a_{k-1} \le 3r_k/y_k^3$ (see Lemma 14), we obtain for $k$ large enough:

$$ \left| \frac{\partial f_k}{\partial y}(z) - \frac{\partial f_{k-1}}{\partial y}(z) \right| \le 2a_{k-1} + \frac{r_k}{2} K_1 \le \frac{6r_k}{y_k^3} + \frac{r_k}{2} K_1 \le \frac{r_k}{y_k^3} \left( 6 + \frac{K_1}{2} \right), $$

since $y_k \le 1$. Inequality (54) follows.
<figure><img src="image_19.png" /></figure>

Derivatives of $\varphi$: We do not need an explicit expression for the derivatives of the smoothing function $\varphi$, but just bounds. From (22), if $|w| \ge 1$, then $\varphi'(w) = \pm 1$ and $\varphi^{(l)}(w) = 0$ for $l \ge 2$. Therefore, since $\varphi \in C^\infty$, for any integer $l \ge 1$, there exists a positive constant $S_l$, such that

$$|\varphi^{(l)}(w)| \le S_l, \quad \text{for any } w \in \mathbb{R}. \qquad (55)$$

The main result of this section is the following.

**Lemma 16** The cost function $F$ of Example 6 is convex and of class $C^\infty$ on $\Omega$.

*Proof.* Using the same arguments as in the beginning of the proof of Lemma 8, we have that $F$ vanishes on $\Omega_- = \{(x, y) \in \text{int} \, \Omega \mid y < 0\}$ and is $C^\infty$ on $\Omega_+ = \{(x, y) \in \text{int} \, \Omega \mid y > 0\}$. It is also convex and continuous on $\Omega$.

We still have to show that $F$ is $C^\infty$ on $\Omega$, knowing that it has this smoothness on $\Omega_0 = \Omega_- \cup \Omega_+$. For this, we apply Lemma 10: it is sufficient to show that any partial derivative of $F$ has a continuous extension from $\Omega_0$ to $\Omega$. This extension at a point $(x, y) \in \Omega \setminus \Omega_0$, with $y \ne 0$, is straightforward; therefore, we concentrate on those points of the form $\tilde{z} = (x, 0)$, with $x \in [-1.5, 1.5]$.

Let us fix $m, n \in \mathbb{N}$, such that $q := m + n > 0$. It is sufficient to show that $\frac{\partial^q F}{\partial x^m \partial y^n}(z_i)$ converges to zero when $z_i = (x_i, y_i) \in \Omega_0$ converges to $\tilde{z}$. We can assume that $y_i > 0$, since otherwise the partial derivative vanishes (an easy case).

For any $i \in \mathbb{N}$, there exists $k_i \in \mathbb{N}$ such that $z_i$ belongs to the strip $\Omega_{k_i}$. Let us simplify the notation by setting, for $z \in \Omega$

$$h_{k_i}(z) = \frac{f_{k_i}(z) - f_{k_i-1}(z)}{r_{k_i}}.$$

From Lemma 13,

$$F(z_i) = M_{r_{k_i}}(f_{k_i}(z_i), f_{k_i-1}(z_i)) = \frac{1}{2}(f_{k_i}(z_i) + f_{k_i-1}(z_i) + r_{k_i}\varphi(h_{k_i}(z_i))).$$

Therefore

$$\frac{\partial^q F}{\partial x^m \partial y^n}(z_i) = \frac{1}{2} \left( \frac{\partial^q f_{k_i}}{\partial x^m \partial y^n}(z_i) + \frac{\partial^q f_{k_i-1}}{\partial x^m \partial y^n}(z_i) + r_{k_i} \frac{\partial^q (\varphi \circ h_{k_i})}{\partial x^m \partial y^n}(z_i) \right). \quad (56)$$

When $z_i \to \tilde{z}$, $k_i \to \infty$, and thus Lemma 15 implies that the first two terms in (56) tend to zero.

Using (44), the last term in (56) can be written

$$r_{k_i} \frac{\partial^q (\varphi \circ h_{k_i})}{\partial x^m \partial y^n}(z_i) = r_{k_i} \sum_j \alpha_j \varphi^{(l_j)}(h_{k_i}(z_i)) \mathcal{P}_j, \quad (57)$$
where $\alpha_j$ are integers, $l_j \in \{1, 2, \dots, q\}$, and $\mathcal{P}_j$ are products of $l_j$ partial derivatives of $h_{k_i}$ at $z_i$, with sum of orders equal to $q$. By (55), for all $l_j \in \{1, 2, \dots, q\}$

$$|\varphi^{(l_j)}(h_{k_i}(z_i))| \le \bar{S}_q, \qquad (58)$$

where $\bar{S}_q := \max\{1, S_1, \dots, S_q\}$ is independent of $i$. Let us now examine the product $\mathcal{P}_j$:

$$|\mathcal{P}_j| = \left| \prod_{l=1}^{l_j} \frac{\partial^{q_l} h_{k_i}}{\partial x^{m_l} \partial y^{n_l}}(z_i) \right| = \frac{1}{r_{k_i}^{l_j}} \prod_{l=1}^{l_j} \left| \frac{\partial^{q_l} f_{k_i}}{\partial x^{m_l} \partial y^{n_l}}(z_i) - \frac{\partial^{q_l} f_{k_i-1}}{\partial x^{m_l} \partial y^{n_l}}(z_i) \right|.$$

By Lemma 15, for $i$ (hence $k_i$) sufficiently large

$$|\mathcal{P}_j| \le \frac{1}{r_{k_i}^{l_j}} \prod_{l=1}^{l_j} \left( R_{q_l} \frac{r_{k_i}}{y_{k_i}^3} \right) \le \left( \frac{\bar{R}_q}{y_{k_i}^3} \right)^q,$$

where $\bar{R}_q := \max\{1, R_1, \dots, R_q\}$ is independent of $i$. Combining this estimate with (57) and (58) yields

$$r_{k_i} \left| \frac{\partial^q (\varphi \circ h_{k_i})}{\partial x^m \partial y^n} (z_i) \right| \le r_{k_i} \bar{S}_q \frac{\bar{R}_q^q}{y_{k_i}^{3q}} \sum_j \alpha_j \le 2K \frac{r_{k_i}}{y_{k_i}^{3q}},$$

where $K$ is a constant independent of $i$. From Lemma 14, $r_{k_i} \le \psi(y_{k_i-1})/2 = \theta(y_{k_i})/2$. Hence

$$r_{k_i} \left| \frac{\partial^q (\varphi \circ h_{k_i})}{\partial x^m \partial y^n} (z_i) \right| \le K \frac{\theta(y_{k_i})}{y_{k_i}^{3q}}.$$

By (30) and $y_{k_i} \to 0$, the right hand side of this inequality converges to zero. $\square$

To conclude, let us look at the central path (4), associated with function $F$ in Example 6. It depends on the values of $\varepsilon_k$ satisfying (14).

If $\varepsilon_k = 0$ for all $k \in \mathcal{N}$, the central path shows an antenna pattern, as before. Indeed, for $y \in (y_k, y_{k-1})$, $f_k(\cdot, y)$ and $f_{k-1}(\cdot, y)$ are both uniquely minimized at $x = 0$ ($g_k^0(\cdot, y)$ is positive and strictly convex and $\theta$ is strictly convex on $(0, 2/3)$), hence so is $F(\cdot, y)$ (see Lemmas 13-7). For $y = y_k$, $F(\cdot, y_k) = f_k(\cdot, y_k)$, which is minimized for $x \in [-1, +1]$.

If $\varepsilon_k \ne 0$ and $|\varepsilon_k|$ is sufficiently small, for all $k \in \mathcal{N}$, the central path shows a zig-zag pattern with infinite variation. Indeed, $F(\cdot, y_k)$ is minimized at a single point $x \notin [-1, +1]$ characterized by

$$\frac{\partial F}{\partial x}(x, y_k) = \frac{\partial f_k}{\partial x}(x, y_k) = c_k \frac{\partial g_k^\infty}{\partial x}(x, y_k) + \varepsilon_k = 0.$$

We have

$$\begin{aligned} \frac{\partial g_k^\infty}{\partial x}(x, y_k) &= \frac{18}{(g_k^0(x, y_k))^3} \frac{\partial g_k^0}{\partial x}(x, y_k) \theta\left(\frac{1}{3}g_k^0(x, y_k)\right) \\ &= \begin{cases} \frac{18}{(x+1)^3} \theta(|x+1|/3) & \text{if } x < -1 \\ \frac{18}{(x-1)^3} \theta(|x-1|/3) & \text{if } x > +1. \end{cases} \end{aligned}$$
Then an easy calculation shows that, if $\epsilon_k > 0$ is small enough, the minimizer $x \in [-1.5, -1)$, and if $-\epsilon_k > 0$ is small enough, the minimizer $x \in (1, 1.5]$. On the other hand, due to the convexity of $g_k$ and Lemmas 13-7, the central path is entirely in $\Omega$ and, by Lemma 9, it is a $C^\infty$ function of $y > 0$.

# 7 Additional notes

It is easy to modify the last examples so that the central path does not change much and $F$ becomes smooth or $C^\infty$ in the whole space. Define the following smooth convex function:

$$z = (x, y) \in \mathbb{R}^2 \mapsto q(z) = \alpha (x^2 - (1.4)^2) + \psi(y),$$

where $\alpha > 0$ is large and $\psi$ is the support function used to form $F$, and set $\bar{F}(\cdot) = \max\{F(\cdot), q(\cdot)\}$. This function coincides with $F$ in the region of interest (for $|x| \le 1.4$ and $y \in [-0.5, 1]$). Smoothing $\bar{F}$ by the method of Section 4 makes it as smooth as $F$, and the central path stays almost the same.

The minimizers in Examples 4-6 do not satisfy strict complementarity, since $F(x, y) = 0$ if $y \le 0$. The central paths would not change, however, if a term $ay$, with $a > 0$, is added to $F$. Then, strict complementarity holds. Note that the shape of the central paths is compatible with McLinden's result [19], according to which, when strict complementarity holds, the limit points of any convergent selection of central points are in the analytic center of the optimal set. Here, the analytic center is identical to the optimal set since the single constraint is always active at the solutions.

It is not possible to construct an antenna-like or a zig-zag central path with an objective function that is analytic. Monteiro and Zhou [22] ensure indeed that if the functions involved in the definition of the problem are analytic, together with some other mild assumptions, then the primal central path is a curve that converges to a single point in the optimal set (related results are given by Cominetti [7] and Champion [4]). It is therefore remarkable that $C^\infty$ smoothness still allowed us to construct central paths with weird layout.

# References

[1] Auslender, A., Cominetti, R., Haddou, M. (1997): Asymptotic analysis for penalty and barrier methods in convex and linear programming. Mathematics of Operations Research 22, 43-62

[2] Bayer, D. A., Lagarias, J. C. (1989): The nonlinear geometry of linear programming, Part I: Affine and projective scaling trajectories. Transactions of the American Mathematical Society 314, 499-526

[3] Byrd, R. H., Gilbert, J. C., Nocedal, J. (2000): A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming 89, 149-185
[4] Champion, T. (2001): Asymptotic convergence of penalty trajectories in convex programming with multiple solutions. Tech. Rep., Département de Mathématique, Université de Montpellier II, France

[5] Chen, C., Mangasarian, O. L. (1995): Smoothing methods for convex inequalities and linear complementary problems. Mathematical Programming **71**, 1–112

[6] Chen, C., Mangasarian, O. L. (1996): A class of smoothing functions for non-linear and mixed complementary problems. Computational Optimization and Applications **5**, 97–138

[7] Cominetti, R. (1999): Nonlinear averages and convergence of penalty trajectories in convex programming. In: Théra, M., Tichatschke, R., eds., Ill-posed variational problems and regularization techniques, Springer Verlag, Berlin, vol. 477 of Lecture Notes in Economics and Mathematical System, 65–78

[8] Conn, A. R., Gould, N. I. M., Orban, D., Toint, P. L. (1999): A primal-dual trust region algorithm for minimizing a non-convex function subject to general inequality and linear equality constraints. Tech. Rep. RAL-TR-1999-054, Computation Science and Engineering Department, Atlas Centre, Rutherford Appleton Laboratory, Oxon, OX11 OQX

[9] den Hertog, D. (1992): Interior Point Approach to Linear, Quadratic and Convex Programming. Mathematics and its Applications 277, Kluwer Academic Publishers, Dordrecht

[10] Dennis, J. E., Heinkenschloss, M., Vicente, L. N. (1994): Trust-region interior-point SQP algorithms for a class of nonlinear programming problems. Tech. Rep. 94-45, Department of Computational and Applied Mathematics, Rice University

[11] Fiacco, A. V., McCormick, G. P. (1968): NonLinear Programming : Sequential Unconstrained Minimization Techniques. John Wiley & Sons, New York, reprint : Volume 4 of *SIAM Classics in Applied Mathematics*, SIAM Publications, Philadelphia, PA 19104-2688, USA, 1990

[12] Fleming, W. H. (1965): Functions of Several Variables. Addison-Wesley Publishing Company, United States

[13] Forsgren, A., Gill, P. E. (1998): Primal-dual interior methods for nonconvex non-linear programming. SIAM Journal on Optimization **8**, 1132–1152

[14] Gay, D. M., Overton, M. L., Wright, M. H. (1998): A primal-dual interior method for nonconvex nonlinear programming. In: Yuan, Y.-X., ed., Advances in Nonlinear Programming, Kluwer Academic Publishers, Dordretch, 31–56

[15] Gonzaga, C. C. (1992): Path following methods for linear programming. SIAM Review **34**, 167–227
[16] Hiriart-Urruty, J.-B., Lemarechal, C. (1993): Convex Analysis and Minimization Algorithms I. Springer-Verlag, New York

[17] Jansen, B. (1997): Interior Point Techniques in Optimization. Applied Optimization 6, Kluwer Academic Publishers, Dordrecht

[18] Kojima, M., Megiddo, N., Noma, T., Yoshise, A. (1991): A unified approach to interior point algorithms for linear complementarity problems. In: Lecture Notes in Computer Science, Springer Verlag, Berlin, vol. 538

[19] McLinden, L. (1980): An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem. Pacific Journal of Mathematics 88, 101-161

[20] Megiddo, N. (1989): Pathways to the optimal set in linear programming. In: Megiddo, N., ed., Progress in Mathematical Programming: Interior Point and Related Methods, Springer Verlag, New York, 131-158, identical version in: *Proceedings of the 6th Mathematical Programming Symposium of Japan, Nagoya, Japan*, pages 1-35, 1986

[21] Monteiro, R. D. C., Tsuchiya, T. (1996): Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem. Mathematics of Operations Research 21, 793-814

[22] Monteiro, R. D. C., Zhou, F. (1998): On the existence and convergence of the centra path for convex programming and some duality results. Computational Optimization and Applications 10, 51-77

[23] Nesterov, Y. E., Nemirovskii, A. S. (1994): Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics 13, SIAM, Philadelphia

[24] Rockafellar, R. T., Wets, R. (1998): Variational analysis. Springer

[25] Roos, C., Terlaky, T., Vial, J. P. (1997): Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, Chichester

[26] Terlaky, T., ed. (1996): Interior Point Methods of Mathematical Programming. Kluwer Academic Press

[27] Vanderbei, R. J., Shanno, D. F. (1997): An interior-point algorithm for nonconvex nonlinear programming. Tech. Rep. SOR-97-21, Statistics and Operations Research, Princeton University, Princeton, USA, to appear in *Computational Optimization and Applications*

[28] Vavasis, S. A., Ye, Y. (1996): A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming 74, 79-120
[29] Whitney, H. (1934): Functions differentiable on the boundaries of regions. Ann. of Math. **35**, 482–485

[30] Wright, S. J. (1997): Primal-Dual Interior-Point Methods. SIAM Publication, Philadelphia
<figure><img src="image_20.png" /></figure>

Unité de recherche INRIA Rocquencourt
Domaine de Voluceau - Rocquencourt - BP 105 - 78153 Le Chesnay Cedex (France)

Unité de recherche INRIA Lorraine : LORIA, Technopôle de Nancy-Brabois - Campus scientifique
615, rue du Jardin Botanique - BP 101 - 54602 Villers-lès-Nancy Cedex (France)

Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu - 35042 Rennes Cedex (France)

Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe - 38330 Montbonnot-St-Martin (France)

Unité de recherche INRIA Sophia Antipolis : 2004, route des Lucioles - BP 93 - 06902 Sophia Antipolis Cedex (France)

Éditeur

INRIA - Domaine de Voluceau - Rocquencourt, BP 105 - 78153 Le Chesnay Cedex (France)

http://www.inria.fr

ISSN 0249-6399