Convexity Determination in the Microsoft Excel Solver Using …

Short Description
Excel Solver aimed at challenging industrial optimization problems of all types. The. modeling language in this case is the Excel formula language, …

Website: www.autodiff.org | Filesize: 36kb

Content
Convexity Determination in the Microsoft Excel Solver Using Automatic Differentiation Techniques
Ivo P. Nenov, Daniel H. Fylstra, Lubomir V. Kolev
Frontline Systems Inc., USA
Abstract: 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…

Get the file Download here