Are optimization results stochastic?

Question

I'm asking myself for some time if the results of optimization are random. As search for stochastic and optimization gives results about stochastic optimization but does not help with the stochasticity of optimization.

Let's say we have a simple knapsack problem:

$\begin{align} &\max\; x_1 + x_2 + 2x_3\\ &\text{s.t. } x_1 + x_2 + 2x_3 \le 2\\ &x_1, x_2, x_3 \in \{0,1\}\end{align}$

There are two possible results: $x_1 = 1, x_2 = 1$, or $x_3 = 1$.

Is it true to say that, in this case, each optimal result has a probability of 50%, as we would deduce from enumeration? As I understand, this would be called random.

However, a solver could apply a deterministic heuristic, which resolves knapsack problems by setting the largest values true, which would always result in $x_3 = 1$, or vice versa. In this case, when we know about this, we should call the result deterministic.

For general optimization problems, it's nearly impossible to predict the interplay of all solution methods. Also, for larger problems it might not be feasible to enumerate all solutions.

I would assume that, if we pick a variable of a complex optimization problem, we probably couldn't tell the probability of a solution value in an optimal solution.

But we should keep in mind that there are processes in the solver which are deterministic and thus reduce randomness.

Could we say that results of sufficiently complex optimization problems are stochastic?

Update

My question aims more in the direction of if the possibility to say that the results are stochastic, and less in the direction of how it is possible to create deterministic results.

Also, what might not have been clear in the question is that it aims at the assessment of the stochasticity of the solution before the solution is known. I could ask more clearly: Can we regard the solution to a complex optimization problem, with solvers which contain random elements, as stochastic, before we solve the problem?

Answer 1

Usually no. All solvers worth their salt can be deterministic, and most are by default. That is, given a fixed configuration and seed for their random number generator, they always give the same solution. So for a given solver configuration finding a solution can not be seen as a random process.

You can make it stochastic

If you add random elements, you could make it stochastic. This could be any randomization in the parameters, the random seed, the order of the formulation, enabling non-deterministic multithreading, changing machine, etc.

But it's likely not very random

Even then, it's not easy to understand how it samples the solution space: preprocessing and branching strategies create a lot of bias. It's hard to sample solutions uniformly and efficiently, and there is ongoing research on the subject (see here for SAT solvers for example).

Answer 2

I suspect that the answer to your question hinges more on how you understand the word stochastic than any particular insight about optimization.

Multiplicity of optima

In the example you gave, we have an optimization problem that has multiple optima. This is a fairly common situation in discrete optimization problems such as integer programs; it can also occur in nonlinear programming.

In designing optimization algorithms, we typically do not concern ourselves with multiple optima. There are cases, such as LP, where you can inspect the final tableau and state whether there are multiple optima and provide them upon request, but this is more of a "cool feature" than an "essential requirement" of a solution algorithm.

So, why aren't multiple optima a big deal?

Well, if you made your objective function correctly—that is, if it truly orders the feasible solutions according to your preferences—then if a problem has multiple optima, you are by definition indifferent between them. Therefore, it shouldn't matter to you whether the solver produces any one of the multiple optima, or selects randomly from among them, or picks the highest one according to a lexicographical tiebreaking rule like you proposed, or something else.

Viewing multiple optima stochastically

In general, the "solution" to an optimization problem is the set of solutions that provide the optimal objective function value. This set can be empty, or have multiple elements, or be a singularity. Only if it is a singularity do we say that the problem has a unique optimal solution.

You argue that when the optimal solution set has many elements, we can "view" this set stochastically. But this is true only inasmuch as we can view any set stochastically, namely, by imposing a probability distribution over its elements and claiming that we can sample from it, calculate its CDF, etc. The question you should ponder is, What do we stand to gain by introducing these additional parameters? More specifically:

• What probability distribution over the optima makes sense?
• Do you want a solver to actually do this random sampling? How? Why?
• Is a random sample from the optimal solution set preferable, in some sense, to a specific or arbitrarily chosen element of the optimal solution set?

If the answer to the last question is yes, then I would suggest that there is a more fundamental issue with your optimization model: You have defined the feasible solution set and/or objective function in a way that does not truly incorporate all of your preferences.

---

One situation where multiple optima may be meaningful

One application of optimization is Lagrangian mechanics: By the laws of physics, systems tend to come to rest in the position that minimizes their potential energy, and this equilibrium state can therefore be modeled as an optimization problem. But the process by which the system equilibrates is, essentially, random: Random perturbations to the system knock it this way and that until it converges to a stable state. So, if a mechanical system has multiple equilibria, it may be meaningful to talk about the probability with which it attains each equilibrium according to the kinds of random perturbation present in the environment.

On the other hand, real-world systems are continuous, rather than discrete, and therefore the odds of having two solutions with exactly the same optimal potential energy is vanishingly rare. A more typical outcome would be that the potential energy is nonconvex in the parameters, and there are multiple local optima which can still represent an equilibrium state. Enumeration the local optima of a nonconvex problem is an hard problem in its own right, before we even get to speculating about the probability with which each equilibrium arises.

(I am not a physicist, so I invite any edits that improve the terminology used here.)

---

Randomized rounding

This isn't really related to the ideas above, but because you brought up the knapsack problem, it is worth mentioning that one heuristic for solving integer programs is to solve the LP relaxation and treat the $x_i$s as probability values for Bernoulli variables.

By randomly sampling these variables, we can sometimes generate a "pretty good" solution (but, of course, there is no guarantee that it will be optimal or even feasible). But this is different from your example, because you are proposing choosing randomly from among integer solution vectors, whereas the randomized rounding heuristic chooses the elements of the solution vector $x$ randomly and independently.

Answer 3

Results are only stochastic if your convergence criterion allows for that. If your convergence criterion is not met but you terminate anyway, there are no results to speak of, so this statement is conveniently consistent.

There is an element of stochasticity in all high performance solvers due to internal working limits, timeouts, RNG, etc., but as long as the solver will only converge if a certain criterion is met, it all really depends on what that criterion is.

There are methods to deterministically solve general optimisation problems to global optimality. Even in the case of multiple global solutions (different vectors with identical objective values), there are ways to deterministically find all of them, as long as the solver is told to do so.

What might vary is solution time - this is nearly always stochastic at high performance. What solution you get is something that can be controlled in many ways, even though that's not always done in practice.

Answer 4

In the example you give, the problem is not stochastic, but the solution that a potential solver gives you, in case multiple optimal solutions do exist. That is an important difference. Deterministic problems are, as the name suggests, not stochastic but multiple optimal solutions might exist. And in that case, it is up to the solver how to deal with this and there might (dependent on the solver) indeed be some stochasticity involved.

Answer 5

In Gurobi, there is a parameter called seed which "typically leads to different solution paths". But the default value is 0 (rather than some dynamically changing value), so that the solution is usually reproducible by default. I think randomly setting this parameter will make your solution stochastic.

Answer 6

As @Max suggested, the answer depends on how we understand the word stochastic. For example, Lionel Pages pleads for the subjectivity of stochasticity, pointing at an ongoing scholarly debate.

In the case of a complex optimization problem, in which several solutions exist, as @Gabriel Gouvine said, we could sample the solution space - of solutions fulfilling our criteria - and from that deduce the probability of each solution, or solution value. However, the probabilities are only known after we solved the problem.

Enumerating solutions and taking the probability of each solution is the frequentist way to understand stochasticity.

Alternatively, we can understand stochasticity as subjective, as a measure of uncertainty.

In the case of a complex optimization problem, in which just one solution exists, the solution is already determinded, even if we are not able to know it before using a sophisticated solver.

In this case, the verdict to call the solution stochastic or not depends on our judgement, if we regard subjective indeterminism as subjective stochasticality or not.

If we don't accept subjective indeterminism as stochastic, the verdict to call a solution stochastic depends on the stochasticity of the solver as a random process and on the existance of several solutions. Because if there is just one solution, which is found by a random solver, it was still determined before finding it. In general, we don't know the number of solutions before solving the problem. Right now, I understand that we can only consider the unknown result of an optimization as stochastic, if we accept subjective indeterminism.