Koopman’s optimal search procedure and duality in optimisation

I’ve always found duality theory in optimisation rather difficult and unintuitive, and I harbour a vague suspicion that many textbooks exagerate its importance. I have never had much use for it in practice, but reading Sperling & Dosher (1986), I came across Koopman’s optimal search ideas and here the dual problem turns out to be very simple and extremely elegant.

During WWII, Bernard Koopman’s was to help protect US convoys against German U-boots. As far as I understood the original problem was to put defensive ships in the locations where they would be most likely to catch submarines. This led him to a general formulation of search problems under constrained resources: we are looking for a certain target, we have a limited budget, and the question is how best to allocate our limited resources over possible locations. For example we could be on a witch hunt, but have only a few trained inquisitors at our disposal. Or, more prosaically, maybe we are looking for keys and the limited resource is time.

Mathematically, Koopman’s setup is as follows: a target can be in one of ${n}$ locations. If we spend an amount of time ${t}$ looking for the target in location ${k}$ , the probability of finding it grows with ${t}$ , according to:

$\displaystyle p(S|t)=1-\exp\left(-t\right)$

This assumes of course that the target actually is in location ${k}$ , otherwise the probability is 0.

Suppose we have some prior distribution ${\pi\left(x\right)}$ over target locations, and a total amount of time we can spend, ${\tau}$ . We can choose to spend time ${t_{1}}$ at location 1, ${t_{2}}$ at location 2, etc. Koopman’s search procedure finds the optimal time allocation on the condition that there are no switching costs (you don’t spend any time going from one location to the next).

Given a certain time allocation ${\mathbf{t}=\left[t_{1}\ldots t_{n}\right]}$ , the probability of finding the target is:

$\displaystyle \sum\pi_{i}\left(1-\exp\left(-t_{i}\right)\right)=1-\sum\pi_{i}\exp\left(-t_{i}\right)$

The objective is then to minimise ${\sum\pi_{i}\exp\left(-t_{i}\right)}$ , under the constraint that ${\sum t_{i}=\tau}$ , the budget constraint. Another constraint is naturally that all the ${t_{i}}$ are 0 or more. Using Boyd & Vanderberghe’s notation, the problem is:

$\displaystyle \begin{array}{rcl} & \underset{\mathbf{t}}{\mbox{argmin}} & \sum\pi_{i}\exp\left(-t_{i}\right)\\ & \mbox{subject to} & \mathbf{t}\succ0\\ & & \sum t_{i}=\tau \end{array}$

We can take that problem and express it as a Lagrangian:

$\displaystyle \mathcal{L}\left(\mathbf{t},\lambda\right)=\sum\pi_{i}\exp\left(-t_{i}\right)+\lambda\left(\sum t_{i}-\tau\right)$

I’m forgetting the inequality constraint for now.

Solving the optimisation problem is equivalent to finding a stationary point for ${\mathcal{L}\left(\mathbf{t},\lambda\right)}$ : as per usual we work out the derivatives.

$\displaystyle \frac{\partial}{\partial t_{i}}\mathcal{L}\left(\mathbf{t},\lambda\right)=-\pi_{i}\exp\left(-t_{i}\right)+\lambda$

This means the first-order stationarity condition is:

$\displaystyle \begin{array}{rcl} -\pi_{i}\exp\left(-t_{i}\right)+\lambda & = & 0\\ t_{i} & = & -\log\left(\frac{\lambda}{\pi_{i}}\right)=\log\pi_{i}-\log\lambda \end{array}$

We still have the requirement that ${t_{i}>0}$ to deal with: we reintroduce it here by setting negative ${t_{i}}$ ‘s in the unconstrained solution to 0 (see below on why it’s legal to do that here). Our solution will satisfy:

$\displaystyle t_{i}=\begin{cases} \log\pi_{i}-\log\lambda & \mbox{if}\pi_{i}>\lambda\\ 0 & \mbox{otherwise} \end{cases}$

The shape of the “dual problem” should begin to appear. The equation above states: given a certain value of ${\lambda}$ , the optimal allocation first sets a lower bound – we ignore all sites with probability less than ${\lambda}$ of containing the target. On the rest of the sites we spend ${\log\pi_{i}-\log\lambda}$ time.

This implies that one way of looking at the problem is to find the minimum value of ${\lambda}$ such that the time constraint is solved. The dual problem is then:

$\displaystyle \begin{array}{rcl} & \mbox{argmin} & \lambda\\ \mbox{subject to} & \sum_{i=1}^{n}\left\lceil \log\pi_{i}-\log\lambda\right\rceil ^{+} & =\tau \end{array}$

where ${\left\lceil x\right\rceil ^{+}}$ denotes the positive part function.

The dual problem is a trivial one-dimensional minimisation! To find the solution we could use any number of simple search procedures. For example you could first test what happens when ${\lambda=0.5}$ : if for this value we need too much search time in total, we can test ${\lambda=0.75}$ , otherwise, we could test ${\lambda=0.25}$ , and so on. Using this bisection trick we could converge very quickly to a solution.

We have reduced a ${n}$ -dimensional problem with easy constraints into a one-dimensional problem with a more complicated constraint. As far as I know all primal-dual transformations feature that kind of trade-off (no free lunch). In the case of Koopman’s problem the dual is particularly nice because writing an algorithm that finds an optimal allocation is trivially easy.

[1. A very rough note on why it’s OK to ignore the ${t_{i}>0}$ constraint in the Lagrangian, then reintroduce it later. A way to look at it is that the Lagrangian as formulated here provides the solution ignoring the constraint, so we can reintroduce the constraint by projecting on the positive quadrant. Since the stationarity conditions are separable, we can project coordinate-wise, and that’s the same as setting all negative values to 0.

A more careful argument is to add the inequality conditions to the Lagrangian, and the conclusion follows from the KKT conditions (using complementary slackness)

2. The whole thing transposes almost unchanged to the continuous case.]

References

Koopman, B. O. (1979). Search and its optimization. The American Mathematical Monthly, 86(7):527+.

Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

Sperling, G. and Dosher, B. A. (1986). Strategy and optimization in human information processing. In Boff, K., Kaufman, L., and Thomas, J., editors, Handbook of perception and human performance: Vol. 1. Sensory processes and perception. Wiley, New York.

optimisation

duality, optimal_search

May 28, 2012

dahtah