An affine-scaling interior-point filter line-search algorithm for constrained optimization

Abstract

This paper presents and analyzes an affine-scaling interior-point algorithm with a filter line-search method for solving nonlinear optimization problems with nonlinear equality constraints and nonnegative variables. In our scheme, we require that a damped Newton’s method is applied to the perturbed first-order necessary conditions to produce a search direction. Some filtered rules for a fixed barrier parameter are used to determine step acceptance. Second-order correction technique is used to reduce infeasibility and overcome the Maratos effect. The global convergence and fast local convergence rate of the proposed algorithm are established under some suitable conditions.

Introduction

The optimization problem considered in this paper is

$$\underset{\mathrm{x}\in {\mathbb{R}}^{\mathrm{n}}}{min}f(x)\mathrm{s}.\mathrm{t}.c(x)=0x\ge 0,$$

(1.1)

where $f(x):{\mathbb{R}}^n\to {\mathbb{R}}^1$ and $c(x):{\mathbb{R}}^n\to {\mathbb{R}}^m$ with $m\le n$ are twice continuously differentiable.

Filter methods have been applied in many current optimization techniques (see e.g. Arzani and Peyghami, ¹ Eichfelder et al., ² and Li and Zhu ³ ). Interior-point methods compute a step by solving a linear system. Researchers have extended filter methods to interior-point methods. Ulbrich et al. ⁴ and Wätcher and Biegler^5,6 developed convergence theory for interior-point filter methods. Ulbrich et al. decomposed the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes were controlled by a trust-region type parameter. However, replacing the objective by the optimality measure means that the algorithm may be more likely to converge to stationary points that are not local minimizers. Wätcher and Biegler proposed a filter method framework which was based on line search and could be applied to barrier interior-point methods as well as active set SQP methods. Their search direction is obtained by calculating the quadratic subproblem, which is known to involve a large amount of calculation. Wätcher and Biegler’s interior-point method avoids the pitfall of many interior-point methods that may converge to spurious stationary points (see Wätcher and Biegler^5,6 and Vicente ⁷ ).

In this paper, we propose a new affine-scaling interior-point filter line search method for solving the optimization (1.1). Different from the method provided by Wätcher and Biegler, ⁶ we combine with an affine-scaling strategy and obtain a search direction by solving linear equations. Using this technique, the computation of the algorithm is relatively small. In the case of local convergence, we show that the proposed method has quadratic convergence rate. The paper is organized as follows. Section “The basic algorithm” presents the overall algorithm, including the affine-scaling barrier method and the filter line-search procedure. In section “Convergence analysis,” global and local convergence properties of the proposed algorithm are established.

Throughout the paper, the element of a sequence is denoted by a subscript (e.g. $f(x_k)=f_k$ ). In particular, $\mathrm{\nabla }f(x_k)$ is denoted by $g_k$ and $\mathrm{\nabla }c(x_k)$ by $A_k,$ where $\mathrm{\nabla }c(x_k)$ is the Jacobian of $c(x).$ The $i$ th component of a vector $v\in {\mathbb{R}}^n$ is written as $v^{(i)}$ .

The basic algorithm

In this section, we modify and improve an existing interior-point line search algorithm, which is formally summarized in section “The basic algorithm.”

The affine-scaling interior-point approach

Let the Lagrangian function of problem (1.1) be

$$L(x,\lambda ,z):=l(x,\lambda )-z^{T}x:=f(x)+{\lambda }^{T}c(x)-z^{T}x$$

(2.1)

where $\lambda \in {\mathbb{R}}^m$ and $z\in {\mathbb{R}}^n$ are the Lagrangian multipliers. The Karush-Kuhn-Tucher (K-K-T) conditions of this problem can be written as

$$\begin{array}{r}\left(\begin{array}{c}{\mathrm{\nabla }}_{x}l(x,\lambda )-z\\ c(x)\\ XZr\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\end{array}$$

(2.2)

and $x\ge 0,z\ge 0,$ where $X:=\mathrm{diag}(x)$ for a vector $x,$ $Z:=\mathrm{diag}(z),$ $r$ stands for the vector of all ones for appropriate dimension. By introducing a diagonal scaling matrix $D(x,\lambda ):=\mathrm{diag}(d(x,\lambda {)}^{(1)},\dots ,$ $d(x,\lambda {)}^{(n)})$ with

$$d(x,\lambda {)}^{(i)}:=\{\begin{array}{cc}(x^{(i)}{)}^{\frac{1}{2}}& \mathrm{if}{\mathrm{\nabla }}_{x}l(x,\lambda {)}^{(i)}\ge 0\\ 1& \mathrm{if}{\mathrm{\nabla }}_{x}l(x,\lambda {)}^{(i)}<0\end{array}$$

(2.3)

we can obtain a modified K-K-T conditions in the form

$$D(x,\lambda {)}^2{\mathrm{\nabla }}_{x}l(x,\lambda )-\mu r=0,c(x)=0$$

(2.4)

and $x>0,$ where $\mu$ is a non-negative number. Note that the equations for $\mu =0$ together with “ $x,z\ge 0$ ” are the K-K-T conditions of the original problem (1.1). Furthermore, the modified Newton step $(\hat{s},{\hat{s}}^{\lambda })$ for (2.4) satisfies

$$\begin{array}{rl}& \left(\begin{array}{cc}D(x,\lambda ){\mathrm{\nabla }}_{xx}^{2}l(x,\lambda )D(x,\lambda )+E(x,\lambda )& D(x,\lambda )A{(x)}^T\\ A(x)D(x,\lambda )& 0\end{array}\right)\left(\begin{array}{c}\hat{s}\\ s^{\lambda }\end{array}\right)\\ & =-\left(\begin{array}{c}D(x,\lambda ){\mathrm{\nabla }}_{x}l(x,\lambda )-\mu D(x,\lambda {)}^{-1}r\\ c(x)\end{array}\right)\end{array}$$

(2.5)

where ${\mathrm{\nabla }}_{xx}^{2}l(x,\lambda )={\mathrm{\nabla }}^{2}f(x)+\sum _{i=1}^m{\lambda }^{(i)}{\mathrm{\nabla }}^{2}c{(x)}^{(i)},$ and $E(x,\lambda ):=\mathrm{diag}(e(x,\lambda {)}^{(1)},\dots ,e(x,\lambda {)}^{(n)})$ with

$$\begin{array}{r}e(x,\lambda {)}^{(i)}:=\{\begin{array}{cc}{\mathrm{\nabla }}_{x}l(x,\lambda {)}^{(i)}& \mathrm{if}{\mathrm{\nabla }}_{x}l(x,\lambda {)}^{(i)}>0\\ 0& \mathrm{if}{\mathrm{\nabla }}_{x}l(x,\lambda {)}^{(i)}\le 0\end{array}\end{array}$$

On the other hand, as a barrier method, the proposed algorithm computes (approximate) solutions for a sequence of barrier problems

$$\underset{\mathrm{x}\in {\mathbb{R}}^{\mathrm{n}}}{min}{\phi }_{\mu }(x):=f(x)-\mu \sum _{i=1}^n\ln (x^{(i)})\mathrm{s}.\mathrm{t}.c(x)=0$$

(2.6)

with the barrier parameter sequence $\mu$ , which is driven to zero. Let $\mathcal{L}$ be the Lagrangian function for the problems (2.6) defined by $\mathcal{L}(x,\lambda ):={\phi }_{\mu }(x)+{\lambda }^{T}c(x):=f(x)-\mu \sum _{i=1}^n\ln (x^{(i)})+{\lambda }^{T}c(x).$ Since $\mathrm{\nabla }{\phi }_{\mu }(x)=g(x)-\mu X^{-1}r,$ we can write (2.5) as

$$\begin{array}{rl}& \left(\begin{array}{cc}D(x,\lambda ){\mathrm{\nabla }}_{xx}^{2}l(x,\lambda )D(x,\lambda )+E(x,\lambda )& D(x,\lambda )A{(x)}^T\\ A(x)D(x,\lambda )& 0\end{array}\right)\left(\begin{array}{c}\hat{s}\\ s^{\lambda }\end{array}\right)\\ & =-\left(\begin{array}{c}D(x,\lambda )(\mathrm{\nabla }{\phi }_{\mu }(x)+A{(x)}^T\lambda )\\ c(x)\end{array}\right)\end{array}$$

(2.7)

Optimality conditions for problem (1.1) are well established by (2.4) for $\mu =0.$ A feasible point $x_{*}$ is said to be the stationary point for problem (1.1), if there exists a vector ${\lambda }_{*}\in R^m$ such that

$$D(x_{*},{\lambda }_{*}{)}^2{\mathrm{\nabla }}_{x}l(x_{*},{\lambda }_{*})=0,c(x_{*})=0,x_{*}\ge 0$$

(2.8)

Strict complementarity is said to hold at $x_{*}$ if one and only one of the two inequalities $x_{*}^{(i)}>0$ and $e_{*}^{(i)}:=e(x_{*},{\lambda }_{*}{)}^{(i)}>0$ ( $z_{*}^{(i)}>0$ ) holds, that is, $|x_{*}^{(i)}|+|e_{*}^{(i)}|>0(i=1,\dots ,n).$ If the pair $(x_{*},{\lambda }_{*})$ satisfies strict complementarity, the second order sufficient conditions are equivalent to (2.8) and the positive definiteness of $D(x_{*},{\lambda }_{*}){\mathrm{\nabla }}_{xx}^{2}l(x_{*},{\lambda }_{*})D(x_{*},{\lambda }_{*})+E(x_{*},{\lambda }_{*})$ on the null space of $A(x_{*})D(x_{*},{\lambda }_{*}).$

Under the standard Newton’s method assumptions for problem (1.1) , we have that the matrix

$$\left(\begin{array}{cc}D(x_{*},{\lambda }_{*}){\mathrm{\nabla }}_{xx}^{2}l(x_{*},{\lambda }_{*})D(x_{*},{\lambda }_{*})+E(x_{*},{\lambda }_{*})& D(x_{*},{\lambda }_{*})A(x_{*}{)}^T\\ A(x_{*})D(x_{*},{\lambda }_{*})& 0\end{array}\right)$$

is nonsingular. The proof is given by [Vicente, ⁸ prop. 3.3].

Therefore, the form of the coefficient matrix in (2.7) and the standard Newton’s method assumptions imply that the affine-scaling interior-point Newton algorithm is well defined in a neighborhood of a nondegenerate regular point that satisfies the second-order sufficient optimality conditions.

The filter line-search method and second-order correction steps

We view (2.6) as a bi-objective optimization problem that minimizes the objective function ${\phi }_{{\mu }_j}(x)$ and the constraint violation $\theta (x):=\Vert c(x){\Vert }_1,$ where ${\mu }_j$ is a given fixed value of the barrier parameter $\mu$ . We apply the filter technique developed and analyzed in section 2. and Section 3. by Wätcher and Biegler ⁶ to solve the barrier problem (2.6) and replace all occurrences of “ $f$ ” by “ ${\phi }_{{\mu }_j}$ .” Using the transformation $\hat{s}=D(x,\lambda {)}^{-1}s$ , (2.7) implies that

$$\begin{array}{rl}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k& =-s_k^T{D_k}^{-1}(D_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+E_k){D_k}^{-1}{s}_k\\ & -(A_k^T(s_k^{\lambda }+{\lambda }_k){)}^T{s}_k\\ & =-{\hat{s}}_k^T(D_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+E_k){\hat{s}}_k-{\lambda }_{k+1}^T{A}_k{s}_k\\ & =-{\hat{s}}_k^T(D_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+E_k){\hat{s}}_k+{\lambda }_{k+1}^T{c}_k\end{array}$$

(2.9)

the switching condition (9) by Wätcher and Biegler ⁶ holds if the projection of the top-left matrix in (2.7) onto the null space of $A_k{D}_k$ is uniformly positive definite and a feasible non-optimal point is approached. However, the Armijo condition (11) by Wätcher and Biegler ⁶ prevents the method from converging to such a point.

Since $x$ is positive at the optimal solution of the barrier problem (2.6), this property is maintained for all iterates. Therefore, in order for $x_{k+1}$ to be strictly feasible, ${\alpha }_{k,l}$ is chosen to satisfy $x_k+{\alpha }_{k,l}{s}_k\ge (1-{\tau }_j)x_k>0,$ where the parameter ${\tau }_j\in (0,1)$ is defined by

$${\tau }_j=max\{{\tau }_{\min },1-{\mu }_j\}$$

(2.10)

with ${\tau }_{\min }\in (0,1)$ . Here, given an initial value for the barrier parameter ${\mu }_0>0,$ the parameter ${\mu }_j$ is obtained from

$${\mu }_{j+1}=max\{\frac{{ϵ}_{\mathrm{tol}}}{10},min\{{\kappa }_{\mu }{\mu }_j,{\mu }_j^{{\theta }_{\mu }}\}\}$$

(2.11)

with constants ${\kappa }_{\mu }\in (0,1)$ and ${\theta }_{\mu }\in (1,2).$ Obviously the barrier parameter is eventually decreased at a superlinear rate and ${\mu }_{j+1}\ge {ϵ}_{\mathrm{tol}}/10$ ensures that numerical difficulties are avoided at the end of the optimization procedure. More precisely, we choose

$${\alpha }_{k,l}=min\{-{\tau }_j{x}_k^{(i)}/s_k^{(i)}:s_k^{(i)}<0,i=1,\dots ,n\}$$

(2.12)

Hence, there exists $t\in \{1,\dots ,n\}$ such that

$${\alpha }_{k,l}=-{\tau }_j{x}_k^{(t)}/s_k^{(t)}$$

(2.13)

According to the Newton’s method assumptions for problem (1.1), there exists $(x_{*},{\lambda }_{*})$ satisfying the K-K-T conditions (2.8). Since the strict complementarity of problem (1.1) holds at $x_{*},$ we have $|x_{*}^{(i)}|+|e_{*}^{(i)}|>0,i=1,\dots ,n.$ Pick $ϵ=\frac{1}{2}(|x_{*}^{(i)}|+|e_{*}^{(i)}|).$

Define the set of active indices $\mathcal{I}(x)=\{i\in \{1,\dots ,n\}:x^{(i)}=0\}.$

If $i\notin \mathcal{I}(x_{*}),$ then $ϵ=\frac{1}{2}(|x_{*}^{(i)}|).$ Since $x_k\to x_{*},$ and $x_k$ is an interior-point, we have $x_k^{(i)}=|x_k^{(i)}|\ge \frac{1}{2}|x_{*}^{(i)}|=ϵ,$ and then $-\frac{s_k^{(i)}}{x_k^{(i)}}\le \frac{\Vert s_k\Vert }{x_k^{(i)}}\le \frac{\Vert s_k\Vert }{ϵ}.$ Using (2.13), we can obtain ${\alpha }_{k,l}\ge \frac{{\tau }_jϵ}{\Vert s_k\Vert }.$

If $i\in \mathcal{I}(x_{*}),$ then $ϵ=\frac{1}{2}(|e_{*}^{(i)}|).$ Since $x_k\to x_{*},$ we have $|e_k^{(i)}|\ge \frac{1}{2}|e_{*}^{(i)}|=ϵ.$ The first equation in (2.5) implies that

$$\begin{array}{rl}-\frac{s_k^{(i)}}{x_k^{(i)}}& =(\frac{(D_k^2{\mathrm{\nabla }}_{xx}^2{l}_k{s}_k{)}^{(i)}}{e_k^{(i)}}+\frac{(D_k^2{A}_k^T{s}_k^{\lambda }{)}^{(i)}}{e_k^{(i)}}+\frac{(D_k^2{\mathrm{\nabla }}_x{l}_k{)}^{(i)}}{e_k^{(i)}}-\frac{{\mu }_j}{e_k^{(i)}})/x_k^{(i)}\\ & =\frac{({\mathrm{\nabla }}_{xx}^2{l}_k{s}_k{)}^{(i)}}{e_k^{(i)}}+\frac{(A_k^T{s}_k^{\lambda }{)}^{(i)}}{e_k^{(i)}}+1-\frac{{\mu }_j}{x_k^{(i)}{e}_k^{(i)}}\end{array}$$

(2.14)

Then (2.13) indicates

$${\alpha }_{k,l}=\frac{{\tau }_j{e}_k^{(t)}}{({\mathrm{\nabla }}_{xx}^2{l}_k{s}_k{)}^{(t)}+(A_k^T{s}_k^{\lambda }{)}^{(t)}+e_k^{(t)}-\frac{{\mu }_j}{x_k^{(t)}}}\ge \frac{{\tau }_j}{1+{\kappa }_1\Vert s_k\Vert +{\kappa }_2\Vert s_k^{\lambda }\Vert }$$

where ${\kappa }_1$ and ${\kappa }_2$ are positive constants and independent of $k,$ and we use $\frac{{\mu }_j}{(x_k{)}^t(e_k{)}^t}>0$ in the first inequality.

Combining with formula (18) by Wätcher and Biegler, ⁶ we can summarize this in the following formula for a minimal trial step size

$${\alpha }_k^{min}:={\gamma }_{\alpha }\cdot \{\begin{array}{c}min\{{\gamma }_{\theta },-\frac{{\gamma }_{\phi }\theta (x_k)}{\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k},\frac{\delta [\theta (x_k){]}^{s_{\theta }}}{[-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k{]}^{s_{\phi }}},\frac{{\tau }_jϵ}{\Vert s_k\Vert },\frac{{\tau }_j}{1+{\kappa }_1\Vert s_k\Vert +{\kappa }_2\Vert s_k^{\lambda }\Vert }\}\\ \mathrm{if}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k<0\mathrm{and}\theta (x_k)\le {\theta }^{min}\\ min\{{\gamma }_{\theta },-\frac{{\gamma }_{\phi }\theta (x_k)}{\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k},\frac{{\tau }_jϵ}{\Vert s_k\Vert },\frac{{\tau }_j}{1+{\kappa }_1\Vert s_k\Vert +{\kappa }_2\Vert s_k^{\lambda }\Vert }\}\\ \mathrm{if}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k<0\mathrm{and}\theta (x_k)>{\theta }^{min}\\ min\{{\gamma }_{\theta },\frac{{\tau }_jϵ}{\Vert s_k\Vert },\frac{{\tau }_j}{1+{\kappa }_1\Vert s_k\Vert +{\kappa }_2\Vert s_k^{\lambda }\Vert }\}\mathrm{otherwise}\end{array}$$

(2.15)

with a “safety factor” ${\gamma }_{\alpha }\in (0,1].$ When ${\alpha }_{k,l}$ becomes smaller than ${\alpha }_k^{min}$ , the algorithm reverts to feasibility restoration phase.

Consider that the filter approach can suffer from the Maratos effect and improve the search direction by means of a second-order correction. If the first trial step size ${\alpha }_{k,0}$ has been rejected, we compute a second-order correction

$$s_k^{\mathrm{soc}}=-D_k(A_k{D}_k{)}^{+}c(x_k+s_k)$$

(2.16)

where $A^{+}$ denotes the pseudo-inverse of $A^T.$ Therefore, $s_k^{\mathrm{soc}}$ can be written as

$$s_k^{\mathrm{soc}}=-D_k(D_k{A}_k^T)[(A_k{D}_k)(D_k{A}_k^T){]}^{-1}c(x_k+s_k)$$

(2.17)

where $s_k=D_k{\hat{s}}_k$ and $\hat{s}$ is defined by (2.7). Note that $s_k^{\mathrm{soc}}$ has the property that satisfies a linearization of the constraints at the point $x_k+s_k$ , that is, $A_k{s}_k^{\mathrm{soc}}+c(x_k+s_k)=0.$

If $s_k^{\mathrm{soc}}$ is a second-order correction step, and ${\overline{s}}_k^{\mathrm{soc}}$ is an additional second-order correction step, then $s_k^{\mathrm{soc}}+{\overline{s}}_k^{\mathrm{soc}}$ can be understood as a single second-order correction step for $s_k.$ Similarly, several consecutive correction steps can be considered as a single one.

The basic algorithm

The algorithm contains an inner and an outer loop. Using the individual parts of (2.4), we define the optimality error for the barrier problem as

$$G_{\mu }(x,\lambda )=\Vert D(x,\lambda {)}^2{\mathrm{\nabla }}_{x}l(x,\lambda )-\mu r\Vert +\Vert c(x){\Vert }_1$$

(2.18)

By $G_0(x,\lambda )$ we denote (2.20) with $\mu =0;$ this measures the optimality error for the original problem (1.1). The overall algorithm terminates if an approximate solution $({\tilde{x}}_{*},{\tilde{\lambda }}_{*})$ satisfying $G_0({\tilde{x}}_{*},{\tilde{\lambda }}_{*})\le {ϵ}_{\mathrm{tol}}$ is found, where ${ϵ}_{\mathrm{tol}}>0$ is the user provided error tolerance. We denote the iteration counter by $j$ for the “outer loop” and require that the approximate solution $({\tilde{x}}_{*,j+1},{\tilde{\lambda }}_{*,j+1})$ of the barrier problem (2.6), for a given value of ${\mu }_j,$ satisfies the tolerance $G_{{\mu }_j}({\tilde{x}}_{*,j+1},{\tilde{\lambda }}_{*,j+1})\le {\kappa }_{ϵ}{\mu }_j$ for a constant ${\kappa }_{ϵ}>0,$ before the algorithm continues with the solution of the next barrier problem. A precise description of the algorithm follows.

Algorithm I

Initialize. Give starting point $(x_0,{\lambda }_0)$ with $x_0>0$ ; ${\mu }_0>0;$ ${ϵ}_{\mathrm{tol}}>0;$ ${\kappa }_{ϵ}>0;{\kappa }_{\mu }\in (0,1);$ ${\theta }_{\mu }\in (1,2);$ ${\tau }_{\min }\in (0,1);$ ${\theta }_{\max }\in (\theta (x_0),\mathrm{\infty }];{\theta }^{\min }>0;$ ${\gamma }_{\theta },{\gamma }_{\phi }\in (0,1);\delta >0;{\gamma }_{\alpha }\in (0,1];s_{\theta }>1;s_{\phi }\ge 2s_{\theta };{\eta }_{\phi }\in (0,\frac{1}{2}).$ Initialize the filter ${\mathcal{F}}_0:=\{(\theta ,\phi )\in {\mathbb{R}}^2:\theta \ge {\theta }_{\max }$ } and the iteration counter $j\leftarrow 0$ and $k\leftarrow 0.$ Obtain ${\tau }_0$ from (2.10).

Check convergence for the overall problem. If $G_0=\Vert D_k^2{\mathrm{\nabla }}_x{l}_k\Vert +\Vert c_k{\Vert }_1\le {ϵ}_{\mathrm{tol}}$ , stop;

Check convergence for the barrier problem. If $G_{{\mu }_j}=\Vert D_k^2{\mathrm{\nabla }}_x{l}_k-{\mu }_{j}r\Vert +\Vert c_k{\Vert }_1\le {\kappa }_{ϵ}{\mu }_j$ , then:

• 3.1

Compute ${\tau }_{j+1}$ and ${\mu }_{j+1}$ from (2.10) and (2.11), and set $j\leftarrow j+1$ .

3.2

Re-initialize the filter ${\mathcal{F}}_k\leftarrow \{(\theta ,\phi )\in {\mathbb{R}}^2:\theta \ge {\theta }_{\max }$ };

3.3

If $k=0$ repeat step 3, if not, then go to the next step.

Compute search direction. Compute $({\hat{s}}_k,s_k^{\lambda })$ by solving the linear system

$$\begin{array}{r}\left(\begin{array}{cc}{D}_k{H}_k{D}_k+E_k& D_k{A}_k^T\\ A_k{D}_k& 0\end{array}\right)\left(\begin{array}{c}\hat{s}\\ s^{\lambda }\end{array}\right)\\ =-\left(\begin{array}{c}{D}_k(\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k)+A_k^T{\lambda }_k)\\ c_k\end{array}\right)\end{array}$$

(2.19)

where $H_k$ is the Hessian matrix ${\mathrm{\nabla }}_{xx}^2{l}_k$ or its approximation. Then compute $(s_k,s_k^{\lambda })$ by setting $s_k=D_k{\hat{s}}_k.$ If the linear system is detected to be too ill-conditioned, go to feasibility restoration phase.

Backtracking line search.

• 5.1

Set ${\alpha }_{k,0}=1$ and $l\leftarrow 0$ .

5.2

Compute new trial point $x_k({\alpha }_{k,l}):=x_k+{\alpha }_{k,l}{s}_k$ .

5.3

Check acceptability to the filter. If $(\theta (x_k({\alpha }_{k,l})),{\phi }_{{\mu }_j}(x_k({\alpha }_{k,l})))\in {\mathcal{F}}_k,$ reject the trial step size and go to 5.5.

5.4

Check sufficient decrease with respect to current iterate.

• 5.4.1

Case I: $\theta (x_k)\le {\theta }^{min}$ and

$$\begin{array}{r}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k<0\mathrm{and}{\alpha }_{k,l}[-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k{]}^{s_{\phi }}>\delta {\theta }_k^{s_{\theta }}\end{array}$$

(2.20)

holds: If the Armijo condition

$${\phi }_{{\mu }_j}(x_k({\alpha }_{k,l}))\le {\phi }_{{\mu }_j}(x_k)+{\eta }_{\phi }{\alpha }_{k,l}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k$$

(2.21)

holds and $x_k({\alpha }_{k,l})>0$ , accept the trial step and go to step 6. Otherwise, go to step 5.5.

5.4.2

Case II: $\theta (x_k)>{\theta }^{min}$ or (2.20) is not satisfied: If

$$\begin{array}{r}\theta (x_k({\alpha }_{k,l}))\le (1-{\gamma }_{\theta }){\theta }_k\mathrm{or}{\phi }_{{\mu }_j}(x_k({\alpha }_{k,l}))<{\phi }_{{\mu }_j}(x_k)-{\gamma }_{\phi }{\theta }_k\end{array}$$

(2.22)

holds and $x_k({\alpha }_{k,l})>0$ , accept the trial step and go to step 6. Otherwise, go to step 5.5.

5.5

Compute second-order correction step. If $l\ne 0$ , go to step 5.8. Otherwise, compute the second-order correction step $s_k^{\mathrm{soc}}$ by (2.17), and obtain the next new trial point ${\tilde{x}}_{k+1}=x_k+s_k+s_k^{\mathrm{soc}}.$

5.6

Check acceptability to the filter. If $(\theta ({\tilde{x}}_{k+1}),{\phi }_{{\mu }_j}({\tilde{x}}_{k+1}))\in {\mathcal{F}}_k$ , reject the second-order correction step and go to the step 5.8.

5.7

Check sufficient decrease with respect to current iterate.

• 5.7.1

Case I: $\theta (x_k)\le {\theta }^{min}$ and (2.20) holds (for ${\alpha }_{k,0}$ ): If

$${\phi }_{{\mu }_j}({\tilde{x}}_{k+1})\le {\phi }_{{\mu }_j}(x_k)+{\eta }_{\phi }\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k$$

(2.23)

holds and ${\tilde{x}}_{k+1}>0$ , accept $x_{k+1}:={\tilde{x}}_{k+1}$ and go to step 6. Otherwise, go to step 5.8.

5.7.2

Case II: $\theta (x_k)>{\theta }^{min}$ or (2.20) is not satisfied (for ${\alpha }_{k,0}$ ): If

$$\begin{array}{r}\theta ({\tilde{x}}_{k+1})\le (1-{\gamma }_{\theta })\theta (x_k),\mathrm{or}{\phi }_{{\mu }_j}({\tilde{x}}_{k+1})\le {\phi }_{{\mu }_j}(x_k)-{\gamma }_{\phi }\end{array}\theta (x_k)$$

holds and ${\tilde{x}}_{k+1}>0$ , accept $x_{k+1}:={\tilde{x}}_{k+1}$ and go to step 6. Otherwise, go to step 5.8.

5.8

Set ${\alpha }_{k,l+1}={\gamma }_{\alpha }{\alpha }_{k,l},$ and $l\leftarrow l+1.$ If ${\alpha }_{k,l}<{\alpha }_k^{\min }$ with ${\alpha }_k^{\min }$ defined in (2.15), go to the feasibility phase. Otherwise, go back to step 5.2.

Accept trial point. Set ${\alpha }_k:={\alpha }_{k,l},$ $x_{k+1}:=x_k+{\alpha }_k{s}_k$ and ${\lambda }_{k+1}:={\lambda }_k+{\alpha }_k{s}_{\lambda }$ .

Augment the filter if necessary. If (2.20) or (2.21) does not hold for ${\alpha }_k$ , augment the filter using ${\mathcal{F}}_{k+1}:={\mathcal{F}}_k\bigcup \{(\theta ,\phi )\in {\mathbb{R}}^2:\theta \ge (1-{\gamma }_{\theta }){\theta }_k\mathrm{and}\phi \ge {\phi }_{{\mu }_j}(x_k)-{\gamma }_{\phi }{\theta }_k\}.$ Otherwise, set ${\mathcal{F}}_{k+1}={\mathcal{F}}_k$ .

Set: $k=k+1$ , go to step 2.

Feasibility restoration phase. Augment the filter, and compute a new iterate $x_{k+1}>0$ by decreasing the infeasibility measure $\theta (x)$ , so that $x_{k+1}$ satisfies the sufficient decrease conditions (2.22) and is acceptable to the filter. Continue with the regular iteration in step 9.

Convergence analysis

We denote by $\mathcal{A}\subseteq \mathbb{N}$ the set of indices of those iterations in which the filter has been augmented, by $\mathcal{R}\subseteq \mathbb{N}$ that of all iterations indices in which the feasibility restoration phase is invoked, and by ${\mathcal{R}}_{\mathrm{inc}}\subseteq \mathcal{R}$ that of those iteration counters in which the restoration phase is invoked from step 4. Obviously, the relationship ${\mathcal{R}}_{\mathrm{inc}}\subseteq \mathcal{R}\subseteq \mathcal{A}\subseteq \mathbb{N}$ holds. For the global convergence analysis of this algorithm, we state the following assumptions.

Assumptions G. Let $\{x_k\}$ be the sequence generated by Algorithm I, where we assume that the feasibility restoration phase in step 10 always terminates successfully and the algorithm does not stop in step 2.

• (G1)

$f$ and $c$ are differentiable on an open set $C$ , where $C\subseteq {\mathbb{R}}^n$ with $[x_k,x_k+s_k]\in C$ for all $k\notin {\mathcal{R}}_{\text{inc}}$ . For $f$ and $c$ , their function values and their first derivatives are bounded and Lipschitz-continuous over $C$ .

(G2)

The matrices $H_k$ are uniformly bounded for all $k\notin {\mathcal{R}}_{\mathrm{inc}}.$

(G3)

The Hessian approximations $D_k{H}_k{D}_k+E_k$ are uniformly positive definite on the null subspace of $A_k{D}_k$ . In other words, there exists a constant $M_H>0$ so that for all $k\notin {\mathcal{R}}_{\mathrm{inc}}$

$${\lambda }_{min}(V_k^T[D_k{H}_k{D}_k+E_k]V_k)\ge M_H,$$

(3.1)

where ${\lambda }_{min}(A)$ is the minimum eigenvalue of matrix $A$ , the columns of $V_k\in R^{n\times (n-m)}$ form an orthonormal basis matrix of the null space of $A_k{D}_k.$

(G4)

The matrices $D_k{A}_k^T$ have full column rank over $C$ . Norm sequences $\{\Vert (A_k{D}_k{)}^{+}\Vert \}$ are bounded for all $k$ .

(G5)

There exists a constant ${\theta }_{\mathrm{inc}}>0$ so that $k\notin {\mathcal{R}}_{\mathrm{inc}}$ whenever $\theta (x_k)\le {\theta }_{\mathrm{inc}}.$

(G6)

The iterates $\{x_k\}$ are bounded.

(G7)

There exist constants ${\delta }_{\theta },{\delta }_x>0$ so that whenever the restoration phase is called in step 10 in an iteration $k\in \mathcal{R}$ with ${\theta }_k\le {\delta }_{\theta },$ it returns a new iterate with $x_{k+1}^{(i)}\ge x_k^{(i)}$ for all components satisfying $x_k^{(i)}\le {\delta }_x.$

Using the QR-factorization of $D_k{A_k}^T$ , we can obtain matrices $U_k\in R^{n\times m}$ and $V_k\in R^{n\times (n-m)}$ . The columns of $[U_k,V_k]$ form an orthonormal basis of $R^n$ . Set

$${\overline{q}}_k:=-[A_k{D}_k{U}_k{]}^{-1}{c}_k$$

(3.2\rm a)

$$\begin{array}{rl}{\overline{p}}_k:=& -[V_k^T(D_k{H}_k{D}_k+E_k)V_k{]}^{-1}{V}_k^T[(D_k{H}_k{D}_k+E_k)q_k\\ & +D_k\mathrm{\nabla }{\phi }_{\mu }(x_k)]\\ & q_k:=U_k{\overline{q}}_k,p_k:=V_k{\overline{p}}_k\end{array}$$

(3.2\rm b)

the overall search direction $s_k=q_k+p_k$ can be taken, where $q_k$ and $p_k$ are two orthogonal components.

We define the criticality measure as

$$\begin{array}{r}\chi (x_k):=\{\begin{array}{cc}\Vert {\overline{p}}_k{\Vert }_2,& \mathrm{if}k\notin {\mathcal{R}}_{\mathrm{inc}}\\ \mathrm{\infty },& \mathrm{otherwise}\end{array}\end{array}$$

(3.3)

Consider a subsequence of iterates $\{x_{k_i}\}$ with ${\lim }_i\chi (x_{k_i})=0$ and ${\lim }_i{x}_{k_i}=x_{*}$ for some feasible limit point $x_{*}$ . Using the definition of $\chi (x_k)$ we get $k_i\notin {\mathcal{R}}_{\mathrm{inc}}$ for $i$ sufficiently large. Assumption (G4) and (3.2a) imply that ${\lim }_i{\overline{q}}_{k_i}=0.$ Therefore, from ${\lim }_i\chi (x_{k_i})=0,$ Assumption (G3) we obtain ${\lim }_i\Vert V_{k_i}^T{D}_{k_i}\mathrm{\nabla }{\phi }_{\mu }(x_{k_i})\Vert =0.$ Therefore, $\chi (x_k)$ defined in this way is an optimality measure for the barrier problem (2.6).

The following lemma can be found by Wätcher and Biegler ⁶ and indicates that the iterates generated by Algorithm I (for the barrier algorithm) are bounded away from the boundary of the region defined by the constraints $x\ge 0$ .

Lemma 3.1

Suppose Assumptions G hold. Then there exists a constant ${ϵ}_x>0$ so that $x_k\ge {ϵ}_{x}r$ for all $k.$

Lemma 3.2

Suppose Assumptions G hold. Then there exist constants $M_d,M_{\lambda },M_m>0$ , such that $\Vert s_k\Vert \le M_d,\Vert {\lambda }_{k+1}\Vert \le M_{\lambda },|\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k|\le M_m$ for all $k\notin {\mathcal{R}}_{\mathrm{inc}},$ where ${\lambda }_{k+1}=s_k^{\lambda }+{\lambda }_k.$

The proofs are similar to those of Lemma 1 by Wätcher and Biegler ⁶ and are omitted.

Lemma 3.3

Suppose Assumptions G hold. If $\{x_{k_i}\}$ is a subsequence of iterates for which $\chi (x_{k_i})\ge ϵ$ with a constant $ϵ>0$ independent of $i$ , then there exist constants ${ϵ}_1,{ϵ}_2>0$ , such that

$$\theta (x_{k_i})\le {ϵ}_1\Rightarrow \mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k\le -{ϵ}_2$$

(3.4)

for all $i.$

Proof

Consider a subset $x_{k_i}$ of iterates with $\chi (x_{k_i})=\Vert {\overline{p}}_{k_i}{\Vert }_2\ge ϵ$ . Then, by Assumption (G4), for all $x_{k_i}$ with $\theta (x_{k_i})\le {\theta }_{\mathrm{inc}}$ we have $k_i\notin {\mathcal{R}}_{\mathrm{inc}}$ . Since (3.2a) implies that $q_{k_i}=O(\Vert c(x_{k_i})\Vert ),$ it follows that for $k_i\notin {\mathcal{R}}_{\mathrm{inc}}$

$$\begin{array}{rl}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_{k_i}{)}^T{s}_{k_i}& =\mathrm{\nabla }{\phi }_{{\mu }_j}(x_{k_i}{)}^T{V}_{k_i}{\overline{p}}_{k_i}+\mathrm{\nabla }{\phi }_{{\mu }_j}(x_{k_i}{)}^T{q}_{k_i}(2.19)=\\ & -{\overline{p}}_{k_i}^T[V_{k_i}^T(D_{k_i}{H}_{k_i}{D}_{k_i}+E_{k_i})V_{k_i}]{\overline{p}}_{k_i}-{\overline{p}}_{k_i}^T{V}_{k_i}^T(D_{k_i}{H}_{k_i}{D}_{k_i}+E_{k_i})q_{k_i}\\ & +\mathrm{\nabla }{\phi }_{{\mu }_j}(x_{k_i}{)}^T{q}_{k_i}(\mathrm{G}3)\le -c_1\Vert {\overline{p}}_{k_i}{\Vert }_2^2+c_2\Vert {\overline{p}}_{k_i}\Vert \Vert c_{k_i}\Vert \\ & +c_3\Vert c_{k_i}\Vert (3.3)\le \chi (x_{k_i})(-c_1ϵ+c_2{\theta }_{k_i}+\frac{c_3{\theta }_{k_i}}{ϵ})\end{array}$$

for some constants $c_1,c_2,c_3>0.$ If we now define ${ϵ}_1:=\min \{{\theta }_{\mathrm{inc}},\frac{{ϵ}^2{c}_1}{2(c_2ϵ+c_3)}\}$ , it follows for all $x_{k_i}$ with $\theta (x_{k_i})\le {ϵ}_1$ that $\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k\le -\frac{ϵc_1}{2}\chi (x_{k_i})\le -\frac{{ϵ}^2{c}_1}{2}.$ The claim follows after defining ${ϵ}_2:=\frac{{ϵ}^2{c}_1}{2}$ .  □

We can build on the previous lemmas and use the same arguments as in the proof of Theorem 2 by Wätcher and Biegler ⁶ to prove the following global convergence result for the proposed method.

Theorem 3.1

Suppose Assumptions G hold. Then $\underset{k\to \mathrm{\infty }}{lim}\theta (x_k)=0\mathrm{and}\underset{k\to \mathrm{\infty }}{lim}inf\chi (x_k)=0$

The local convergence analysis of the algorithm is based on the necessary assumptions as follows:

Assumptions L. Assume that $\{x_k\}$ converges to a local solution $x_{*}$ of problem (1.1). Assume furthermore that the standard Newton’s method assumptions and the following hold.

• (L1)

In (2.19), $D_k{H}_k{D}_k+E_k$ is uniformly positive definite on the null space of $A_k{D}_k,$ as well as bounded.

(L2)

$$\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert (H_k-{\mathrm{\nabla }}_{xx}^2{l}_{*})s_k\Vert }{\Vert s_k\Vert }=0.$$

(3.5)

Define $W(x,\lambda ):={\mathrm{\nabla }}_{xx}^2\mathcal{L}(x,\lambda ).$ Since

$$D_k{W}_k{D}_k=D_k{\mathrm{\nabla }}_{xx}^2{\mathcal{L}}_k{D}_k=D_k({\mathrm{\nabla }}_{xx}^2{l}_k+{\mu }_j{D}_k^{-4})D_k=D_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+Z_k=D_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+E_k$$

condition (3.5) could be written as follows:

$$\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert (D_k{H}_k{D}_k+E_k-D_{*}{W}_{*}{D}_{*})s_k\Vert }{\Vert s_k\Vert }=0$$

which mean

$$s_k^T(D_k{H}_k{D}_k+E_k)s_k=s_k^T{D}_k{W}_k{D}_k{s}_k+o(\Vert s_k{\Vert }^2)$$

(3.6)

Lemma 3.4

If Assumptions L hold, then there exists a neighborhood $U_1$ of $x_{*}$ , so that for all $x_k\in U_1$ we have

$$\Vert s_k^{\mathrm{soc}}\Vert =O(\Vert s_k{\Vert }^2)$$

(3.7)

$$\Vert c(x_k+s_k+s_k^{\mathrm{soc}})\Vert =o(\Vert s_k{\Vert }^2)$$

(3.8)

Proof

The proof is essentially identical to that of Lemma 4.1 by Wätcher and Biegler. ⁵ $c(x_k+s_k)=c(x_k)+A_k{s}_k+O(\Vert s_k{\Vert }^2)=(\Vert s_k{\Vert }^2)$ which implies (3.7) by (2.16). Since

$$\begin{array}{rl}c(x_k+s_k+s_k^{\mathrm{soc}})& =c(x_k+s_k)+A(x_k+s_k)s_k^{\mathrm{soc}}+O(\Vert s_k^{\mathrm{soc}}{\Vert }^2)\\ & =-D_k^{-1}(A_k{D}_k)s_k^{\mathrm{soc}}+A(x_k+s_k)s_k^{\mathrm{soc}}+O(\Vert s_k^{\mathrm{soc}}{\Vert }^2)\\ & =[A(x_k+s_k)-A_k]s_k^{\mathrm{soc}}+O(\Vert s_k^{\mathrm{soc}}{\Vert }^2)=o(\Vert s_k{\Vert }^2)\end{array}$$

for $x_k$ close to $x_{*}$ , where noting that $A(x)$ is Lipschitz-continuous, the claim follows.  □

Lemma 3.5

Suppose Assumptions L hold and the strict complementarity of problem (1.1) holds at the limit point $x_{*}$ of $\{x_k\}$ . Then there exists a neighborhood $U_2\subseteq U_1$ of $x_{*}$ so that whenever (2.20) holds for ${\alpha }_{k,l}=1$ , the Armijo condition (2.23) is satisfied.

Proof

Let the step size scalar ${\alpha }_{k,l}=min\{-{\tau }_j\frac{x_k^{(i)}}{s_k^{(i)}}:s_k^{(i)}<0,i=1,\dots ,n\}$ along $s_k$ to the boundary of the inequality constraints $x_k({\alpha }_{k,l})>0$ . Because the strict complementarity of problem (1.1) holds at the limit point $x_{*}$ of $\{x_k\},$ we have that $|x_{*}^{(i)}|+|e_{*}^{(i)}|>0,i=1,\dots ,m.$ Pick $ϵ=\frac{1}{2}(|x_{*}^{(i)}|+|e_{*}^{(i)}|).$

If $i\notin \mathcal{I}(x_{*}),$ then $|x_{*}^{(i)}|=2ϵ>0.$ $x_k\to x_{*}$ and $x_k>0$ then imply that both $s_k\to 0$ and $x_k^{(i)}=|x_k^{(i)}|\ge \frac{1}{2}|x_{*}^{(i)}|=ϵ$ hold. Since ${\tau }_j\in (0,1)$ is bounded, we can obtain from (2.13)

$${\alpha }_{k,l}=-\frac{{\tau }_j{x}_k^{(t)}}{s_k^{(t)}}\ge \frac{{\tau }_jϵ}{\Vert s_k\Vert }\to \mathrm{\infty }$$

If $i\in \mathcal{I}(x_{*}),$ then $|e_{*}^{(i)}|=2ϵ.$ Since $(x_k,{\lambda }_k)\to (x_{*},{\lambda }_{*}),$ we have $|e_k^{(i)}|\ge \frac{1}{2}|e_{*}^{(i)}|=ϵ,$ and $s_k\to 0,s_k^{\lambda }\to 0.$ Since for sufficiently large $j,$ ${\tau }_j\to 1$ and ${\mu }_j\to 0$ , we deduce that, for sufficiently large $k,$

$${\alpha }_{k,l}=-\frac{{\tau }_j{x}_k^{(t)}}{s_k^{(t)}}=\frac{{\tau }_j}{\frac{({\mathrm{\nabla }}_{xx}^2{l}_k{s}_k{)}^{(t)}}{e_k^{(t)}}+\frac{(A_k{s}_k^{\lambda }{)}^{(t)}}{e_k^{(t)}}+1-\frac{{\mu }_j}{x_k^{(t)}{e}_k^{(t)}}}\to 1$$

From the above discussion, we have obtained that if the step size ${\alpha }_{k,l}$ is given in (2.13), then the step size will be determined in (2.20) and (2.21). Therefore, we will show that whenever (2.20) holds for ${\alpha }_{k,l}=1$ , the Armijo condition (2.23) is satisfied.

First, we try to get the relationship between $p_k$ , $q_k$ and $s_k.$ Choose $U_1$ to be the neighborhood from Lemma 3.4. From the switching condition (2.20), we have

$$\begin{array}{r}\Vert c(x_k)\Vert =\theta (x_k)<{\delta }^{-\frac{1}{s_{\theta }}}[-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k{]}^{\frac{s_{\phi }}{s_{\theta }}}=o(\Vert s_k{\Vert }^2)\end{array}$$

(3.9)

since $s_{\phi }>2s_{\theta }$ and $\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k)$ is uniformly bounded in $U_1$ . From (3.2a) and (3.9), it is easy to verify that

$$q_k=O(\Vert c_k\Vert )=o(\Vert s_k{\Vert }^2)=o(p_k^T{p}_k+q_k^T{q}_k)=o(\Vert {\overline{p}}_k{\Vert }^2)+o(\Vert q_k{\Vert }^2)$$

(3.10)

and therefore $q_k=o(\Vert {\overline{p}}_k{\Vert }^2).$ On the other hand, we can get $s_k=O(\Vert p_k\Vert )+O(\Vert q_k\Vert )=O(\Vert {\overline{p}}_k\Vert )+o(\Vert {\overline{p}}_k{\Vert }^2).$ Furthermore, we can easily get

$$\begin{array}{rl}{s}_k& =O(\Vert {\overline{p}}_k\Vert )\\ \mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k^{\mathrm{soc}}& \stackrel{(2.16)}{=}-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{D}_k(A_k{D}_k{)}^{+}c(x_k+s_k)\\ & \stackrel{(2.19)}{=}[D_k^{-2}(D_k{H}_k{D}_k+E_k)s_k+A_k^T{\lambda }_{k+1}{]}^T\\ & D_k(A_k{D}_k{)}^{+}c(x_k+s_k)\end{array}$$

(3.11)

$$=\frac{1}{2}{s}_k^T\sum _{i=1}^m{\lambda }_{k+1}^{(i)}{\mathrm{\nabla }}^2{c}_k^{(i)}{s}_k+o(\Vert s_k{\Vert }^2)$$

(3.12)

and

$$\begin{array}{rl}& {\phi }_{{\mu }_j}(x_k)-{\phi }_{{\mu }_j}(x_k+s_k+s_k^{\mathrm{soc}})\\ & =-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T(s_k+s_k^{\mathrm{soc}})-\frac{1}{2}(s_k+s_k^{\mathrm{soc}}{)}^T{\mathrm{\nabla }}_{xx}^2{\phi }_{{\mu }_j}(x_k{)}^T\\ & (s_k+s_k^{\mathrm{soc}})+o(\Vert s_k{\Vert }^2)\\ & =-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k-\frac{1}{2}{s}_k^T\sum _{i=1}^m{\lambda }_{k+1}^{(i)}{\mathrm{\nabla }}^2{c}_k^{(i)}{s}_k\\ & -\frac{1}{2}{s}_k^T{\mathrm{\nabla }}_{xx}^2{\phi }_{{\mu }_j}(x_k{)}^T{s}_k+o(\Vert s_k{\Vert }^2)\\ & =-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k-\frac{1}{2}{s}_k^T{W}_k{s}_k+o(\Vert s_k{\Vert }^2)\end{array}$$

(3.13)

simply that

$$\begin{array}{rl}& {\phi }_{{\mu }_j}(x_k+s_k+s_k^{\mathrm{soc}})-{\phi }_{{\mu }_j}(x_k)-\eta \mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k\\ & \stackrel{(3.13)}{=}(1-\eta )\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k+\frac{1}{2}{s}_k^T{W}_k{s}_k+o(\Vert s_k{\Vert }^2)\\ & \stackrel{(2.9)}{=}(\eta -1)s_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{s}_k\\ & +(1-\eta ){\lambda }_{k+1}^T{c}_k+\frac{1}{2}{s}_k^T{W}_k{s}_k+o(\Vert s_k{\Vert }^2)\\ & \stackrel{(3.6)}{=}(\eta -\frac{1}{2})s_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{s}_k+o(\Vert s_k{\Vert }^2)\\ & \stackrel{(3.11)}{=}(\eta -\frac{1}{2}){\overline{p}}_k^T{V}_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{V}_k{\overline{p}}_k\\ & +o(\Vert {\overline{p}}_k{\Vert }^2)\end{array}$$

where ${\lambda }_{k+1}=({\lambda }_{k+1}^{(1)},\dots ,{\lambda }_{k+1}^{(m)}).$ Since ${\overline{p}}_k\to 0$ as $x_k\to x_{*}$ , the proposed algorithm implies the Armijo condition (2.23) with ${\alpha }_{k,l}=1$ because of Assumption (L1) and $\eta <\frac{1}{2}$ , if $x_k$ is sufficiently close to $x_{*}$ .  □

In the following, we employ the exact penalty function ${\varphi }_{\rho }(x)={\phi }_{{\mu }_j}(x)+\rho \theta (x)$ and the model of the penalty function $q_{\rho }(x_k,s)={\phi }_{{\mu }_j}(x_k)+\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^{T}s+\frac{1}{2}{s}^T{W}_{k}s+\rho \Vert A_k^{T}s+c_k{\Vert }_1$ to prove the local convergence results and to regard the effect of second-order correction steps. The algorithm never refers to them. Lemma 3.6

Suppose Assumptions L hold. Then there exists a neighborhood $U_3\subseteq U_2$ and a constant $\rho \ge \Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }}$ , so that for all $x_k\in U_3$ we have ${\varphi }_{\rho }(x_k)-{\varphi }_{\rho }(x_k+s_k+s_k^{\mathrm{soc}})\ge \frac{1+{\gamma }_{\theta }}{2}(q_{\rho }(x_k,0)-q_{\rho }(x_k,s_k))\ge 0.$

Proof

Since

$$\begin{array}{rl}& q_{\rho }(x_k,0)-q_{\rho }(x_k,s_k)=\rho \Vert c_k{\Vert }_1-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k-\frac{1}{2}{s}_k^T{W}_k{s}_k\\ & \stackrel{(2.9)}{=}\rho \Vert c_k{\Vert }_1+s_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{s}_k-{\lambda }_{k+1}^T\\ & c_k-\frac{1}{2}{s}_k^T{W}_k{s}_k\\ & =\rho \Vert c_k{\Vert }_1-{\lambda }_{k+1}^T{c}_k+\frac{1}{2}{s}_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{s}_k\\ & +\frac{1}{2}{s}_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k-D_k{W}_k{D}_k)D_k^{-1}{s}_k\\ & \ge (\rho -\Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }})\Vert c_k{\Vert }_1+\frac{1}{2}{s}_k^T{D}_k^{-1}(D_k{H}_k{D}_k+E_k)D_k^{-1}{s}_k\\ & +o(\Vert s_k{\Vert }^2)\end{array}$$

choosing $\rho \ge \Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }},$ we obtain $q_{\rho }(x_k,0)-q_{\rho }(x_k,s_k)\ge 0,$ which follows the required latter inequality. Further, we have that

$$\begin{array}{rl}& {\varphi }_{\rho }(x_k)-{\varphi }_{\rho }(x_k+s_k+s_k^{\mathrm{soc}})-\frac{1+{\gamma }_{\theta }}{2}(q_{\rho }(x_k,0)-q_{\rho }(x_k,s_k))\\ & =\rho {\theta }_k-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k-\frac{1}{2}{s}_k^T{W}_k{s}_k\\ & -\frac{1+{\gamma }_{\theta }}{2}(\rho \Vert c_k{\Vert }_1-\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k-\frac{1}{2}{s}_k^T{W}_k{s}_k)+o(\Vert s_k{\Vert }^2)\\ & =\frac{{\gamma }_{\theta }-1}{2}\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k{)}^T{s}_k+\frac{{\gamma }_{\theta }-1}{4}{s}_k^T{W}_k{s}_k\\ & +\frac{1-{\gamma }_{\theta }}{2}\rho \Vert c_k{\Vert }_1+o(\Vert s_k{\Vert }^2)\\ & \ge \frac{1-{\gamma }_{\theta }}{2}(\rho -\Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }})\Vert c_k{\Vert }_1-\frac{{\gamma }_{\theta }-1}{4}{\overline{p}}_k^T{V}_k^T{D}_k^{-1}\\ & (D_k{H}_k{D}_k+E_k)D_k^{-1}{V}_k{\overline{p}}_k\\ & +o(\Vert {\overline{p}}_k{\Vert }^2)+o(\Vert s_k{\Vert }^2)\\ & =\frac{1-{\gamma }_{\theta }}{2}(\rho -\Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }})\Vert c_k{\Vert }_1+\frac{1-{\gamma }_{\theta }}{4}{\overline{p}}_k^T{V}_k^T{D}_k^{-1}\\ & (D_k{H}_k{D}_k+E_k)D_k^{-1}{V}_k{\overline{p}}_k+o(\Vert {\overline{p}}_k{\Vert }^2)\end{array}$$

The last inequity is induced by using ${\gamma }_{\theta }<1$ and Assumption (L1). Then defining $\rho \ge \Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }}$ , we get our desired results.  □

For the necessary of showing the main local convergence theorem, we define constants ${\rho }_1,{\rho }_2,{\rho }_3$ with: ${\rho }_1=\rho >\Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }},{\rho }_2=\frac{1+{\gamma }_{\theta }}{1-{\gamma }_{\theta }}{\rho }_1+\frac{3{\gamma }_f}{1-{\gamma }_{\theta }},{\rho }_3=(1-{\gamma }_{\theta }){\rho }_2-{\gamma }_f.$

Lemma 3.7

Suppose Assumptions L hold. Then there exists a neighborhood $U_3\subseteq U_2$ and constants ${\rho }_1,{\rho }_2,{\rho }_3>0$ , so that for all $x_k\in U_3$ , we have

$$2{\gamma }_{\theta }{\rho }_2<(1+{\gamma }_{\theta })({\rho }_2-{\rho }_1)-2{\gamma }_f$$

(3.14\rm a)

$$2{\rho }_3\ge (1+{\gamma }_{\theta }){\rho }_1+(1-{\gamma }_{\theta }){\rho }_2$$

(3.14\rm b)

$${\rho }_i>\Vert {\lambda }_{k+1}{\Vert }_{\mathrm{\infty }},\mathrm{for}i=1,2,3$$

(3.14\rm c)

Proof.

Using the definitions of ${\rho }_i,i=1,2,3$ , we get

$$\begin{array}{rl}& (1+{\gamma }_{\theta })({\rho }_2-{\rho }_1)-2{\gamma }_f-2{\gamma }_{\theta }{\rho }_2\\ & =(1-{\gamma }_{\theta }){\rho }_2-(1+{\gamma }_{\theta }){\rho }_1-2{\gamma }_f\\ & =(1+{\gamma }_{\theta }){\rho }_1+3{\gamma }_f-(1+{\gamma }_{\theta }){\rho }_1-2{\gamma }_f={\gamma }_f>0.\end{array}$$

It follows that $2{\gamma }_{\theta }{\rho }_2<(1+{\gamma }_{\theta })({\rho }_2-{\rho }_1)-2{\gamma }_f.$ From

$$\begin{array}{rl}(1+{\gamma }_{\theta }){\rho }_1+(1-{\gamma }_{\theta }){\rho }_2-2{\rho }_3& =(1+{\gamma }_{\theta }){\rho }_1+(1-{\gamma }_{\theta }){\rho }_2\\ & -2(1-{\gamma }_{\theta }){\rho }_2+2{\gamma }_f\\ \\ & =(1+{\gamma }_{\theta }){\rho }_1-(1+{\gamma }_{\theta }){\rho }_1\\ & -3{\gamma }_f+2{\gamma }_f\\ & =-{\gamma }_f<0,\end{array}$$

the claim (3.14b) follows. Note that ${\rho }_2-{\rho }_1=\frac{2{\gamma }_{\theta }{\rho }_1}{1-{\gamma }_{\theta }}{\rho }_1+\frac{3{\gamma }_f}{1-{\gamma }_{\theta }}$ and ${\rho }_3-{\rho }_1={\gamma }_{\theta }{\rho }_1+2{\gamma }_f>0$ . Hence, we have ${\rho }_2,{\rho }_3>{\rho }_1$ . Combine the definition of ${\rho }_1$ to get (3.14c).  □

The following result corresponds to the result that Wätcher and Biegler ⁵ obtained for the local version of the line search filter methods. The proof is similar and is omitted.

Theorem 3.2

Suppose Assumptions L hold. Then, for $k$ sufficiently large, full steps of the form $x_{k+1}=x_k+s_k$ or $x_{k+1}=x_k+s_k+s_k^{\mathrm{soc}}$ are taken.

Theorem 3.3

Suppose Assumptions L hold. Then, for $k$ sufficiently large, $\{x_k\}$ converges to $x_{*}$ superlinearly. Furthermore, if $H_k={\mathrm{\nabla }}_{xx}^2{l}_k,$ then $\{x_k\}$ converges to $x_{*}$ quadratically.

Proof

According to Theorem 3.2, for $k$ sufficiently large, full steps of the form $x_{k+1}=x_k+s_k$ or $x_{k+1}=x_k+s_k+s_k^{\mathrm{soc}}$ are taken in Algorithm I. We start by showing the statements being true for $x_{k+1}=x_k+s_k.$

For the analysis below, it is convenient to use the following notations: $w_k=(x_k,{\lambda }_k{)}^T,$ $\mathrm{\Delta }{w}_k=(s_k,s_k^{\lambda }{)}^T,w_{k+1}=w_k+\mathrm{\Delta }{w}_k,$ $S_k=(\begin{array}{cc}{D}_k{H}_k{D}_k+E_k& D_k{A}_k^T\\ A_k{D}_k& 0\end{array})$ and

$T_k=(\begin{array}{c}{D}_k(\mathrm{\nabla }{\phi }_{{\mu }_j}(x_k)+A_k^T{\lambda }_k)\\ c_k\end{array}).$ Hence, $\mathrm{\nabla }{T}_k=(\begin{array}{cc}{D}_k{\mathrm{\nabla }}_{xx}^2{l}_k{D}_k+E_k& D_k{A}_k^T\\ A_k{D}_k& 0\end{array}).$ Since

$${\Vert (S_k-\mathrm{\nabla }{T}_{*})(w_{k+1}-w_k)\Vert }^2$$

we can obtain $\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert (S_k-\mathrm{\nabla }{T}_{*})(w_{k+1}-w_k)\Vert }{\Vert w_{k+1}-w_k\Vert }=0.$ Applying Theorem 3 by Yamashita and Yabe, ⁹ one can show that the sequence $\{w_k\}$ converges superlinearly to $w_{*},$ that is, $\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert w_{k+1}-w_{*}\Vert }{\Vert w_k-w_{*}\Vert }=0,$ which indicates that

$$\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert x_{k+1}-x_{*}\Vert }{\Vert x_k-x_{*}\Vert }=\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert x_k+s_k-x_{*}\Vert }{\Vert x_k-x_{*}\Vert }=0$$

(3.15)

We now consider the second case that full steps of the form $x_{k+1}=x_k+s_k+s_k^{\mathrm{soc}}$ are taken. Since for all large $k,$ we have $\Vert s_k\Vert =\Vert D_k{\hat{s}}_k\Vert =\Vert D_k(A_k{D}_k{)}^{-1}{c}_k\Vert \le K_1\Vert x_k-x_{*}\Vert ,$ for some positive constant $K_1.$ Therefore, (3.7) yields $\Vert s_k^{\mathrm{soc}}\Vert =O(\Vert s_k{\Vert }^2)=O(\Vert x_k-x_{*}{\Vert }^2).$ Further, we get $\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert s_k^{\mathrm{soc}}\Vert }{\Vert x_k-x_{*}\Vert }=0.$ Hence, (3.15) implies that:

$$\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert x_k+s_k+s_k^{\mathrm{soc}}-x_{*}\Vert }{\Vert x_k-x_{*}\Vert }\le \underset{k\to \mathrm{\infty }}{lim}\frac{\Vert x_k+s_k-x_{*}\Vert }{\Vert x_k-x_{*}\Vert }+\underset{k\to \mathrm{\infty }}{lim}\frac{\Vert s_k^{\mathrm{soc}}\Vert }{\Vert x_k-x_{*}\Vert }=0$$

If $H_k={\mathrm{\nabla }}_{xx}^2{l}_k,$ we can get $S_k=\mathrm{\nabla }{T}_k,$ and further

$$\begin{array}{rl}\Vert w_{k+1}-w_{*}\Vert & =\Vert w_k-w_{*}+\mathrm{\Delta }{w}_k\Vert =\Vert w_k-w_{*}-\mathrm{\nabla }{T}_k^{-1}{T}_k\Vert \\ & \le \Vert \mathrm{\nabla }{T}_k^{-1}\Vert \Vert T_k-T_{*}-\mathrm{\nabla }{T}_k(w_k-w_{*})\Vert \\ & =O(\Vert w_k-w_{*}{\Vert }^2)\end{array}$$

Hence, we can have $\Vert x_{k+1}-x_{*}\Vert =\Vert x_k+s_k-x_{*}\Vert \le O(\Vert x_k-x_{*}{\Vert }^2),$ which implies that $\Vert x_k+s_k+s_k^{\mathrm{soc}}-x_{*}\Vert \le \Vert x_k+s_k-x_{*}\Vert +\Vert s_k^{\mathrm{soc}}\Vert \le O(\Vert x_k-x_{*}{\Vert }^2)$

 □