Mathematics Subject Classification (2010) 65K05 · 65L05 · 65L20 · 90C53
Introduction
In this article, we consider the optimization problem with nonlinear equality constraints as follows:
min x ∈ R n f ( x ) subject to c ( x ) = 0 , (1) \begin{aligned}
\min_{x\in\mathfrak{R}^{n}}\quad&f(x)\\
\text{subject to}\quad&c(x)=0, \tag*{(1)}
\end{aligned} x ∈ R n min subject to f ( x ) c ( x ) = 0 , (1)
where f : R n → R f:\mathfrak{R}^{n}\to\mathfrak{R} f : R n → R and c : R n → R m c:\mathfrak{R}^{n}\to\mathfrak{R}^{m} c : R n → R m (m ≤ n m\le n m ≤ n ). This problem has many applications in engineering fields such as the visual-inertial navigation of an unmanned aerial vehicle maintaining the horizontal flight [11 ] [49], constrained sparse regression [8 ] , sparse signal recovery [20 , 83 ] , image restoration and de-noising [21 , 77 ] [57], the Dantzig selector [43], support vector machines [22 ] , and sparse principal component analysis (PCA) methods [15 , 86 , 84 ] . And there are many practical methods [65 ] [38, 42] and many efficient solvers (the built-in subroutine fmincon [72 ] of MATLAB 2020a [60 ] and the subroutine SNOPT [29 , 30 ] in the GAMS environment [23 ] ) to solve it based on the sequential quadratic programming (SQP) method [31 , 70 , 85 ] .
For the constrained optimization problem (1) , the continuation method [3 , 12 , 24 , 67 , 80 ] [37] is another method other than the traditional optimization method such as SQP [31 , 70 , 71 , 85 ] or the penalty function method [17 ] . The advantage of the continuation method over the SQP method is that the continuation method is capable of finding many local optimal points of the non-convex optimization problem by tracking its trajectory, and it is even possible to find the global optimal solution [6 , 73 , 87 ] [55]. However, the computational efficiency of the classical continuation methods is lower than that of the traditional optimization method such as SQP. Recently, Luo et al intensively investigate the continuation methods for nonlinear equations [50,53], linear programming problems [51], linear complementarity problems [56], unconstrained optimization problems [52,55], and linearly constrained optimization problems [49,54]. And they obtain the more robust and faster continuation methods than the traditional optimization methods.
Here, we extend their ideas to the optimization problem with nonlinear equality constraints. In order to improve the computational efficiency of the continuation method for the large-scale optimization problem further, we consider the regularization BFGS (a special quasi-Newton method) preconditioned technique for the regularization continuation method and use an adaptive time step control based on the trust-region updating strategy in this article. Moreover, in order to improve its robustness, we replace the inverse of the regularization BFGS matrix with the inverse of the regularization two-sided projection of the Hessian matrix in the ill-posed phase.
The rest of the paper is organized as follows. In Section 2, we give the regularization continuation method with the switching preconditioned technique and the trust-region updating strategy for the problem (1) . In Section 3, we analyze the global convergence of this new method. In Section 4, we report some promising numerical results of the new method, in comparison to the state-of-art optimization methods (SQP, the built-in subroutine fmincon [72 ] of MATLAB 2020a [60 ] and the subroutine SNOPT [29 , 30 ] in the GAMS environment [23 ] ) for some large-scale problems. Finally, we give some discussions and conclusions in Section 5.
The regularization continuation method
In this section, we give the regularization continuation method with the switching preconditioned technique and the adaptive time-stepping scheme based on the trust-region updating strategy [13 ] for the optimization problem with nonlinear equality constraints. Firstly, we consider the regularized projection gradient flow based on the KKT conditions of equality-constrained optimization problems. Then, we construct the regularization continuation method with the trust-region updating strategy to follow this special ordinary differential equations (ODEs). The new method uses the Broyden-Fletcher-Goldfarb-Shanno (BFGS) updating formula [5 , 18 , 25 , 76 ] as the preconditioned technique to improve its computational efficiency in the well-posed phase, and it adopts the inverse of the regularized two-sided projection Hessian as the pre-conditioner to improve its robustness in the ill-posed phase. Furthermore, we use the generalized continuation Newton method [53] to find an initial feasible point.
The regularized projection Newton flow
For the nonlinearly constrained optimization problem (1) , it is well known that its optimal solution x ∗ x^* x ∗ needs to satisfy the Karush-Kuhn-Tucker conditions (p. 328, [65 ] ) as follows:
∇ x L ( x , λ ) = ∇ f ( x ) + A ( x ) T λ = 0 , (2) \nabla_x L(x,\lambda)=\nabla f(x)+A(x)^T\lambda=0, \tag*{(2)} ∇ x L ( x , λ ) = ∇ f ( x ) + A ( x ) T λ = 0 , (2)
c ( x ) = 0 , (3) c(x)=0, \tag*{(3)} c ( x ) = 0 , (3)
where A ( x ) T = [ ∇ c 1 ( x ) , … , ∇ c m ( x ) ] A(x)^T=[\nabla c_1(x),\ldots,\nabla c_m(x)] A ( x ) T = [ ∇ c 1 ( x ) , … , ∇ c m ( x )] and the Lagrangian function L ( x , λ ) L(x,\lambda) L ( x , λ ) is defined by
L ( x , λ ) = f ( x ) + λ T c ( x ) . (4) L(x,\lambda)=f(x)+\lambda^T c(x). \tag*{(4)} L ( x , λ ) = f ( x ) + λ T c ( x ) . (4)
Similarly to the method of the negative gradient flow for the unconstrained optimization problem [33 ] , from the first-order necessary conditions (2)-(3), we can construct a dynamical system of differential-algebraic equations for problem (1) [14 , 74 ] [46, 47, 48, 49, 54] as follows:
d x d t = − ∇ L x ( x , λ ) = − ( ∇ f ( x ) + A ( x ) T λ ) , (5) \frac{dx}{dt}=-\nabla L_x(x,\lambda)=-(\nabla f(x)+A(x)^T\lambda), \tag*{(5)} d t d x = − ∇ L x ( x , λ ) = − ( ∇ f ( x ) + A ( x ) T λ ) , (5)
c ( x ) = 0. (6) c(x)=0. \tag*{(6)} c ( x ) = 0. (6)
By differentiating the algebraic constraint (6) with respect to t t t and substituting it into the differential equation (5) , we obtain
d c ( x ) d t = A ( x ) d x d t = − A ( x ) ( ∇ f ( x ) + A ( x ) T λ ) = − A ( x ) ∇ f ( x ) − A ( x ) A ( x ) T λ = 0. (7) \frac{dc(x)}{dt}=A(x)\frac{dx}{dt}=-A(x)\left(\nabla f(x)+A(x)^{T}\lambda\right)
= -A(x)\nabla f(x)-A(x)A(x)^{T}\lambda=0. \tag*{(7)} d t d c ( x ) = A ( x ) d t d x = − A ( x ) ( ∇ f ( x ) + A ( x ) T λ ) = − A ( x ) ∇ f ( x ) − A ( x ) A ( x ) T λ = 0. (7)
If we assume that matrix A ( x ) A(x) A ( x ) has full row rank further, from equation (7) , we obtain
λ = − ( A ( x ) A ( x ) T ) − 1 A ( x ) ∇ f ( x ) . (8) \lambda=-\left(A(x)A(x)^{T}\right)^{-1}A(x)\nabla f(x). \tag*{(8)} λ = − ( A ( x ) A ( x ) T ) − 1 A ( x ) ∇ f ( x ) . (8)
By substituting λ \lambda λ of equation (8) into equation (5) , we obtain the projected gradient flow [80 ] for the constrained optimization problem (1) as follows:
d x d t = − ( I − A ( x ) T ( A ( x ) A ( x ) T ) − 1 A ( x ) ) ∇ f ( x ) = − P ( x ) g ( x ) , (9) \frac{dx}{dt}=-\left(I-A(x)^{T}\left(A(x)A(x)^{T}\right)^{-1}A(x)\right)\nabla f(x)=-P(x)g(x), \tag*{(9)} d t d x = − ( I − A ( x ) T ( A ( x ) A ( x ) T ) − 1 A ( x ) ) ∇ f ( x ) = − P ( x ) g ( x ) , (9)
where g ( x ) = ∇ f ( x ) g(x)=\nabla f(x) g ( x ) = ∇ f ( x ) and the projection matrix P ( x ) P(x) P ( x ) is defined by
P ( x ) = I − A ( x ) T ( A ( x ) A ( x ) T ) − 1 A ( x ) . (10) P(x)=I-A(x)^{T}\left(A(x)A(x)^{T}\right)^{-1}A(x). \tag*{(10)} P ( x ) = I − A ( x ) T ( A ( x ) A ( x ) T ) − 1 A ( x ) . (10)
It is not difficult to verify ( P ( x ) ) 2 = P ( x ) (P(x))^{2}=P(x) ( P ( x ) ) 2 = P ( x ) . That is to say, the projection matrix P ( x ) P(x) P ( x ) is symmetric and its eigenvalues are 0 or 1. From Theorem 2.3.1 in p. 73 of [27 ] , we know that its matrix 2-norm is
∥ P ( x ) ∥ = 1. (11) \lVert P(x)\rVert=1. \tag*{(11)} ∥ P ( x )∥ = 1. (11)
We denote P ( x ) † P(x)^{\dagger} P ( x ) † as the Moore-Penrose generalized inverse of the projection matrix P ( x ) P(x) P ( x ) (see p. 11, [79 ] or [64 , 68 ] ). Since the projection matrix P ( x ) P(x) P ( x ) is symmetric and ( P ( x ) ) 2 = P ( x ) (P(x))^{2}=P(x) ( P ( x ) ) 2 = P ( x ) , it is not difficult to verify
P ( x ) † = P ( x ) . (12) P(x)^{\dagger}=P(x). \tag*{(12)} P ( x ) † = P ( x ) . (12)
Actually, from equation (12) , we have P ( x ) ( P ( x ) ) † P ( x ) = P ( x ) P(x)(P(x))^{\dagger}P(x)=P(x) P ( x ) ( P ( x ) ) † P ( x ) = P ( x ) , P ( x ) † P ( x ) P ( x ) † = P ( x ) † P(x)^{\dagger}P(x)P(x)^{\dagger}=P(x)^{\dagger} P ( x ) † P ( x ) P ( x ) † = P ( x ) † , ( P ( x ) † P ( x ) ) T = P ( x ) † P ( x ) (P(x)^{\dagger}P(x))^{T}=P(x)^{\dagger}P(x) ( P ( x ) † P ( x ) ) T = P ( x ) † P ( x ) and ( P ( x ) P ( x ) † ) T = P ( x ) P ( x ) † (P(x)P(x)^{\dagger})^{T}=P(x)P(x)^{\dagger} ( P ( x ) P ( x ) † ) T = P ( x ) P ( x ) † .
Remark 1 If x ( t ) x(t) x ( t ) is the solution of the ODE (9) , it is not difficult to verify that x ( t ) x(t) x ( t ) satisfies A ( x ) ( d x / d t ) = 0 A(x)(dx/dt)=0 A ( x ) ( d x / d t ) = 0 . That is to say, if the initial point x 0 x_{0} x 0 satisfies c ( x 0 ) = 0 c(x_{0})=0 c ( x 0 ) = 0 , the solution x ( t ) x(t) x ( t ) of the projected gradient flow (9) also satisfies c ( x ) = 0 c(x)=0 c ( x ) = 0 , ∀ t ≥ 0 \forall t\geq0 ∀ t ≥ 0 . This property is very useful such that we can construct an ODE method to follow the trajectory of the ODE (9) and obtain its steady-state solution x ∗ x^{*} x ∗ .
If we assume that x ( t ) x(t) x ( t ) is the solution of the ODE (9) , by using the property ( P ( x ) ) 2 = P ( x ) (P(x))^{2}=P(x) ( P ( x ) ) 2 = P ( x ) , we obtain
d f ( x ) d t = ( ∇ f ( x ) ) T d x d t = − ( ∇ f ( x ) ) T P ( x ) ∇ f ( x ) = − g ( x ) T ( P ( x ) ) 2 g ( x ) = − ∥ P ( x ) g ( x ) ∥ 2 ≤ 0. \frac{df(x)}{dt}=(\nabla f(x))^{T}\frac{dx}{dt}=-(\nabla f(x))^{T}P(x)\nabla f(x)
=-g(x)^{T}(P(x))^{2}g(x)=-\lVert P(x)g(x)\rVert^{2}\leq0. d t df ( x ) = ( ∇ f ( x ) ) T d t d x = − ( ∇ f ( x ) ) T P ( x ) ∇ f ( x ) = − g ( x ) T ( P ( x ) ) 2 g ( x ) = − ∥ P ( x ) g ( x ) ∥ 2 ≤ 0.
That is to say, f ( x ) f(x) f ( x ) is monotonically decreasing along the solution curve x ( t ) x(t) x ( t ) of the dynamical system (9) . Furthermore, the solution x ( t ) x(t) x ( t ) converges to x ∗ x^{*} x ∗ when f ( x ) f(x) f ( x ) is lower bounded and t t t tends to infinity [33 , 73 , 80 ] , where x ∗ x^{*} x ∗ satisfies the first-order Karush-Kuhn-Tucker conditions (2) –(3) . Thus, we can follow the trajectory x ( t ) x(t) x ( t ) of the ODE (9) to obtain its steady-state solution x ∗ x^{*} x ∗ , which is also one stationary point of the original optimization problem (1) .
However, since the right-hand-side function P ( x ) g ( x ) P(x)g(x) P ( x ) g ( x ) of the ODE (9) is rank-deficient, we will confront the numerical difficulties when we use the explicit ODE method to follow the projected gradient flow (9) [4 , 7 , 9 ] . In order to mitigate the stiffness of the ODE (9) , we use the generalized inverse ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † (P(x)\nabla^{2}f(x)P(x))^{\dagger} ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † of the two-sided projection matrix P ( x ) ∇ 2 f ( x ) P ( x ) P(x)\nabla^{2}f(x)P(x) P ( x ) ∇ 2 f ( x ) P ( x ) as the pre-conditioner for the ODE (9) , which is used similarly to the system of nonlinear equations [50], the unconstrained optimization problem [33 ] [52, 55], the linear programming problem [51], the linear complementarity problem [56], the underdetermined system of nonlinear equations [49,54] and the linearly constrained optimization problem [54].
By using the generalized inverse ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † (P(x)\nabla^{2}f(x)P(x))^{\dagger} ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † of P ( x ) ∇ 2 f ( x ) P ( x ) P(x)\nabla^{2}f(x)P(x) P ( x ) ∇ 2 f ( x ) P ( x ) as the pre-conditioner for the ODE (9) , we obtain the projected Newton flow
d x ( t ) d t = − ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † P ( x ) g ( x ) . (13) \frac{dx(t)}{dt}=-(P(x)\nabla^{2}f(x)P(x))^{\dagger}P(x)g(x). \tag*{(13)} d t d x ( t ) = − ( P ( x ) ∇ 2 f ( x ) P ( x ) ) † P ( x ) g ( x ) . (13)
Since P ( x ) ∇ 2 f ( x ) P ( x ) P(x)\nabla^{2}f(x)P(x) P ( x ) ∇ 2 f ( x ) P ( x ) is singular, we reformulate equation (13) as
( P ( x ) ∇ 2 f ( x ) P ( x ) ) d x ( t ) d t = − P ( x ) g ( x ) . (14) (P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-P(x)g(x). \tag*{(14)} ( P ( x ) ∇ 2 f ( x ) P ( x )) d t d x ( t ) = − P ( x ) g ( x ) . (14)
Although the projected Newton flow (14) mitigates the stiffness of the ODE such that we can adopt the explicit ODE method to integrate it on the infinite interval, there are two disadvantages. One is that the two-side projection matrix P ( x ) ∇ 2 f ( x ) P ( x ) P(x)\nabla^{2}f(x)P(x) P ( x ) ∇ 2 f ( x ) P ( x ) may be not positive semi-definite. Consequently, it can not ensure the objective function f ( x ) f(x) f ( x ) is monotonically decreasing along the solution x ( t ) x(t) x ( t ) of the ODE (14) . The other is that the solution x ( t ) x(t) x ( t ) of the ODE (14) can not ensure to satisfy the feasibility, i.e., d c ( x ) / d t = A ( x ) d x ( t ) / d t = 0 dc(x)/dt=A(x)dx(t)/dt=0 d c ( x ) / d t = A ( x ) d x ( t ) / d t = 0 . In order to overcome these two shortcomings, we use the regularization technique [32 , 81 , 82 ] for the projected Newton flow (14) as follows:
( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x ) ) d x ( t ) d t = − P ( x ) g ( x ) , (15) (\sigma(x)I+P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-P(x)g(x), \tag*{(15)} ( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x )) d t d x ( t ) = − P ( x ) g ( x ) , (15)
where the regularization parameter σ ( x ) \sigma(x) σ ( x ) satisfies σ ( x ) + μ min ( P ( x ) ∇ 2 f ( x ) P ( x ) ) ≥ σ min > 0 \sigma(x)+\mu_{\min}(P(x)\nabla^{2}f(x)P(x))\geq\sigma_{\min}>0 σ ( x ) + μ m i n ( P ( x ) ∇ 2 f ( x ) P ( x )) ≥ σ m i n > 0 . Here, μ min ( B ) \mu_{\min}(B) μ m i n ( B ) represents the smallest eigenvalue of matrix B B B .
Remark 2 If we assume that x ( t ) x(t) x ( t ) is the solution of the ODE (15) , from the property A ( x ) P ( x ) = 0 A(x)P(x)=0 A ( x ) P ( x ) = 0 , we have
A ( x ) ( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x ) ) d x ( t ) d t = − A ( x ) P ( x ) g ( x ) = 0. A(x)(\sigma(x)I+P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-A(x)P(x)g(x)=0. A ( x ) ( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x )) d t d x ( t ) = − A ( x ) P ( x ) g ( x ) = 0.
Consequently, we obtain σ ( x ) A ( x ) d x ( t ) d t = 0 \sigma(x)A(x)\frac{dx(t)}{dt}=0 σ ( x ) A ( x ) d t d x ( t ) = 0 , i.e. A ( x ) d x ( t ) d t = 0 A(x)\frac{dx(t)}{dt}=0 A ( x ) d t d x ( t ) = 0 . By integrating it, we obtain c ( x ) = c ( x 0 ) = 0 c(x)=c(x_0)=0 c ( x ) = c ( x 0 ) = 0 . That is to say, the solution x ( t ) x(t) x ( t ) of the ODE (15) preserves the feasibility c ( x ) = 0 c(x)=0 c ( x ) = 0 when c ( x 0 ) = 0 c(x_0)=0 c ( x 0 ) = 0 . □ \square □
Remark 3 From ( P ( x ) ) 2 = P ( x ) (P(x))^2=P(x) ( P ( x ) ) 2 = P ( x ) , we know that the solution x ( t ) x(t) x ( t ) of the ODE (15) satisfies P ( x ) d x ( t ) d t = d x ( t ) d t P(x)\frac{dx(t)}{dt}=\frac{dx(t)}{dt} P ( x ) d t d x ( t ) = d t d x ( t ) . Consequently, from equation (15) and the assumption σ ( x ) + λ min ( P ( x ) ∇ 2 f ( x ) P ( x ) ) ≥ σ min > 0 \sigma(x)+\lambda_{\min}(P(x)\nabla^2f(x)P(x))\geq\sigma_{\min}>0 σ ( x ) + λ m i n ( P ( x ) ∇ 2 f ( x ) P ( x )) ≥ σ m i n > 0 , we obtain
d f ( x ( t ) ) d t = ( ∇ f ( x ) ) T d x ( t ) d t = ( ∇ f ( x ) ) T P ( x ) d x ( t ) d t = ( P ( x ) g ( x ) ) T d x ( t ) d t = − ( P ( x ) g ( x ) ) T ( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x ) ) − 1 ( P ( x ) g ( x ) ) ≤ 0. \begin{aligned}
\frac{df(x(t))}{dt}=(\nabla f(x))^T\frac{dx(t)}{dt}=(\nabla f(x))^TP(x)\frac{dx(t)}{dt}=(P(x)g(x))^T\frac{dx(t)}{dt} \\
&=-(P(x)g(x))^T\left(\sigma(x)I+P(x)\nabla^2f(x)P(x)\right)^{-1}(P(x)g(x))\leq0.
\end{aligned} d t df ( x ( t )) = ( ∇ f ( x ) ) T d t d x ( t ) = ( ∇ f ( x ) ) T P ( x ) d t d x ( t ) = ( P ( x ) g ( x ) ) T d t d x ( t ) = − ( P ( x ) g ( x ) ) T ( σ ( x ) I + P ( x ) ∇ 2 f ( x ) P ( x ) ) − 1 ( P ( x ) g ( x )) ≤ 0.
That is to say, f ( x ) f(x) f ( x ) is monotonically decreasing along the solution x ( t ) x(t) x ( t ) of the ODE (15) . Furthermore, the solution x ( t ) x(t) x ( t ) converges to x ∗ x^* x ∗ when f ( x ) f(x) f ( x ) is lower bounded and ∥ P ( x ) ∇ 2 f ( x ) P ( x ) ∥ ≤ M \lVert P(x)\nabla^2f(x)P(x)\rVert\leq M ∥ P ( x ) ∇ 2 f ( x ) P ( x )∥ ≤ M [33 , 73 , 80 ] [41], where M M M is a positive constant and x ∗ x^* x ∗ is the stationary point of the regularization projected Newton flow (15) . Thus, we can follow the trajectory x ( t ) x(t) x ( t ) of the ODE (15) to obtain its stationary point x ∗ x^* x ∗ , which is also one stationary point of the original optimization problem (1) . □ \square □
The regularization continuation method
The solution curve x ( t ) x(t) x ( t ) of the ODE (15) can not be efficiently followed by the general ODE method [4 , 7 , 9 ] [36] such as backward differentiation formulas (BDFs, the subroutine ode15s.m of the MATLAB R2020a environment [60 ] ). Thus, we need to construct the particular method for this problem. We apply the first-order explicit Euler method [75 ] to the ODE (15) , then we obtain the regularized projection Newton method as follows:
( σ k I + P ( x k ) ∇ 2 f ( x k ) P ( x k ) ) d k = − P ( x k ) g ( x k ) , (16) \left(\sigma_k I+P(x_k)\nabla^2f(x_k)P(x_k)\right)d_k=-P(x_k)g(x_k), \tag*{(16)} ( σ k I + P ( x k ) ∇ 2 f ( x k ) P ( x k ) ) d k = − P ( x k ) g ( x k ) , (16)
x k + 1 = x k + α k d k , (17) x_{k+1}=x_k+\alpha_kd_k, \tag*{(17)} x k + 1 = x k + α k d k , (17)
where α k \alpha_k α k is the time step. When α k = 1 \alpha_k=1 α k = 1 , the regularized projection Newton method (16) –(17) is similar to the Levenberg-Marquardt method [62 ] [40, 45].
Since the time step α k \alpha_k α k of the regularized projection Newton method (16) –(17) is restricted by the numerical stability [75 ] . That is to say, for the linear test equation d x d t = − λ x \frac{dx}{dt}=-\lambda x d t d x = − λ x , its time step α k \alpha_k α k is restricted by the stable region ∣ 1 − α k λ σ k + λ ∣ ≤ 1 \left|1-\frac{\alpha_k\lambda}{\sigma_k+\lambda}\right|\leq1 1 − σ k + λ α k λ ≤ 1 . In order to avoid this disadvantage, similarly to the processing technique of the nonlinear equations [50,51,53], the unconstrained optimization problem [52,54] and the linearly constrained optimization problem [54], we replace α k \alpha_k α k with Δ t k 1 + Δ t k \frac{\Delta t_k}{1+\Delta t_k} 1 + Δ t k Δ t k in equation (17) and let σ k = σ 0 Δ t k \sigma_k=\frac{\sigma_0}{\Delta t_k} σ k = Δ t k σ 0 in equation (16) . Then, we obtain the regularization continuation method:
( σ 0 Δ t k I + B k ) d k = − P k g k , s k p = Δ t k 1 + Δ t k ( P k d k ) , (18) \left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)d_k=-P_kg_k,\quad s_k^p=\frac{\Delta t_k}{1+\Delta t_k}(P_kd_k), \tag*{(18)} ( Δ t k σ 0 I + B k ) d k = − P k g k , s k p = 1 + Δ t k Δ t k ( P k d k ) , (18)
x k + 1 p = x k + s k p . (19) x_{k+1}^p=x_k+s_k^p. \tag*{(19)} x k + 1 p = x k + s k p . (19)
where Δ t k \Delta t_k Δ t k is the time step, P k = P ( x k ) P_k=P(x_k) P k = P ( x k ) , g k = ∇ f ( x k ) g_k=\nabla f(x_k) g k = ∇ f ( x k ) and B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) B_k=P(x_k)\nabla^2 f(x_k)P(x_k) B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) or its quasi-Newton approximation.
We denote A k = A ( x k ) A_k=A(x_k) A k = A ( x k ) . The matrix A k A k T A_kA_k^T A k A k T may be ill-conditioned. Thus, the Cholesky factorization method may fail to solve the projection matrix defined by equation (10) for the large-scale problem. Therefore, we use the QR decomposition (pp. 247-248, [27 ] ) to solve it as follows:
A k T = Q k R k , (20) A_k^T=Q_kR_k, \tag*{(20)} A k T = Q k R k , (20)
where Q k ∈ R n × m Q_k\in\mathbb{R}^{n\times m} Q k ∈ R n × m satisfies Q k T Q k = I Q_k^TQ_k=I Q k T Q k = I and R k ∈ R m × m R_k\in\mathbb{R}^{m\times m} R k ∈ R m × m is an upper triangle matrix. Consequently, the projection matrix P k P_k P k defined by equation (10) can be simplified as follows:
P k = I − Q k Q k T . (21) P_k=I-Q_kQ_k^T. \tag*{(21)} P k = I − Q k Q k T . (21)
From equations (18) -(19) and the property A ( x k ) P ( x k ) = 0 A(x_k)P(x_k)=0 A ( x k ) P ( x k ) = 0 of the projection matrix P ( x k ) P(x_k) P ( x k ) , it is not difficult to verify A ( x k ) s k p = 0 A(x_k)s_k^p=0 A ( x k ) s k p = 0 . Thus, when the constraint is linear, i.e. c ( x ) = A x − b = 0 c(x)=Ax-b=0 c ( x ) = A x − b = 0 , x k + 1 p x_{k+1}^p x k + 1 p also satisfies the linear constraint A x k + 1 p − b = 0 Ax_{k+1}^p-b=0 A x k + 1 p − b = 0 if A x k − b = 0 Ax_k-b=0 A x k − b = 0 [54]. However, for the nonlinear constraint c ( x ) = 0 c(x)=0 c ( x ) = 0 , this property is not true. In other words, we may not have c ( x k + 1 p ) = 0 c(x_{k+1}^p)=0 c ( x k + 1 p ) = 0 when c ( x k ) = 0 c(x_k)=0 c ( x k ) = 0 , where x k + 1 p x_{k+1}^p x k + 1 p is the solution of equations (18) -(19) . Therefore, we need to compute the correction step s k c s_k^c s k c such that x k + 1 = x k + 1 p + s k c x_{k+1}=x_{k+1}^p+s_k^c x k + 1 = x k + 1 p + s k c is pulled back to the constraint c ( x ) = 0 c(x)=0 c ( x ) = 0 . In order to save the computational time, we use the following generalized Newton iteration with the shortest increment [53] to achieve this aim:
s k c = − ( A k + 1 p ) † c ( x k + 1 p ) , ( A k + 1 p ) † = ( A k + 1 p ) T ( A k + 1 p ( A k + 1 p ) T ) − 1 , s k = s k p + s k c , x k + 1 = x k + 1 p + s k c = x k + s k , (22) \begin{aligned}
s_k^c&=-(A_{k+1}^p)^\dagger c(x_{k+1}^p),\quad(A_{k+1}^p)^\dagger=(A_{k+1}^p)^T\left(A_{k+1}^p(A_{k+1}^p)^T\right)^{-1},\\
s_k&=s_k^p+s_k^c,\quad x_{k+1}=x_{k+1}^p+s_k^c=x_k+s_k, \tag*{(22)}
\end{aligned} s k c s k = − ( A k + 1 p ) † c ( x k + 1 p ) , ( A k + 1 p ) † = ( A k + 1 p ) T ( A k + 1 p ( A k + 1 p ) T ) − 1 , = s k p + s k c , x k + 1 = x k + 1 p + s k c = x k + s k , (22)
where A k + 1 p A_{k+1}^p A k + 1 p equals A ( x k ) A(x_k) A ( x k ) or A ( x k + 1 p ) A(x_{k+1}^p) A ( x k + 1 p ) . We first try A k + 1 p = A ( x k ) A_{k+1}^p=A(x_k) A k + 1 p = A ( x k ) and solve equation (22) . If ∥ c ( x k + 1 ) ∥ ∞ > ϵ 0 \lVert c(x_{k+1})\rVert_\infty>\epsilon_0 ∥ c ( x k + 1 ) ∥ ∞ > ϵ 0 , we try A k + 1 p = A ( x k + 1 p ) A_{k+1}^p=A(x_{k+1}^p) A k + 1 p = A ( x k + 1 p ) and solve equation (22) again, where ϵ 0 \epsilon_0 ϵ 0 is a given small constant that is less than the termination tolerance ϵ \epsilon ϵ such as ϵ 0 = 1 10 ϵ \epsilon_0=\frac{1}{10}\epsilon ϵ 0 = 10 1 ϵ and ϵ = 10 − 6 \epsilon=10^{-6} ϵ = 1 0 − 6 .
When A k + 1 p = A ( x k ) = A k A_{k+1}^p=A(x_k)=A_k A k + 1 p = A ( x k ) = A k , we have obtained its QR decomposition (20) and let Q k p = Q k Q_k^p=Q_k Q k p = Q k , R k p = R k R_k^p=R_k R k p = R k . If A k + 1 p = A ( x k + 1 p ) A_{k+1}^p=A(x_{k+1}^p) A k + 1 p = A ( x k + 1 p ) , we also use the QR decomposition (pp. 247-248, [27 ] ) to factorize it as ( A k + 1 p ) T = Q k p R k p (A_{k+1}^p)^T=Q_k^pR_k^p ( A k + 1 p ) T = Q k p R k p , where Q k p ∈ R n × m Q_k^p\in\mathbb{R}^{n\times m} Q k p ∈ R n × m satisfies ( Q k p ) T Q k p = I (Q_k^p)^TQ_k^p=I ( Q k p ) T Q k p = I and R k p ∈ R m × m R_k^p\in\mathbb{R}^{m\times m} R k p ∈ R m × m is an upper triangle matrix. Then, we solve the linear system (22) as follows:
( R k p ) T d k c = − c ( x k + 1 p ) , s k c = Q k p d k c , x k + 1 = x k + 1 p + s k c . (23) (R_k^p)^Td_k^c=-c(x_{k+1}^p),\quad s_k^c=Q_k^pd_k^c,\quad x_{k+1}=x_{k+1}^p+s_k^c. \tag*{(23)} ( R k p ) T d k c = − c ( x k + 1 p ) , s k c = Q k p d k c , x k + 1 = x k + 1 p + s k c . (23)
We define the quadratic model q k ( s ) q_k(s) q k ( s ) as follows:
q k ( s ) = f ( x k ) + s T g k + 1 2 s T B k s , (24) q_k(s)=f(x_k)+s^Tg_k+\frac{1}{2}s^TB_ks, \tag*{(24)} q k ( s ) = f ( x k ) + s T g k + 2 1 s T B k s , (24)
where g k = ∇ f ( x k ) g_k=\nabla f(x_k) g k = ∇ f ( x k ) and B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) B_k=P(x_k)\nabla^2 f(x_k)P(x_k) B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) or its quasi-Newton approximation. Similarly to the trust-region subproblem of the null space method (pp. 571-574, [79 ] ), we decompose the predicted reduction into two parts:
H p r e d k = q k ( 0 ) − q k ( s k p ) , V p r e d k = q k ( s k p ) − q k ( s k p + s k c ) . (25) Hpred_k=q_k(0)-q_k(s_k^p),\quad Vpred_k=q_k(s_k^p)-q_k(s_k^p+s_k^c). \tag*{(25)} H p r e d k = q k ( 0 ) − q k ( s k p ) , V p r e d k = q k ( s k p ) − q k ( s k p + s k c ) . (25)
Thus, in order to ensure the global convergence of the regularization continuation method (18)–(23), the accepted prediction step s k p s_k^p s k p and the correction step s k c s_k^c s k c need to satisfy the following condition:
∥ s k c ∥ ≤ θ 1 ∥ s k p ∥ , (26) \lVert s_k^c\rVert\leq\theta_1\lVert s_k^p\rVert, \tag*{(26)} ∥ s k c ∥ ≤ θ 1 ∥ s k p ∥ , (26)
where θ 1 \theta_1 θ 1 is a large positive constant such as 10 6 10^6 1 0 6 .
Remark 4 The time step Δ t k \Delta t_k Δ t k of the regularization continuation method (18)–(22) is not restricted by the numerical stability. Therefore, the large time step Δ t k \Delta t_k Δ t k can be adopted in the steady-state phase such that the regularization continuation method (18)–(22) mimics the projected Newton method near the stationary point x ∗ x^* x ∗ and it has the fast rate of convergence. The most of all, the new step α k = Δ t k / ( Δ t k + 1 ) \alpha_k=\Delta t_k/(\Delta t_k+1) α k = Δ t k / ( Δ t k + 1 ) is favourable to adopt the trust-region updating strategy for adjusting the time step Δ t k \Delta t_k Δ t k . Consequently, the regularization continuation method (18)–(22) accurately follows the trajectory of the regularization flow (15) in the transient-state phase and achieves the fast rate of convergence near the stationary point x ∗ x^* x ∗ .
The adaptive step control
Another issue is how to adaptively adjust the time step Δ t k \Delta t_k Δ t k at every iteration. We borrow the adjustment technique of the trust-region method due to its robustness and its fast rate of convergence [13 , 88 ] . According to the structure-preserving property of the regularization continuation method (18)–(22), x k + 1 x_{k+1} x k + 1 will be expected to preserve the feasibility by computing the correction step s k c s_k^c s k c of equation (23) . That is to say, x k + 1 x_{k+1} x k + 1 satisfies c ( x k + 1 ) ≈ 0 c(x_{k+1})\approx0 c ( x k + 1 ) ≈ 0 . Therefore, we use the objective function f ( x ) f(x) f ( x ) instead of the nonsmooth penalty function f ( x ) + σ ∥ c ( x ) ∥ 1 f(x)+\sigma\lVert c(x)\rVert_1 f ( x ) + σ ∥ c ( x ) ∥ 1 as the merit function. Similarly to the stepping-time scheme of the ODE method for the unconstrained optimization problem [34 ] [45, 52] and the linearly constrained optimization problem [49,54], we also need to construct a local approximation model of f ( x ) f(x) f ( x ) around x k x_k x k . Here, we adopt the quadratic function defined by equation (24) as its approximation model.
We define the ratio of the actual reduction A r e d k Ared_k A r e d k to the predicted reduction P r e d k Pred_k P r e d k as follows:
A r e d k ≜ f ( x k ) − f ( x k + s k ) , P r e d k ≜ q k ( 0 ) − q k ( s k ) , ρ k = A r e d k P r e d k . (27) Ared_k\triangleq f(x_k)-f(x_k+s_k),\quad Pred_k\triangleq q_k(0)-q_k(s_k),\quad\rho_k=\frac{Ared_k}{Pred_k}. \tag*{(27)} A r e d k ≜ f ( x k ) − f ( x k + s k ) , P r e d k ≜ q k ( 0 ) − q k ( s k ) , ρ k = P r e d k A r e d k . (27)
Thus, we accept the trial step s k s_k s k and let x k + 1 = x k + s k x_{k+1}=x_k+s_k x k + 1 = x k + s k , when ρ k ≥ η a \rho_k\geq\eta_a ρ k ≥ η a , ∥ c ( x k + s k ) ∥ ∞ ≤ ε 0 \lVert c(x_k+s_k)\rVert_\infty\leq\varepsilon_0 ∥ c ( x k + s k ) ∥ ∞ ≤ ε 0 and the predicted reduction P r e d k = q k ( 0 ) − q k ( s k ) Pred_k=q_k(0)-q_k(s_k) P r e d k = q k ( 0 ) − q k ( s k ) satisfies the Armijo sufficient descent condition:
P r e d k ≥ η q ∥ s k p ∥ ∥ p g ∥ , (28) Pred_k\geq\eta_q\lVert s_k^p\rVert\lVert p_g\rVert, \tag*{(28)} P r e d k ≥ η q ∥ s k p ∥ ∥ p g ∥ , (28)
where p g k = P ( x k ) g ( x k ) = P ( x k ) ∇ f ( x k ) p_{gk}=P(x_k)g(x_k)=P(x_k)\nabla f(x_k) p g k = P ( x k ) g ( x k ) = P ( x k ) ∇ f ( x k ) and s k p s_k^p s k p is computed by equation (18) , and η a \eta_a η a , η q \eta_q η q are the small positive constants such as η a = η q = 10 − 6 \eta_a=\eta_q=10^{-6} η a = η q = 1 0 − 6 , and ε 0 \varepsilon_0 ε 0 is less than the tolerance error ε \varepsilon ε such as ε 0 = 1 10 ε \varepsilon_0=\frac{1}{10}\varepsilon ε 0 = 10 1 ε and ε = 10 − 6 \varepsilon=10^{-6} ε = 1 0 − 6 . Otherwise, we discard it and let x k + 1 = x k x_{k+1}=x_k x k + 1 = x k .
Consequently, we reduce or enlarged the time step Δ t k + 1 \Delta t_{k+1} Δ t k + 1 at every iteration according to the ratio ρ k \rho_k ρ k defined by equation (27) . A particular adjustment strategy is given as follows:
Δ t k + 1 = { γ 1 Δ t k , if (the trial step s k is accepted and ρ k ≥ η 2 ) , Δ t k , else if (the trial step s k is accepted and η 1 < ρ k < η 2 ) , γ 2 Δ t k , others . (29) \Delta t_{k+1} =
\begin{cases}
\gamma_1\Delta t_k, & \text{if (the trial step }s_k\text{ is accepted and }\rho_k\geq\eta_2\text{)},\\
\Delta t_k, & \text{else if (the trial step }s_k\text{ is accepted and }\eta_1<\rho_k<\eta_2\text{)},\\
\gamma_2\Delta t_k, & \text{others}.
\end{cases} \tag*{(29)} Δ t k + 1 = ⎩ ⎨ ⎧ γ 1 Δ t k , Δ t k , γ 2 Δ t k , if (the trial step s k is accepted and ρ k ≥ η 2 ) , else if (the trial step s k is accepted and η 1 < ρ k < η 2 ) , others . (29)
where the constants are selected as η 1 = 0.25 \eta_1=0.25 η 1 = 0.25 , γ 1 = 2 \gamma_1=2 γ 1 = 2 , η 2 = 0.75 \eta_2=0.75 η 2 = 0.75 , γ 2 = 0.5 \gamma_2=0.5 γ 2 = 0.5 according to our numerical experiments.
Remark 5 This new time-stepping scheme based on the trust-region updating strategy has some advantages compared to the traditional line search strategy [44]. If we use the line search strategy and the damped projection Newton method (16) –(17) to follow the trajectory x ( t ) x(t) x ( t ) of the projected Newton flow (15) , in order to achieve the fast rate of convergence in the steady-state phase, the time step α k \alpha_k α k of the damped projection Newton method is tried from 1 and reduced by half with many times at every iteration. Since the quadratic model f ( x k ) + ∇ f ( x k ) T s k + 1 2 s k T B k s k f(x_k)+\nabla f(x_k)^T s_k+\frac{1}{2}s_k^T B_k s_k f ( x k ) + ∇ f ( x k ) T s k + 2 1 s k T B k s k may not approximate f ( x k + s k ) f(x_k+s_k) f ( x k + s k ) well in the transient-state phase, the time step α k \alpha_k α k will be small. Consequently, the line search strategy consumes the unnecessary trial steps in the transient-state phase. However, the selection scheme of the time step based on the trust-region strategy (27) –(29) can overcome this shortcoming.
The adaptively preconditioned technique
For the large-scale problem, the numerical evaluation of the two-sided projection matrix P ( x k ) ∇ 2 f ( x k ) P ( x k ) P(x_k)\nabla^2 f(x_k)P(x_k) P ( x k ) ∇ 2 f ( x k ) P ( x k ) consumes much time. In order to overcome this shortcoming, in the well-posed phase, we use the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton matrix (see [5 , 18 , 25 , 76 ] [58] or pp. 222–230, [65 ] ) to approximate the two-sided projection matrix P ( x k ) ∇ 2 f ( x k ) P ( x k ) P(x_k)\nabla^2 f(x_k)P(x_k) P ( x k ) ∇ 2 f ( x k ) P ( x k ) of the regularization continuation method (18) –(23) as follows:
B k + 1 = { B k + y k y k T y k T s k − B k s k s k T B k s k T B k s k , if y k T s k > 0 , B k , otherwise . (30) B_{k+1}=
\begin{cases}
B_k+\dfrac{y_k y_k^T}{y_k^T s_k}-\dfrac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}, & \text{if }y_k^T s_k>0,\\
B_k, & \text{otherwise}.
\end{cases} \tag*{(30)} B k + 1 = ⎩ ⎨ ⎧ B k + y k T s k y k y k T − s k T B k s k B k s k s k T B k , B k , if y k T s k > 0 , otherwise . (30)
where y k = P ( x k + 1 ) g ( x k + 1 ) − P ( x k ) g ( x k ) y_k=P(x_{k+1})g(x_{k+1})-P(x_k)g(x_k) y k = P ( x k + 1 ) g ( x k + 1 ) − P ( x k ) g ( x k ) , s k = x k + 1 − x k s_k=x_{k+1}-x_k s k = x k + 1 − x k and B 0 = I B_0=I B 0 = I .
The BFGS updating matrix B k B_k B k has some nice properties. For example, B k + 1 B_{k+1} B k + 1 is symmetric positive definite when B k B_k B k is symmetric positive definite and B k + 1 B_{k+1} B k + 1 is updated by the BFGS formula (30) (p. 199, [65 ] ). For the large-scale problem, it consumes much time to solve the large-scale system (18) of linear equations. In order to save the computational time of solving linear equations, we obtain the inverse ( σ k I + B k ) − 1 (\sigma_k I+B_k)^{-1} ( σ k I + B k ) − 1 of the regularization matrix ( σ k I + B k ) (\sigma_k I+B_k) ( σ k I + B k ) by using the following Sherman-Morrison-Woodbury formula (p. 17, [79 ] ):
( B + S V T ) − 1 = B − 1 − B − 1 S ( I + V T B − 1 S ) − 1 V T B − 1 , (31) (B+SV^T)^{-1}=B^{-1}-B^{-1}S(I+V^TB^{-1}S)^{-1}V^TB^{-1}, \tag*{(31)} ( B + S V T ) − 1 = B − 1 − B − 1 S ( I + V T B − 1 S ) − 1 V T B − 1 , (31)
where B B B is an n × n n \times n n × n nonsingular matrix and S S S , V V V are two p × n p \times n p × n matrices. Generally speaking, p p p is less more than n n n . We denote matrices S k S_k S k and V k V_k V k as follows:
S k = { [ S k − 1 , y k ( s k T y k ) 1 / 2 , m k ( s k T m k ) 1 / 2 ] , if y k T s k > 0 , [ S k − 1 , 0 , 0 ] , otherwise , (32) S_k=
\begin{cases}
\left[S_{k-1},\dfrac{y_k}{(s_k^T y_k)^{1/2}},\dfrac{m_k}{(s_k^T m_k)^{1/2}}\right], & \text{if }y_k^T s_k>0,\\
[S_{k-1},0,0], & \text{otherwise},
\end{cases} \tag*{(32)} S k = ⎩ ⎨ ⎧ [ S k − 1 , ( s k T y k ) 1/2 y k , ( s k T m k ) 1/2 m k ] , [ S k − 1 , 0 , 0 ] , if y k T s k > 0 , otherwise , (32)
V k = { [ V k − 1 , y k ( s k T y k ) 1 / 2 , − m k ( s k T m k ) 1 / 2 ] , if y k T s k > 0 , [ V k − 1 , 0 , 0 ] , otherwise , (33) V_k=
\begin{cases}
\left[V_{k-1},\dfrac{y_k}{(s_k^T y_k)^{1/2}},-\dfrac{m_k}{(s_k^T m_k)^{1/2}}\right], & \text{if }y_k^T s_k>0,\\
[V_{k-1},0,0], & \text{otherwise},
\end{cases} \tag*{(33)} V k = ⎩ ⎨ ⎧ [ V k − 1 , ( s k T y k ) 1/2 y k , − ( s k T m k ) 1/2 m k ] , [ V k − 1 , 0 , 0 ] , if y k T s k > 0 , otherwise , (33)
where m k = B k s k = s k + S k − 1 ( V k − 1 T s k ) m_k=B_k s_k=s_k+S_{k-1}(V_{k-1}^T s_k) m k = B k s k = s k + S k − 1 ( V k − 1 T s k ) . Then, from equations (32) –(33) , the BFGS quasi-Newton formula (30) can be written as
B k + 1 = I + S k V k T . (34) B_{k+1}=I+S_kV_k^T. \tag*{(34)} B k + 1 = I + S k V k T . (34)
By using the Sherman-Morrison-Woodbury formula (31) , from equation (34) , we obtain
( σ k I + B k ) − 1 = 1 1 + σ k ( I − S k − 1 ( ( 1 + σ k ) I + V k − 1 T S k − 1 ) − 1 V k − 1 T ) . (35) (\sigma_k I+B_k)^{-1}=\frac{1}{1+\sigma_k}\left(I-S_{k-1}\left((1+\sigma_k)I+V_{k-1}^T S_{k-1}\right)^{-1}V_{k-1}^T\right). \tag*{(35)} ( σ k I + B k ) − 1 = 1 + σ k 1 ( I − S k − 1 ( ( 1 + σ k ) I + V k − 1 T S k − 1 ) − 1 V k − 1 T ) . (35)
Remark 6 It is worthwhile to discuss whether matrix I + V T B − 1 S I+V^TB^{-1}S I + V T B − 1 S in equation (31) is nonsingular or not. Actually, when matrix B B B is symmetric positive definite and matrix B + S V T B+SV^T B + S V T is positive definite (that is to say, all eigenvalues of B + S V T B+SV^T B + S V T are greater than 0), I + V T B − 1 S I+V^TB^{-1}S I + V T B − 1 S is nonsingular.
Proof. Since B B B is symmetric positive definite, it can be decomposed as B = L L T B=LL^T B = L L T by the Cholesky factorization (p. 163, [27 ] ), where L L L is a nonsingular matrix. Thus, we have B + S V T = L ( I + ( L − 1 S ) ( V T L − T ) ) L T B+SV^T=L(I+(L^{-1}S)(V^TL^{-T}))L^T B + S V T = L ( I + ( L − 1 S ) ( V T L − T )) L T . By combining the positive definiteness of B + S V T B+SV^T B + S V T , we know that I + ( L − 1 S ) ( V T L − T ) I+(L^{-1}S)(V^TL^{-T}) I + ( L − 1 S ) ( V T L − T ) is positive definite. Therefore, all eigenvalues of ( L − 1 S ) ( V T L − T ) (L^{-1}S)(V^TL^{-T}) ( L − 1 S ) ( V T L − T ) are greater than -1. Furthermore, the eigenvalues of ( L − 1 S ) ( V T L − T ) (L^{-1}S)(V^TL^{-T}) ( L − 1 S ) ( V T L − T ) equal those of ( V T L − T ) ( L − 1 S ) (V^TL^{-T})(L^{-1}S) ( V T L − T ) ( L − 1 S ) except for their zero eigenvalues. Consequently, all eigenvalues of ( V T L − T ) ( L − 1 S ) (V^TL^{-T})(L^{-1}S) ( V T L − T ) ( L − 1 S ) are greater than -1. Namely, all eigenvalues of V T B − 1 S V^TB^{-1}S V T B − 1 S are greater than -1. Therefore, I + V T B − 1 S I+V^TB^{-1}S I + V T B − 1 S is a nonsingular matrix. □
According to our numerical experiments [49,54], the regularization continuation method (18) –(23) with the BFGS updating formula (32) –(35) works well for most problems and the objective function decreases very fast in the well-posed phase. However, for the ill-posed problems, the regularization continuation method (18) –(23) with the BFGS updating formula (32) –(35) will approach the stationary solution x ∗ x^* x ∗ very slow in the ill-posed phase. Furthermore, it fails to get close to the stationary solution x ∗ x^* x ∗ sometimes.
In order to improve the robustness of the regularization continuation method (18) –(23) , we set B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) B_k=P(x_k)\nabla^2 f(x_k)P(x_k) B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) in the ill-posed phase. Now, the problem is how to automatically identify the ill-posed phase and switch to B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) B_k=P(x_k)\nabla^2 f(x_k)P(x_k) B k = P ( x k ) ∇ 2 f ( x k ) P ( x k ) from the BFGS updating formula (30) . Here, we adopt the simple criterion. That is to say, we regard that the regularization continuation method (18) –(23) is in the ill-posed phase once there exists the time step Δ t K ≤ 10 − 3 \Delta t_K \le10^{-3} Δ t K ≤ 1 0 − 3 .
In the ill-posed phase, the computational time of the projected Hessian matrix P ( x k ) ∇ 2 f ( x k ) P ( x k ) P(x_k)\nabla^2 f(x_k)P(x_k) P ( x k ) ∇ 2 f ( x k ) P ( x k ) is heavy if we update it at every iteration. In order to save the computational time of the Hessian evaluation ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇ 2 f ( x k ) , we set B k + 1 = B k B_{k+1}=B_k B k + 1 = B k when q k ( 0 ) − q k ( s k ) q_k(0)-q_k(s_k) q k ( 0 ) − q k ( s k ) approximates f ( x k ) − f ( x k + s k ) f(x_k)-f(x_k+s_k) f ( x k ) − f ( x k + s k ) well, where the approximation model q k ( s ) q_k(s) q k ( s ) is defined by equation (24) . Otherwise, we update B k + 1 = P ( x k + 1 ) ∇ 2 f ( x k + 1 ) P ( x k + 1 ) B_{k+1}=P(x_{k+1})\nabla^2 f(x_{k+1})P(x_{k+1}) B k + 1 = P ( x k + 1 ) ∇ 2 f ( x k + 1 ) P ( x k + 1 ) in the ill-posed phase [53,54]. In the ill-posed phase, a practice updating strategy is give by
B k + 1 = { B k , if ∣ 1 − ρ k ∣ ≤ η 1 , P ( x k + 1 ) ∇ 2 f ( x k + 1 ) P ( x k + 1 ) , otherwise, (36) B_{k+1}=
\begin{cases}
B_k, & \text{if } |1-\rho_k|\le\eta_1,\\
P(x_{k+1})\nabla^2 f(x_{k+1})P(x_{k+1}), & \text{otherwise,}
\end{cases} \tag*{(36)} B k + 1 = { B k , P ( x k + 1 ) ∇ 2 f ( x k + 1 ) P ( x k + 1 ) , if ∣1 − ρ k ∣ ≤ η 1 , otherwise, (36)
where ρ k \rho_k ρ k is defined by equations (24) –(27) and η 1 = 0.25 \eta_1=0.25 η 1 = 0.25 .
Finding an initial feasible point
For the regularization continuation method based on the ODE system (15) , one of the important issues is how to find an initial feasible point x 0 x_0 x 0 . That is to say, the initial point x 0 x_0 x 0 needs to satisfy c ( x 0 ) = 0 c(x_0)=0 c ( x 0 ) = 0 . Here, we use the generalized continuation Newton method [53] to solve the under-determined system c ( x ) = 0 c(x)=0 c ( x ) = 0 due to its robustness and efficiency. For convenience, we give the rough description of the generalized continuation Newton method. Its detailed description and its convergence analysis can be found in reference [53].
For the under-determined system c ( z ) = 0 c(z)=0 c ( z ) = 0 , we construct the generalized Newton flow
d z ( τ ) d τ = − A ( z ) † c ( z ) , z ( τ 0 ) = z 0 , (37) \frac{dz(\tau)}{d\tau}=-A(z)^{\dagger}c(z),\quad z(\tau_0)=z_0, \tag*{(37)} d τ d z ( τ ) = − A ( z ) † c ( z ) , z ( τ 0 ) = z 0 , (37)
where A ( z ) † A(z)^{\dagger} A ( z ) † is the Moore-Penrose generalized inverse of the Jacobian matrix A ( z ) A(z) A ( z ) (p. 11, [79 ] or p. 290, [27 ] ). Then, we construct the generalized continuation Newton method [53] to follow the generalized Newton flow (37) and obtain its steady-state solution z ∗ z^* z ∗ as follows:
Δ z j = − Δ τ j 1 + Δ τ j A j † c ( z j ) , z j + 1 = z j + Δ z j , (38) \Delta z_j=-\frac{\Delta\tau_j}{1+\Delta\tau_j}A_j^{\dagger}c(z_j),\quad z_{j+1}=z_j+\Delta z_j, \tag*{(38)} Δ z j = − 1 + Δ τ j Δ τ j A j † c ( z j ) , z j + 1 = z j + Δ z j , (38)
where A j A_j A j equals A ( x j ) A(x_j) A ( x j ) or its approximation according to the following ratio
r j = ∥ c ( z j ) ∥ − ∥ c ( z j + Δ z j ) ∥ ∥ c ( z j ) ∥ − ∥ c ( z j ) + A j Δ z j ∥ = ∥ c ( z j ) ∥ − ∥ c ( z j + Δ z j ) ∥ ( Δ τ j / ( 1 + Δ τ j ) ) ∥ c ( z j ) ∥ . (39) r_j=\frac{\lVert c(z_j)\rVert-\lVert c(z_j+\Delta z_j)\rVert}{\lVert c(z_j)\rVert-\lVert c(z_j)+A_j\Delta z_j\rVert}=\frac{\lVert c(z_j)\rVert-\lVert c(z_j+\Delta z_j)\rVert}{(\Delta\tau_j/(1+\Delta\tau_j))\lVert c(z_j)\rVert}. \tag*{(39)} r j = ∥ c ( z j )∥ − ∥ c ( z j ) + A j Δ z j ∥ ∥ c ( z j )∥ − ∥ c ( z j + Δ z j )∥ = ( Δ τ j / ( 1 + Δ τ j )) ∥ c ( z j )∥ ∥ c ( z j )∥ − ∥ c ( z j + Δ z j )∥ . (39)
In other words, we update the Jacobian matrix A j + 1 A_{j+1} A j + 1 according to the following strategy:
A j + 1 = { A j , if ∣ 1 − r j ∣ ≤ η 1 , A ( z j + 1 ) , otherwise. (40) A_{j+1}=\begin{cases} A_j, & \text{if } |1-r_j|\le\eta_1,\\ A(z_{j+1}), & \text{otherwise.} \end{cases} \tag*{(40)} A j + 1 = { A j , A ( z j + 1 ) , if ∣1 − r j ∣ ≤ η 1 , otherwise. (40)
For a real-world problem, A j A j T A_jA_j^T A j A j T may be ill-conditioned. Thus, the Cholesky decomposition may fail to solve the linear system (38) for the large-scale problem. In order to improve its robustness, we use the QR decomposition to solve it as follows:
A j T = U j W j , W j T Δ z j m = − c ( z j ) , Δ z j N = U j Δ z j m , Δ z j = Δ τ j 1 + Δ τ j Δ z j N , (41) A_j^T=U_jW_j,\quad W_j^T\Delta z_j^m=-c(z_j),\quad\Delta z_j^N=U_j\Delta z_j^m,\quad\Delta z_j=\frac{\Delta\tau_j}{1+\Delta\tau_j}\Delta z_j^N, \tag*{(41)} A j T = U j W j , W j T Δ z j m = − c ( z j ) , Δ z j N = U j Δ z j m , Δ z j = 1 + Δ τ j Δ τ j Δ z j N , (41)
where U j ∈ R n × m U_j\in\mathbb{R}^{n\times m} U j ∈ R n × m satisfies U j T U j = I U_j^TU_j=I U j T U j = I and W j ∈ R m × m W_j\in\mathbb{R}^{m\times m} W j ∈ R m × m is an upper triangle matrix. In practice, in order to save the computational time of decomposing the matrix A j + 1 A_{j+1} A j + 1 when A j A_j A j performs well, i.e. ∣ 1 − r j ∣ ≤ η 1 |1-r_j|\le\eta_1 ∣1 − r j ∣ ≤ η 1 , according to the updating formula (40) , we set W j + 1 = W j W_{j+1}=W_j W j + 1 = W j and U j + 1 = U j U_{j+1}=U_j U j + 1 = U j in equation (41) .
The adaptive time step Δ τ j \Delta\tau_j Δ τ j of the generalized continuation Newton method (38) is adjusted by the following trust-region updating strategy:
Δ τ j + 1 = { γ 1 Δ τ j , if ∣ 1 − r j ∣ ≤ η 1 , Δ τ j , else if η 1 < ∣ 1 − r j ∣ < η 2 , γ 2 Δ τ j , others, (42) \Delta\tau_{j+1}=\begin{cases} \gamma_1\Delta\tau_j, & \text{if } |1-r_j|\le\eta_1,\\ \Delta\tau_j, & \text{else if }\eta_1<|1-r_j|<\eta_2,\\ \gamma_2\Delta\tau_j, & \text{others,} \end{cases} \tag*{(42)} Δ τ j + 1 = ⎩ ⎨ ⎧ γ 1 Δ τ j , Δ τ j , γ 2 Δ τ j , if ∣1 − r j ∣ ≤ η 1 , else if η 1 < ∣1 − r j ∣ < η 2 , others, (42)
where the constants are selected as γ 1 = 2 \gamma_1=2 γ 1 = 2 , γ 2 = 0.5 \gamma_2=0.5 γ 2 = 0.5 , η 1 = 0.25 \eta_1=0.25 η 1 = 0.25 , η 2 = 0.75 \eta_2=0.75 η 2 = 0.75 , according to our numerical experiments.
For a real-world problem, the analytical Jacobian A ( z j ) A(z_j) A ( z j ) may not be offered. Thus, in practice, we replace the Jacobian matrix A ( z j ) A(z_j) A ( z j ) with its difference approximation as follows:
A ( z k ) ≈ [ c ( z j + ε e 1 ) − c ( z j ) ε , … , c ( z j + ε e n ) − c ( z j ) ε ] , (43) A(z_k)\approx\left[\frac{c(z_j+\varepsilon e_1)-c(z_j)}{\varepsilon},\ldots,\frac{c(z_j+\varepsilon e_n)-c(z_j)}{\varepsilon}\right], \tag*{(43)} A ( z k ) ≈ [ ε c ( z j + ε e 1 ) − c ( z j ) , … , ε c ( z j + ε e n ) − c ( z j ) ] , (43)
where the elements of e i e_i e i equal zeros except for the i i i -th element which equals 1, and the parameter ε \varepsilon ε can be selected as 10 − 6 10^{-6} 1 0 − 6 according to our numerical experiments.
According to the above descriptions, we give the detailed implementation of the generalized continuation Newton method with the trust-region updating strategy (GCNMtr) to find an initial feasible point z ∗ z^* z ∗ of c ( z ) = 0 c(z)=0 c ( z ) = 0 in Algorithm 1.
By combining the discussions of the previous sections and Algorithm 1, we give the detailed implementation of the regularization continuation method and the trust-region updating strategy for the optimization problem (1) with nonlinear equality constraints in Algorithm 2.
Algorithm 1 Generalized continuation Newton methods and the trust-region updating strategy for the under-determined system (The GCNMTr method)
Input: Function c : R n → R m c : \mathbb{R}^{n} \to\mathbb{R}^{m} c : R n → R m , m ≤ n m \le n m ≤ n , the initial point z 0 z_{0} z 0 (optional), and the tolerance ε \varepsilon ε (optional).
Output: An approximation solution z ∗ z^{*} z ∗ of nonlinear equations.
Set the default z 0 = ones ( n , 1 ) z_{0} = \operatorname{ones}(n,1) z 0 = ones ( n , 1 ) and ε = 10 − 7 \varepsilon= 10^{-7} ε = 1 0 − 7 , when z 0 z_{0} z 0 or ε \varepsilon ε is not provided.
Initialize the parameters: η a = 10 − 6 \eta_{a} = 10^{-6} η a = 1 0 − 6 , η 1 = 0.25 \eta_{1} = 0.25 η 1 = 0.25 , γ 1 = 2 \gamma_{1} = 2 γ 1 = 2 , η 2 = 0.75 \eta_{2} = 0.75 η 2 = 0.75 , γ 2 = 0.5 \gamma_{2} = 0.5 γ 2 = 0.5 , maxit = 400 \operatorname{maxit} = 400 maxit = 400 .
Set Δ τ 0 = 10 − 2 \Delta\tau_{0} = 10^{-2} Δ τ 0 = 1 0 − 2 , flag_success_trialstep = 1 \operatorname{flag\_success\_trialstep} = 1 flag_success_trialstep = 1 , itc = 0 \operatorname{itc} = 0 itc = 0 , j = 0 j = 0 j = 0 .
Evaluate c j = c ( z j ) c_{j} = c(z_{j}) c j = c ( z j ) .
Set r j − 1 = 0 r_{j-1} = 0 r j − 1 = 0 .
while (itc < maxit \operatorname{itc} < \operatorname{maxit} itc < maxit ) do
if (flag_success_trialstep = = 1 \operatorname{flag\_success\_trialstep} == 1 flag_success_trialstep == 1 ) then
Set itc = itc + 1 \operatorname{itc} = \operatorname{itc} + 1 itc = itc + 1 .
Compute Res j = ∥ c j ∥ ∞ \operatorname{Res}_{j} = \lVert c_{j} \rVert_{\infty} Res j = ∥ c j ∥ ∞ .
if (Res j < ε \operatorname{Res}_{j} < \varepsilon Res j < ε ) then
break;
end if
if (∣ 1 − r j − 1 ∣ > η 1 \lvert1-r_{j-1} \rvert> \eta_{1} ∣ 1 − r j − 1 ∣ > η 1 ) then
Evaluate A j = A ( z j ) A_{j} = A(z_{j}) A j = A ( z j ) from equation (43) .
Use the QR decomposition [ U ‾ j , W ‾ j ] = qr ( A j ) [\overline{U}_{j},\overline{W}_{j}] = \operatorname{qr}(A_{j}) [ U j , W j ] = qr ( A j ) and set U j = U ‾ j ( : , 1 : m ) U_{j} = \overline{U}_{j}(:,1:m) U j = U j ( : , 1 : m ) , W j = W ‾ j ( 1 : m , 1 : m ) W_{j} = \overline{W}_{j}(1:m,1:m) W j = W j ( 1 : m , 1 : m ) .
else
Set U j = U j − 1 U_{j} = U_{j-1} U j = U j − 1 , W j = W j − 1 W_{j} = W_{j-1} W j = W j − 1 .
end if
By solving W j T Δ z j N = − c j W_{j}^{T}\Delta z_{j}^{N} = -c_{j} W j T Δ z j N = − c j and Δ z j N = U j Δ z j M \Delta z_{j}^{N} = U_{j}\Delta z_{j}^{M} Δ z j N = U j Δ z j M , we obtain the Newton step Δ z j N \Delta z_{j}^{N} Δ z j N .
end if
Set Δ z j = Δ τ j / ( 1 + Δ τ j ) Δ z j N \Delta z_{j} = \Delta\tau_{j}/(1+\Delta\tau_{j})\Delta z_{j}^{N} Δ z j = Δ τ j / ( 1 + Δ τ j ) Δ z j N , z j + 1 = z j + Δ z j z_{j+1} = z_{j}+\Delta z_{j} z j + 1 = z j + Δ z j .
Evaluate c j + 1 = c ( z j + 1 ) c_{j+1} = c(z_{j+1}) c j + 1 = c ( z j + 1 ) .
if (∥ c j ∥ < ∥ c j + 1 ∥ \lVert c_{j} \rVert< \lVert c_{j+1} \rVert ∥ c j ∥ < ∥ c j + 1 ∥ ) then
Set r j = − 1 r_{j} = -1 r j = − 1 ;
else
Compute the ratio r j r_{j} r j from equation (39) .
end if
Adjust the time step size Δ τ j + 1 \Delta\tau_{j+1} Δ τ j + 1 according to the trust-region updating strategy (42) .
if (r j ≥ η a r_{j} \ge\eta_{a} r j ≥ η a ) then
Accept the trial point z j + 1 z_{j+1} z j + 1 . Set flag_success_trialstep = 1 \operatorname{flag\_success\_trialstep} = 1 flag_success_trialstep = 1 .
else
Set z j + 1 = z j z_{j+1} = z_{j} z j + 1 = z j , c j + 1 = c j c_{j+1} = c_{j} c j + 1 = c j , Δ z j + 1 N = Δ z j N \Delta z_{j+1}^{N} = \Delta z_{j}^{N} Δ z j + 1 N = Δ z j N , flag_success_trialstep = 0 \operatorname{flag\_success\_trialstep} = 0 flag_success_trialstep = 0 .
end if
Set j ← j + 1 j \leftarrow j+1 j ← j + 1 .
end while
Algorithm Analysis
In this section, we analyze the global convergence of the regularization continuation method (18) -(23) and the adaptive time step control for the nonlinearly equality-constrained optimization problem (i.e. Algorithm 2). Similarly to the result of the trust-region method for the unconstrained optimization problem [69 ] and the continuation method for linearly constrained optimization problem [49], we have the following lower bound estimation of q k ( 0 ) − q k ( s k p ) q_{k}(0)-q_{k}(s_{k}^{p}) q k ( 0 ) − q k ( s k p ) .
Lemma 1 *Assume that the quadratic model q k ( s ) q_{k}(s) q k ( s ) is defined by equation (24) and d k d_{k} d k is the solution of equation (18) . Furthermore, we suppose that the time step Δ t k \Delta t_{k} Δ t k
Algorithm 2 The regularization continuation method for optimization problems with nonlinear equality constraints (the Rcm method)
Input: the objective function f : R n → R f:\mathbb{R}^{n}\to\mathbb{R} f : R n → R , the equality constraints c ( x ) = 0 c(x)=0 c ( x ) = 0 , c : R n → R m c:\mathbb{R}^{n}\to\mathbb{R}^{m} c : R n → R m , the initial point z 0 z_{0} z 0 (optional), the terminated parameter ε \varepsilon ε (optional).
Output: the optimal approximation solution x ∗ x^{*} x ∗ .
If z 0 z_{0} z 0 or ε \varepsilon ε is not provided, we set z 0 = ones ( n , 1 ) z_{0}=\operatorname{ones}(n,1) z 0 = ones ( n , 1 ) or ε = 10 − 6 \varepsilon=10^{-6} ε = 1 0 − 6 . We let ε 0 = 1 10 ε \varepsilon_{0}=\frac{1}{10}\varepsilon ε 0 = 10 1 ε .
Initialize parameters: η a = 10 − 6 \eta_{a}=10^{-6} η a = 1 0 − 6 , η m = 10 − 6 \eta_{m}=10^{-6} η m = 1 0 − 6 , η 1 = 0.25 \eta_{1}=0.25 η 1 = 0.25 , γ 1 = 2 \gamma_{1}=2 γ 1 = 2 , η 2 = 0.75 \eta_{2}=0.75 η 2 = 0.75 , γ 2 = 0.5 \gamma_{2}=0.5 γ 2 = 0.5 , σ 0 = 10 − 5 \sigma_{0}=10^{-5} σ 0 = 1 0 − 5 , Δ t K = 10 − 3 \Delta t_{K}=10^{-3} Δ t K = 1 0 − 3 , max_itc = 300 \operatorname{max\_itc}=300 max_itc = 300 . Set Δ t 0 = 10 − 2 \Delta t_{0}=10^{-2} Δ t 0 = 1 0 − 2 , flag_illposed_phase = 0 \operatorname{flag\_illposed\_phase}=0 flag_illposed_phase = 0 , flag_success_trialstep = 1 \operatorname{flag\_success\_trialstep}=1 flag_success_trialstep = 1 , s − 1 = 0 s_{-1}=0 s − 1 = 0 , y − 1 = 0 y_{-1}=0 y − 1 = 0 , ρ − 1 = 0 \rho_{-1}=0 ρ − 1 = 0 , B 0 = I B_{0}=I B 0 = I , H 0 = I H_{0}=I H 0 = I , Q − 1 = I Q_{-1}=I Q − 1 = I , R − 1 = I R_{-1}=I R − 1 = I , S − 1 = zeros ( n , 1 ) S_{-1}=\operatorname{zeros}(n,1) S − 1 = zeros ( n , 1 ) , V − 1 = zeros ( n , 1 ) V_{-1}=\operatorname{zeros}(n,1) V − 1 = zeros ( n , 1 ) , itc = 0 \operatorname{itc}=0 itc = 0 .
Use the generalized continuation Newton method (the GCNMTr method, Algorithm 1) to find an initial feasible point from z 0 z_{0} z 0 and denote this initial feasible point as x 0 x_{0} x 0 .
Set k = 0 k=0 k = 0 . Evaluate f 0 = f ( x 0 ) f_{0}=f(x_{0}) f 0 = f ( x 0 ) and g 0 = ∇ f ( x 0 ) g_{0}=\nabla f(x_{0}) g 0 = ∇ f ( x 0 ) . Evaluate A 0 = A ( x 0 ) A_{0}=A(x_{0}) A 0 = A ( x 0 ) from equation (43) .
Factorize A 0 T A_{0}^{T} A 0 T by the QR decomposition [ Q ˉ 0 , R ˉ 0 ] = qr ( A 0 T ) [\bar{Q}_{0},\bar{R}_{0}]=\operatorname{qr}(A_{0}^{T}) [ Q ˉ 0 , R ˉ 0 ] = qr ( A 0 T ) .
Set Q 0 = Q ˉ 0 ( : , 1 : m ) Q_{0}=\bar{Q}_{0}(:,1:m) Q 0 = Q ˉ 0 ( : , 1 : m ) , R 0 = R ˉ 0 ( 1 : m , 1 : m ) R_{0}=\bar{R}_{0}(1:m,1:m) R 0 = R ˉ 0 ( 1 : m , 1 : m ) .
Compute the projected gradient p g 0 = P 0 g 0 pg_{0}=P_{0}g_{0} p g 0 = P 0 g 0 , where P 0 P_{0} P 0 is computed by equation (21) .
while ( ∥ p g k ∥ ∞ > ε ) (\lVert pg_{k}\rVert_{\infty}>\varepsilon) (∥ p g k ∥ ∞ > ε ) and ( itc < max_itc ) (\operatorname{itc}<\operatorname{max\_itc}) ( itc < max_itc ) do
itc = itc + 1 \operatorname{itc}=\operatorname{itc}+1 itc = itc + 1 ;
if Δ t k < Δ t K \Delta t_{k}<\Delta t_{K} Δ t k < Δ t K then
Set flag_illposed_phase = 1 \operatorname{flag\_illposed\_phase}=1 flag_illposed_phase = 1 .
end if
if ( flag_illposed_phase = = 0 ) (\operatorname{flag\_illposed\_phase}==0) ( flag_illposed_phase == 0 ) then
if ( flag_success_trialstep = = 1 ) (\operatorname{flag\_success\_trialstep}==1) ( flag_success_trialstep == 1 ) then
if k > 0 k>0 k > 0 then
Solve equations (32)–(33) to obtain matrices S k − 1 S_{k-1} S k − 1 and V k − 1 V_{k-1} V k − 1 .
else
Set S − 1 = zeros ( n , 1 ) S_{-1}=\operatorname{zeros}(n,1) S − 1 = zeros ( n , 1 ) and V − 1 = zeros ( n , 1 ) V_{-1}=\operatorname{zeros}(n,1) V − 1 = zeros ( n , 1 ) .
end if
Solve equations (18) and (35) to obtain
d k = − ( p g k − S k − 1 ( ( 1 + σ 0 Δ t k ) I + V k − 1 T S k − 1 ) − 1 ( V k − 1 T p g k ) ) / ( 1 + σ 0 Δ t k ) . d_{k}=-\left(pg_{k}-S_{k-1}\left(\left(1+\frac{\sigma_{0}}{\Delta t_{k}}\right)I+V_{k-1}^{T}S_{k-1}\right)^{-1}\left(V_{k-1}^{T}pg_{k}\right)\right)\bigg/\left(1+\frac{\sigma_{0}}{\Delta t_{k}}\right). d k = − ( p g k − S k − 1 ( ( 1 + Δ t k σ 0 ) I + V k − 1 T S k − 1 ) − 1 ( V k − 1 T p g k ) ) / ( 1 + Δ t k σ 0 ) .
end if
else
if ( ∣ ρ k − 1 − 1 ∣ > η 1 ) (|\rho_{k-1}-1|>\eta_{1}) ( ∣ ρ k − 1 − 1∣ > η 1 ) then
Evaluate H k = P k ∇ 2 f ( x k ) P k H_{k}=P_{k}\nabla^{2}f(x_{k})P_{k} H k = P k ∇ 2 f ( x k ) P k from equation (115) .
Set B k = ( σ 0 / Δ t k ) I + H k B_{k}=(\sigma_{0}/\Delta t_{k})I+H_{k} B k = ( σ 0 /Δ t k ) I + H k and use the QR decomposition B k = Q k b R k b B_{k}=Q_{k}^{b}R_{k}^{b} B k = Q k b R k b .
else
Q k b = Q k − 1 b Q_{k}^{b}=Q_{k-1}^{b} Q k b = Q k − 1 b , R k b = R k − 1 b R_{k}^{b}=R_{k-1}^{b} R k b = R k − 1 b ;
end if
Solve the linear system R k b d k = − ( Q k b ) T p g k R_{k}^{b}d_{k}=-(Q_{k}^{b})^{T}pg_{k} R k b d k = − ( Q k b ) T p g k to obtain d k d_{k} d k .
end if
Set s k p = Δ t k 1 + Δ t k ( P k d k ) s_{k}^{p}=\frac{\Delta t_{k}}{1+\Delta t_{k}}(P_{k}d_{k}) s k p = 1 + Δ t k Δ t k ( P k d k ) and x k + 1 p = x k + s k p x_{k+1}^{p}=x_{k}+s_{k}^{p} x k + 1 p = x k + s k p . Evaluate c k + 1 p = c ( x k + 1 p ) c_{k+1}^{p}=c(x_{k+1}^{p}) c k + 1 p = c ( x k + 1 p ) .
Solve the linear systems ( R k ) T d c k = − c k + 1 p (R_{k})^{T}d c_{k}=-c_{k+1}^{p} ( R k ) T d c k = − c k + 1 p , s k c = Q k d c k s_{k}^{c}=Q_{k}d c_{k} s k c = Q k d c k .
Set x k + 1 = x k + 1 p + s k c x_{k+1}=x_{k+1}^{p}+s_{k}^{c} x k + 1 = x k + 1 p + s k c , c k + 1 = c ( x k + 1 ) c_{k+1}=c(x_{k+1}) c k + 1 = c ( x k + 1 ) .
if ( ∥ c k + 1 ∥ ∞ > ε 0 ) (\lVert c_{k+1}\rVert_{\infty}>\varepsilon_{0}) (∥ c k + 1 ∥ ∞ > ε 0 ) then
Evaluate A k + 1 p = A ( x k + 1 p ) A_{k+1}^{p}=A(x_{k+1}^{p}) A k + 1 p = A ( x k + 1 p ) from equation (43) .
Solve the linear system (23) to obtain x k + 1 x_{k+1} x k + 1 and evaluate c k + 1 = c ( x k + 1 ) c_{k+1}=c(x_{k+1}) c k + 1 = c ( x k + 1 ) .
end if
Evaluate f k + 1 = f ( x k + 1 ) f_{k+1}=f(x_{k+1}) f k + 1 = f ( x k + 1 ) and compute the ratio ρ k \rho_{k} ρ k from equations (24)–(27).
if ( ρ k ≥ η a , ∥ c k + 1 ∥ ∞ ≤ ε 0 and s k satisfies the sufficient descent condition (28) ) (\rho_{k}\geq\eta_{a},\ \lVert c_{k+1}\rVert_{\infty}\leq\varepsilon_{0}\text{ and }s_{k}\text{ satisfies the sufficient descent condition (28)}) ( ρ k ≥ η a , ∥ c k + 1 ∥ ∞ ≤ ε 0 and s k satisfies the sufficient descent condition (28) ) then
Set flag_success_trialstep = 1 \operatorname{flag\_success\_trialstep}=1 flag_success_trialstep = 1 . Evaluate g k + 1 = ∇ f ( x k + 1 ) g_{k+1}=\nabla f(x_{k+1}) g k + 1 = ∇ f ( x k + 1 ) .
Evaluate A k + 1 = A ( x k + 1 ) A_{k+1}=A(x_{k+1}) A k + 1 = A ( x k + 1 ) from equation (43) .
Factorize A k + 1 T A_{k+1}^{T} A k + 1 T by the QR decomposition [ Q ˉ k + 1 , R ˉ k + 1 ] = qr ( A k + 1 T ) [\bar{Q}_{k+1},\bar{R}_{k+1}]=\operatorname{qr}(A_{k+1}^{T}) [ Q ˉ k + 1 , R ˉ k + 1 ] = qr ( A k + 1 T ) .
Set Q k + 1 = Q ˉ k + 1 ( : , 1 : m ) Q_{k+1}=\bar{Q}_{k+1}(:,1:m) Q k + 1 = Q ˉ k + 1 ( : , 1 : m ) , R k + 1 = R ˉ k + 1 ( 1 : m , 1 : m ) R_{k+1}=\bar{R}_{k+1}(1:m,1:m) R k + 1 = R ˉ k + 1 ( 1 : m , 1 : m ) .
Set p g k + 1 = P k + 1 g k + 1 pg_{k+1}=P_{k+1}g_{k+1} p g k + 1 = P k + 1 g k + 1 , where P k + 1 P_{k+1} P k + 1 is computed by equation (21) .
Set s k = x k + 1 − x k s_{k}=x_{k+1}-x_{k} s k = x k + 1 − x k and y k = p g k + 1 − p g k y_{k}=pg_{k+1}-pg_{k} y k = p g k + 1 − p g k .
else
Set flag_success_trialstep = 0 \operatorname{flag\_success\_trialstep}=0 flag_success_trialstep = 0 .
x k + 1 = x k x_{k+1}=x_{k} x k + 1 = x k , f k + 1 = f k f_{k+1}=f_{k} f k + 1 = f k , p g k + 1 = p g k pg_{k+1}=pg_{k} p g k + 1 = p g k , g k + 1 = g k g_{k+1}=g_{k} g k + 1 = g k , H k + 1 = H k H_{k+1}=H_{k} H k + 1 = H k , d k + 1 = d k d_{k+1}=d_{k} d k + 1 = d k .
end if
Adjust the time step Δ t k + 1 \Delta t_{k+1} Δ t k + 1 based on the trust-region updating strategy (29).
Set k ← k + 1 k\leftarrow k+1 k ← k + 1 .
end while
satisfies
( σ 0 Δ t k I + B k ) ≻ 0 and ( σ 0 Δ t k I + B k − P k T B k P k ) ⪰ 0 , (44) \left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)\succ0 \quad\text{and}\quad\left(\frac{\sigma_0}{\Delta t_k}I+B_k-P_k^T B_kP_k\right)\succeq0, \tag*{(44)} ( Δ t k σ 0 I + B k ) ≻ 0 and ( Δ t k σ 0 I + B k − P k T B k P k ) ⪰ 0 , (44)
where P k = P ( x k ) P_k=P(x_k) P k = P ( x k ) is the projection matrix defined by equation (10) . Then, we have
q k ( 0 ) − q k ( P k d k ) ≥ 1 2 ∥ p g k ∥ min { ∥ P k d k ∥ , ∥ p g k ∥ 3 ∥ B k ∥ } , (45) q_k(0)-q_k(P_kd_k)\geq\frac{1}{2}\lVert p_{g_k}\rVert\min\left\{\lVert P_kd_k\rVert,\frac{\lVert p_{g_k}\rVert}{3\lVert B_k\rVert}\right\}, \tag*{(45)} q k ( 0 ) − q k ( P k d k ) ≥ 2 1 ∥ p g k ∥ min { ∥ P k d k ∥ , 3 ∥ B k ∥ ∥ p g k ∥ } , (45)
where p g k = P k g k p_{g_k}=P_kg_k p g k = P k g k .
Proof. Let τ k = σ 0 / Δ t k \tau_k=\sigma_0/\Delta t_k τ k = σ 0 /Δ t k . From equation (18) , we obtain
q k ( 0 ) − q k ( P k d k ) = − 1 2 ( d k T P k T B k P k d k ) − ( P k g k ) T d k = − 1 2 ( d k T P k T B k P k d k ) + p g k T ( τ k I + B k ) − 1 p g k = 1 2 ( p g k T ( τ k I + B k ) − 1 p g k + d k T ( − P k T B k P k + τ k I + B k ) d k ) . (46) \begin{aligned}
q_k(0)-q_k(P_kd_k)&=-\frac{1}{2}\left(d_k^TP_k^TB_kP_kd_k\right)-(P_kg_k)^Td_k\\
&=-\frac{1}{2}\left(d_k^TP_k^TB_kP_kd_k\right)+p_{g_k}^T(\tau_kI+B_k)^{-1}p_{g_k}\\
&=\frac{1}{2}\left(p_{g_k}^T(\tau_kI+B_k)^{-1}p_{g_k}+d_k^T\left(-P_k^TB_kP_k+\tau_kI+B_k\right)d_k\right). \tag*{(46)}
\end{aligned} q k ( 0 ) − q k ( P k d k ) = − 2 1 ( d k T P k T B k P k d k ) − ( P k g k ) T d k = − 2 1 ( d k T P k T B k P k d k ) + p g k T ( τ k I + B k ) − 1 p g k = 2 1 ( p g k T ( τ k I + B k ) − 1 p g k + d k T ( − P k T B k P k + τ k I + B k ) d k ) . (46)
We denote μ min ( B k − P k T B k P k ) \mu_{\min}\left(B_k-P_k^TB_kP_k\right) μ m i n ( B k − P k T B k P k ) as the smallest eigenvalue of matrix ( B k − P k T B k P k ) \left(B_k-P_k^TB_kP_k\right) ( B k − P k T B k P k ) , and set
τ l b = min { 0 , μ min ( B k − P k T B k P k ) } . (47) \tau_{lb}=\min\left\{0,\mu_{\min}\left(B_k-P_k^TB_kP_k\right)\right\}. \tag*{(47)} τ l b = min { 0 , μ m i n ( B k − P k T B k P k ) } . (47)
From equations (44) , (46) –(47) and the bound on the eigenvalues of matrix ( τ k I + B k ) − 1 (\tau_kI+B_k)^{-1} ( τ k I + B k ) − 1 , we obtain
q k ( 0 ) − q k ( P k d k ) ≥ 1 2 ( p g k T ( τ k I + B k ) − 1 p g k + ( τ k + τ l b ) ∥ d k ∥ 2 ) ≥ 1 2 ( ∥ p g k ∥ 2 τ k + ∥ B k ∥ + ( τ k + τ l b ) ∥ d k ∥ 2 ) . (48) \begin{aligned}
q_k(0)-q_k(P_kd_k)&\geq\frac{1}{2}\left(p_{g_k}^T(\tau_kI+B_k)^{-1}p_{g_k}+(\tau_k+\tau_{lb})\lVert d_k\rVert^2\right)\\
&\geq\frac{1}{2}\left(\frac{\lVert p_{g_k}\rVert^2}{\tau_k+\lVert B_k\rVert}+(\tau_k+\tau_{lb})\lVert d_k\rVert^2\right). \tag*{(48)}
\end{aligned} q k ( 0 ) − q k ( P k d k ) ≥ 2 1 ( p g k T ( τ k I + B k ) − 1 p g k + ( τ k + τ l b ) ∥ d k ∥ 2 ) ≥ 2 1 ( τ k + ∥ B k ∥ ∥ p g k ∥ 2 + ( τ k + τ l b ) ∥ d k ∥ 2 ) . (48)
In the above second inequality, we use the property ∣ μ i ( B k ) ∣ ≤ ∥ B k ∥ |\mu_i(B_k)|\leq\lVert B_k\rVert ∣ μ i ( B k ) ∣ ≤ ∥ B k ∥ , where μ i ( B k ) \mu_i(B_k) μ i ( B k ) is an eigenvalue of matrix B k B_k B k .
Now we consider the properties of the function
φ ( τ ) ≜ τ ∥ d k ∥ 2 + ∥ p g k ∥ 2 τ − τ l b + ∥ B k ∥ . (49) \varphi(\tau)\triangleq\tau\lVert d_k\rVert^2+\frac{\lVert p_{g_k}\rVert^2}{\tau-\tau_{lb}+\lVert B_k\rVert}. \tag*{(49)} φ ( τ ) ≜ τ ∥ d k ∥ 2 + τ − τ l b + ∥ B k ∥ ∥ p g k ∥ 2 . (49)
From equation (49) , we have φ ′ ′ ( τ ) = 2 ∥ p g k ∥ 2 / ( τ − τ l b + ∥ B k ∥ ) 3 ≥ 0 \varphi^{\prime\prime}(\tau)=2\lVert p_{g_k}\rVert^2/(\tau-\tau_{lb}+\lVert B_k\rVert)^3\geq0 φ ′′ ( τ ) = 2 ∥ p g k ∥ 2 / ( τ − τ l b + ∥ B k ∥ ) 3 ≥ 0 when ( τ − τ l b + ∥ B k ∥ ) > 0 (\tau-\tau_{lb}+\lVert B_k\rVert)>0 ( τ − τ l b + ∥ B k ∥) > 0 . Thus, the function φ ( τ ) \varphi(\tau) φ ( τ ) attains its minimum φ ( τ min ) \varphi(\tau_{\min}) φ ( τ m i n ) when τ min \tau_{\min} τ m i n satisfies φ ′ ( τ min ) = 0 \varphi^\prime(\tau_{\min})=0 φ ′ ( τ m i n ) = 0 and τ ≥ − ( − τ l b + ∥ B k ∥ ) \tau\geq-( -\tau_{lb}+\lVert B_k\rVert) τ ≥ − ( − τ l b + ∥ B k ∥) . Namely, we have
φ ( τ min ) = 2 ∥ p g k ∥ ∥ d k ∥ + ( τ l b − ∥ B k ∥ ) ∥ d k ∥ 2 , (50) \varphi(\tau_{\min})=2\lVert p_{g_k}\rVert\lVert d_k\rVert+(\tau_{lb}-\lVert B_k\rVert)\lVert d_k\rVert^2, \tag*{(50)} φ ( τ m i n ) = 2 ∥ p g k ∥ ∥ d k ∥ + ( τ l b − ∥ B k ∥) ∥ d k ∥ 2 , (50)
where
τ min = ∥ p g k ∥ ∥ d k ∥ + τ l b − ∥ B k ∥ . (51) \tau_{\min}=\frac{\lVert p_{g_k}\rVert}{\lVert d_k\rVert}+\tau_{lb}-\lVert B_k\rVert. \tag*{(51)} τ m i n = ∥ d k ∥ ∥ p g k ∥ + τ l b − ∥ B k ∥ . (51)
We prove the property (45) via separately considering τ min ≥ 0 \tau_{\min} \ge0 τ m i n ≥ 0 or τ min < 0 \tau_{\min} < 0 τ m i n < 0 as follows.
(i) When ( ∥ p g k ∥ / ∥ d k ∥ + ( τ l b − ∥ B k ∥ ) ) ≥ 0 (\|p_{g_k}\|/\|d_k\|+(\tau_{lb}-\|B_k\|)) \ge0 ( ∥ p g k ∥/∥ d k ∥ + ( τ l b − ∥ B k ∥ )) ≥ 0 , from equation (51) , we have τ min ≥ 0 \tau_{\min} \ge0 τ m i n ≥ 0 . From the assumption (44) and the definition (47) of τ l b \tau_{lb} τ l b , we have τ k ≥ − τ l b \tau_k \ge-\tau_{lb} τ k ≥ − τ l b . Thus, from equations (48) –(51) , we obtain
q k ( 0 ) − q k ( P k d k ) ≥ 1 2 ( ( τ k + τ l b ) ∥ d k ∥ 2 + ∥ p g k ∥ 2 τ k + ∥ B k ∥ ) = 1 2 φ ( τ k + τ l b ) ≥ 1 2 φ ( τ min ) = 1 2 ( ∥ p g k ∥ ∥ d k ∥ + ( ∥ p g k ∥ ∥ d k ∥ + ( τ l b − ∥ B k ∥ ) ∥ d k ∥ 2 ) ) ≥ 1 2 ∥ p g k ∥ ∥ d k ∥ . (52) \begin{aligned}
q_k(0)-q_k(P_kd_k) \ge\frac{1}{2}\left((\tau_k+\tau_{lb})\|d_k\|^2+\frac{\|p_{g_k}\|^2}{\tau_k+\|B_k\|}\right)=\frac{1}{2}\varphi(\tau_k+\tau_{lb})\ge\frac{1}{2}\varphi(\tau_{\min}) \\
&=\frac{1}{2}\left(\|p_{g_k}\|\|d_k\|+\left(\|p_{g_k}\|\|d_k\|+(\tau_{lb}-\|B_k\|)\|d_k\|^2\right)\right)\ge\frac{1}{2}\|p_{g_k}\|\|d_k\|. \tag*{(52)}
\end{aligned} q k ( 0 ) − q k ( P k d k ) ≥ 2 1 ( ( τ k + τ l b ) ∥ d k ∥ 2 + τ k + ∥ B k ∥ ∥ p g k ∥ 2 ) = 2 1 φ ( τ k + τ l b ) ≥ 2 1 φ ( τ m i n ) = 2 1 ( ∥ p g k ∥∥ d k ∥ + ( ∥ p g k ∥∥ d k ∥ + ( τ l b − ∥ B k ∥ ) ∥ d k ∥ 2 ) ) ≥ 2 1 ∥ p g k ∥∥ d k ∥. (52)
(ii) The other case is ( ∥ p g k ∥ / ∥ d k ∥ + ( τ l b − ∥ B k ∥ ) ) < 0 (\|p_{g_k}\|/\|d_k\|+(\tau_{lb}-\|B_k\|)) < 0 ( ∥ p g k ∥/∥ d k ∥ + ( τ l b − ∥ B k ∥ )) < 0 . In this case, from equation (51) , we have τ min < 0 \tau_{\min}<0 τ m i n < 0 . It is not difficult to verify that φ ( τ ) \varphi(\tau) φ ( τ ) is monotonically increasing when τ ≥ 0 \tau\ge0 τ ≥ 0 and τ min < 0 \tau_{\min}<0 τ m i n < 0 . From the definition (47) of τ l b \tau_{lb} τ l b and the property (11) , we have
∣ τ l b ∣ ≤ ∣ μ min ( B k − P k T B k P k ) ∣ ≤ ∥ B k − P k T B k P k ∥ ≤ ∥ B k ∥ + ∥ P k T B k P k ∥ ≤ ∥ B k ∥ + ∥ P k T ∥ ∥ B k ∥ ∥ P k ∥ = 2 ∥ B k ∥ . \begin{aligned}
|\tau_{lb}|\le|\mu_{\min}(B_k-P_k^T B_kP_k)|\le\|B_k-P_k^T B_kP_k\|\le\|B_k\|+\|P_k^T B_kP_k\| \\
&\le\|B_k\|+\|P_k^T\|\|B_k\|\|P_k\|=2\|B_k\|.
\end{aligned} ∣ τ l b ∣ ≤ ∣ μ m i n ( B k − P k T B k P k ) ∣ ≤ ∥ B k − P k T B k P k ∥ ≤ ∥ B k ∥ + ∥ P k T B k P k ∥ ≤ ∥ B k ∥ + ∥ P k T ∥∥ B k ∥∥ P k ∥ = 2∥ B k ∥.
By using this property and the monotonicity of φ ( τ ) \varphi(\tau) φ ( τ ) , from equations (48) –(49) , we obtain
q k ( 0 ) − q k ( P k d k ) ≥ 1 2 ( ( τ k + τ l b ) ∥ d k ∥ 2 + ∥ p g k ∥ 2 τ k + ∥ B k ∥ ) = 1 2 φ ( τ k + τ l b ) ≥ 1 2 φ ( 0 ) = 1 2 ( − τ l b + ∥ B k ∥ ) ∥ p g k ∥ 2 ≥ 1 6 ∥ B k ∥ ∥ p g k ∥ 2 . (53) \begin{aligned}
q_k(0)-q_k(P_kd_k)\ge\frac{1}{2}\left((\tau_k+\tau_{lb})\|d_k\|^2+\frac{\|p_{g_k}\|^2}{\tau_k+\|B_k\|}\right) \\
&=\frac{1}{2}\varphi(\tau_k+\tau_{lb})\ge\frac{1}{2}\varphi(0)=\frac{1}{2(-\tau_{lb}+\|B_k\|)}\|p_{g_k}\|^2\ge\frac{1}{6\|B_k\|}\|p_{g_k}\|^2. \tag*{(53)}
\end{aligned} q k ( 0 ) − q k ( P k d k ) ≥ 2 1 ( ( τ k + τ l b ) ∥ d k ∥ 2 + τ k + ∥ B k ∥ ∥ p g k ∥ 2 ) = 2 1 φ ( τ k + τ l b ) ≥ 2 1 φ ( 0 ) = 2 ( − τ l b + ∥ B k ∥ ) 1 ∥ p g k ∥ 2 ≥ 6∥ B k ∥ 1 ∥ p g k ∥ 2 . (53)
From equations (52) –(53) , we get
q k ( 0 ) − q k ( P k d k ) ≥ 1 2 ∥ p g k ∥ min { ∥ d k ∥ , ∥ p g k ∥ 3 ∥ B k ∥ } . (54) q_k(0)-q_k(P_kd_k)\ge\frac{1}{2}\|p_{g_k}\|\min\left\{\|d_k\|,\frac{\|p_{g_k}\|}{3\|B_k\|}\right\}. \tag*{(54)} q k ( 0 ) − q k ( P k d k ) ≥ 2 1 ∥ p g k ∥ min { ∥ d k ∥ , 3∥ B k ∥ ∥ p g k ∥ } . (54)
By using the property (11) of matrix P k P_k P k , we have
∥ P k d k ∥ ≤ ∥ P k ∥ ∥ d k ∥ = ∥ d k ∥ . (55) \|P_kd_k\|\le\|P_k\|\|d_k\|=\|d_k\|. \tag*{(55)} ∥ P k d k ∥ ≤ ∥ P k ∥∥ d k ∥ = ∥ d k ∥. (55)
Therefore, from inequalities (54) –(55) , we obtain the estimation (45) . □ \square □
When Δ t k ≤ σ 0 2 ∥ B k ∥ \Delta t_k\le\frac{\sigma_0}{2\|B_k\|} Δ t k ≤ 2∥ B k ∥ σ 0 , by using the property ∥ P k ∥ = 1 \|P_k\|=1 ∥ P k ∥ = 1 of the projection matrix P k P_k P k , we have
( σ 0 Δ t k I + B k ) ≻ 0 and ( σ 0 Δ t k I + B k − P k T B k P k ) ⪰ 0. (56) \left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)\succ0\quad\text{and}\quad\left(\frac{\sigma_0}{\Delta t_k}I+B_k-P_k^T B_kP_k\right)\succeq0. \tag*{(56)} ( Δ t k σ 0 I + B k ) ≻ 0 and ( Δ t k σ 0 I + B k − P k T B k P k ) ⪰ 0. (56)
Thus, from equation (18) and Lemma 1, when Δ t k ≤ σ 0 4 ∥ B k ∥ \Delta t_k\le\frac{\sigma_0}{4\|B_k\|} Δ t k ≤ 4∥ B k ∥ σ 0 , we obtain the estimation of the predicted reduction of the horizontal step as follows.
Lemma 2 Assume that the quadratic model q k ( s ) q_k(s) q k ( s ) is defined by equation (24) and s k p s_k^p s k p is solved by the regularization method (18) . Then, when Δ t k ≤ σ 0 4 ∥ B k ∥ \Delta t_k \le\frac{\sigma_0}{4\lVert B_k\rVert} Δ t k ≤ 4 ∥ B k ∥ σ 0 , we have the lower bounded estimation of q 0 − q k ( s k p ) q_0-q_k(s_k^p) q 0 − q k ( s k p ) as follows:
H p r e d k = q k ( 0 ) − q k ( s k p ) = q k ( 0 ) − q k ( Δ t k 1 + Δ t k P k d k ) ≥ 1 2 ∥ P k g k ∥ ∥ s k p ∥ . (57) Hpred_k=q_k(0)-q_k(s_k^p)=q_k(0)-q_k\left(\frac{\Delta t_k}{1+\Delta t_k}P_kd_k\right)\ge\frac{1}{2}\lVert P_kg_k\rVert\lVert s_k^p\rVert. \tag*{(57)} H p r e d k = q k ( 0 ) − q k ( s k p ) = q k ( 0 ) − q k ( 1 + Δ t k Δ t k P k d k ) ≥ 2 1 ∥ P k g k ∥ ∥ s k p ∥ . (57)
Proof. We prove this result via considering two different cases, i.e. ( s k p ) T B k s k p ≤ 0 (s_k^p)^TB_ks_k^p\le0 ( s k p ) T B k s k p ≤ 0 or ( s k p ) T B k s k p > 0 (s_k^p)^TB_ks_k^p>0 ( s k p ) T B k s k p > 0 . (i) When ( s k p ) T B k s k p ≤ 0 (s_k^p)^TB_ks_k^p\le0 ( s k p ) T B k s k p ≤ 0 , from equation (24) and equation (18) , we have
q k ( 0 ) − q k ( s k p ) = − g k T s k p − 1 2 ( s k p ) T B k s k p ≥ − g k T s k p = − Δ t k 1 + Δ t k ( P k g k ) T d k = Δ t k 1 + Δ t k ( P k g k ) T ( σ 0 Δ t k I + B k ) − 1 ( P k g k ) ≥ Δ t k 1 + Δ t k 1 σ 0 / Δ t k + ∥ B k ∥ ∥ P k g k ∥ 2 . (58) \begin{aligned}
q_k(0)-q_k(s_k^p)=-g_k^Ts_k^p-\frac{1}{2}(s_k^p)^TB_ks_k^p\ge-g_k^Ts_k^p=-\frac{\Delta t_k}{1+\Delta t_k}(P_kg_k)^Td_k \\
&=\frac{\Delta t_k}{1+\Delta t_k}(P_kg_k)^T\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)^{-1}(P_kg_k)\ge\frac{\Delta t_k}{1+\Delta t_k}\frac{1}{\sigma_0/\Delta t_k+\lVert B_k\rVert}\lVert P_kg_k\rVert^2. \tag*{(58)}
\end{aligned} q k ( 0 ) − q k ( s k p ) = − g k T s k p − 2 1 ( s k p ) T B k s k p ≥ − g k T s k p = − 1 + Δ t k Δ t k ( P k g k ) T d k = 1 + Δ t k Δ t k ( P k g k ) T ( Δ t k σ 0 I + B k ) − 1 ( P k g k ) ≥ 1 + Δ t k Δ t k σ 0 /Δ t k + ∥ B k ∥ 1 ∥ P k g k ∥ 2 . (58)
Furthermore, from equation (18) , when Δ t k < σ 0 ∥ B k ∥ \Delta t_k<\frac{\sigma_0}{\lVert B_k\rVert} Δ t k < ∥ B k ∥ σ 0 , we have
∥ P k g k ∥ = ∥ ( σ 0 Δ t k I + B k ) d k ∥ ≥ ( σ 0 / Δ t k − ∥ B k ∥ ) ∥ d k ∥ ≥ ( σ 0 / Δ t k − ∥ B k ∥ ) ∥ P k d k ∥ . (59) \begin{aligned}
\lVert P_kg_k\rVert=\left\lVert\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)d_k\right\rVert\ge(\sigma_0/\Delta t_k-\lVert B_k\rVert)\lVert d_k\rVert\\
&\ge(\sigma_0/\Delta t_k-\lVert B_k\rVert)\lVert P_kd_k\rVert. \tag*{(59)}
\end{aligned} ∥ P k g k ∥ = ( Δ t k σ 0 I + B k ) d k ≥ ( σ 0 /Δ t k − ∥ B k ∥) ∥ d k ∥ ≥ ( σ 0 /Δ t k − ∥ B k ∥) ∥ P k d k ∥ . (59)
By substituting equation (59) into equation (58) , when Δ t k ≤ σ 0 4 ∥ B k ∥ \Delta t_k\le\frac{\sigma_0}{4\lVert B_k\rVert} Δ t k ≤ 4 ∥ B k ∥ σ 0 , we obtain
q k ( 0 ) − q k ( s k p ) ≥ Δ t k 1 + Δ t k σ 0 / Δ t k − ∥ B k ∥ σ 0 / Δ t k + ∥ B k ∥ ∥ P k g k ∥ ∥ P k d k ∥ ≥ σ 0 / Δ t k − ∥ B k ∥ σ 0 / Δ t k + ∥ B k ∥ ∥ P k g k ∥ ∥ s k p ∥ ≥ 4 ∥ B k ∥ − ∥ B k ∥ 4 ∥ B k ∥ + ∥ B k ∥ ∥ P k g k ∥ ∥ s k p ∥ = 3 5 ∥ P k g k ∥ ∥ s k p ∥ . (60) \begin{aligned}
q_k(0)-q_k(s_k^p)\ge\frac{\Delta t_k}{1+\Delta t_k}\frac{\sigma_0/\Delta t_k-\lVert B_k\rVert}{\sigma_0/\Delta t_k+\lVert B_k\rVert}\lVert P_kg_k\rVert\lVert P_kd_k\rVert\\
&\ge\frac{\sigma_0/\Delta t_k-\lVert B_k\rVert}{\sigma_0/\Delta t_k+\lVert B_k\rVert}\lVert P_kg_k\rVert\lVert s_k^p\rVert\ge\frac{4\lVert B_k\rVert-\lVert B_k\rVert}{4\lVert B_k\rVert+\lVert B_k\rVert}\lVert P_kg_k\rVert\lVert s_k^p\rVert=\frac{3}{5}\lVert P_kg_k\rVert\lVert s_k^p\rVert. \tag*{(60)}
\end{aligned} q k ( 0 ) − q k ( s k p ) ≥ 1 + Δ t k Δ t k σ 0 /Δ t k + ∥ B k ∥ σ 0 /Δ t k − ∥ B k ∥ ∥ P k g k ∥ ∥ P k d k ∥ ≥ σ 0 /Δ t k + ∥ B k ∥ σ 0 /Δ t k − ∥ B k ∥ ∥ P k g k ∥ ∥ s k p ∥ ≥ 4 ∥ B k ∥ + ∥ B k ∥ 4 ∥ B k ∥ − ∥ B k ∥ ∥ P k g k ∥ ∥ s k p ∥ = 5 3 ∥ P k g k ∥ ∥ s k p ∥ . (60)
Thus, the result (57) is true for the case ( s k p ) T B k s k p ≤ 0 (s_k^p)^TB_ks_k^p\le0 ( s k p ) T B k s k p ≤ 0 .
(ii) When ( s k p ) T B k s k p ≥ 0 (s_k^p)^TB_ks_k^p\ge0 ( s k p ) T B k s k p ≥ 0 , i.e. ( P k d k ) T B k ( P k d k ) ≥ 0 (P_kd_k)^TB_k(P_kd_k)\ge0 ( P k d k ) T B k ( P k d k ) ≥ 0 , from equation (24) and equation (18) , we have
q k ( 0 ) − q k ( s k p ) = − g k T s k p − 1 2 ( s k p ) T B k s k p = − Δ t k 1 + Δ t k g k T ( P k d k ) − 1 2 ( Δ t k 1 + Δ t k ) 2 ( P k d k ) T B k ( P k d k ) ≥ Δ t k 1 + Δ t k ( − g k T ( P k d k ) − 1 2 ( P k d k ) T B k ( P k d k ) ) = Δ t k 1 + Δ t k ( q k ( 0 ) − q k ( P k d k ) ) . (61) \begin{aligned}
q_k(0)-q_k(s_k^p)=-g_k^Ts_k^p-\frac{1}{2}(s_k^p)^TB_ks_k^p \\
&=-\frac{\Delta t_k}{1+\Delta t_k}g_k^T(P_kd_k)-\frac{1}{2}\left(\frac{\Delta t_k}{1+\Delta t_k}\right)^2(P_kd_k)^TB_k(P_kd_k) \\
&\ge\frac{\Delta t_k}{1+\Delta t_k}\left(-g_k^T(P_kd_k)-\frac{1}{2}(P_kd_k)^TB_k(P_kd_k)\right)=\frac{\Delta t_k}{1+\Delta t_k}(q_k(0)-q_k(P_kd_k)). \tag*{(61)}
\end{aligned} q k ( 0 ) − q k ( s k p ) = − g k T s k p − 2 1 ( s k p ) T B k s k p = − 1 + Δ t k Δ t k g k T ( P k d k ) − 2 1 ( 1 + Δ t k Δ t k ) 2 ( P k d k ) T B k ( P k d k ) ≥ 1 + Δ t k Δ t k ( − g k T ( P k d k ) − 2 1 ( P k d k ) T B k ( P k d k ) ) = 1 + Δ t k Δ t k ( q k ( 0 ) − q k ( P k d k )) . (61)
When Δ t k ≤ σ 0 4 ∥ B k ∥ \Delta t_k\le\frac{\sigma_0}{4\lVert B_k\rVert} Δ t k ≤ 4 ∥ B k ∥ σ 0 , by substituting equation (45) and equation (59) into equation (61) , we obtain
q k ( 0 ) − q k ( s k p ) ≥ 1 2 Δ t k 1 + Δ t k ∥ P k g k ∥ min { ∥ P k d k ∥ , ∥ P k g k ∥ 3 ∥ B k ∥ } ≥ 1 2 Δ t k 1 + Δ t k ∥ P k g k ∥ min { ∥ P k d k ∥ , ( σ 0 / Δ t k − ∥ B k ∥ ) ∥ P k d k ∥ 3 ∥ B k ∥ } ≥ 1 2 Δ t k 1 + Δ t k ∥ P k g k ∥ ∥ P k d k ∥ = 1 2 ∥ P k g k ∥ ∥ s k p ∥ . (62) \begin{aligned}
q_k(0)-q_k(s_k^p)\ge\frac{1}{2}\frac{\Delta t_k}{1+\Delta t_k}\lVert P_kg_k\rVert\min\left\{\lVert P_kd_k\rVert,\frac{\lVert P_kg_k\rVert}{3\lVert B_k\rVert}\right\} \\
&\ge\frac{1}{2}\frac{\Delta t_k}{1+\Delta t_k}\lVert P_kg_k\rVert\min\left\{\lVert P_kd_k\rVert,\frac{(\sigma_0/\Delta t_k-\lVert B_k\rVert)\lVert P_kd_k\rVert}{3\lVert B_k\rVert}\right\} \\
&\ge\frac{1}{2}\frac{\Delta t_k}{1+\Delta t_k}\lVert P_kg_k\rVert\lVert P_kd_k\rVert=\frac{1}{2}\lVert P_kg_k\rVert\lVert s_k^p\rVert. \tag*{(62)}
\end{aligned} q k ( 0 ) − q k ( s k p ) ≥ 2 1 1 + Δ t k Δ t k ∥ P k g k ∥ min { ∥ P k d k ∥ , 3 ∥ B k ∥ ∥ P k g k ∥ } ≥ 2 1 1 + Δ t k Δ t k ∥ P k g k ∥ min { ∥ P k d k ∥ , 3 ∥ B k ∥ ( σ 0 /Δ t k − ∥ B k ∥) ∥ P k d k ∥ } ≥ 2 1 1 + Δ t k Δ t k ∥ P k g k ∥ ∥ P k d k ∥ = 2 1 ∥ P k g k ∥ ∥ s k p ∥ . (62)
Thus, the result (57) is also true for the case ( s k p ) T B k s k p > 0 (s_k^p)^{T}B_ks_k^p>0 ( s k p ) T B k s k p > 0 . □
In the following analysis of Algorithm 2, f ( x ) f(x) f ( x ) and c ( x ) c(x) c ( x ) are assumed to satisfy Assumption 1.
Assumption 1 Assume that f ( x ) f(x) f ( x ) is twice continuously differentiable and c ( x ) c(x) c ( x ) is continuously differentiable, that the sequence { x k } \{x_k\} { x k } is generated by Algorithm 2 in an open set S S S , that ∇ f ( x ) \nabla f(x) ∇ f ( x ) , ∇ 2 f ( x ) \nabla^2 f(x) ∇ 2 f ( x ) , A ( x ) A(x) A ( x ) are bounded above on S S S . We also assume that ∥ B k ∥ \|B_k\| ∥ B k ∥ ( k = 0 , 1 , 2 , … ) (k=0,1,2,\ldots) ( k = 0 , 1 , 2 , … ) are uniformly bounded. Namely, there exists three positive constants M B M_B M B , M g M_g M g , M A M_A M A such that
∥ ∇ 2 f ( x ) ∥ ≤ M B , ∥ A ( x ) ∥ ≤ M A , ∥ A ( x ) † ∥ ≤ M A , ∀ x ∈ S , \|\nabla^2f(x)\|\leq M_B,\ \|A(x)\|\leq M_A,\ \|A(x)^\dagger\|\leq M_A,\ \forall x\in S, ∥ ∇ 2 f ( x ) ∥ ≤ M B , ∥ A ( x ) ∥ ≤ M A , ∥ A ( x ) † ∥ ≤ M A , ∀ x ∈ S , and ∥ B k ∥ ≤ M B , ∥ ∇ f ( x k ) ∥ ≤ M g , k = 0 , 1 , 2 , … (63) \text{and }\|B_k\|\leq M_B,\ \|\nabla f(x_k)\|\leq M_g,\ k=0,1,2,\ldots \tag*{(63)} and ∥ B k ∥ ≤ M B , ∥∇ f ( x k ) ∥ ≤ M g , k = 0 , 1 , 2 , … (63) hold.
By combining the property ∥ P k ∥ = 1 \|P_k\|=1 ∥ P k ∥ = 1 of the projection matrix P k P_k P k , from the assumption (63) , we obtain
∥ P k ∇ 2 f ( x k ) P k ∥ ≤ ∥ P k ∥ ∥ ∇ 2 f ( x k ) ∥ ∥ P k ∥ = ∥ ∇ 2 f ( x k ) ∥ ≤ M B , \|P_k\nabla^2f(x_k)P_k\|\leq\|P_k\|\|\nabla^2f(x_k)\|\|P_k\|=\|\nabla^2f(x_k)\|\leq M_B, ∥ P k ∇ 2 f ( x k ) P k ∥ ≤ ∥ P k ∥∥ ∇ 2 f ( x k ) ∥∥ P k ∥ = ∥ ∇ 2 f ( x k ) ∥ ≤ M B ,
∥ P k B k P k ∥ ≤ ∥ P k ∥ ∥ B k ∥ ∥ P k ∥ = ∥ B k ∥ ≤ M B , k = 0 , 1 , 2 , … (64) \|P_kB_kP_k\|\leq\|P_k\|\|B_k\|\|P_k\|=\|B_k\|\leq M_B,\quad k=0,1,2,\ldots \tag*{(64)} ∥ P k B k P k ∥ ≤ ∥ P k ∥∥ B k ∥∥ P k ∥ = ∥ B k ∥ ≤ M B , k = 0 , 1 , 2 , … (64)
According to the property of the matrix norm, we know that the absolute eigenvalue of P k ∇ 2 f ( x k ) P k P_k\nabla^2f(x_k)P_k P k ∇ 2 f ( x k ) P k is less than M B M_B M B . If we denote μ ( P k ∇ 2 f ( x k ) P k ) \mu\left(P_k\nabla^2f(x_k)P_k\right) μ ( P k ∇ 2 f ( x k ) P k ) as the eigenvalue of P k ∇ 2 f ( x k ) P k P_k\nabla^2f(x_k)P_k P k ∇ 2 f ( x k ) P k , we know that the eigenvalue of ( σ 0 Δ t k I + P k ∇ 2 f ( x k ) P k ) \left(\frac{\sigma_0}{\Delta t_k}I+P_k\nabla^2f(x_k)P_k\right) ( Δ t k σ 0 I + P k ∇ 2 f ( x k ) P k ) is σ 0 Δ t k + μ ( P k ∇ 2 f ( x k ) P k ) \frac{\sigma_0}{\Delta t_k}+\mu\left(P_k\nabla^2f(x_k)P_k\right) Δ t k σ 0 + μ ( P k ∇ 2 f ( x k ) P k ) . Consequently, from equation (64) , we known that
σ 0 Δ t k I + P k ∇ 2 f ( x k ) P k ≻ 0 , when Δ t k < σ 0 M B . (65) \frac{\sigma_0}{\Delta t_k}I+P_k\nabla^2f(x_k)P_k\succ0,\quad\text{when }\Delta t_k<\frac{\sigma_0}{M_B}. \tag*{(65)} Δ t k σ 0 I + P k ∇ 2 f ( x k ) P k ≻ 0 , when Δ t k < M B σ 0 . (65)
In order to prove the global convergence of Algorithm 2, we need to prove the iteration sequence { x k } \{x_k\} { x k } preserves the constraint feasible c ( x k ) ≈ 0 c(x_k)\approx0 c ( x k ) ≈ 0 and its convergence point x ∗ x^* x ∗ satisfies the KKT condition (2). In the following Lemma 3, we prove that the iteration sequence { x k } \{x_k\} { x k } generated by Algorithm 2 will preserve on the neighbourhood of the feasibility c ( x ) = 0 c(x)=0 c ( x ) = 0 when the time steps Δ t k \Delta t_k Δ t k ( k = 0 , 1 , … ) (k=0,1,\ldots) ( k = 0 , 1 , … ) are sufficiently small. The proof of the convergence point x ∗ x^* x ∗ satisfying the KKT condition (2) is left to Theorem 1.
Lemma 3 Assume that c ( x ) c(x) c ( x ) is continuously differentiable and its Jacobian matrix A ( x ) A(x) A ( x ) is Lipschitz continuous. Namely, there exists a positive constant L A L_A L A such that
∥ A ( x ) − A ( y ) ∥ ≤ L A ∥ x − y ∥ , ∀ x , y ∈ R n . (66) \|A(x)-A(y)\|\leq L_A\|x-y\|,\quad\forall x,y\in\mathbb{R}^n. \tag*{(66)} ∥ A ( x ) − A ( y ) ∥ ≤ L A ∥ x − y ∥ , ∀ x , y ∈ R n . (66) Furthermore, we suppose s k s_k s k is solved by equations (18) -(22) and B k B_k B k , ∇ f ( x k ) \nabla f(x_k) ∇ f ( x k ) ( k = 0 , 1 , 2 , … ) (k=0,1,2,\ldots) ( k = 0 , 1 , 2 , … ) are uniformly bounded. Namely, they satisfy Assumption 1. Then, there exists a positive constant δ c \delta_c δ c such that
∥ c ( x k + s k ) ∥ ≤ ε 0 , (67) \|c(x_k+s_k)\|\leq\varepsilon_0, \tag*{(67)} ∥ c ( x k + s k ) ∥ ≤ ε 0 , (67) when Δ t k ≤ δ c \Delta t_k\leq\delta_c Δ t k ≤ δ c , 0 < ε 0 ≤ min { 1 / ( L A M A 2 ) , ε } 0<\varepsilon_0\leq\min\{1/(L_AM_A^2),\varepsilon\} 0 < ε 0 ≤ min { 1/ ( L A M A 2 ) , ε } and ∥ c ( x k ) ∥ ≤ ε 0 \|c(x_k)\|\leq\varepsilon_0 ∥ c ( x k ) ∥ ≤ ε 0 .
Proof. When A k + 1 p = A ( x k ) A_{k+1}^{p}=A(x_k) A k + 1 p = A ( x k ) and ∥ c ( x k + 1 ) ∥ ≤ ε 0 \lVert c(x_{k+1})\rVert\leq\varepsilon_0 ∥ c ( x k + 1 )∥ ≤ ε 0 , we obtain the result (67) . Therefore, we only need to consider the case A k + 1 p = A ( x k + 1 p ) A_{k+1}^{p}=A(x_{k+1}^{p}) A k + 1 p = A ( x k + 1 p ) below. From the first-order Taylor expansion and equation (22) , we have
c ( x k + s k ) = c ( x k + s k p + s k c ) = c ( x k + 1 p + s k c ) = c ( x k + 1 p ) + ∫ 0 1 A ( x k + 1 p + t s k c ) s k c d t = c ( x k + 1 p ) + A ( x k + 1 p ) s k c + ∫ 0 1 ( A ( x k + 1 p + t s k c ) − A ( x k + 1 p ) ) s k c d t = ∫ 0 1 ( A ( x k + 1 p + t s k c ) − A ( x k + 1 p ) ) s k c d t . (68) \begin{aligned}
c(x_k+s_k)&=c(x_k+s_k^p+s_k^c)=c(x_{k+1}^p+s_k^c)=c(x_{k+1}^p)+\int_0^1 A(x_{k+1}^p+ts_k^c)s_k^c\,\mathrm{d}t\\
&=c(x_{k+1}^p)+A(x_{k+1}^p)s_k^c+\int_0^1\left(A(x_{k+1}^p+ts_k^c)-A(x_{k+1}^p)\right)s_k^c\,\mathrm{d}t\\
&=\int_0^1\left(A(x_{k+1}^p+ts_k^c)-A(x_{k+1}^p)\right)s_k^c\,\mathrm{d}t. \tag*{(68)}
\end{aligned} c ( x k + s k ) = c ( x k + s k p + s k c ) = c ( x k + 1 p + s k c ) = c ( x k + 1 p ) + ∫ 0 1 A ( x k + 1 p + t s k c ) s k c d t = c ( x k + 1 p ) + A ( x k + 1 p ) s k c + ∫ 0 1 ( A ( x k + 1 p + t s k c ) − A ( x k + 1 p ) ) s k c d t = ∫ 0 1 ( A ( x k + 1 p + t s k c ) − A ( x k + 1 p ) ) s k c d t . (68)
By substituting the Lipschitz continuity (66) of A ( x ) A(x) A ( x ) and the bounded assumption ∥ A ( x ) † ∥ ≤ M A \lVert A(x)^\dagger\rVert\leq M_A ∥ A ( x ) † ∥ ≤ M A into equation (68) , we obtain
∥ c ( x k + s k ) ∥ ≤ ∫ 0 1 ∥ A ( x k + 1 p + t s k c ) − A ( x k + 1 p ) ∥ ∥ s k c ∥ d t ≤ 1 2 L A ∥ s k c ∥ 2 = 1 2 L A ∥ A ( x k + 1 p ) † c ( x k + 1 p ) ∥ 2 ≤ 1 2 L A ∥ A ( x k + 1 p ) † ∥ 2 ∥ c ( x k + 1 p ) ∥ 2 ≤ 1 2 L A M A 2 ∥ c ( x k + 1 p ) ∥ 2 . (69) \begin{aligned}
\lVert c(x_k+s_k)\rVert
&\leq\int_0^1\lVert A(x_{k+1}^p+ts_k^c)-A(x_{k+1}^p)\rVert\lVert s_k^c\rVert\,\mathrm{d}t
\leq\frac{1}{2}L_A\lVert s_k^c\rVert^2\\
&=\frac{1}{2}L_A\left\lVert A(x_{k+1}^p)^\dagger c(x_{k+1}^p)\right\rVert^2
\leq\frac{1}{2}L_A\left\lVert A(x_{k+1}^p)^\dagger\right\rVert^2\lVert c(x_{k+1}^p)\rVert^2\\
&\leq\frac{1}{2}L_AM_A^2\lVert c(x_{k+1}^p)\rVert^2. \tag*{(69)}
\end{aligned} ∥ c ( x k + s k )∥ ≤ ∫ 0 1 ∥ A ( x k + 1 p + t s k c ) − A ( x k + 1 p )∥ ∥ s k c ∥ d t ≤ 2 1 L A ∥ s k c ∥ 2 = 2 1 L A A ( x k + 1 p ) † c ( x k + 1 p ) 2 ≤ 2 1 L A A ( x k + 1 p ) † 2 ∥ c ( x k + 1 p ) ∥ 2 ≤ 2 1 L A M A 2 ∥ c ( x k + 1 p ) ∥ 2 . (69)
In order to estimate the upper bound of ∥ c ( x k + s k ) ∥ \lVert c(x_k+s_k)\rVert ∥ c ( x k + s k )∥ , we need to estimate the upper bound of ∥ c ( x k + 1 p ) ∥ \lVert c(x_{k+1}^p)\rVert ∥ c ( x k + 1 p )∥ . From the property A k P k = 0 A_kP_k=0 A k P k = 0 of the projection matrix P k P_k P k , we have
A k s k p = Δ t k 1 + Δ t k A k P k d k = 0. (70) A_ks_k^p=\frac{\Delta t_k}{1+\Delta t_k}A_kP_kd_k=0. \tag*{(70)} A k s k p = 1 + Δ t k Δ t k A k P k d k = 0. (70)
Thus, from the first-order Taylor expansion, the property (70) and the Lipschitz continuity (66) of A ( x ) A(x) A ( x ) , we have
∥ c ( x k + 1 p ) ∥ = ∥ c ( x k ) + ∫ 0 1 A ( x k + t s k p ) s k p d t ∥ = ∥ c ( x k ) + ∫ 0 1 ( A ( x k + t s k p ) − A ( x k ) ) s k p d t ∥ ≤ ∥ c ( x k ) ∥ + ∫ 0 1 ∥ A ( x k + t s k p ) − A ( x k ) ∥ ∥ s k p ∥ d t ≤ ∥ c ( x k ) ∥ + 1 2 L A ∥ s k p ∥ 2 . (71) \begin{aligned}
\lVert c(x_{k+1}^p)\rVert
&=\left\lVert c(x_k)+\int_0^1A(x_k+ts_k^p)s_k^p\,\mathrm{d}t\right\rVert\\
&=\left\lVert c(x_k)+\int_0^1\left(A(x_k+ts_k^p)-A(x_k)\right)s_k^p\,\mathrm{d}t\right\rVert\\
&\leq\lVert c(x_k)\rVert+\int_0^1\lVert A(x_k+ts_k^p)-A(x_k)\rVert\lVert s_k^p\rVert\,\mathrm{d}t
\leq\lVert c(x_k)\rVert+\frac{1}{2}L_A\lVert s_k^p\rVert^2. \tag*{(71)}
\end{aligned} ∥ c ( x k + 1 p )∥ = c ( x k ) + ∫ 0 1 A ( x k + t s k p ) s k p d t = c ( x k ) + ∫ 0 1 ( A ( x k + t s k p ) − A ( x k ) ) s k p d t ≤ ∥ c ( x k )∥ + ∫ 0 1 ∥ A ( x k + t s k p ) − A ( x k )∥ ∥ s k p ∥ d t ≤ ∥ c ( x k )∥ + 2 1 L A ∥ s k p ∥ 2 . (71)
Furthermore, from equation (18) and the assumption (63) of g ( x ) g(x) g ( x ) and B k B_k B k , when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k\leq\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) , we obtain
∥ s k p ∥ = Δ t k 1 + Δ t k ∥ ( σ 0 Δ t k I + B k ) − 1 P k g k ∥ ≤ Δ t k 1 + Δ t k ∥ P k g k ∥ σ 0 / Δ t k − ∥ B k ∥ ≤ Δ t k 1 + Δ t k ∥ P k ∥ ∥ g k ∥ σ 0 / Δ t k − M B ≤ Δ t k 1 + Δ t k M g 2 M B − M B = Δ t k 1 + Δ t k M g M B . (72) \begin{aligned}
\lVert s_k^p\rVert
&=\frac{\Delta t_k}{1+\Delta t_k}\left\lVert\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)^{-1}P_kg_k\right\rVert
\leq\frac{\Delta t_k}{1+\Delta t_k}\frac{\lVert P_kg_k\rVert}{\sigma_0/\Delta t_k-\lVert B_k\rVert}\\
&\leq\frac{\Delta t_k}{1+\Delta t_k}\frac{\lVert P_k\rVert\lVert g_k\rVert}{\sigma_0/\Delta t_k-M_B}
\leq\frac{\Delta t_k}{1+\Delta t_k}\frac{M_g}{2M_B-M_B}
=\frac{\Delta t_k}{1+\Delta t_k}\frac{M_g}{M_B}. \tag*{(72)}
\end{aligned} ∥ s k p ∥ = 1 + Δ t k Δ t k ( Δ t k σ 0 I + B k ) − 1 P k g k ≤ 1 + Δ t k Δ t k σ 0 /Δ t k − ∥ B k ∥ ∥ P k g k ∥ ≤ 1 + Δ t k Δ t k σ 0 /Δ t k − M B ∥ P k ∥ ∥ g k ∥ ≤ 1 + Δ t k Δ t k 2 M B − M B M g = 1 + Δ t k Δ t k M B M g . (72)
According to the inductive hypothesis, we have ∥ c ( x k ) ∥ ≤ ε 0 \lVert c(x_k)\rVert\le\varepsilon_0 ∥ c ( x k )∥ ≤ ε 0 . By substituting it and equation (72) into equation (71) , when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k \le\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) , we obtain
∥ c ( x k + 1 p ) ∥ ≤ ε 0 + 1 2 L A ( Δ t k 1 + Δ t k M g M B ) 2 . (73) \lVert c(x_{k+1}^{p})\rVert\le\varepsilon_0+\frac{1}{2}L_A\left(\frac{\Delta t_k}{1+\Delta t_k}\frac{M_g}{M_B}\right)^2. \tag*{(73)} ∥ c ( x k + 1 p )∥ ≤ ε 0 + 2 1 L A ( 1 + Δ t k Δ t k M B M g ) 2 . (73)
Thus, from equation (69) and equation (73) , when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k \le\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) , we prove ∥ c ( x k + s k ) ∥ ≤ ε 0 \lVert c(x_k+s_k)\rVert\le\varepsilon_0 ∥ c ( x k + s k )∥ ≤ ε 0 if only we prove
1 2 L A M A 2 ( ε 0 + 1 2 L A ( Δ t k 1 + Δ t k M g M B ) 2 ) 2 ≤ ε 0 . \frac{1}{2}L_AM_A^2\left(\varepsilon_0+\frac{1}{2}L_A\left(\frac{\Delta t_k}{1+\Delta t_k}\frac{M_g}{M_B}\right)^2\right)^2\le\varepsilon_0. 2 1 L A M A 2 ( ε 0 + 2 1 L A ( 1 + Δ t k Δ t k M B M g ) 2 ) 2 ≤ ε 0 .
Namely, when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k \le\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) , we only need to prove
Δ t k 1 + Δ t k ≤ 2 M B 2 L A M g 2 ( − ε 0 + 2 ε 0 L A M A 2 ) . (74) \frac{\Delta t_k}{1+\Delta t_k}\le\frac{2M_B^2}{L_AM_g^2}\left(-\varepsilon_0+\sqrt{\frac{2\varepsilon_0}{L_AM_A^2}}\right). \tag*{(74)} 1 + Δ t k Δ t k ≤ L A M g 2 2 M B 2 ( − ε 0 + L A M A 2 2 ε 0 ) . (74)
We select
δ c = min { σ 0 4 M B , 2 M B 2 L A M g 2 ( − ε 0 + 2 ε 0 L A M A 2 ) 1 − 2 M B 2 L A M g 2 ( − ε 0 + 2 ε 0 L A M A 2 ) } . (75) \delta_c=\min\left\{\frac{\sigma_0}{4M_B},\frac{\frac{2M_B^2}{L_AM_g^2}\left(-\varepsilon_0+\sqrt{\frac{2\varepsilon_0}{L_AM_A^2}}\right)}{1-\frac{2M_B^2}{L_AM_g^2}\left(-\varepsilon_0+\sqrt{\frac{2\varepsilon_0}{L_AM_A^2}}\right)}\right\}. \tag*{(75)} δ c = min ⎩ ⎨ ⎧ 4 M B σ 0 , 1 − L A M g 2 2 M B 2 ( − ε 0 + L A M A 2 2 ε 0 ) L A M g 2 2 M B 2 ( − ε 0 + L A M A 2 2 ε 0 ) ⎭ ⎬ ⎫ . (75)
Then, when Δ t k ≤ δ c \Delta t_k\le\delta_c Δ t k ≤ δ c and ε 0 ≤ min { 1 / ( L A M A 2 ) , ε } \varepsilon_0\le\min\{1/(L_AM_A^2),\varepsilon\} ε 0 ≤ min { 1/ ( L A M A 2 ) , ε } , we know that equation (74) is true. Namely, we have ∥ c ( x k + s k ) ∥ ≤ ε 0 \lVert c(x_k+s_k)\rVert\le\varepsilon_0 ∥ c ( x k + s k )∥ ≤ ε 0 when Δ t k ≤ δ c \Delta t_k\le\delta_c Δ t k ≤ δ c and ε 0 ≤ min { 1 / ( L A M A 2 ) , ε } \varepsilon_0\le\min\{1/(L_AM_A^2),\varepsilon\} ε 0 ≤ min { 1/ ( L A M A 2 ) , ε } . □ \square □
In order to estimate the lower bound of the time steps Δ t k \Delta t_k Δ t k (k = 1 , 2 , … k=1,2,\ldots k = 1 , 2 , … ), we need to prove the correction step s k c s_k^c s k c is less than the predicted step s k p s_k^p s k p and the predicted vertical reduction V p r e d k Vpred_k V p r e d k is less than the predicted horizontal reduction H p r e d k Hpred_k H p r e d k , where s k c s_k^c s k c is solved by equation (22) , and s k p s_k^p s k p is solved by equation (18) , and V p r e d k Vpred_k V p r e d k , H p r e d k Hpred_k H p r e d k are defined by equation (25) . Their proofs are given by the following Lemma 4 under some assumptions.
Lemma 4 Assume that c ( x ) c(x) c ( x ) is continuously differentiable and its Jacobian matrix A ( x ) A(x) A ( x ) satisfies the Lipschitz continuity (66) . Furthermore, we suppose s k p s_k^p s k p is solved by equation (18) and B k B_k B k (k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … ) are uniformly bounded. Namely, B k B_k B k (k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … ) satisfy equation (63) . Assume that ∥ P k g k ∥ ≥ ε \lVert P_kg_k\rVert\ge\varepsilon ∥ P k g k ∥ ≥ ε (k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … ). Then, there exists five positive constants θ c \theta_c θ c , θ v \theta_v θ v , δ 0 \delta_0 δ 0 , δ v \delta_v δ v and δ ε 0 \delta_{\varepsilon_0} δ ε 0 such that
∥ s k c ∥ ≤ θ c ∥ s k p ∥ 2 and ∣ V p r e d k ∣ ≤ θ v ∥ P k g k ∥ ∥ s k p ∥ , (76) \lVert s_k^c\rVert\le\theta_c\lVert s_k^p\rVert^2 \quad\text{and}\quad|Vpred_k|\le\theta_v\lVert P_kg_k\rVert\lVert s_k^p\rVert, \tag*{(76)} ∥ s k c ∥ ≤ θ c ∥ s k p ∥ 2 and ∣ V p r e d k ∣ ≤ θ v ∥ P k g k ∥ ∥ s k p ∥ , (76) when δ 0 ≤ Δ t k ≤ δ v \delta_0\le\Delta t_k\le\delta_v δ 0 ≤ Δ t k ≤ δ v , 0 < ε 0 ≤ δ ε 0 0<\varepsilon_0\le\delta_{\varepsilon_0} 0 < ε 0 ≤ δ ε 0 and ∥ c ( x k ) ∥ ≤ ε 0 \lVert c(x_k)\rVert\le\varepsilon_0 ∥ c ( x k )∥ ≤ ε 0 , where 0 < θ v < 1 / 2 0<\theta_v<1/2 0 < θ v < 1/2 , s k c s_k^c s k c is solved by equation (22) , and V p r e d k Vpred_k V p r e d k is defined by equation (25) .
Proof. From equation (18) , when Δ t k < σ 0 / ∥ B k ∥ \Delta t_k<\sigma_0/\lVert B_k\rVert Δ t k < σ 0 / ∥ B k ∥ , we have
P k d k = − P k ( σ 0 Δ t k I + B k ) − 1 P k g k . P_kd_k=-P_k\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)^{-1}P_kg_k. P k d k = − P k ( Δ t k σ 0 I + B k ) − 1 P k g k .
By combining it with the Cauchy-Schwartz inequality ∣ x T y ∣ ≤ ∥ x ∥ ∥ y ∥ |x^T y| \le\|x\|\|y\| ∣ x T y ∣ ≤ ∥ x ∥∥ y ∥ and P k 2 = P k P_k^2=P_k P k 2 = P k , when Δ t k < σ 0 / ∥ B k ∥ \Delta t_k < \sigma_0/\|B_k\| Δ t k < σ 0 /∥ B k ∥ , we have
∥ P k g k ∥ ∥ P k d k ∥ ≥ ∣ g k T P k 2 d k ∣ = ∣ ( P k g k ) T ( σ 0 Δ t k I + B k ) − 1 ( P k g k ) ∣ ≥ 1 σ 0 / Δ t k + ∥ B k ∥ ∥ P k g k ∥ 2 . (77) \|P_k g_k\|\|P_k d_k\| \ge|g_k^T P_k^2 d_k| = \left|(P_k g_k)^T\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)^{-1}(P_k g_k)\right|
\ge\frac{1}{\sigma_0/\Delta t_k+\|B_k\|}\|P_k g_k\|^2. \tag*{(77)} ∥ P k g k ∥∥ P k d k ∥ ≥ ∣ g k T P k 2 d k ∣ = ( P k g k ) T ( Δ t k σ 0 I + B k ) − 1 ( P k g k ) ≥ σ 0 /Δ t k + ∥ B k ∥ 1 ∥ P k g k ∥ 2 . (77)
Namely, when Δ t k < σ 0 / ∥ B k ∥ \Delta t_k < \sigma_0/\|B_k\| Δ t k < σ 0 /∥ B k ∥ , from equation (77) , we have
∥ s k p ∥ = ∥ Δ t k 1 + Δ t k P k d k ∥ = Δ t k 1 + Δ t k ∥ P k d k ∥ ≥ Δ t k 1 + Δ t k 1 σ 0 / Δ t k + ∥ B k ∥ ∥ P k g k ∥ . (78) \|s_k^p\|=\left\|\frac{\Delta t_k}{1+\Delta t_k}P_kd_k\right\|=\frac{\Delta t_k}{1+\Delta t_k}\|P_kd_k\|\ge\frac{\Delta t_k}{1+\Delta t_k}\frac{1}{\sigma_0/\Delta t_k+\|B_k\|}\|P_kg_k\|. \tag*{(78)} ∥ s k p ∥ = 1 + Δ t k Δ t k P k d k = 1 + Δ t k Δ t k ∥ P k d k ∥ ≥ 1 + Δ t k Δ t k σ 0 /Δ t k + ∥ B k ∥ 1 ∥ P k g k ∥. (78)
Thus, according to the assumptions ∥ B k ∥ ≤ M B \|B_k\|\le M_B ∥ B k ∥ ≤ M B and ∥ P k g k ∥ ≥ ε \|P_kg_k\|\ge\varepsilon ∥ P k g k ∥ ≥ ε , when δ 0 ≤ Δ t k < σ 0 / M B \delta_0\le\Delta t_k<\sigma_0/M_B δ 0 ≤ Δ t k < σ 0 / M B , from equation (78) , we have
∥ s k p ∥ ≥ δ 0 1 + δ 0 1 σ 0 / δ 0 + M B ε = δ 0 ε ( 1 + δ 0 ) ( σ 0 / δ 0 + M B ) . (79) \|s_k^p\|\ge\frac{\delta_0}{1+\delta_0}\frac{1}{\sigma_0/\delta_0+M_B}\varepsilon=\frac{\delta_0\varepsilon}{(1+\delta_0)(\sigma_0/\delta_0+M_B)}. \tag*{(79)} ∥ s k p ∥ ≥ 1 + δ 0 δ 0 σ 0 / δ 0 + M B 1 ε = ( 1 + δ 0 ) ( σ 0 / δ 0 + M B ) δ 0 ε . (79)
From equation (22) , the Lipschitz continuity (66) and equation (71) , we have
∥ s k c ∥ = ∥ A ( x k + 1 p ) † c ( x k + 1 p ) ∥ ≤ M A ∥ c ( x k + 1 p ) ∥ = M A ∥ c ( x k + s k p ) ∥ ≤ M A ( ∥ c ( x k ) ∥ + 1 2 L A ∥ s k p ∥ 2 ) ≤ M A ( ε 0 + 1 2 L A ∥ s k p ∥ 2 ) . (80) \begin{aligned}
\|s_k^c\|=\|A(x_{k+1}^p)^\dagger c(x_{k+1}^p)\|\le M_A\|c(x_{k+1}^p)\|=M_A\|c(x_k+s_k^p)\| \\
&\le M_A\left(\|c(x_k)\|+\frac{1}{2}L_A\|s_k^p\|^2\right)\le M_A\left(\varepsilon_0+\frac{1}{2}L_A\|s_k^p\|^2\right). \tag*{(80)}
\end{aligned} ∥ s k c ∥ = ∥ A ( x k + 1 p ) † c ( x k + 1 p ) ∥ ≤ M A ∥ c ( x k + 1 p ) ∥ = M A ∥ c ( x k + s k p ) ∥ ≤ M A ( ∥ c ( x k ) ∥ + 2 1 L A ∥ s k p ∥ 2 ) ≤ M A ( ε 0 + 2 1 L A ∥ s k p ∥ 2 ) . (80)
We select
δ ε 0 = min { ( δ 0 ε ( 1 + δ 0 ) ( σ 0 / δ 0 + M B ) ) 2 , 1 L A M A 2 } . (81) \delta_{\varepsilon_0}=\min\left\{\left(\frac{\delta_0\varepsilon}{(1+\delta_0)(\sigma_0/\delta_0+M_B)}\right)^2,\frac{1}{L_AM_A^2}\right\}. \tag*{(81)} δ ε 0 = min { ( ( 1 + δ 0 ) ( σ 0 / δ 0 + M B ) δ 0 ε ) 2 , L A M A 2 1 } . (81)
Then, from equations (79) –(81) , when ε 0 ≤ δ ε 0 \varepsilon_0\le\delta_{\varepsilon_0} ε 0 ≤ δ ε 0 , we have
∥ s k c ∥ ≤ M A ( 1 + 1 2 L A ) ∥ s k p ∥ 2 = θ c ∥ s k p ∥ 2 , (82) \|s_k^c\|\le M_A\left(1+\frac{1}{2}L_A\right)\|s_k^p\|^2=\theta_c\|s_k^p\|^2, \tag*{(82)} ∥ s k c ∥ ≤ M A ( 1 + 2 1 L A ) ∥ s k p ∥ 2 = θ c ∥ s k p ∥ 2 , (82)
where we select θ c = M A ( 1 + 0.5 L A ) \theta_c=M_A(1+0.5L_A) θ c = M A ( 1 + 0.5 L A ) . Thus, we prove the first inequality of equation (76) .
From equation (18) , when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k\le\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) , we have
∥ s k p ∥ = ∥ Δ t k 1 + Δ t k P k d k ∥ ≤ ∥ P k d k ∥ ≤ ∥ d k ∥ = ∥ ( σ 0 Δ t k I + B k ) − 1 P k g k ∥ ≤ 1 σ 0 / Δ t k − M B ∥ P k g k ∥ ≤ M g M B . (83) \|s_k^p\|=\left\|\frac{\Delta t_k}{1+\Delta t_k}P_kd_k\right\|\le\|P_kd_k\|\le\|d_k\|=\left\|\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)^{-1}P_kg_k\right\|
\le\frac{1}{\sigma_0/\Delta t_k-M_B}\|P_kg_k\|\le\frac{M_g}{M_B}. \tag*{(83)} ∥ s k p ∥ = 1 + Δ t k Δ t k P k d k ≤ ∥ P k d k ∥ ≤ ∥ d k ∥ = ( Δ t k σ 0 I + B k ) − 1 P k g k ≤ σ 0 /Δ t k − M B 1 ∥ P k g k ∥ ≤ M B M g . (83)
Thus, from equation (25) , equation (82) and the assumption (63) , we have
∣ V p r e d k ∣ = ∣ q k ( s k p ) − q k ( s k p + s k c ) ∣ = ∣ ( s k c ) T ∇ q k ( s k p ) + 1 2 ( s k c ) T ∇ 2 q k ( s k p ) s k c ∣ = ∣ ( s k c ) T ( g k + B k s k p + 1 2 B k s k c ) ∣ ≤ ∥ s k c ∥ ∥ g k + B k s k p + 1 2 B k s k c ∥ ≤ ∥ s k c ∥ ( ∥ g k ∥ + ∥ B k ∥ ( ∥ s k p ∥ + ∥ s k c ∥ ) ) ≤ θ c ( M g + M B ( ∥ s k p ∥ + ∥ s k c ∥ ) ) ∥ s k p ∥ 2 . (84) \begin{aligned}
|Vpred_k| &= |q_k(s_k^p)-q_k(s_k^p+s_k^c)| \\
&= \left|(s_k^c)^T\nabla q_k(s_k^p)+\frac{1}{2}(s_k^c)^T\nabla^2q_k(s_k^p)s_k^c\right| \\
&= \left|(s_k^c)^T\left(g_k+B_ks_k^p+\frac{1}{2}B_ks_k^c\right)\right|
\leq\|s_k^c\|\left\|g_k+B_ks_k^p+\frac{1}{2}B_ks_k^c\right\| \\
&\leq\|s_k^c\|\left(\|g_k\|+\|B_k\|(\|s_k^p\|+\|s_k^c\|)\right)
\leq\theta_c(M_g+M_B(\|s_k^p\|+\|s_k^c\|))\|s_k^p\|^2. \tag*{(84)}
\end{aligned} ∣ V p r e d k ∣ = ∣ q k ( s k p ) − q k ( s k p + s k c ) ∣ = ( s k c ) T ∇ q k ( s k p ) + 2 1 ( s k c ) T ∇ 2 q k ( s k p ) s k c = ( s k c ) T ( g k + B k s k p + 2 1 B k s k c ) ≤ ∥ s k c ∥ g k + B k s k p + 2 1 B k s k c ≤ ∥ s k c ∥ ( ∥ g k ∥ + ∥ B k ∥ ( ∥ s k p ∥ + ∥ s k c ∥ ) ) ≤ θ c ( M g + M B ( ∥ s k p ∥ + ∥ s k c ∥ )) ∥ s k p ∥ 2 . (84)
By substituting equation (82) and equation (83) into equation (84) , when Δ t k ≤ σ 0 2 M B \Delta t_k\leq\frac{\sigma_0}{2M_B} Δ t k ≤ 2 M B σ 0 , we obtain
∣ V p r e d k ∣ ≤ θ c ( 2 M g M B + θ c M g 2 ) M B ∥ s k p ∥ 2 ≤ θ c ( 2 M g M B + θ c M g 2 ) M B ( σ 0 / Δ t k − M B ) ∥ P k g k ∥ ∥ s k p ∥ . (85) |Vpred_k|\leq\frac{\theta_c(2M_gM_B+\theta_cM_g^2)}{M_B}\|s_k^p\|^2\leq\frac{\theta_c(2M_gM_B+\theta_cM_g^2)}{M_B(\sigma_0/\Delta t_k-M_B)}\|P_kg_k\|\|s_k^p\|. \tag*{(85)} ∣ V p r e d k ∣ ≤ M B θ c ( 2 M g M B + θ c M g 2 ) ∥ s k p ∥ 2 ≤ M B ( σ 0 /Δ t k − M B ) θ c ( 2 M g M B + θ c M g 2 ) ∥ P k g k ∥∥ s k p ∥. (85)
We select
δ v = min { σ 0 4 M B , δ c , σ 0 M B θ v ( 2 M g M B + θ c M g 2 ) θ c + M B 2 θ v } , (86) \delta_v=\min\left\{\frac{\sigma_0}{4M_B},\delta_c,\frac{\sigma_0M_B\theta_v}{(2M_gM_B+\theta_cM_g^2)\theta_c+M_B^2\theta_v}\right\}, \tag*{(86)} δ v = min { 4 M B σ 0 , δ c , ( 2 M g M B + θ c M g 2 ) θ c + M B 2 θ v σ 0 M B θ v } , (86)
where the positive constant δ c \delta_c δ c is defined by equation (75) . Thus, from equations (85) -(86) , when Δ t k ≤ δ v \Delta t_k\leq\delta_v Δ t k ≤ δ v , we have ∣ V p r e d k ∣ ≤ θ v ∥ P k g k ∥ ∥ s k p ∥ |Vpred_k|\leq\theta_v\|P_kg_k\|\|s_k^p\| ∣ V p r e d k ∣ ≤ θ v ∥ P k g k ∥∥ s k p ∥ . We select the small positive constant δ 0 \delta_0 δ 0 to satisfy δ 0 ≤ δ v \delta_0\leq\delta_v δ 0 ≤ δ v . Then, by combining equation (82) , when δ 0 ≤ Δ t k ≤ δ v \delta_0\leq\Delta t_k\leq\delta_v δ 0 ≤ Δ t k ≤ δ v and ϵ 0 ≤ δ ϵ 0 \epsilon_0\leq\delta_{\epsilon_0} ϵ 0 ≤ δ ϵ 0 , we obtain the result (76) . □ \square □
In order to prove that p g k p_{g_k} p g k converges to zero when k k k tends to infinity, we need to estimate the lower bound of time step sizes Δ t k \Delta t_k Δ t k (k = 1 , 2 , … k=1,2,\ldots k = 1 , 2 , … ). By using Lemma 2, Lemma 3 and Lemma 4, we can obtain the lower bound of time step sizes Δ t k \Delta t_k Δ t k (k = 1 , 2 , … k=1,2,\ldots k = 1 , 2 , … ) as follows.
Lemma 5 Assume that f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R is twice continuously differentiable and ∇ f ( x ) \nabla f(x) ∇ f ( x ) is Lipschitz continuous. Namely, there exists a positive constant L g L_g L g such that
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L g ∥ x − y ∥ , ∀ x , y ∈ R n . (89) \|\nabla f(x)-\nabla f(y)\|\leq L_g\|x-y\|,\quad\forall x,y\in\mathbb{R}^n. \tag*{(89)} ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L g ∥ x − y ∥ , ∀ x , y ∈ R n . (89) Assume that c ( x ) c(x) c ( x ) is continuously differentiable and its Jacobian matrix A ( x ) A(x) A ( x ) satisfies the Lipschitz continuity (66) . We suppose that the sequence { x k } \{x_k\} { x k } is generated by Algorithm 2 and Assumption 1 holds. Furthermore, we assume
∥ P k g k ∥ > ϵ (90) \|P_kg_k\|>\epsilon \tag*{(90)} ∥ P k g k ∥ > ϵ (90)
holds for all k = 0 , 1 , 2 , … k = 0, 1, 2, \ldots k = 0 , 1 , 2 , … , where g k = g ( x k ) = ∇ f ( x k ) g_k = g(x_k) = \nabla f(x_k) g k = g ( x k ) = ∇ f ( x k ) , P k = P ( x k ) P_k = P(x_k) P k = P ( x k ) and the projection matrix P ( x ) P(x) P ( x ) is defined by equation (10) . Then, it exists a positive constant δ Δ t \delta_{\Delta t} δ Δ t such that
Δ t k ≥ γ 2 δ Δ t > 0 , k = 0 , 1 , 2 , … , (91) \Delta t_k \ge\gamma_2\delta_{\Delta t} > 0,\quad k = 0, 1, 2, \ldots, \tag*{(91)} Δ t k ≥ γ 2 δ Δ t > 0 , k = 0 , 1 , 2 , … , (91)
where Δ t k \Delta t_k Δ t k is adaptively adjusted by the trust-region updating strategy (27) -(29) .
Proof. According to Lemma 3, by induction, when δ 0 ≤ Δ t k ≤ δ v \delta_0 \le\Delta t_k \le\delta_v δ 0 ≤ Δ t k ≤ δ v and 0 < ϵ 0 ≤ δ ϵ 0 0 < \epsilon_0 \le\delta_{\epsilon_0} 0 < ϵ 0 ≤ δ ϵ 0 , we have
∥ c ( x k ) ∥ ≤ ϵ 0 , k = 0 , 1 , 2 , … , (92) \lVert c(x_k)\rVert\le\epsilon_0,\quad k = 0, 1, 2, \ldots, \tag*{(92)} ∥ c ( x k )∥ ≤ ϵ 0 , k = 0 , 1 , 2 , … , (92)
where δ ϵ 0 \delta_{\epsilon_0} δ ϵ 0 is defined by equation (81) and δ v \delta_v δ v is defined by equation (86) .
From equation (11) , we know ∥ P k ∥ = 1 \lVert P_k\rVert= 1 ∥ P k ∥ = 1 . By using this property and the assumption (63) , we have
∣ μ min ( B k − P k T B k P k ) ∣ ≤ ∥ B k − P k T B k P k ∥ ≤ ∥ B k ∥ + ∥ P k T ∥ ∥ B k ∥ ∥ P k ∥ = 2 ∥ B k ∥ ≤ 2 M B , k = 0 , 1 , 2 , … , (93) \begin{aligned}
\left|\mu_{\min}\left(B_k-P_k^T B_kP_k\right)\right| \le\left\lVert B_k-P_k^T B_kP_k\right\rVert\\
&\le\lVert B_k\rVert+\lVert P_k^T\rVert\lVert B_k\rVert\lVert P_k\rVert= 2\lVert B_k\rVert\le2M_B,\quad k = 0, 1, 2, \ldots, \tag*{(93)}
\end{aligned} μ m i n ( B k − P k T B k P k ) ≤ B k − P k T B k P k ≤ ∥ B k ∥ + ∥ P k T ∥ ∥ B k ∥ ∥ P k ∥ = 2 ∥ B k ∥ ≤ 2 M B , k = 0 , 1 , 2 , … , (93)
where μ min ( B ) \mu_{\min}(B) μ m i n ( B ) represents the smallest eigenvalue of matrix B B B . Thus, from equation (93) , we obtain
μ min ( σ 0 Δ t k I + B k − P k T B k P k ) = σ 0 Δ t k + μ min ( B k − P k T B k P k ) ≥ σ 0 Δ t k − 2 M B , k = 0 , 1 , 2 , … (94) \begin{aligned}
\mu_{\min}\left(\frac{\sigma_0}{\Delta t_k}I+B_k-P_k^T B_kP_k\right)
= \frac{\sigma_0}{\Delta t_k}+\mu_{\min}\left(B_k-P_k^T B_kP_k\right) \\
&\ge\frac{\sigma_0}{\Delta t_k}-2M_B,\quad k = 0, 1, 2, \ldots \tag*{(94)}
\end{aligned} μ m i n ( Δ t k σ 0 I + B k − P k T B k P k ) = Δ t k σ 0 + μ m i n ( B k − P k T B k P k ) ≥ Δ t k σ 0 − 2 M B , k = 0 , 1 , 2 , … (94)
Similarly, from the assumption (63) , we have
μ min ( σ 0 Δ t k I + B k ) = σ 0 Δ t k + μ min ( B k ) ≥ σ 0 Δ t k − M B , k = 0 , 1 , 2 , … (95) \mu_{\min}\left(\frac{\sigma_0}{\Delta t_k}I+B_k\right)
= \frac{\sigma_0}{\Delta t_k}+\mu_{\min}(B_k)
\ge\frac{\sigma_0}{\Delta t_k}-M_B,\quad k = 0, 1, 2, \ldots \tag*{(95)} μ m i n ( Δ t k σ 0 I + B k ) = Δ t k σ 0 + μ m i n ( B k ) ≥ Δ t k σ 0 − M B , k = 0 , 1 , 2 , … (95)
Therefore, the positive definite conditions of equation (44) are satisfied when Δ t k ≤ σ 0 / ( 2 M B ) \Delta t_k \le\sigma_0/(2M_B) Δ t k ≤ σ 0 / ( 2 M B ) (k = 1 , 2 , … k = 1, 2, \ldots k = 1 , 2 , … ).
From the Lipschitz continuity (89) of ∇ f ( x ) \nabla f(x) ∇ f ( x ) and the Cauchy-Schwartz inequality ∣ x T y ∣ ≤ ∥ x ∥ ∥ y ∥ \lvert x^T y\rvert\le\lVert x\rVert\lVert y\rVert ∣ x T y ∣ ≤ ∥ x ∥ ∥ y ∥ , we have
∣ ∫ 0 1 ( ∇ f ( x k + t s k ) − ∇ f ( x k ) ) T s k d t ∣ ≤ ∫ 0 1 ∥ ∇ f ( x k + t s k ) − ∇ f ( x k ) ∥ ∥ s k ∥ d t ≤ ∫ 0 1 L g ∥ s k ∥ 2 t d t = 1 2 L g ∥ s k ∥ 2 = 1 2 L g ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 ≤ 1 2 L g ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 . (96) \begin{aligned}
\left\lvert\int_0^1\left(\nabla f(x_k+ts_k)-\nabla f(x_k)\right)^Ts_k\,dt\right\rvert
\le\int_0^1\lVert\nabla f(x_k+ts_k)-\nabla f(x_k)\rVert\lVert s_k\rVert\,dt \\
&\le\int_0^1 L_g\lVert s_k\rVert^2t\,dt
= \frac{1}{2}L_g\lVert s_k\rVert^2
= \frac{1}{2}L_g\left(\lVert s_k^p\rVert+\lVert s_k^c\rVert\right)^2
\le\frac{1}{2}L_g\left(\lVert s_k^p\rVert+\lVert s_k^c\rVert\right)^2. \tag*{(96)}
\end{aligned} ∫ 0 1 ( ∇ f ( x k + t s k ) − ∇ f ( x k ) ) T s k d t ≤ ∫ 0 1 ∥ ∇ f ( x k + t s k ) − ∇ f ( x k )∥ ∥ s k ∥ d t ≤ ∫ 0 1 L g ∥ s k ∥ 2 t d t = 2 1 L g ∥ s k ∥ 2 = 2 1 L g ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 ≤ 2 1 L g ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 . (96)
By substituting equation (76) and equation (83) into equation (96) , when δ 0 ≤ Δ t k ≤ δ v \delta_0 \le\Delta t_k \le\delta_v δ 0 ≤ Δ t k ≤ δ v and 0 < ϵ 0 ≤ δ ϵ 0 0 < \epsilon_0 \le\delta_{\epsilon_0} 0 < ϵ 0 ≤ δ ϵ 0 , we obtain
∣ ∫ 0 1 ( ∇ f ( x k + t s k ) − ∇ f ( x k ) ) T s k d t ∣ ≤ 1 2 L g ( ∥ s k p ∥ + θ c ∥ s k p ∥ 2 ) 2 ≤ 1 2 L g ( 1 + θ c M g M B ) 2 ∥ s k p ∥ 2 , (97) \begin{aligned}
\left\lvert\int_0^1\left(\nabla f(x_k+ts_k)-\nabla f(x_k)\right)^Ts_k\,dt\right\rvert
\le\frac{1}{2}L_g\left(\lVert s_k^p\rVert+\theta_c\lVert s_k^p\rVert^2\right)^2 \\
&\le\frac{1}{2}L_g\left(1+\frac{\theta_cM_g}{M_B}\right)^2\lVert s_k^p\rVert^2, \tag*{(97)}
\end{aligned} ∫ 0 1 ( ∇ f ( x k + t s k ) − ∇ f ( x k ) ) T s k d t ≤ 2 1 L g ( ∥ s k p ∥ + θ c ∥ s k p ∥ 2 ) 2 ≤ 2 1 L g ( 1 + M B θ c M g ) 2 ∥ s k p ∥ 2 , (97)
and
1 2 ∣ s k T B k s k ∣ ≤ 1 2 ∥ B k ∥ ∥ s k ∥ 2 ≤ 1 2 M B ∥ s k p + s k c ∥ 2 ≤ 1 2 M B ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 ≤ 1 2 M B ( ∥ s k p ∥ + θ c ∥ s k p ∥ 2 ) 2 = 1 2 M B ( 1 + θ c ∥ s k p ∥ ) 2 ∥ s k p ∥ 2 ≤ 1 2 M B ( 1 + θ c M g M B ) 2 ∥ s k p ∥ 2 . (98) \begin{aligned}
\frac{1}{2}\lvert s_k^T B_k s_k\rvert\le\frac{1}{2}\lVert B_k\rVert\lVert s_k\rVert^2 \le\frac{1}{2}M_B\lVert s_k^p+s_k^c\rVert^2 \le\frac{1}{2}M_B\left(\lVert s_k^p\rVert+\lVert s_k^c\rVert\right)^2 \\
&\le\frac{1}{2}M_B\left(\lVert s_k^p\rVert+\theta_c\lVert s_k^p\rVert^2\right)^2 = \frac{1}{2}M_B\left(1+\theta_c\lVert s_k^p\rVert\right)^2\lVert s_k^p\rVert^2 \\
&\le\frac{1}{2}M_B\left(1+\theta_c\frac{M_g}{M_B}\right)^2\lVert s_k^p\rVert^2. \tag*{(98)}
\end{aligned} 2 1 ∣ s k T B k s k ∣ ≤ 2 1 ∥ B k ∥ ∥ s k ∥ 2 ≤ 2 1 M B ∥ s k p + s k c ∥ 2 ≤ 2 1 M B ( ∥ s k p ∥ + ∥ s k c ∥ ) 2 ≤ 2 1 M B ( ∥ s k p ∥ + θ c ∥ s k p ∥ 2 ) 2 = 2 1 M B ( 1 + θ c ∥ s k p ∥ ) 2 ∥ s k p ∥ 2 ≤ 2 1 M B ( 1 + θ c M B M g ) 2 ∥ s k p ∥ 2 . (98)
From the first-order Taylor expansion of f ( x k + s k ) f(x_k+s_k) f ( x k + s k ) and equation (97) , we have
∣ f ( x k ) − f ( x k + s k ) + ∇ f ( x k ) T s k ∣ = ∣ ∇ f ( x k ) T s k − ∫ 0 1 ∇ f ( x k + t s k ) T s k d t ∣ = ∣ ∫ 0 1 ( ∇ f ( x k ) − ∇ f ( x k + t s k ) ) T s k d t ∣ ≤ 1 2 L g ( 1 + θ c M g M B ) 2 ∥ s k p ∥ 2 . (99) \begin{aligned}
\left\lvert f(x_k)-f(x_k+s_k)+\nabla f(x_k)^T s_k\right\rvert= \left\lvert\nabla f(x_k)^T s_k-\int_0^1\nabla f(x_k+ts_k)^T s_k\,dt\right\rvert\\
&= \left\lvert\int_0^1\left(\nabla f(x_k)-\nabla f(x_k+ts_k)\right)^T s_k\,dt\right\rvert\le\frac{1}{2}L_g\left(1+\frac{\theta_cM_g}{M_B}\right)^2\lVert s_k^p\rVert^2. \tag*{(99)}
\end{aligned} f ( x k ) − f ( x k + s k ) + ∇ f ( x k ) T s k = ∇ f ( x k ) T s k − ∫ 0 1 ∇ f ( x k + t s k ) T s k d t = ∫ 0 1 ( ∇ f ( x k ) − ∇ f ( x k + t s k ) ) T s k d t ≤ 2 1 L g ( 1 + M B θ c M g ) 2 ∥ s k p ∥ 2 . (99)
From equation (57) and equation (76) , we have
q k ( 0 ) − q k ( s k ) = ( q k ( 0 ) − q k ( s k p ) ) − ( q k ( s k p ) − q k ( s k p + s k c ) ) ≥ 1 2 ∥ P k g k ∥ ∥ s k p ∥ − θ v ∥ P k g k ∥ ∥ s k p ∥ = ( 0.5 − θ v ) ∥ P k g k ∥ ∥ s k p ∥ . (100) \begin{aligned}
q_k(0)-q_k(s_k)=\left(q_k(0)-q_k(s_k^p)\right)-\left(q_k(s_k^p)-q_k(s_k^p+s_k^c)\right) \\
&\ge\frac{1}{2}\lVert P_kg_k\rVert\lVert s_k^p\rVert-\theta_v\lVert P_kg_k\rVert\lVert s_k^p\rVert=(0.5-\theta_v)\lVert P_kg_k\rVert\lVert s_k^p\rVert. \tag*{(100)}
\end{aligned} q k ( 0 ) − q k ( s k ) = ( q k ( 0 ) − q k ( s k p ) ) − ( q k ( s k p ) − q k ( s k p + s k c ) ) ≥ 2 1 ∥ P k g k ∥ ∥ s k p ∥ − θ v ∥ P k g k ∥ ∥ s k p ∥ = ( 0.5 − θ v ) ∥ P k g k ∥ ∥ s k p ∥ . (100)
Thus, from equations (24) , (27) , (57) , (76) and (98)–(100), when δ 0 ≤ Δ t k ≤ δ v \delta_0\le\Delta t_k\le\delta_v δ 0 ≤ Δ t k ≤ δ v and 0 < ϵ 0 ≤ ϵ δ 0 0<\epsilon_0\le\epsilon_{\delta_0} 0 < ϵ 0 ≤ ϵ δ 0 , we have
∣ ρ k − 1 ∣ = ∣ ( f ( x k ) − f ( x k + s k ) ) − ( q k ( 0 ) − q k ( s k ) ) q k ( 0 ) − q k ( s k ) ∣ ≤ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 ∣ q k ( 0 ) − q k ( s k ) ∣ ≤ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 ∣ q k ( 0 ) − q k ( s k p ) ∣ − ∣ q k ( s k p ) − q k ( s k p + s k c ) ∣ ≤ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 ( 0.5 − θ v ) ∥ P k g k ∥ ∥ s k p ∥ . (101) \begin{aligned}
\lvert\rho_k-1\rvert=\left\lvert\frac{\left(f(x_k)-f(x_k+s_k)\right)-\left(q_k(0)-q_k(s_k)\right)}{q_k(0)-q_k(s_k)}\right\rvert\\
&\le\frac{0.5(L_g+M_B)\left(1+(\theta_cM_g)/M_B\right)^2\lVert s_k^p\rVert^2}{\lvert q_k(0)-q_k(s_k)\rvert} \\
&\le\frac{0.5(L_g+M_B)\left(1+(\theta_cM_g)/M_B\right)^2\lVert s_k^p\rVert^2}{\lvert q_k(0)-q_k(s_k^p)\rvert-\lvert q_k(s_k^p)-q_k(s_k^p+s_k^c)\rvert} \\
&\le\frac{0.5(L_g+M_B)\left(1+(\theta_cM_g)/M_B\right)^2\lVert s_k^p\rVert^2}{(0.5-\theta_v)\lVert P_kg_k\rVert\lVert s_k^p\rVert}. \tag*{(101)}
\end{aligned} ∣ ρ k − 1 ∣ = q k ( 0 ) − q k ( s k ) ( f ( x k ) − f ( x k + s k ) ) − ( q k ( 0 ) − q k ( s k ) ) ≤ ∣ q k ( 0 ) − q k ( s k )∣ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 ≤ ∣ q k ( 0 ) − q k ( s k p )∣ − ∣ q k ( s k p ) − q k ( s k p + s k c )∣ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 ≤ ( 0.5 − θ v ) ∥ P k g k ∥ ∥ s k p ∥ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ∥ s k p ∥ 2 . (101)
By substituting equation (83) into equation (101) , we obtain
∣ ρ k − 1 ∣ ≤ 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 ( 0.5 − θ v ) ( σ 0 / Δ t k − M B ) . (102) \lvert\rho_k-1\rvert\le\frac{0.5(L_g+M_B)\left(1+(\theta_cM_g)/M_B\right)^2}{(0.5-\theta_v)(\sigma_0/\Delta t_k-M_B)}. \tag*{(102)} ∣ ρ k − 1 ∣ ≤ ( 0.5 − θ v ) ( σ 0 /Δ t k − M B ) 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 . (102)
We denote
δ u b = ( 0.5 − θ v ) ( 1 − η 2 ) σ 0 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 + ( 0.5 − θ v ) ( 1 − η 2 ) M B , \delta_{ub}=\frac{(0.5-\theta_v)(1-\eta_2)\sigma_0}{0.5(L_g+M_B)\left(1+(\theta_cM_g)/M_B\right)^2+(0.5-\theta_v)(1-\eta_2)M_B}, δ u b = 0.5 ( L g + M B ) ( 1 + ( θ c M g ) / M B ) 2 + ( 0.5 − θ v ) ( 1 − η 2 ) M B ( 0.5 − θ v ) ( 1 − η 2 ) σ 0 ,
δ Δ t ≜ min { δ u b , σ 0 4 M B , δ v , Δ t 0 } . (103) \delta_{\Delta t}\triangleq\min\left\{\delta_{ub},\frac{\sigma_0}{4M_B},\delta_v,\Delta t_0\right\}. \tag*{(103)} δ Δ t ≜ min { δ u b , 4 M B σ 0 , δ v , Δ t 0 } . (103)
Thus, from equations (102) –(103) , when δ 0 ≤ Δ t k ≤ δ Δ t \delta_0 \le\Delta t_k \le\delta_{\Delta t} δ 0 ≤ Δ t k ≤ δ Δ t , we have ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 . We select δ 0 ≤ γ 2 δ Δ t \delta_0 \le\gamma_2\delta_{\Delta t} δ 0 ≤ γ 2 δ Δ t . We assume that K K K is the first index such that Δ t K ≤ δ Δ t \Delta t_K \le\delta_{\Delta t} Δ t K ≤ δ Δ t . Then, from equations (102) –(103) , we know that ρ K ≥ η 2 \rho_K \ge\eta_2 ρ K ≥ η 2 . According to the time-stepping adjustment formula (29) and Lemma 3, when 0 < ε 0 ≤ δ ε 0 0 < \varepsilon_0 \le\delta_{\varepsilon_0} 0 < ε 0 ≤ δ ε 0 , x K + s K x_K+s_K x K + s K will be accepted and the time step Δ t K + 1 \Delta t_{K+1} Δ t K + 1 will be enlarged. Consequently, Δ t k ≥ γ 2 δ Δ t \Delta t_k \ge\gamma_2\delta_{\Delta t} Δ t k ≥ γ 2 δ Δ t holds for all k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … .
Remark 8 We select η q ≤ 0.5 − θ v \eta_q \le0.5-\theta_v η q ≤ 0.5 − θ v . Then, when δ 0 ≤ Δ t k ≤ δ v \delta_0 \le\Delta t_k \le\delta_v δ 0 ≤ Δ t k ≤ δ v , from equation (100) , we have
q k ( 0 ) − q k ( s k ) ≥ ( 0.5 − θ v ) ∥ P K g k ∥ ∥ s k p ∥ ≥ η q ∥ P K g k ∥ ∥ s k p ∥ . (104) q_k(0)-q_k(s_k) \ge(0.5-\theta_v)\lVert P_K g_k\rVert\lVert s_k^p\rVert\ge\eta_q\lVert P_K g_k\rVert\lVert s_k^p\rVert. \tag*{(104)} q k ( 0 ) − q k ( s k ) ≥ ( 0.5 − θ v ) ∥ P K g k ∥ ∥ s k p ∥ ≥ η q ∥ P K g k ∥ ∥ s k p ∥ . (104)
Namely, the sufficient descent condition (28) is satisfied.
By using the results of Lemma 3 and Lemma 5, we prove the global convergence of Algorithm 2 for the equality-constrained optimization problem (1) as follows.
Theorem 1 Assume that Assumption 1 holds, ∇ f ( x ) \nabla f(x) ∇ f ( x ) satisfies the Lipschitz continuity (89) , and the Jacobian matrix A ( x ) A(x) A ( x ) of c ( x ) c(x) c ( x ) satisfies the Lipschitz continuity (66) . We suppose that the sequence { x k } \{x_k\} { x k } is generated by Algorithm 2 and f ( x k ) f(x_k) f ( x k ) (k = 0 , 1 , … k=0,1,\ldots k = 0 , 1 , … ) are bounded below. Then, for any positive constant ε \varepsilon ε , we can select a sufficiently small constant ε 0 > 0 \varepsilon_0>0 ε 0 > 0 such that
∥ P K g K ∥ ≤ ε and ∥ c ( x K ) ∥ ≤ ε 0 (105) \lVert P_Kg_K\rVert\le\varepsilon\text{ and } \lVert c(x_K)\rVert\le\varepsilon_0 \tag*{(105)} ∥ P K g K ∥ ≤ ε and ∥ c ( x K )∥ ≤ ε 0 (105) hold for an index K K K when ∥ c ( x 0 ) ∥ ≤ ε 0 \lVert c(x_0)\rVert\le\varepsilon_0 ∥ c ( x 0 )∥ ≤ ε 0 .
Proof. We prove this result by contradiction. Assume that the result (105) is not true. Then, we have
∥ P k g k ∥ > ε for all k = 0 , 1 , 2 , … (106) \lVert P_kg_k\rVert> \varepsilon\text{ for all } k=0,1,2,\ldots \tag*{(106)} ∥ P k g k ∥ > ε for all k = 0 , 1 , 2 , … (106)
Thus, from Lemma 3 and Lemma 5, we can select a sufficiently small constant ε 0 > 0 \varepsilon_0>0 ε 0 > 0 and there exists an infinite subsequence { x k i } \{x_{k_i}\} { x k i } such that the trial steps s k i s_{k_i} s k i are accepted, i.e., ρ k i ≥ η a \rho_{k_i}\ge\eta_a ρ k i ≥ η a , i = 1 , 2 , … i=1,2,\ldots i = 1 , 2 , … . Otherwise, all steps are rejected after a given iteration index, then the time step will keep decreasing, which contradicts (91) . Therefore, from equation (27) , we have ∥ c ( x k i ) ∥ ≤ ε 0 \lVert c(x_{k_i})\rVert\le\varepsilon_0 ∥ c ( x k i )∥ ≤ ε 0 and
f 0 − lim k → ∞ f k = ∑ k = 0 ∞ ( f k − f k + 1 ) ≥ η a ∑ i = 0 ∞ ( q k i ( 0 ) − q k i ( s k i ) ) , (107) f_0-\lim_{k\to\infty}f_k=\sum_{k=0}^{\infty}(f_k-f_{k+1})\ge\eta_a\sum_{i=0}^{\infty}\left(q_{k_i}(0)-q_{k_i}(s_{k_i})\right), \tag*{(107)} f 0 − k → ∞ lim f k = k = 0 ∑ ∞ ( f k − f k + 1 ) ≥ η a i = 0 ∑ ∞ ( q k i ( 0 ) − q k i ( s k i ) ) , (107)
where s k i s_{k_i} s k i is computed by equation (18) and equation (22) .
Since f k = f ( x k ) f_k=f(x_k) f k = f ( x k ) (k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … ) are bounded below and the sequence { f k } \{f_k\} { f k } decreases monotonically, we know that the limit of the sequence { f ( x k ) } \{f(x_k)\} { f ( x k )} exists and we denote it as lim k → ∞ f k = f ∗ \lim_{k\to\infty}f_k=f^* lim k → ∞ f k = f ∗ . Thus, from equation (107) , we have
lim k i → ∞ ( q k i ( 0 ) − q k i ( s k i ) ) = 0. (108) \lim_{k_i\to\infty}\left(q_{k_i}(0)-q_{k_i}(s_{k_i})\right)=0. \tag*{(108)} k i → ∞ lim ( q k i ( 0 ) − q k i ( s k i ) ) = 0. (108)
By substituting equation (28) into equation (108) , we obtain
lim i → ∞ ∥ P k i g k i ∥ ∥ s k i p ∥ = 0. (109) \lim_{i\to\infty}\lVert P_{k_i}g_{k_i}\rVert\lVert s^p_{k_i}\rVert=0. \tag*{(109)} i → ∞ lim ∥ P k i g k i ∥ ∥ s k i p ∥ = 0. (109)
According to the assumption ∥ P k g k ∥ > ε > 0 \lVert P_{k}g_k\rVert>\varepsilon>0 ∥ P k g k ∥ > ε > 0 , from equation (109) , we have
lim i → ∞ ∥ s k i p ∥ = 0. (110) \lim_{i\to\infty}\lVert s^p_{k_i}\rVert=0. \tag*{(110)} i → ∞ lim ∥ s k i p ∥ = 0. (110)
From Lemma 5 , we know that it exists a positive constant δ Δ t \delta_{\Delta t} δ Δ t such that
Δ t k ≥ γ 2 δ Δ t > 0 , k = 0 , 1 , 2 , … . (111) \Delta t_k\ge\gamma_2\delta_{\Delta t}>0,\quad k=0,1,2,\ldots. \tag*{(111)} Δ t k ≥ γ 2 δ Δ t > 0 , k = 0 , 1 , 2 , … . (111)
(i) When B k i B_{k_i} B k i is updated by the BFGS quasi-Newton formula (30) , we know that B k i ≻ 0 B_{k_i}\succ0 B k i ≻ 0 . Thus, by substituting equation (111) into equation (78) , we have
∥ s k i p ∥ ≥ Δ t k i 1 + Δ t k i 1 σ 0 / Δ t k i + ∥ B k i ∥ ∥ P k i g k i ∥ ≥ γ 2 δ Δ t 1 + γ 2 δ Δ t 1 σ 0 / ( γ 2 δ Δ t ) + M B ∥ P k i g k i ∥ . (112) \begin{aligned}
\lVert s^p_{k_i}\rVert\ge\frac{\Delta t_{k_i}}{1+\Delta t_{k_i}}\frac{1}{\sigma_0/\Delta t_{k_i}+\lVert B_{k_i}\rVert}\lVert P_{k_i}g_{k_i}\rVert\\
&\ge\frac{\gamma_2\delta_{\Delta t}}{1+\gamma_2\delta_{\Delta t}}\frac{1}{\sigma_0/(\gamma_2\delta_{\Delta t})+M_B}\lVert P_{k_i}g_{k_i}\rVert. \tag*{(112)}
\end{aligned} ∥ s k i p ∥ ≥ 1 + Δ t k i Δ t k i σ 0 /Δ t k i + ∥ B k i ∥ 1 ∥ P k i g k i ∥ ≥ 1 + γ 2 δ Δ t γ 2 δ Δ t σ 0 / ( γ 2 δ Δ t ) + M B 1 ∥ P k i g k i ∥ . (112)
(ii) When B k i = P k i ∇ 2 f ( x k i ) P k i B_{k_i}=P_{k_i}\nabla^2f(x_{k_i})P_{k_i} B k i = P k i ∇ 2 f ( x k i ) P k i , from equation (18) , we have
P k i ( σ 0 Δ t k i I + P k i ∇ 2 f ( x k i ) P k i ) d k i = − P k i 2 g k i = − P k i g k i = ( σ 0 Δ t k i I + P k i ∇ 2 f ( x k i ) P k i ) d k i , \begin{aligned}
P_{k_i}\left(\frac{\sigma_0}{\Delta t_{k_i}}I+P_{k_i}\nabla^2f(x_{k_i})P_{k_i}\right)d_{k_i}=-P_{k_i}^2g_{k_i} \\
&=-P_{k_i}g_{k_i}=\left(\frac{\sigma_0}{\Delta t_{k_i}}I+P_{k_i}\nabla^2f(x_{k_i})P_{k_i}\right)d_{k_i},
\end{aligned} P k i ( Δ t k i σ 0 I + P k i ∇ 2 f ( x k i ) P k i ) d k i = − P k i 2 g k i = − P k i g k i = ( Δ t k i σ 0 I + P k i ∇ 2 f ( x k i ) P k i ) d k i ,
which gives P k i d k i = d k i P_{k_i}d_{k_i}=d_{k_i} P k i d k i = d k i . By combining it with equation (18) and equation (111) , we have
γ 2 δ Δ t 1 + γ 2 δ Δ t ∥ P k i g k i ∥ ≤ ∥ Δ t k i 1 + Δ t k i P k i g k i ∥ = ∥ Δ t k i 1 + Δ t k i ( σ 0 Δ t k i I + P k i ∇ 2 f ( x k i ) P k i ) d k i ∥ = ∥ Δ t k i 1 + Δ t k i ( σ 0 Δ t k i I + P k i ∇ 2 f ( x k i ) P k i ) P k i d k i ∥ = ∥ ( σ 0 Δ t k i I + P k i ∇ 2 f ( x k i ) P k i ) s k i p ∥ ≤ ( σ 0 Δ t k i + ∥ B k i ∥ ) ∥ s k i p ∥ ≤ ( σ 0 γ 2 δ Δ t + M B ) ∥ s k i p ∥ . (113) \begin{aligned}
\frac{\gamma_2\delta_{\Delta t}}{1+\gamma_2\delta_{\Delta t}}\lVert P_{k_i}g_{k_i}\rVert\le\left\lVert\frac{\Delta t_{k_i}}{1+\Delta t_{k_i}}P_{k_i}g_{k_i}\right\rVert\\
&=\left\lVert\frac{\Delta t_{k_i}}{1+\Delta t_{k_i}}\left(\frac{\sigma_0}{\Delta t_{k_i}}I+P_{k_i}\nabla^2f(x_{k_i})P_{k_i}\right)d_{k_i}\right\rVert\\
&=\left\lVert\frac{\Delta t_{k_i}}{1+\Delta t_{k_i}}\left(\frac{\sigma_0}{\Delta t_{k_i}}I+P_{k_i}\nabla^2f(x_{k_i})P_{k_i}\right)P_{k_i}d_{k_i}\right\rVert\\
&=\left\lVert\left(\frac{\sigma_0}{\Delta t_{k_i}}I+P_{k_i}\nabla^2f(x_{k_i})P_{k_i}\right)s^p_{k_i}\right\rVert\\
&\le\left(\frac{\sigma_0}{\Delta t_{k_i}}+\lVert B_{k_i}\rVert\right)\lVert s^p_{k_i}\rVert
\le\left(\frac{\sigma_0}{\gamma_2\delta_{\Delta t}}+M_B\right)\lVert s^p_{k_i}\rVert. \tag*{(113)}
\end{aligned} 1 + γ 2 δ Δ t γ 2 δ Δ t ∥ P k i g k i ∥ ≤ 1 + Δ t k i Δ t k i P k i g k i = 1 + Δ t k i Δ t k i ( Δ t k i σ 0 I + P k i ∇ 2 f ( x k i ) P k i ) d k i = 1 + Δ t k i Δ t k i ( Δ t k i σ 0 I + P k i ∇ 2 f ( x k i ) P k i ) P k i d k i = ( Δ t k i σ 0 I + P k i ∇ 2 f ( x k i ) P k i ) s k i p ≤ ( Δ t k i σ 0 + ∥ B k i ∥ ) ∥ s k i p ∥ ≤ ( γ 2 δ Δ t σ 0 + M B ) ∥ s k i p ∥ . (113)
By substituting equations (112) –(113) into equation (110) , we obtain
lim i → ∞ ∥ P k i g k i ∥ = 0 , (114) \lim_{i\to\infty}\lVert P_{k_i}g_{k_i}\rVert=0, \tag*{(114)} i → ∞ lim ∥ P k i g k i ∥ = 0 , (114)
which contradicts the bounded assumption (106) of P k g k P_kg_k P k g k (k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … ). Therefore, the result (105) is true. ⊓⊔
Numerical Experiments
In this section, we conduct some numerical experiments to test the performance of Algorithm 2 (the Rcm method). The codes are executed by a HP notebook with the Intel quad-core CPU and 8Gb memory in the MATLAB R2020a environment [60 ] . For a real-world problem, the analytical Hessian matrix ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇ 2 f ( x k ) may not be offered. Thus, in practice, we replace the two sided projection P ( x k ) ∇ 2 f ( x k ) P ( x k ) P(x_k)\nabla^2 f(x_k)P(x_k) P ( x k ) ∇ 2 f ( x k ) P ( x k ) of the Hessian matrix with its difference approximation as follows:
P k ∇ 2 f ( x k ) P k ≈ [ P k g ( x k + ε P k e 1 ) − P k g ( x k ) ε , … , P k g ( x k + ε P k e n ) − P k g ( x k ) ε ] (115) P_k\nabla^2 f(x_k)P_k \approx\left[\frac{P_k g(x_k+\varepsilon P_k e_1)-P_k g(x_k)}{\varepsilon},\ldots,\frac{P_k g(x_k+\varepsilon P_k e_n)-P_k g(x_k)}{\varepsilon}\right] \tag*{(115)} P k ∇ 2 f ( x k ) P k ≈ [ ε P k g ( x k + ε P k e 1 ) − P k g ( x k ) , … , ε P k g ( x k + ε P k e n ) − P k g ( x k ) ] (115)
where the elements of e i e_i e i equal zeros except for the i i i -th element which equals 1, P k = P ( x k ) P_k=P(x_k) P k = P ( x k ) and the parameter ε \varepsilon ε can be selected as 10 − 6 10^{-6} 1 0 − 6 according to our numerical experiments.
SQP [19 , 25 , 65 , 85 ] is a representative method for constrained optimization problems. And there are two representative implementation codes of the SQP method. One is the built-in subroutine fmincon.m (NLPQL) of the MATLAB2020a environment [60 , 72 ] . The other is the subroutine SNOPT [29 , 30 ] executed in GAMS v28.2 (2019) environment [23 ] . fmincon and SNOPT are two robust and efficient solvers for nonlinear equality-constrained optimization problems. Therefore, we select these two typical solvers as the basis for comparison.
We select 65 nonlinear equality-constrained optimization problems from CUTEst [26 ] and construct 60 test problems. Therefore, we use these 125 problems to test their performance of these three algorithms (Rcm, fmincon and SNOPT). For those 60 constructed test problems, we use Ackley Function [78 ] as their objective functions. Ackley Function can be written as:
f ( x ) = − a e − b 1 n ∑ i = 1 n x i 2 − e 1 n ∑ i = 1 n cos ( 2 π x i ) + a + e , (116) f(x)=-a e^{-b\sqrt{\frac{1}{n}\sum_{i=1}^{n}x_i^2}}-e^{\frac{1}{n}\sum_{i=1}^{n}\cos(2\pi x_i)}+a+e, \tag*{(116)} f ( x ) = − a e − b n 1 ∑ i = 1 n x i 2 − e n 1 ∑ i = 1 n c o s ( 2 π x i ) + a + e , (116)
where a = 20 a=20 a = 20 , b = 0.2 b=0.2 b = 0.2 , n = 2000 n=2000 n = 2000 . Then, we use the gradients of 20 unconstrained optimization problems from [1 , 61 , 78 ] [39] as their constrained functions. In order to test the performance of the method for the different dimensions of constraints, we test the problems with few constraints (m ≪ n m\ll n m ≪ n such as m = 10 m=10 m = 10 , n = 2000 n=2000 n = 2000 ), medium constraints (m ≈ 1 2 n m\approx\frac{1}{2}n m ≈ 2 1 n such as m = 1000 m=1000 m = 1000 , n = 2000 n=2000 n = 2000 ) and many constraints (m ≈ n m\approx n m ≈ n such as m = 1999 m=1999 m = 1999 , n = 2000 n=2000 n = 2000 ).
The termination conditions of three compared algorithms (Rcm, fmincon and SNOPT) are all set by
∥ ∇ x L ( x k , λ k ) ∥ ∞ ≤ 1.0 × 10 − 6 , (117) \lVert\nabla_x L(x_k,\lambda_k)\rVert_\infty\leq1.0\times10^{-6}, \tag*{(117)} ∥ ∇ x L ( x k , λ k ) ∥ ∞ ≤ 1.0 × 1 0 − 6 , (117)
∥ c ( x k ) ∥ ∞ ≤ 1.0 × 10 − 6 , k = 1 , 2 , … , (118) \lVert c(x_k)\rVert_\infty\leq1.0\times10^{-6},\quad k=1,2,\ldots, \tag*{(118)} ∥ c ( x k ) ∥ ∞ ≤ 1.0 × 1 0 − 6 , k = 1 , 2 , … , (118)
where the Lagrange function L ( x , λ ) L(x,\lambda) L ( x , λ ) is defined by equation (4) and λ \lambda λ is defined by equation (8) . We test those 100 problems with n ≈ 1000 n\approx1000 n ≈ 1000 to n = 2000 n=2000 n = 2000 . Numerical results are arranged in Table 1 -Table 6 . Numerical results of 65 constrained optimization problems from CUTEst [26 ] are arranged in Table 1 -Table 3 . And numerical results of 60 constructed constrained optimization problems are arranged in Table 4 -Table 6 . The computational time and the number of iterations of Rcm, fmincon and SNOPT are illustrated in Figure 1 -Figure 2 , respectively.
Figure 1. Iterations of Rcm, fmincon and SNOPT for test problems.
Figure 2. CPU time of Rcm, fmincon and SNOPT for test problems.
Table 1. Numerical results of Rcm, fmincon and SNOPT for CUTEst problems (Exam. 1-20).
Table 3. Numerical results of Rcm, fmincon and SNOPT for CUTEst problems (Exam. 41-65).
Table 4. Numerical results of Rcm, fmincon and SNOPT for large-scale problems with n = 2000 , m = 10 n=2000,m=10 n = 2000 , m = 10 .
Table 6. Numerical results of Rcm, fmincon and SNOPT for large-scale problems with n = 2000 n = 2000 n = 2000 , m = 1999 m = 1999 m = 1999 .
Since Algorithm 2 (Rcm) use Algorithm 1 (GCNMTr) to find an initial feasible point, we count its iterations including the iterations of GCNMTr (which are represented by i t c G itc_G i t c G ) and the self iterations of Rcm (which are represented by i t c R itc_R i t c R ) in Table 1 -Table 6 . SNOPT gives the number of solving QP subproblems (which are represented by “Major”) and uses SQOPT solver [30 ] to find a solution of the QP subproblem. SNOPT also gives the total iterations of solving QP subproblems, which are represented by “ICTS”. In order to ensure the evaluation objectivity, we count the number of solving QP subproblems and the total iterations of solving QP subproblems for SNOPT in Table 1 -Table 6 . fmincon only gives the number of solving QP subproblems and we denote them as “steps” in Table 1 -Table 6 .
In order to evaluate and compare those three methods (Rcm, fmincon and SNOPT) fairly, we also adopt the performance profile as a evaluation tool [16 ] . The performance profile for a solver is the (cumulative) distribution function for a performance metric, which is the ratio of the computing time of the solver versus the best time of all of the solvers as the performance metric. If the solver fails to solve a problem, we let its ratio be a bigger number such as 999. Figure 3 is the performance profiles for three nonlinear programming solvers (Rcm, fmincon and SNOPT). We also count the statistic number of failed problems and fasted problems computed by Rcm, fminincon and SNOPT. The statistical results are put in Table 7 .
Figure 3. Performance profile for nonlinear programming solvers.
Table 7. The number of failed problems computed by Rcm, fmincon and SNOPT.
From Table 1 -Table 6 and Table 7 , we find that Rcm can solve most of test problems and few problems (6.4%) can not be solved. However, fmincon fails to solve CUTEst problems about 28 125 \frac{28}{125} 125 28 (22.4%) and SNOPT fails to solve problems about 21 125 \frac{21}{125} 125 21 (16.8%). From Table 1 -Table 6 and Figure 2 , Figure 3 , we find that the computational time of Rcm is significantly less than that of fmincon for most of test problems. From Table 1 -Table 6 and Figure 1 , we also find that the iterations of Rcm is significantly less than that of SNOPT for most of test problems. One of reasons is that Rcm only needs to solve a linear system of equations with dimension n n n at every iteration. SQP needs to solve a linear system of equations with dimension ( m + n ) (m+n) ( m + n ) when it solves a quadratic programming subproblem at every iteration (pp. 531-532, [65 ] ) and involves about 2 3 ( m + n ) 3 \frac{2}{3}(m+n)^3 3 2 ( m + n ) 3 flops (p. 116, [27 ] ). The other reason is that Rcm uses the adaptive updating technique of the Jacobian matrix A ( x ) A(x) A ( x ) of constraints c ( x ) = 0 c(x)=0 c ( x ) = 0 when it uses Algorithm 1 (GCNMTr) to find an initial feasible point. This technique can significantly save the computational time when GCNMTr solves an under-determined system of nonlinear equations [53]. We also find that SNOPT is significantly faster than Rcm on several test cases. The reason is due to the more gain of the compiled language than that of the interpreted language, since SNOPT is written by C++ language (a compiled language), and Rcm is written by MATLAB language (an interpreted language).
Table 2. Numerical results of Rcm, fmincon and SNOPT for CUTEst problems (Exam. 21-40).
Table 5. Numerical results of Rcm, fmincon and SNOPT for large-scale problems with n = 2000 , m = 1000 n = 2000,m = 1000 n = 2000 , m = 1000 .
Conclusions
In this paper, we give the regularization continuation method with the trust-region updating strategy (Rcm) for nonlinear equality-constrained optimization problems. Namely, we use the inverse of the regularization quasi-Newton matrix as the pre-conditioner to improve its computational efficiency in the well-posed phase, and we use the inverse of the regularization two-sided projection of the Hessian matrix as the pre-conditioner to improve its robustness in the ill-conditioned phase. Since Rcm only solves a linear system of equations at every iteration and SQP needs to solve a quadratic programming subproblem at every iteration, Rcm is faster than SQP. Numerical results also show that Rcm is more robust and faster than SQP (the built-in subroutine fmincon.m of the MATLAB2020a environment [60 , 72 ] and the subroutine SNOPT [29 , 30 ] executed in GAMS v28.2 (2019) environment [23 ] ). The computational time of Rcm is about one third of that fmincon.m for the large-scale problem. Therefore, Rcm is an alternating solver for equality-constrained optimization problems and the regularization continuation method is worthy to be explored further for inequality-constrained optimization problems and the orthogonal matrix constraint problems [84 ] .
Acknowledgments
This work was supported in part by Grant 61876199 from National Natural Science Foundation of China, Grant YBWL2011085 from Huawei Technologies Co., Ltd., and Grant YJCB2011003HI from the Innovation Research Program of Huawei Technologies Co., Ltd.. The authors are grateful to two anonymous referees for their comments and suggestions which greatly improve the presentation of this paper.
Conflicts of interest / Competing interests: Not applicable.
Availability of data and material (data transparency): If it is requested, we will provide the test data.
Code availability (software application or custom code): If it is requested, we will provide the code.