Convexity Determination in the Microsoft Excel Solver Using Automatic Differentiation Techniques
Ivo P. Nenov, Daniel H. Fylstra, Lubomir V. Kolev · 2004
We present algorithmic tests to determine whether smooth functions are convex over certain regions, in an algebraic modeling system implemented in the Premium Solver Platform for Microsoft Excel. We apply convexity determination to the objective, constraints and bounds of an optimization problem, to determine whether a locally optimal solution will be globally optimal, and whether an interior point algorithm for convex problems can be used as the solution method. The algorithms generally rely on fast and accurate computation of the ‘Hessian sign’ or the full interval Hessian of each problem function, making automatic differentiation techniques a practical requirement for their use; their effectiveness is improved by using constraint propagation techniques to narrow the intervals over which the functions are evaluated. We compare different convexity determination algorithms on a test set of models and functions defined by expressions in the Microsoft Excel formula language. Introduction: Convexity is clearly a desirable property for an optimization model. If a model is known or can be shown to be convex, we can be confident of finding a globally optimal solution, and we can apply (among others) high performance interior point methods to find that solution. Linear programming (LP) problems are of course convex, and quadratic programming (QP) problems are convex if the Hessian of the objective is positive semidefinite. But for general smooth nonlinear problems, it is nontrivial to determine whether each problem function is convex over the feasible region determined by bounds on the variables and other constraint functions. Yet many smooth nonlinear problems of interest may be convex, more than is commonly realized; for example, Stephen Boyd [1], who has studied many such problems arising in electrical engineering, has described a wide range of practical problems shown to be convex. In view of the importance of convexity, it is somewhat surprising that existing algebraic modeling systems do not provide much support for testing convexity of optimization problems written in the modeling language. This paper describes an effort to implement convexity determination in the framework of the Microsoft Excel Solver, specifically in the Premium Solver Platform, an upward compatible extension of the Excel Solver aimed at challenging industrial optimization problems of all types. The modeling language in this case is the Excel formula language, which is richly expressive with over 300 built-in functions. Our convexity tests utilize support in the Premium Solver Platform for model diagnosis, interval evaluation and automatic differentiation of Excel spreadsheet formulas, as previously described [2, 3]. They may prove or disprove convexity or yield inconclusive results, but in many practical cases they yield useful information for the modeler and the solver. In this paper, functions are assumed to be smooth, though we note in the summary that a variety of techniques exist to convert certain commonly used non-smooth constraint functions (e.g. IF, MIN, MAX) into linear constraints with additional binary integer variables – potentially yielding a mixed-integer convex problem. The original problem is: given a function (twice continuously differentiable in the box ), prove computationally that the function is convex, concave, or neither convex nor concave in . In our implementation four general steps are used, in order of increasing computational cost: ) ( , : 2 x x C f R R f n ∈ → ∈