A trust region method based on a new affine scaling technique for simple bounded optimization

In this paper, we propose a new trust region affine scaling method for nonlinear programming with simple bounds. Our new method is an interior-point trust region method with a new scaling technique. The scaling matrix depends on the distances of the current iterate to the boundaries, the gradient of the objective function and the trust region radius. This scaling technique is different from the existing ones. It is motivated by our analysis of the linear programming case. The trial step is obtained by minimizing the quadratic approximation to the objective function in the scaled trust region. It is proved that our algorithm guarantees that at least one accumulation point of the iterates is a stationary point. Preliminary numerical experience on problems with simple bounds from the CUTEr collection is also reported. The numerical performance reveals that our method is effective and competitive with the famous algorithm LANCELOT. It also indicates that the new scaling technique is very effective and might be a good alternative to that used in the subroutine fmincon from Matlab optimization toolbox.     

A derivative-free affine scaling trust region methods based on probabilistic models with new nonmonotone line search technique for linear inequality constrained minimization without strict complementarity

ABSTRACT

In this paper, a derivative-free trust region methods based on probabilistic models with new nonmonotone line search technique is considered for nonlinear programming with linear inequality constraints. The proposed algorithm is designed to build probabilistic polynomial interpolation models for the objective function. We build the affine scaling trust region methods which use probabilistic or random models within a classical trust region framework. The new backtracking linear search technique guarantee the descent of the objective function, and new iterative points are in the feasible region. In order to overcome the strict complementarity hypothesis, under some reasonable conditions which are weaker than strong second order sufficient condition, we give the new and more simple identification function to structure the affine matrix. The global and local fast convergence of the algorithm are shown and the results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A computational comparison of scaling techniques for linear optimization problems on a graphical processing unit

Preconditioning techniques are important in solving linear problems, as they improve their computational properties. Scaling is the most widely used preconditioning technique in linear optimization algorithms and is used to reduce the condition number of the constraint matrix, to improve the numerical behavior of the algorithms and to reduce the number of iterations required to solve linear problems. Graphical processing units (GPUs) have gained a lot of popularity in the recent years and have been applied for the solution of linear optimization problems. In this paper, we review and implement ten scaling techniques with a focus on the parallel implementation of them on GPUs. All these techniques have been implemented under the MATLAB and CUDA environment. Finally, a computational study on the Netlib set is presented to establish the practical value of GPU-based implementations. On average the speedup gained from the GPU implementations of all scaling methods is about 7×.     

Using a spectral scaling structured BFGS method for constrained nonlinear least squares

In this paper, we use a spectral scaled structured BFGS formula for approximating projected Hessian matrices in an exact penalty approach for solving constrained nonlinear least-squares problems. We show this spectral scaling formula has a good self-correcting property. The reported numerical results show that the use of the spectral scaling structured BFGS method outperforms the standard structured BFGS method.     

A central path interior point method for nonlinear programming and its local convergence

In this paper, we present an interior point method for nonlinear programming that avoids the use of penalty function or filter. We use an adaptively perturbed primal dual interior point framework to computer trial steps and a central path technique is used to keep the iterate bounded away from 0 and not to deviate too much from the central path. A trust-funnel-like strategy is adopted to drive convergence. We also use second-order correction (SOC) steps to achieve fast local convergence by avoiding Maratos effect. Furthermore, the presented algorithm can avoid the blocking effect. It also does not suffer the blocking of productive steps that other trust-funnel-like algorithm may suffer. We show that, under second-order sufficient conditions and strict complementarity, the full Newton step (combined with an SOC step) will be accepted by the algorithm near the solution, and hence the algorithm is superlinearly local convergent. Numerical experiments results, which are encouraging, are reported.     

An affine scaling interior trust-region method combining with nonmonotone line search filter technique for linear inequality constrained minimization

This paper proposes an affine scaling interior trust-region method in association with nonmonotone line search filter technique for solving nonlinear optimization problems subject to linear inequality constraints. Based on a Newton step which is derived from the complementarity conditions of linear inequality constrained optimization, a trust-region subproblem subject only to an ellipsoidal constraint is defined by minimizing a quadratic model with an appropriate quadratic function and scaling matrix. The nonmonotone schemes combining with trust-region strategy and line search filter technique can bring about speeding up the convergence progress in the case of high nonlinear. A new backtracking relevance condition is given which assures global convergence without using the switching condition used in the traditional line search filter technique. The fast local convergence rate of the proposed algorithm is achieved which is not depending on any external restoration procedure. The preliminary numerical experiments are reported to show effectiveness of the proposed algorithm.