Trust region

The above subproblem can be solved very efficiently for fixed values of the multipliers X and v and penalty parameter p. Here a gradient projection trust region method is applied. Once subproblem (3-104) is solved, the multipliers and penalty parameter are updated in an outer loop and the cycle repeats until the KKT conditions for (3-85) are satisfied. LANCELOT works best when exact second derivatives are available. This promotes a fast convergence rate in solving each... 

KNITRO (Byrd et al., 1997) SQP, barrier Trust region Exact and quasi-Newton... 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

Trust regions. The name trust region refers to the region in which the quadratic model can be trusted to represent /(x) reasonably well. In the unidimensional line search, the search direction is retained but the step length is reduced if the Newton step proves to be unsatisfactory. In the trust region approach, a shorter step length is selected and then the search direction determined. Refer to Dennis and Schnabel (1996) and Section 8.5.1 for details. 

The trust region approach estimates the length of a maximal successful step from xk. In other words, x < p, the bound on the step. Figure 6.11 shows /(x), the quadratic model of /(x), and the desired trust region. First, an initial estimate of p or the step bound has to be determined. If knowledge about the problem does... 

Representation of the trust region to select the step length. Solid lines are contours of fix). Dashed lines are contours of the convex quadratic approximation of fix) at x. The dotted circle is the trust region boundary in which 8 is the step length. x0 is the minimum of the quadratic model for which H(x) is positive-definite. 

The PSLP algorithm is a steepest descent procedure applied to the exact Lx penalty function (see Section 8.4). It uses a trust region strategy (see Section 6.3.2) to guar-... 

The trust region problem is to choose Ax to minimize PI in (8.54) subject to the trust region bounds (8.55) and (8.56). As discussed in Section (8.4), this piecewise linear problem can be transformed into an LP by introducing deviation variables p, and The absolute value terms become (p, + ,) and their arguments are set equal to Pi — nt. The equivalent LP is... 

If predk = 0, then no changes Ax within the rectangular trust region (8.58) can reduce PI below the value P1(0, x ). Then x is called a stationary point of the nonsmooth function P, that is, the condition predk = 0 is analogous to the condition V/(x ) = 0 for smooth functions. If predk = 0, the PSLP algorithm stops. Otherwise predk > 0, so we can compute the ratio of actual to predicted reduction. 

Step 4 rejects the new point and decreases the step bounds if ratiok < 0. This step can only be repeated a finite number of times because, as the step bounds approach zero, the ratio approaches 1.0. Step 6 decreases the size of the trust region if the ratio is too small, and increases it if the ratio is close to 1.0. Zhang et al. (1986) proved that a similar SLP algorithm converges to a stationary point of P from any initial point. 

For process optimization problems, the sparse approach has been further developed in studies by Kumar and Lucia (1987), Lucia and Kumar (1988), and Lucia and Xu (1990). Here they formulated a large-scale approach that incorporates indefinite quasi-Newton updates and can be tailored to specific process optimization problems. In the last study they also develop a sparse quadratic programming approach based on indefinite matrix factorizations due to Bunch and Parlett (1971). Also, a trust region strategy is substituted for the line search step mentioned above. This approach was successfully applied to the optimization of several complex distillation column models with up to 200 variables. 

The quadratic model is an improvement on the linear model since it gives information about the curvature of the function and contains a stationary point. However, the model is still unbounded and it is a good approximation to fix) only in some region around xc. The region where we can trust the model to represent fix) adequately is called the trust region. Usually it is impossible to specify this region in detail and for convenience we assume that it has the shape of a hypersphere s <, h where h is the trust... 

The trust radius h reflects our confidence in the SO model. For highly anharmonic functions the trust region must be set small, for quadratic functions it is infinite. Clearly, during an optimization we must be prepared to modify h based on our experience with the function. We return to the problem of updating the trust radius later. 

For the same reason we assumed that the trust region of the RSO model is a simple hypersphere with an adjustable radius h. 

Global strategies for minimization are needed whenever the current estimate of the minimizer is so far from x that the local model is not a good approximation to fix) in the neighborhood of x. Three methods are considered in this section the quadratic model with line search, trust region (restricted second-order) minimization and rational function (augmented Hessian) minimization. 

In the trust region or restricted step method we determine in each iteration the global minimizer of the RSO model Eq. (3.10). In the global region a step is taken to the boundary of the trust region... 

The trust region method is usually implemented with the exact Hessian. Updated Hessians may also be used but an approximate Hessian usually does not contain enough information about the function to make the trust region reliable in all directions. The trust region method provides us with the possibility to carry out an unbiased search in all directions at each step. An updated Hessian does not contain the information necessary for such a search. 

One advantage of the KF minimization over trust region RSO minimization is that we need only calculate the lowest eigenvalue and eigenvector of the augmented Hessian. In the trust region method we must first calculate the lowest eigenvalue of the Hessian and then solve a set of Unear equations to obtain the step. 

In conclusion, the trust region method is more intuitive than the RF model and provides a more natural step control. On the other hand, RF optimization avoids the solution of one set of linear equations, which is important when the number of variables is large. 

To minimize the image function we use a second-order method since in each iteration the Hessian is needed anyway to identify the mode to be inverted (the image mode). Line search methods cannot be used since it is impossible to calculate the image function itself when carrying out the line search. However, the trust region RSO minimization requires only gradient and Hessian information and may therefore be used. In the diagonal representation the step Eq. (5.8) becomes... 

The only difference between the steps along the image mode and the transverse modes is the sign of the level shift. The level shift p < —A.i is determined such that the step is to the boundary of the trust region. Equation (6.18) forms the basis for the trust region image minimization (TRIM) method for calculating saddle points.20... 

In RSO minimizations we minimize Eq. (6.19) within the trust region. If instead we wish to maximize the lowest mode and minimize the others we may use the model... 

---