We consider the problem of accurate computation of the finite difference $f(\x+\s)-f(\x)$ when $\Vert\s\Vert$ is very small. Direct evaluation of this difference in floating point arithmetic succumbs to cancellation error and yields 0 when $\s$ is sufficiently small. Nonetheless, accurate computation of this finite difference is required by many optimization algorithms for a “sufficient decrease” … Read more
The state of numerical computing is currently characterized by a divide between highly efficient yet typically cumbersome low-level languages such as C, C++, and Fortran and highly expressive yet typically slow high-level languages such as Python and MATLAB. This paper explores how Julia, a modern programming language for numerical computing which claims to bridge this … Read more
This position paper reflects on the generalization of adaptive methods for Constraint Programming (CP) solving mechanisms, and suggests the use of application-oriented descriptions as a means to broaden CP adoption in the industry. We regard as an adaptive method any procedure that modifies the behavior of the solving process according to previous experience gathered from … Read more
It is shown how functions that are defined by evaluation programs involving the absolute value function (besides smooth elementals), can be approximated locally by piecewise-linear models in the style of algorithmic, or automatic, differentiation (AD). The model can be generated by a minor modification of standard AD tools and it is Lipschitz continuous with respect … Read more
We analyze the relationship between the noise level of a function and the accuracy and reliability of derivatives and difference estimates. We derive and empirically validate measures of quality for both derivatives and difference estimates. Using these measures, we quantify the accuracy of derivatives and differences in terms of the noise level of the function. … Read more
Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users … Read more
Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One key factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of deterministic models, which are often formulated first. A second key factor relates to the difficulty of solving stochastic … Read more
Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more
An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the “Newton chip method”, a noncommutative analog of the classical Newton polytope method, and semide finite programming. CitationI. Klep and J. Povh. Semidenite programming and sums of hermitian squares of noncommutative polynomials. J. Pure Appl. … Read more
We describe Pyomo, an open-source tool for modeling optimization applications in Python. Pyomo can be used to define abstract problems, create concrete problem instances, and solve these instances with standard solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages like AMPL and GAMS. Pyomo leverages the capabilities of the Coopr software, … Read more