A Mixed Interpolation Method For Wedge Trust Region Algorithm

This paper focuses on the wedge trust region algorithm. It belongs to the derivative free optimization category. Here are the two aspects of the work:First, we propose an algorithm of mixed linear model and quadratic model. To structure a linear model we need n+1 interpolation points for an n-dimensional problem. To construct a quadratic model we need( n+1)( n+2)/2points. In order to guarantee the existence and uniqueness of the model, interpolation points must satisfy a certain geometric characteristic,that is to say, their positions should be well poised. So when the algorithm change from the linear model to quadratic model, it is difficult to construct the quadratic interpolation set through linear interpolation set while remaining the good geometric characteristics. We use the NEWOUA algorithm proposed by Powell and multiple polynomial interpolation theory to construct a new set of interpolation points. When the iterative point is far from the best, we use linear interpolation model. When the iteration point is close to the best, we use the quadratic interpolation model.Second, we combine the non-monotone technique with wedge trust region technique. In the classical non-monotone trust region algorithm, we use the ratio to adjust the trust region radius. In fact, the denominator of the ratio does not correspond to the fact. So we use a ratio as the acceptance criteria, and another ratio to update the trust region radius.