# Optimization in the presence of known uncertainty using the downhill simplex technique

I'm interested in how I might consider optimization in the case where I have a function of known variables with known uncertainties (this can occur, for example, with resistors in electronics where they are purchased with a guarantee to be within 1% or 2%, for example, of their nominal values.) Some uncertainties will be different in magnitude than others. (For example, a voltage may be $$5\pm5\%$$ but a resistor may be $$1\:\text{k}\Omega\pm1\%$$.)

The problem may involve $$N$$ components, but where only two of them are to be optimized to meet a goal. The rest are known except for the fact that they also include uncertainties, as well. The desire is, within this uncertain environment, to find the optimal set of values that are allowed to vary, by some definition.

In this case, I'd like to assume that it is possible to develop an equation set to zero where exact values are used. And that we can square this equation for the purposes of optimizing it, so that it is guaranteed to be a downhill progress towards the zero result from positive values. (In that sense, this is a root-finding problem. The difference being that these values aren't exact but have known ranges.)

For the purposes of making the example concrete, though I'm fine with a generalized answer too, let's say there the problem involves $$9$$ variables and $$2$$ variables to be optimized in combination out of that $$9$$. In this case, the $$7$$ known values are uncertain by some specified amount and the magnitude range of their values is known, a priori, so that we can establish some appropriate $$\Delta$$ for each dimension that is different from other dimensions for purposes of searching. Similarly, the remaining $$2$$ variables also have their own uncertainties as well as their own $$\Delta$$ span to help normalize the search algorithm's scale along each dimension.

For example, here is a sample "surface" in just two dimensions, where $$x$$ is uncertain and so is $$y$$ (it's difficult to display an example for $$9$$ variables, $$2$$ of which are to be optimized, so forgive me for the simplification here): In this case, I might want to minimize the rate of change of the area of circle of least confusion. How I might exactly define it might be, for example, based upon the point at $$\left(x,y\right)$$ and where the radius is defined as the worst case in the $$y$$ direction. Regardless of how that is defined, the process for developing a concrete downhill simplex algorithm seems a bit fuzzy to me at the moment.

The optimum goal to be found should be similarly definable. The problem here, to me, is that all of the input variables as well as the remaining variables to be optimized each have associated error bounds. So this implies a fuzzy simplex and therefore a fuzzy approach to applying rules to how to produce the next simplex to attempt. In some cases, it will be uncertain which direction to take.

I'd appreciate any constructive thoughts or references to appropriate papers in combination with such thoughts that may help me think better about this problem. I'd also appreciate any criticism about how I've written this question and might improve it. I'd very much like to improve it, where possible.

I'm interested in a generalized approach where each of the variables have associated uncertainties to them and therefore the optimal minimization is similarly uncertain, as well, but where I can define something to be minimized. The complexity in my mind relates to the algorithm needed for moving from the current simplex to the following simplex, given these uncertainties. It's not clear to me how that step itself may be decided. Perhaps I've just not yet thought it out well enough. But I wouldn't mind a clue or two.

Any help in clarifying my thinking towards an approach would be very much appreciated.

EDIT: note: The problem domain I'm in does have known error bounds and therefore, as one comment below hinted towards, this is a problem involving deterministic variability. It does not involve knowledge of Poisson events or Gaussian distributions for these purposes. I think this means that stochastic tools are probably not appropriate here.

For example, a voltage will possess an initial accuracy based upon manufacturer specifications and will drift from there over time and temperature in ways that are relatively complex to capture. So a simple range is used, instead. There just isn't enough information to develop a distribution with any confidence to it. Similarly, resistors will possess an initial accuracy specification, but it's possible that manufacturers will "select out" the more accurate values to sell at a higher price, leaving a missing middle section in the distribution that you find you never receive when buying them. You just get the skirts, instead, if you pay less than others do.

The upshot is that we can estimate a given variability range but we cannot say much more about it.

• You can think of the known quantities with known uncertainty as random variables with a probability distribution over their interval of uncertainty, uniform if you like. This formulates your problem as stochastic optimisation. – abhi01nat Sep 16 at 7:17
• @abhi01nat I'll look over that, probably tomorrow. The hint is appreciated. – jonk Sep 16 at 7:19
• Robust optimization applies when you have intervals of uncertainty but not necessarily probability distributions. – RobPratt Sep 16 at 14:06
• @RobPratt Thanks. Now that is the situation I have and that seems like a good term to look up. As I initially imagined it, there exists a composite surface. But perhaps that's an incorrect approach. So thanks very much for the phrase. I suspect you've made my day! I'll incorporate your clarification in my question, too. It improves what I'd written before. The concept of deterministic variability is important to include. – jonk Sep 16 at 18:52
• See especially work by Bertsimas and Sim where the robust counterpart to the nominal problem preserves tractability. – RobPratt Sep 16 at 19:37