17.1.1 A few integer parameters

In cases where there are at most two or three integer optimization parameters, I would create a loop or grid and solve the optimization problem for each value of the integer in a reasonable range. This is, admittedly, a very crude approach, but mixed integer optimization is a field full of difficulties. Let us look at our classic Rosenbrock function in the integer domain as an example.

fr <- function(x) {
    ## Rosenbrock Banana function
    x1 <- x[1]
    x2 <- x[2]
    value <- 100 * (x2 - x1 * x1)^2 + (1 - x1)^2
}
x1r <- seq(-10, 10, 1)
x2r <- x1r
frbest <- 1e+300
xbest <- rep(NA, 2)
for (x1 in x1r) {
    for (x2 in x2r) {
        fval <- fr(c(x1, x2))
        if (fval < frbest) {
            xbest <- c(x1, x2)
            frbest <- fval
        }
    }
}

This approach can also be used for situations where we need to decide which sequence of activities is best by generating the set of possible sequences and looping over them. Clearly this is NOT a good approach in general. I would not recommend it, for example, for the type of schedule optimization performed by Michael Trick (see, for example, http://mat.tepper.cmu.edu/trick/). However, when a simple construct such as the example above can be used to perform an essentially exhaustive search, it is likely less work than learning how to set up and use a more sophisticated tool. R is quite weak in this area, and relies on calls to external packages, no doubt because of its statistical heritage. My own experience with integer optimization parameters is severely limited for the same reasons.

17.3.1 Unconstrained problems

For unconstrained minimization of functions that have continuous gradients, the solution must have a zero gradient at every local minimum (Karush, 1939; Kuhn and Tucker, 1951). This is a necessary condition, but because local maxima and saddle points also give zero gradients, it is not sufficient. We call this the first-order KKT (Karush–Kuhn–Tucker) condition.

We also want the objective function to be higher at every point “near” the proposed minimum, so that the function is locally convex. There is a nice mnemonic at http://shreevatsa.wordpress.com/2009/03/17/convex-and-concave/ to help one remember this. If the second-order derivatives of the objective can be computed, they define the Hessian matrix

The condition for the proposed solution to be at “the bottom of a bowl” is that the Hessian is positive-definite, for which the most common test is that its eigenvalues are all positive.

Reality, of course, is never so nice. The villain in this is the possibility of floating-point representations of eigenvalues that are “small.” Indeed, we can likely create matrices that resemble Hessians that are provably positivee-definite in exact arithmetic that give some small negative estimates of the eigenvalues. And it is very common that real problems give positive but small Hessian eigenvalues. Thus we must test for “small.”

In this activity, my own rule of thumb is to first look for all positive eigenvalues. Those computed negative or zero should, I believe, be reported as such, even if it turns out later that they are an awkward special case of unfortunate rounding. In any event, these cases are candidates for careful examination and will likely cause trouble for our optimizers.

Assuming all the eigenvalues are strictly positive, I take the ratio of the smallest to the largest of the Hessian eigenvalues. This ratio should not be “too small.” In package optimx, ratios smaller than 1e are taken as evidence of effective singularity of the Hessian.

There is no absolute rule about such tolerances. My own justification comes from multiple linear regression, where the singular values of the matrix of variables are comparable to the square roots of the Hessian eigenvalues. Thus a ratio of singular values smaller than 1e would be taken as evidence of singularity, which in linear regression is indicative of a lack of independence between the explanatory variables. The singular values give the relative contribution of orthogonalized explanatory variables to the overall variability of these variables. Thus a singular value that is 1/1000 as big as the largest is contributing a very tiny fraction of the overall variability. Indeed, if we graph the singular values as bars on a regular-sized sheet of paper, the smallest singular value is represented by a bar about 0.2 mm long or less, because A4 and “letter” sizes are 210 and 216 mm wide, respectively.

Warning: Many people assume that computed eigenvalues will be sorted largest to smallest. While many programs do indeed provide them in this ordering, it pays to be careful and check or else use program code that explicitly looks for the maximal and minimal values. The extra time for the check is small compared to the time to repair the damage when we get this wrong.

17.3.2 Constrained problems

The optimality conditions for constrained problems are more demanding to both specify and compute. Gill et al. (1981, Chapter 3) give a fairly comprehensive solution, but for most R users, I believe that the material will not be easy reading. There is a good summary introduction to the wider topic in http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.

Clearly, if the constraints are not active, we can use the KKT conditions above. When one or more constraints are active, however, we need to ensure that the gradient as projected along any feasible direction is essentially zero as a first-order condition. There are extensions of the KKT conditions for such situations, but we need to be conscious that they depend on assumptions of continuity and differentiability that may not be true.

My own preference—and this is colored by the limited number of problems with general constraints I have encountered—is to test the proposed optimum to see if it satisfies the constraints. This has the merit that the computations are done using the user's own code. We can also check nearby points to ensure that they are either infeasible (we are on a constraint boundary) or have a higher value of the objective function.