We are concerned with the solution of the bound constrained minimization problem {minf(x), l≤x≤u}. For the solution of this problem we propose an active set method that combines ideas from projected and nonmonotone Newton-type methods. It is based on an iteration of the form x k+1=[x k +α k d k ]♯, where α k is the steplength, d k is the search direction and [⋅]♯ is the projection operator on the set [l,u]. At each iteration a new formula to estimate the active set is first employed. Then the components dNkd_{N}^{k} of d k corresponding to the free variables are determined by a truncated Newton method, and the components dAkd_{A}^{k} of d k corresponding to the active variables are computed by a Barzilai-Borwein gradient method. The steplength α k is computed by an adaptation of the nonmonotone stabilization technique proposed in Grippo et al. (Numer. Math. 59:779–805, 1991). The method is a feasible one, since it maintains feasibility of the iterates x k , and is well suited for large-scale problems, since it uses matrix-vector products only in the truncated Newton method for computing dNkd_{N}^{k}. We prove the convergence of the method, with superlinear rate under usual additional assumptions. An extensive numerical experimentation performed on an algorithmic implementation shows that the algorithm compares favorably with other widely used codes for bound constrained problems.
展开▼
机译：我们关注有界约束的最小化问题{minf（x），l≤x≤u}的解。为了解决该问题，我们提出了一种主动集方法，该方法结合了投影和非单调牛顿型方法的思想。它基于形式为x k + 1 = [x k +α k d k 的迭代] ♯，其中α k 是步长，d k 是搜索方向，而[⋅] ♯是集合[l，u]上的投影算子。在每次迭代中，首先采用一个新公式来估算活动集。然后，通过截断牛顿法确定与自由变量相对应的d k 的分量d N k d_ {N} ^ {k} ，并且与有效变量相对应的d k 的分量d A k d_ {A} ^ {k}由Barzilai- Borwein梯度法。步长α k 是通过对Grippo等人提出的非单调稳定技术进行调整而得出的。 （Numer。Math。59：779-805，1991）。该方法是可行的，因为它保持了迭代x k 的可行性，并且非常适用于大规模问题，因为它仅在截断牛顿法中使用矩阵矢量乘积来计算d。 N k d_ {N} ^ {k}。我们证明了该方法的收敛性，在通常的附加假设下具有超线性速率。在算法实现上进行的大量数值实验表明，该算法与其他广泛使用的代码在有限约束问题上具有优势。
展开▼
