Constraint Optimization: From Efficient Computation of What Can Be Achieved to Efficient Computation of a Way to Achieve The Corresponding Optimum

摘要

In many practically useful cases, we know how to efficiently compute the exact range of a function over given intervals (and, possibly, under additional constraints). In other words, we know how to efficiently compute the minimum and maximum of a given function f(x1, ..., xn) on any box. From the practical viewpoint, it is important not only to find the value of the corresponding maximum or minimum, but also to know for what values of the parameters xi this optimum is attained. We prove a general result: that if we can efficiently compute the optimum, then we can also efficiently find the values at which this optimum is attained.