wn_nlp_conj_method, wn_make_linear_constraint, wn_make_nonlinear_constraint - constrained non-linear optimization package

#include <wn/wnnlp.h>

#define WN_EQ_COMPARISON 1
#define WN_GT_COMPARISON 2
#define WN_LT_COMPARISON 3

typedef struct wn_linear_constraint_type_struct
{
...

int size;
int *vars;
int comparison_type;

double *weights;
double rhs;
} *wn_linear_constraint_type;

typedef struct wn_nonlinear_constraint_type_struct
{
...

int size;
int *vars;
int comparison_type;
double offset;

ptr client_data;
double (*pfunction)(int size,double *values,ptr client_data);
void (*pgradient)(double *grad,int size,double *values,ptr client_data);
} *wn_nonlinear_constraint_type;

void wn_nlp_conj_method
(
int *code,
double *val_min,
double solution_vect[],
double delta_vect[],
wn_nonlinear_constraint_type objective,
wn_sll constraint_list,
int num_vars,
int conj_iterations,
int offset_iterations,
double offset_adjust_rate
)

void wn_make_linear_constraint
(
wn_linear_constraint_type *constraint,
int size,double rhs,int comparison_type
)

void wn_make_nonlinear_constraint
(
wn_nonlinear_constraint_type *constraint,
int size,int comparison_type
)

extern int wn_nlp_verbose;

This package is useful for minimizing general functions of many variables subject to general constraints. The function to minimize and the constraints can be linear or non-linear. If they are non-linear, they must be continuous and differentiable. The constraints can be equality or inequality constraints.

The optimization algorithm works roughly as follows: the constraints and the objective function are combined to create a master unconstrained objective function. The constraints are handled by adding a quadratic penalty function to the master objective function for each constraint that is violated. The master objective function is optimized using the conjugate-gradient hill-climbing algorithm (see wn_conj_direction_method(3)). The resulting solution probably violates some of the constraints. Offsets are added to the violated constraints in order to push the solution toward compliance with the violated constraints. The conjugate-gradient procedure is repeated. This entire cycle is repeated until convergence.

If all goes well, the algorithm converges to a local minimum; this local minimum is not necessarily a global minimum or even a good local minimum. If either the objective function or the constraint functions are not differentiable, the algorithm often gets stuck in a very sub-optimal solution, and no warning is given that this has happened.

Proper scaling of the objective function and of the constraint functions is important to ensure fast and accurate convergence of the algorithm. The functions and variables should be scaled so that the partial derivatives of all functions with respect to all variables in the region of the solution is near +1 and -1. Partials which are always very large or always very small should be scaled so as to be in this region.

wn_nlp_conj_method solves a constrained non-linear minimization problem. objective specifies the linear or non-linear objective function to minimize. constraint_list is a singly-linked list of linear and non-linear constraints. objective and constraint_list together comprise the problem to be solved. They must be composed of objects of types wn_linear_constraint_type and wn_nonlinear_constraint_type. num_vars is the number of variables in the problem. solution_vect is a vector which the caller should initialize to contain a vector which is as close a possible to the solution; after termination solution_vect contains the solution. val_min is set to the value of the objective function of solution_vect. code indicates the status of the run. conj_iterations specifies the number of iterations in the conjugate-gradient algorithm. Making it too small results in erratic behavior and non-convergence; making it too big wastes CPU time. Often setting conj_iterations to the same value as len works well. offset_iterations specifies the number of iterations to adjust constraint offsets; often a number like 10 or 20 works well. offset_adjust_rate specifies how aggressively constraint offsets are adjusted. 1 is the most agressive, 0 means no adjustment at all. offset_adjust_rate should always be in the range (0,1]. For linear problems, or problems which are only "mildly" nonlinear, 1 usually works well. Using a value too large results in erratic non-convergence; using a value too small wastes CPU time. delta_vect is a vector of delta values for computing numerical gradients if the caller does not provide symbolic gradients for all of his non-linear constraints. If all non-linear constraints have symbolic gradients, set delta_vect to NULL.

wn_make_linear_constraint makes a linear constraint. size specifies the number of variables involved in the constraint; rhs is the right hand side of the constraint. rhs is ignored if the constraint is used as the objective function. comparison_type must be one of WN_EQ_COMPARISON, WN_GT_COMPARISON, or WN_LT_COMPARISON. After creating the linear constraint, the caller must set the vectors weights and vars of the linear constraint. vars is an array of integers of size size. Each entry specifies the index of a variable which is included in the constraint. weights is an array of doubles of size size. Each entry specifies a coefficient for the corresponding variable of vars.

wn_make_nonlinear_constraint makes a non-linear constraint. size specifies the number of variables involved in the constraint; comparison_type must be one of WN_EQ_COMPARISON, WN_GT_COMPARISON, or WN_LT_COMPARISON. After creating the non-linear constraint, the caller must set vars, pfunction, and possibly pgradient and client_data. vars is an array of integers of size size. Each entry specifies the index of a variable which is included in the constraint. pfunction is a pointer to a non-linear function of the variables in vars. The constraint implemented is one of (*function(...) >= 0

(*function(...) <= 0

(*function(...) == 0 depending on the value of comparison_type. pgradient places the gradient of pfunction in grad. If you do not want to bother figuring out the gradient of pfunction, do not set pgradient. The gradient will be computed numerically by calling pfunction with domain values differing by amounts from delta_vect. This can be slow. client_data is a pointer to user-defined data to be associated with the constraint.

wn_nlp_verbose controls the amount of status information output by wn_nlp_conj_method. 0 produces no output; 1 produces some output; 2 produces more; 3 produces the most.

wn_nlp_conj_method runs with time = conj_iterations*offset_iterations*<num terms in constraints>

stack memory = 1

dynamic memory = len Of course, this figure tells one nothing about the time required to achieve good convergence. This depends heavily on the problem being solved and the user's skill in properly adjusting conj_iterations, offset_iterations, and offset_adjust_rate, and the problem scaling.

Typically, if the problem is reasonably behaved and well scaled, one can set conj_iterations to something of order of the number of variables len, and set offset_iterations to some number like 10 or 20.

The author has succesfully used this routine to solve non-linear problems with 10,000 variables and 50,000 constraints in a few hours of workstation time. This routine can also solve large linear programming problems, but the numerical accuracy is not as good as that of a more specialized LP algorithm.

code == WN_SUCCESS means successful completion, optimum found code == WN_SUBOPTIMAL means termination before optimum found code == WN_UNBOUNDED means function is unbounded

wnconj(3), wnsplx(3), wnsll(3)

Will Naylor