| Details: |
Stochastic optimisation has been largely concerned with
probabilistic or stochastic models used in Operational
Research, or in decision-making under risk, where we come
across randomness in
i) the objective function (s) caused by randomness in the
‘state of nature’ and / or
ii) the constraints in terms of random given variables or
given relations and / or
iii) the decision variable (s) –by choice
In solving such models ( or the corresponding problems), we
deal with probability distributions of the random variable(s)
involved—usually assumed to be completely specified—and
use some optimisation techniques to suitable deterministic
formulations of the problems, replacing the distributions by
some summary measure (s).
In the first view of Stochastic Optimisation, the search for the
optimal solution or an approximation thereof does not involve
any randomness. And, the optimality criterion is not unique, in
the absence of a unique summarisation of a probability
distribution.
Not to be restricted with a completely known distribution, we
can try Bayesian Analysis, that treats some distribution
parameter (s) as random, with some assumed prior
distribution (s). Hyper-parameters are assumed as known.
Several decision problems like the Secretary Selection problem
or the problem of locating the optimal design point in terms of
the estimated response function in a multi-factor experiment
or the problem of determining the parameters in a single
sampling inspection plan by attributes are not usually
recognised as O.R. problems.
These, however, involve stochastic optimisation in a broad
sense. Similar is the case with some problems in control theory
In fact, many problems in Statistics and its applications also
take recourse to stochastic optimisation.
A second view of Stochastic Optimisation emerged in the
context of various search procedures or meta-heuristics to
arrive at some optimal or near-optimal solution to complex
optimisation problems faced quite often in the context of
combinatorial optimisation of functions—not necessarily
complex or probabilistic—subject to constraints—which also
are not always complicated or probabilistic.
Usually, a huge number of possible solutions ( not all feasible )
exists, and stochasticity in such a context relates to the
concrete use of randomness in the search for an optimal
solution. Combinatorial optimisation may also have to reckon
with randomnes in the objective function, e.g. in a situation
involving random processing times in a sequencing problem.
In the second view of stochastic optimisation, we introduce
certain probabilities for generating new solutions and /or for
accepting or rejecting a new solution. Certain decisions about
these probabilities ( including the ways these are to be found
out numerically) have to be taken pro-actively before the
search. There are varying suggestions here.
Let us consider the Secretary Selection Problem which has
been examined by various authors . The simplest
formulation runs like the following
There are n candidates who can be ranked according to
some selection criterion (criteria) from 1 ( best) to n (worst) and there is no tie. We interview I randomly selected
candidates one by one and select the best of these I
candidates ( or the candidate with the smallest rank in the sample). Let r be the rank of the selected candidate in the
population of candidates with the expected value E (r).
is a minimum.
We can make the formulation more acceptable by adding a
chance constraint on i such that
Pr{ lr - r_0l ≥ m } ≤ α} ( pre-assigned small)
where r_0 and m are very small integers.
This innocent problem in the integer variable i is a
chance-constrained non-linear integer programming problem.
A simple algorithm has been offered by Mukherjee and Mandal. |