Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times

We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non-uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each cell can take place, the problem more appropriately models the search of environments which cannot be easily partitioned into equally sized cells. An existing OSP bounding method in literature, the MEAN bound, is generalised to provide bounds for solving the new problem in a branch and bound framework. The main contribution of this paper is an enhancement, discounted MEAN (DMEAN), which greatly tightens the bound for the new and existing problems alike with almost no additional computation. We test the new algorithm against existing OSP bounding methods and show it leads to faster solution times for moving target search problems.     

Search allocation game

This paper deals with a two-person zero-sum game called search allocation game (SAG), where a searcher allocates his searching resources in a search space to detect a target while the target takes a path running across the space to evade the searcher. We consider the discrete SAG and the continuous SAG defined on the discrete search space and the continuous one, respectively. In a general way, we prove an existence theorem of equilibrium points for both the SAGs and elucidate that an equilibrium of the continuous SAG is given by a convergence point of equilibria of the discrete SAG. After then we develop a method to solve a large size of the discrete problem with specific feasibility conditions. As one of numerical examples, we take so-called flaming datum search game, which is adequate to demonstrate the convergence theorem.     

Optimal searching for a Helix target motion

This paper discusses a search problem for a Helix target motion in which any information of the target position is not available to the searchers. There exist three searchers start searching for the target from the origin. The purpose of this paper is to formulate a search model and finds the conditions under which the expected value of the first meeting time between one of the searchers and the target is finite. Also, the existence of the optimal search plan that minimizes the expected value of the first meeting time is shown. Furthermore,this optimal search plan is found. The effectiveness of this method is illustrated by using an example with numerical results.     

Finding Your Kids When They Are Lost

If two searchers are searching for a stationary target and wish to minimize the expected time until both searchers and the lost target are reunited, there is a trade off between searching for the target and checking back to see if the other searcher has already found the target. This note solves a non-linear optimization problem to find the optimal search strategy for this problem.     

Optimal search paths for random variables

Let X be a real random variable, distributed according to some symmetric distribution F. A searcher starts at the origin and moves with an upper bound on his speed until he finds X. Which search path does he have to choose in order to minimize the expected searching time (or equivalently, to minimize the expected path length)? By means of numerical methods the solution is calculated for the normal, Student, logistic and Laplace distributions.     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

Star search—A different show

An extension of the line search problem is considered in which the number of directions in which the searcher can head from the origin is arbitrary, but finite. One problem under study is when the distribution of the particle to be found has a bounded support. Sufficient conditions are established under which an optimal policy exhausts a given direction before it proceeds to another one, and the optimal order of directions in which to search is found. Special cases and some extensions are considered. A second problem has a game theoretic flavor, in particular a conjecture of Gal [13] is partially resolved.     

A two-cell model of search for an evading target

A form of game-theoretic model is proposed for the problem of search for an evading target. The region of search is divided into two cells, with the evader starting in the first cell and having the objective of moving from there, through the second to some goal area, without being detected. Optimal searcher strategy is derived in analytical form for some special cases of practical interest. The results indicate that if there is any difference in detectability in the two cells, then there is optimally a rather large concentration of search effort in the more favourable cell. The special cases are also compared numerically with some more general situations. Although both the model and the solution are relatively simple, they serve to demonstrate the potential value of this form of approach to the problem, as well as the complexity of the problem for more general situations.     

Quasi-Newton methods for multiobjective optimization problems

This work is an attempt to develop multiobjective versions of some well-known single objective quasi-Newton methods, including BFGS, self-scaling BFGS (SS-BFGS), and the Huang BFGS (H-BFGS). A comprehensive and comparative study of these methods is presented in this paper. The Armijo line search is used for the implementation of these methods. The numerical results show that the Armijo rule does not work the same way for the multiobjective case as for the single objective case, because, in this case, it imposes a large computational effort and significantly decreases the speed of convergence in contrast to the single objective case. Hence, we consider two cases of all multi-objective versions of quasi-Newton methods: in the presence of the Armijo line search and in the absence of any line search. Moreover, the convergence of these methods without using any line search under some mild conditions is shown. Also, by introducing a multiobjective subproblem for finding the quasi-Newton multiobjective search direction, a simple representation of the Karush–Kuhn–Tucker conditions is derived. The H-BFGS quasi-Newton multiobjective optimization method provides a higher-order accuracy in approximating the second order curvature of the problem functions than the BFGS and SS-BFGS methods. Thus, this method has some benefits compared to the other methods as shown in the numerical results. All mentioned methods proposed in this paper are evaluated and compared with each other in different aspects. To do so, some well-known test problems and performance assessment criteria are employed. Moreover, these methods are compared with each other with regard to the expended CPU time, the number of iterations, and the number of function evaluations.     

Optimal interception with time constraint

This paper considers the problem of minimum-fuel interception with time constraint. The maneuver consists of using impulsive thrust to bring the interceptor from its initial orbit into a collision course with a target which is moving on a well-defined trajectory. The intercept time is either prescribed or is restricted to be less than an upper limit.The necessary conditions and the transversality conditions for optimality are discussed. The method of solution amounts to first solving a set of equations to obtain the primer vector for an initial one-impulse solution. Then, based on the information provided by the primer vector, rules are established to search for the optimal solution if the initial one-impulse trajectory is not optimal. The method is general, in the sense that it allows for solving the problem of three-dimensional interception with arbitrary motion for the target.Several numerical examples are presented, including orbital interceptions and interception at hyperbolic speeds of a ballistic missile.This research was supported by US Army Strategic Defense Command, Contract No. DASG60-88-C-0037.     

The search for an alerted moving target

We investigate a two-sided, multi-stage search problem where a continuous search effort is made by one or more search units to detect a moving target in a continuous target space, under noisy detection conditions. A specific example of this problem is hunting for an enemy submarine by naval forces. So far, this problem has not been solved, because of the difficulty of predicting the target's behaviour. In finding promising routes for the search units, a heuristic has been developed. To obtain these routes, at every decision moment in time an optimal point to go to must be determined. This amounts to finding at every decision moment an optimum of a function that changes over time.     

Optimal discrete search with imperfect specificity

A target is hidden in one of several possible locations, and the objective is to find the target as fast as possible. One common measure of effectiveness for the search process is the expected time of the search. This type of search optimization problem has been addressed and solved in the literature for the case where the searcher has imperfect sensitivity (possible false negative results), but perfect specificity (no false positive detections). In this paper, which is motivated by recent military and homeland security search situations, we extend the results to the case where the search is subject to false positive detections.     

On optimal search plans to detect a target moving randomly on the real line

A target, whose initial position is unknown, is performing a random walk on the integers. A searcher, starting at the origin, wants to follow a search plan for which E[τ^k] is finite, where k ≥ 1 and τ is the time to capture. The searcher, who has a prior distribution over the target's initial position, can move only to adjacent positions, and cannot travel faster than the target. Necessary and sufficient conditions are given for the existence of search plans for which E[τ^k] is finite and a minimum.     

A new branch and bound algorithm for solving quadratic programs with linear complementarity constraints

In order to find a global solution for a quadratic program with linear complementarity constraints (QPLCC) more quickly than some existing methods, we consider to embed a local search method into a global search method. To say more specifically, in a branch-and-bound algorithm for solving QPLCC, when we find a new feasible solution to the problem, we utilize an extreme point algorithm to obtain a locally optimal solution which can provide a better bound and help us to trim more branches. So, the global algorithm can be accelerated. A preliminary numerical experiment was conducted which supports the new algorithm.     

A novel job search problem in hybrid uncertain environment

This paper investigates a novel job search problem in a hybrid uncertain environment. Hybrid uncertainty consists of the randomness in search process and the fuzziness of offered wage. The expected value criterion and the risk tolerance criterion are designed for the job searcher to accept or reject the job offer. Under these two criteria, computing formulas to calculate the expected return of the job searcher are presented. Simultaneously, the average search times and the average chances that search returns exceed reservation wages are provided. Finally, a numerical example is given to illustrate the relationships between the expected returns of the job searcher under two criteria, and the relationships between two average chances as well.     

LINEAR SEARCH FOR A BROWNIAN TARGET MOTION

A target is assumed to move according to a Brownian motion on the real line. The searcher starts from the origin and moves in the two directions from the starting point.The object is to detect the target. The purpose of this paper is to find the conditions under which the expected value of the first meeting time of the searcher and the target is finite,and to show the existence of a search plan which made this expected value minimum.     

An automated surface surveillance system

This paper describes an automated surface surveillance system, developed on behalf of the Government of Canada to detect and track illegal vessels. The scenario involves a moving target having speed significantly less than the searcher speed, slowly approaching Canada's coastline. The crux of the surveillance problem is to determine the sequence of sub-regions to search in order to maximize the probability of target detection. The complexity of our surveillance problem lies in the absence of knowledge on the target location, speeds and course. Additionally, the searcher is frequently confronted with insufficient time to area search the sub-regions. The presence of false targets and the occurrence of irregular search area further compound the problem. Our decision support system is a combination of established theories on probability maps, barrier patrol and a novel construction of heuristics for area searching irregular regions. Our approach also involves extensive use of visualization tools to aid code debugging and validation. More importantly, our automated surveillance system provides a user-friendly environment for decision planners.     

Monte Carlo methods for mean-risk optimization and portfolio selection

Stochastic programming is a well-known instrument to model many risk management problems in finance. In this paper we consider a stochastic programming model where the objective function is the variance of a random function and the constraint function is the expected value of the random function. Instead of using popular scenario tree methods, we apply the well-known sample average approximation (SAA) method to solve it. An advantage of SAA is that it can be implemented without knowing the distribution of the random data. We investigate the asymptotic properties of statistical estimators obtained from the SAA problem including examining the rate of convergence of optimal solutions of the SAA problem as sample size increases. By using the classical penalty function technique and recent results on uniform exponential convergence of sample average random functions, we show that under some mild conditions the statistical estimator of the optimal solution converges to its true counterpart at an exponential rate. We apply the proposed model and the numerical method to a portfolio management problem and present some numerical results.     

Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.     

The Lie-Group Shooting Method for Solving Multi-dimensional Nonlinear Boundary Value Problems

This paper presents a Lie-group shooting method for the numerical solutions of multi-dimensional nonlinear boundary-value problems, which may exhibit multiple solutions. The Lie-group shooting method is a powerful technique to search unknown initial conditions through a single parameter, which is determined by matching the multiple targets through a minimum of an appropriately defined measure of the mis-matching error to target equations. Several numerical examples are examined to show that the novel approach is highly efficient and accurate. The number of solutions can be identified in advance, and all possible solutions can be numerically integrated by using the fourth-order Runge–Kutta method. We also apply the Lie-group shooting method to a numerical solution of an optimal control problem of the Duffing oscillator.