How to handle the time complexity for an optimization that depends on numerical values
One approach not mentioned above is parametrized complexity. The idea is to express the complexity of the algorithm with respect to a parameter of the input. A classical example is when the input is a graph and the parameter is the tree-width. But more generally, the parameter will be something that is typically not easily computable from the input. On a related note, the condition number can be seen as a particular case of parametrized complexity when dealing with numerical problems.