Powell’s COBYLA Algorithm

Powell’s COBYLA algorithm is a sequential trust-region algorithm that tries to maintain a regularly shaped simplex throughout the iterations. The algorithm uses a monotone-decreasing radius, , of a spheric trust region. The modification implemented in the NLPNMS call permits an increase of the trust-region radius in special situations. A sequence of iterations is performed with a constant trust-region radius until the computed function reduction is much less than the predicted reduction. Then, the trust-region radius is reduced. The trust-region radius is increased only if the computed function reduction is relatively close to the predicted reduction and if the simplex is well-shaped. The start radius, , can be specified with the second element of the par argument, and the final radius, , can be specified with the ninth element of the tc argument. Convergence to small values of , or high-precision convergence, can require many calls of the function and constraint modules and can result in numerical problems. The main reasons for the slow convergence of the COBYLA algorithm are as follows:

• Linear approximations of the objective and constraint functions are used locally.

• Maintaining the regularly shaped simplex and not adapting its shape to nonlinearities yields very small simplexes for highly nonlinear functions, such as fourth-order polynomials.

To allocate memory for the vector returned by the "nlc" module argument, you must specify the total number of nonlinear constraints with the tenth element of the opt argument. If any of the constraints are equality constraints, the number of equality constraints must be specified by the eleventh element of the opt argument. See the section Parameter Constraints for details.

For more information about the special sets of termination criteria used by the NLPNMS algorithms, see the section Termination Criteria.

In addition to the standard iteration history, the NLPNMS subroutine prints the following information. For unconstrained or boundary-constrained problems, the subroutine also prints the following:

• difcrit, which, in this subroutine, refers to the difference between the largest and smallest function values of the simplex vertices

• std, which is the standard deviation of the function values of the simplex vertices

• deltax, which is the vertex length of a restarted simplex. If there are convergence problems, the algorithm restarts the iteration process with a simplex of smaller vertex length.

• size, which is the average distance of the simplex vertex with the smallest function value to the other simplex vertices

For linearly and nonlinearly constrained problems, the subroutine prints the following:

• conmax is the maximum constraint violation.

• meritf is the value of the merit function, .

• difmerit is the difference between adjacent values of the merit function.

• is the trust-region radius.

The following statements uses the NLPNMS call to solve the Rosen-Suzuki problem (see the section Rosen-Suzuki Problem), which has three nonlinear constraints. Figure 23.199 is a partial listing of the output:

start F_HS43(x);
   f = x*x` + x[3]*x[3] - 5*(x[1] + x[2]) - 21*x[3] + 7*x[4];
   return(f);
finish F_HS43;
start C_HS43(x);
   c = j(3,1,0.);
   c[1] = 8 - x*x` - x[1] + x[2] - x[3] + x[4];
   c[2] = 10 - x*x` - x[2]*x[2] - x[4]*x[4] + x[1] + x[4];
   c[3] = 5 - 2.*x[1]*x[1] - x[2]*x[2] - x[3]*x[3]
            - 2.*x[1] + x[2] + x[4];
   return(c);
finish C_HS43;

x = j(1, 4, 1);
opt = j(1, 11, .); 
opt[2] = 3; opt[10] = 3; opt[11] = 0;
call nlpnms(rc, xres, "F_HS43", x, opt, , , , , "C_HS43");