Tyge Rugenstein, RPI

An active set strategy for the ellipsoid algorithm allows the algorithm to focus on the inequality constraints expected to be active, or tight, at optimality. In order for this strategy to be effective, the algorithm must test constraints at some specified interval, called a "drop-check interval, and eliminate those constraints found to be slack. The quicker the algorithm can drop a constraint the more efficient it will be in solving the optimization problem. However, if the constraint is dropped erroneously the algorithm is required to backtrack, thus adding a computational penalty to the run time of the algorithm.

I have defined success as a 99% probability that a constraint is checked for feasibility during the drop-check interval. In other words, the goal is to ensure P(Success) ? .99 before a constraint is dropped from the active set. This presentation will focus on how the multinomial distribution is used to model the behavior of the active set strategy and ultimately solve for the number of iterations required to ensure success with a .99 probability. In addition to the development of the model, I will highlight the use of Maple in the problem solving process.