A simple approximated solution method for solving fractional trust region subproblems of nonlinearly equality constrained optimization

In this paper, we consider the nonlinear equality constrained optimization problem where \(C(x)=(c_{1}(x), \ldots , c_{m}(x))^{T}\) (\(m\leq n\)) and \(f(x)\), \(c_{i}(x)\) (\(i=1,\ldots ,m\)) are continuously differentiable. The Lagrangian function for problem (1.1)–(1.2) is defined as follows: where \(\lambda _{i}\) for \(i=1,\ldots ,m\) are Lagrange multipliers. Problem (1.1)–(1.2) has been studied by many researchers, including Han [1], Powell [2], Yuan and Sun [3], Powell and Yuan [4], etc.

There are many efficient methods to solve problem (1.1)–(1.2), and the trust region method is a very effective method (see [4‐13]). In addition, the book of Conn, Gould, and Toint [14] is an excellent and comprehensive one on trust region methods. However, most of these methods use the quadratic model to approximate \(f(x)\). The sequential quadratic programming method for (1.1)–(1.2) computes a search direction by minimizing a quadratic model of the Lagrangian subject to the linearized constraints. That is, at the kth iteration, the following subproblem is solved to obtain a search direction \(s_{k}\), where \(x_{k}\) is the current iterate point, \(g_{k}=\nabla f(x_{k})\), \(B_{k}\) is symmetric and an approximation to the Hessian \(\nabla _{xx} L(x_{k}, \lambda _{k})\) of the Lagrangian of problem (1.1)–(1.2), \(A_{k}=[\nabla c_{1}(x _{k}),\ldots ,\nabla c_{m}(x_{k})]\) and \(C_{k}=C(x_{k})\). The constraint gradients \(\nabla c_{i}(x_{k})\) are assumed to be linearly independent for all \(x_{k}\). However, if the objective function possesses high nonlinear property and the iterative point is far away from the minimum, the quadratic model could not approximate the original problem very well, which may lead to iteration proceeding slowly.

In 1980, Davidon [15] first proposed the collinear scaling of variables and conic model method for unconstrained optimization. The conic model is where \(a_{k}\in R^{n}\) is a horizontal vector. Then, Sorensen [16] published detailed results on a class of conic model methods and proved that a particular member of this class has the Q-superlinear convergence. Many other scholars have also studied the trust region algorithm of the conic model (see [17, 18]).

The trial step of a trust region algorithm is usually obtained by solving a trust region subproblem. In our trust region subproblem, the trust region bound constraint is where \(\Delta _{k}\) is the trust region radius at the kth iteration. It is easy to see that there is a possibility that the linearized constraints (1.5) may have no solutions in the trust region (1.7). To overcome this difficulty, we use a relaxed version of the linearized constraint, which was proposed by Byrd, Schnabel, and Schultz in [19]. In [20], Sun also used this relaxed version of the linearized constraint and proposed a conic trust region method for nonlinearly constrained optimization. That is, at the kth iteration, the trial step \(s_{k}\) is computed by solving the following conic model trust region subproblem: where \(\|\cdot \|\) refers to the Euclidean norm and \(\theta _{k}\) is a relaxation parameter. \(\theta _{k}\in (0,1]\) is chosen such that the feasible set of (1.9) and (1.10) is not empty. Geometrically speaking, the role of \(\theta _{k}\) is to compress the feasible area of each constraints of (1.5) to the direction of origin (see [8, 21]).

The above conic model (1.8) has only one parameter \(a_{k}\) and less degree of freedom, which affects the effect of the model approaching the objective function. Therefore, we consider selecting a fractional model with more parameters, which can make full use of the function and gradient information in the previous iteration and can approximate the original function well, thus obtaining a new method for solving the optimization problem. In [22], Zhu considered the unconstrained optimization problem and proposed a fractional model where and horizontal vectors \(a_{k}, b_{k}, c_{k}\in R^{n}\) are bounded. The gradient of \(\psi _{k} (s)\) is where If \(b_{k}=c_{k}=0\), then \(\psi _{k} (s)\) is reduced to the conic model. If \(a_{k}=b_{k}=c_{k}=0\), then \(\psi _{k}(s)\) is the quadratic model \(\varrho _{k} (s)\). The fractional model is new and it is an extension to conic model \(\phi _{k} (s)\). It has more choice of parameter vectors and can make use of their function and gradient information. Based the new fractional model \(\psi _{k} (s)\), a simplified fractional trust region subproblem is proposed, where and the parameters \(a_{k}\), \(b_{k}\), \(c_{k}\) were chosen such that Subproblem (1.16)–(1.17) is solved only in quasi-Newton direction in [22]. Based on this, we study in depth the Newton point and the steepest descent point of the fractional trust region subproblem, so as to construct a simple dogleg method to solve the subproblem (see [23]). Numerical experiments show that the fractional model trust region quasi-Newton algorithm seems to be superior to the conic model trust region algorithm in terms of the number of iterations and the running time as the dimension of the optimization problem increases. For the linear equality constrained optimization problem, the null space technique is used to delete the linear equality constraint, and the fractional trust region method for solving the linear equality constrained optimization problem is proposed (see [24]).

Now we use the fractional model to solve nonlinearly constrained optimization problems. In order to solve problem (1.1)–(1.2), we consider the following fractional trust region subproblem. That is, if the current iteration point is \(x_{k}\), then the trial step \(s_{k}\) is computed by where \(\varepsilon _{0}\in (0,1)\). The purpose of adding constraint (1.23) is to guarantee that the objective function \(\psi _{k} (s)\) is bounded in the trust region and this also increases the difficulty of calculation.

We know that the exact solution of the trust region subproblem is often difficult to obtain, so many approximate solution methods have been spawned. For example, the trust region method is often combined with dogleg method, conjugate gradient method, inexact line search method, alternate direction search method, and other methods to obtain approximate solutions of trust region subproblems. In this paper, we also consider an approximate solution method for the subproblem of the trust region. First, the null space technique is used to remove the linear equality constraints of the trust region subproblem; then the fractional model of the subproblem is reduced to a quadratic model by cyclically fixing the coefficient part; finally, the problem can be easily solved by searching in the descending direction to obtain an approximate solution to the subproblem.

In the global algorithm, we propose a quasi-Newton trust region method with a fractional model and prove the global convergence of the new algorithm. The numerical experiment shows that the new algorithm is effective and robust, especially for large-scale test problems.

The organization of this paper is as follows. In Sect. 2, the fractional trust region subproblem and an algorithm for solving the subproblem are presented. In Sect. 3, we propose a quasi-Newton method with a fractional model for nonlinearly equality constrained optimization and prove its convergence under some reasonable conditions. Numerical results are given in Sect. 4.

Throughout this paper, we use \(\|\cdot \|\) for the 2-norm.

In order to solve (1.21)–(1.24), firstly we consider removing constraint (1.23) by the same process of simplification as in [22]. Therefore, when the parameters \(a_{k}\), \(b _{k}\), \(c_{k}\) satisfy (1.20) where then subproblem (1.21)–(1.24) can be rewritten as the following reduced subproblem: where \(\tilde{\Delta }_{k} \) is defined as (1.18).

The null-space technique (see [20, 25, 26]) is an important technique for solving optimization problems with equality constraints. In the following, we show the method to eliminate constraint (1.22). Assume that \(A_{k}\) has full column rank, and there exist an orthogonal matrix \(Q_{k}\) and a nonsingular upper triangular matrix \(R_{k}\) such that where \(Q_{k}^{(1)}\in R^{n\times m}\), \(Q_{k}^{(2)}\in R^{n\times (n-m)}\), and \(R^{(1)}_{k} \in R^{m \times m}\). Then (1.22) can be rewritten as Therefore the feasible point for (1.22) can be presented by for any \(u \in R^{n-m}\), where and \(Q_{k}^{(2)} u\) lies in the null space of \(A_{k}\). We denote then In order to ensure that s lies in the trust region, we choose \(\theta _{k}\) such that the norm of \(\tilde{s}_{k}\) is at most \(\iota \tilde{\Delta }_{k}\), where \(\iota \in (0,1)\) is a given constant. That is, Define Then the fractional trust region subproblem (2.2)–(2.4) becomes where \(s(u)=\tilde{s}_{k}+ Q_{k}^{(2)} u\).

Therefore, if \(u_{\ast }\) is the solution of (2.13)–(2.14), then \(s_{\ast } = \tilde{s}_{k}+ Q_{k} ^{(2)} u_{\ast }\) is the solution of (2.2)–(2.4), whereas if \(s_{\ast }\) is the solution of (2.2)–(2.4), then \(u_{\ast } = (Q_{k}^{(2)})^{T}(s_{\ast }-\tilde{s}_{k})\) is the solution of (2.13)–(2.14).

In order to solve subproblem (2.13)–(2.14) by a simple method, we first fix the fractional part of \(\tilde{\psi }_{k} (u)\) by letting \(u=0\) in \(h_{k} (s(u))\). At the same time, we set \(u= - \tau \nabla \tilde{\psi }_{k} (0)\), where \(\tau >0\), \(\nabla \tilde{\psi }_{k} (0)\neq 0\). By direct computation, we know that \(\nabla \tilde{\psi }_{k} (0)= (Q_{k}^{(2)})^{T} \nabla \psi _{k} ( \tilde{s}_{k})\), where \(\nabla \psi _{k} (s)\) is defined by (1.13). Then from (2.7) we have that (2.13)–(2.14) reduce to the following simplified subproblem: where and Combining with (1.17)–(1.20) and (2.11), we can obtain that \(\|\tilde{s}_{k}\| \leq \tilde{\Delta }_{k}\) and where From (1.19), it is obvious that \(0<\zeta _{1}<1\) and \(\zeta _{2}>1\). From lines 2 and 3 before (2.15), we know that \((Q_{k}^{(2)})^{T} \nabla \psi _{k}(\tilde{s}_{k})\neq 0\), where \(Q_{k}^{(2)}\) is defined in (2.5). For \(Q_{k}^{(2)}\in R ^{n\times (n-m)}\), \(\nabla \psi _{k} (\tilde{s}_{k})\in R^{n}\), then \(Q_{k}^{(2)}(Q_{k}^{(2)})^{T}\nabla \psi _{k} (\tilde{s}_{k})\in R^{n}\) and \(Q_{k}^{(2)}(Q_{k}^{(2)})^{T}\nabla \psi _{k} (\tilde{s}_{k}) \neq 0\) can be proved easily. Assume that \(B_{k}\) is a symmetric positive definite matrix, then combining with (2.20), (2.24), and (2.25) we have When \(B_{k}\) is only symmetric but not positive definite matrix, then the modified BFGS formula can be used to modify the positive semi-definite matrix to a positive definite matrix (see [25]). Hence, it is easy to see that the solution of (2.15)–(2.16) is where We know that \(u^{(1)} =-\tau ^{(1)}\nabla \tilde{\psi }_{k} (0)\) is an approximate solution of (2.13)–(2.14). In order to better approximate the solution of the subproblem, we are constantly repeating the above process similarly, except for fixing the fractional part. That is, in the ith iteration we substitute \(u=-\tau ^{(i)}\nabla \tilde{\psi }_{k} (0)\) into \(h_{k} (s(u))\), where \(i=2,3,\ldots \) . We denote Then we can obtain a similar trust-region subproblem to (2.15)–(2.16). That is, where By the computation, we have the solution of subproblem (2.30)–(2.31) as follows: where However, if \(\tau ^{(i)}= 0\), then subproblem (2.30)–(2.31) has no positive real roots. For this case, we set \(b_{k} = c_{k}= 0\), and then the fractional model reduces to the conic model. Subproblem (1.21)–(1.24) can be solved by Algorithm 2.4 in [26]. That is, we calculate where Z is an orthonormal rotation matrix and satisfies \(Z\bar{a}= \|\bar{a}e_{1}\|\), and \(e_{1}=(1,0,\ldots,0)^{T}\). Then the solution of (2.13)–(2.14) is where \(d^{\ast }\) is the solution of the quadratic trust region subproblem

Now we give an algorithm for solving the fractional trust region subproblems (2.13)–(2.14).

From the above analysis, we know that the steepest descent point \(u_{\ast } \) is an approximate solution of the fractional trust region subproblem (2.13)–(2.14).

In this section, we propose a quasi-Newton method with a fractional model for nonlinearly equality constrained optimization and prove its convergence under some reasonable conditions. In order to solve problem (1.1)–(1.2), we approximate \(f(x)\) with a fractional model of the form where \(f_{k}=f(x_{k})\), \(g_{k}=\nabla f(x_{k})\), \(B_{k}\in R^{n\times n}\) is a positive definite matrix, and \(a_{k}, b_{k}, c_{k}\in R^{n}\) are parameter vectors. We choose these vectors such that (3.1) satisfies the following conditions: where \(x_{k}=x_{k-1}+s_{k-1}\). Obviously, (3.2) holds. Then from (3.3) we have

where \(v_{k-1} = (1-a_{k}^{T} s_{k-1})(1-b_{k}^{T} s_{k-1})\) and

We choose where \(k_{1}\), \(k_{2}\), \(k_{3}\) are unknown parameters, and details of the choice of parameters \(k_{1}\), \(k_{2}\), \(k_{3}\) can be found in [24].

The merit function we applied is the \(L_{1}\) exact penalty function where \(\sigma >0\) is a penalty parameter. We know that, for σ sufficiently large, any strong local minimizer of (1.1)–(1.2) is a local minimizer of \(P(x)\) (see [27]). It is found that this function is very convenient to be used as a merit function to force global convergence in line search type algorithms (for example, see [1]). We define the actual reduction in the merit function by where \(s_{k}\) is a trial step computed by the algorithm at \(x_{k}\). The above choice of actual reduction is used to prove the global convergence of the algorithm conveniently. Correspondingly, the predicted reduction is defined as where \(\psi _{k} (s)\) is defined as (1.11). If we set the penalty parameter otherwise, Then holds for all k.

In the following algorithm, we compute the ratio of the actual reduction and the predicted reduction to choose the next iterate point and update the new trust region. Now we give the new quasi-Newton algorithm based on the fractional model (3.1).

In the following, we establish the convergence results of Algorithm 3.1. The focus of this paper is to transform the fractional model trust region subproblem of the equality constrained optimization model into a simple one-dimensional quadratic model subproblem by cyclically fixing the fractional coefficient part of the model, so as to obtain a new approximate solution method for solving the subproblem. Therefore, the framework of the global convergence proof is similar to the proof process of the conic model trust region algorithm in [20], with a major difference being the lower bound of reduction in each iteration (see Lemma 3.1), which is an important result required in the proof of convergence.

The proofs of the following Theorems 3.1–3.2 are similar to those in [20], so we only give the conclusion and omit the proofs.

From Theorems 3.1 and 3.3, we know that there exists a subsequence of \(\{x_{k}\}\) produced by Algorithm 3.1 converging to the KT point of (1.1)–(1.2).

In this section, Algorithm 3.1 (abbreviated as FTR) is tested with some test problems, where eight problems are directly chosen from [28, 29] and are listed in Table 1.

Moreover, in order to test Algorithm 3.1 more generally, we designed three problems (Problems 9–11) where Problems 10–11 are chosen from [30, 31] and the nonlinear equality constraints are polynomials (see [26]).

Our fractional model is proposed on the basis of the conic model, and it is a generalized form of the conic model. Both of them are suitable for solving the optimization problem that the objective function is non-quadratic and the curvature changes severely. At this time, the quadratic model methods often produce a poor prediction of the minimizer of the function. In order to compare the calculation results of the fractional model and the conic model, we let \(b_{k}=c_{k}=0\) in Algorithm 3.1. Then we can obtain the conic model algorithm and call this algorithm CTR. Therefore, we solve these test problems by FTR and CTR respectively and compare their results.

All the computations are carried out in Matlab R2013b on a microcomputer in double precision arithmetic. These tests use the same stopping criterion \(\| (Q_{k}^{(2)} )^{T} g_{k} \|\leq \varepsilon \) and \(\| C_{k} \|\leq \varepsilon \). If the stoping criterion is not satisfied with \(\text{Iter} \leq 5000\), then the test is terminated. We mark these by an ∗ in such tables. The columns in the tables have the following meanings: Pro denotes the number of the test problems; n is the dimension of the test problems, Iter is the number of iterations; nf and ng are the numbers of function and gradient evaluations respectively; Qg is the value of Euclidean norm \(\|(Q_{k}^{(2)} )^{T} g_{k}\|\) at the final iteration; CPU(s) denotes the total iteration time of the algorithm in seconds.

The parameters in these algorithms are as follows:

The numerical comparison for 11 test problems is listed in Table 2. Because of the difference in the initial iteration point, we actually performed 19 experiments. In terms of the number of iterations, our algorithm FTR may be somewhat superior to CTR for 17 tests, and the two algorithms are the same in efficiency for the other 2 tests. Because FTR needs some extra algebra computation for some parameters, FTR takes more time than CTR.

We know that large-scale problems with 10,000 or more dimensions can be tested for unconstrained optimization problems. But when the test problem contains nonlinear equality constraints, the difficulty of solving the problem is greatly increased. Therefore, the dimensions of the nonlinear equality constraint problems are limited. From Table 3, we can see that as the dimensions of each test problem range from 25 to 400, we have computed nine numerical comparisons experiments for three test questions. It can be found that our algorithm can get the minimum value of the function after a finite number of iterations, but the algorithm CTR can not, and some test problem algorithms failed. The number of iterations of FTR is less than that of CTR. That is, with the increase of the dimension of the problem, our algorithm FTR can be superior to CTR both in iteration number and algorithm stability.

The fractional model in Algorithm 3.1 is the extension of a conic model. By using more information of function and gradient from the previous iterations and choosing parameters flexibly, the fractional model can be more approximate to the original problem. When solving the trust region subproblem, we reduce the fractional model of the subproblem to a quadratic model by cycling the fixed coefficient part, and iteratively search in the descending direction to obtain the approximate solution of the subproblem. Solving of the subproblems is creative and the algorithm is simple. The theoretical and numerical results show that the method is effective and robust.