The return of the linear search problem

The linear search problem concerns a search on the real line for a point selected at random according to a given probability distribution. The search begins at zero and is made by a continuous motion with constant speed, first in one direction and then the other. The problem is to determine when it is possible to devise a “best” search plan. In former papers the best plan has been selected according to the criterion of minimum expected path length. In this paper we consider a more general, nonlinear criterion for a “best” plan and show that the substantive requirements of the earlier results are not affected by these changes.     

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.     

Multiplicative linear search for a brownian target motion

This paper investigates a search problem for a brownian target motion on one of n-intersected real lines in which any information of the target position is not available to the searchers all the time. We have n-searchers start searching for the target from the origin that is the intersection point of these lines. Each of the searchers moves continuously along his line in both directions of the starting point. The purpose of this paper is to formulate a search model and find the condition under which the expected value of the first meeting time between one of the searchers and the target is finite. Also, we show the existence of the optimal search plan which minimizes the expected value of the first meeting time and find it.     

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.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

Yet more on the linear search problem

The linear search problem has been discussed previously by one of the present authors. In this paper, the probability distribution of the point sought in the real line is not known to the searcher. Since there is noa priori choice of distribution which recommends itself above all others, we treat the situation as a game and obtain minimax type solutions. Different minimaxima apply depending on the factors which one wishes to minimize (resp. maximize). Certain criteria are developed which help the reader judge whether the results obtained can be considered “good advice” in the solution of real problems analogous to this one. The research of this paper has been supported in part by the following agencies: National Science Foundation, Wisconsin Alumni Research Foundation, German Academic Exchange Service (DAAD), and Air Force Office of Scientific Research.     

SAPI: Statistical Analysis of Propagation of Incidents. A new approach for rescheduling trains after disruptions

In this paper, we present a new approach to solve the railway rescheduling problem. This problem deals with the reparation of a disturbed railway timetable after incidents in such a way to minimize the difference between the original plan and the new provisional plan. We use a mixed integer linear programming (MIP) formulation that models this problem correctly. However, the large number of variables and constraints denies the possibility to solve this problem efficiently using a standard MIP solver. A new approach called SAPI (Statistical Analysis of Propagation of Incidents) has been developed to tackle the problem. The key point of SAPI is to estimate the probability that an event, one step of the itinerary of a train, is affected by a set of incidents. Using these probabilities, the search space is reduced, obtaining very good solutions in a short time. The method has been tested with two different networks located in France and Chile. The numerical results show that our procedure is viable in practice.     

Son of the linear search problem

I wish to find something which is located on a certain road. I start at a point on the road, but I do not know in which direction the object sought is to be found. Somehow, I must incorporate in my way of searching the possibility that it is either to the right or to the left. Thus, I must search first to the right, and then to the left, and then to the right again until it is found. What is a good way of conducting this search, and what is a bad way? This general problem can be phrased in many ways mathematically, some of which are answered in the papers in the bibliography. In this paper, we consider three well-known assumptions concerning thea priori guesses for the probability distribution on where the object is located. These concern uniform distribution on an interval, triangular distribution around the original point, and normal distribution about that point. The uniform distribution has a simple answer. For the triangular distribution, we obtain qualitative results and calculate approximate values for the turning points.     

Hitting Times in Markov Chains with Restart and their Application to Network Centrality

Motivated by applications in telecommunications, computer science and physics, we consider a discrete-time Markov process with restart. At each step the process either with a positive probability restarts from a given distribution, or with the complementary probability continues according to a Markov transition kernel. The main contribution of the present work is that we obtain an explicit expression for the expectation of the hitting time (to a given target set) of the process with restart. The formula is convenient when considering the problem of optimization of the expected hitting time with respect to the restart probability. We illustrate our results with two examples in uncountable and countable state spaces and with an application to network centrality.     

Selection of intensity modulated radiation therapy treatment beam directions using radial basis functions within a pattern search methods framework

The selection of appropriate radiation incidence directions in radiation therapy treatment planning is important for the quality of the treatment plan, both for appropriate tumor coverage and for better organ sparing. The objective of this paper is to discuss the benefits of using radial basis functions within a pattern search methods framework in the optimization of the highly non-convex beam angle optimization (BAO) problem. Pattern search methods are derivative-free optimization methods that require few function value evaluations to converge and have the ability to avoid local entrapment. These two characteristics gathered together make pattern search methods suited to address the BAO problem. The pattern search methods framework is composed by a search step and a poll step at each iteration. The poll step performs a local search in a mesh neighborhood and assures convergence to a local minimizer or stationary point. The search step provides the flexibility for a global search since it allows searches away from the neighborhood of the current iterate. Radial basis functions are used and tested in this step both to influence the quality of the local minimizer found by the method and to obtain a better coverage of the search space in amplitude. A set of retrospective treated cases of head-and-neck tumors at the Portuguese Institute of Oncology of Coimbra is used to discuss the benefits of using this approach in the optimization of the BAO problem.     

An SQP approach with line search for a system of nonlinear equations

In this paper, a line search sequential quadratic programming (SQP) approach to a system of nonlinear equations (SNE) is taken. In this method, the system of nonlinear equations is transformed into a constrained nonlinear programming problem at each step, which is then solved using SQP algorithms with a line search strategy. Furthermore, at each step, some equations, which are satisfied at the current point, are treated as constraints and the others act as objective functions. In essence, constrained optimization strategies are utilized to cope with the system of nonlinear equations.     

Optimal Positioning of a Mobile Service Unit on a Line

In this paper we address the problem of locating a mobile response unit when demand is distributed according to a random variable on a line. Properties are proven which reduce the problem to locating a non-mobile facility, transforming the original optimization problem into an one-dimensional convex program.In the special case of a discrete demand (a simple probability measure), an algorithm which runs in expected linear time is proposed.     

A nonmonotone trust-region line search method for large-scale unconstrained optimization

We consider an efficient trust-region framework which employs a new nonmonotone line search technique for unconstrained optimization problems. Unlike the traditional nonmonotone trust-region method, our proposed algorithm avoids resolving the subproblem whenever a trial step is rejected. Instead, it performs a nonmonotone Armijo-type line search in direction of the rejected trial step to construct a new point. Theoretical analysis indicates that the new approach preserves the global convergence to the first-order critical points under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed approach for solving unconstrained optimization problems.     

一种改进的进化规划算法

本对于全局优化问题提出一个改进的进化规划算法，该算法以概率p接收基于电磁理论求出合力方向作为随机搜索方向，以概率1-p接收按正态分布产生的随机搜索方向。改进算法不仅克服了传统进化规划算法随机搜索的盲目性，而且保留了传统进化规划算法全局搜索性。本算法应用于几个典型例题，数值结果表明本算法是可行的，有效的。     

An algorithm for linearly constrained nonlinear programming problems

In this paper an algorithm for solving a linearly constrained nonlinear programming problem is developed. Given a feasible point, a correction vector is computed by solving a least distance programming problem over a polyhedral cone defined in terms of the gradients of the “almost” binding constraints. Mukai's approximate scheme for computing the step size is generalized to handle the constraints. This scheme provides an estimate for the step size based on a quadratic approximation of the function. This estimate is used in conjunction with Armijo line search to calculate a new point. It is shown that each accumulation point is a Kuhn-Tucker point to a slight perturbation of the original problem. Furthermore, under suitable second order optimality conditions, it is shown that eventually only one trial is needed to compute the step size.     

Multi-objective tabu search using a multinomial probability mass function

A tabu search approach to solve multi-objective combinatorial optimization problems is developed in this paper. This procedure selects an objective to become active for a given iteration with a multinomial probability mass function. The selection step eliminates two major problems of simple multi-objective methods, a priori weighting and scaling of objectives. Comparison of results on an NP-hard combinatorial problem with a previously published multi-objective tabu search approach and with a deterministic version of this approach shows that the multinomial approach is effective, tractable and flexible.     

Optimal ambushing search for a moving target

This paper investigates a search problem for a moving target in which a searcher can anticipate the probabilities of routes selected by the target but does not have any time information about when the target transits the route. If the searcher had some time information, he could develop an efficient search plan by varying allocations of search effort based on time. Due to the lack of time information, the searcher must ambush the target by distributing search effort to places where the target is likely to pass. There are few papers that deal mathematically with this type of search problem with no time information. Employing the criterion of detection probability, we formulate the problem and obtain necessary and sufficient conditions for the optimal solution. By applying the conditions, we propose two methods for solving the problem. The convex programming problem can be easily solved numerically by some well-known methods, e.g. the gradient projection method or the multiplier method. By numerical comparison, it is verified that the proposed methods have the excellent performance in computational time. We also elucidate some properties of the optimal distribution of search effort by some numerical examples.     

A Line Search and Trust Region Algorithm with Trust Region Radius Converging to Zero

In this paper, we present a new line search and trust region algorithm for unconstrained optimization problem with the trust region radius converging to zero. The new trust region algorithm performs a backtracking line search from the failed, point instead of resolving the subproblem when the trial step results in an increase in the objective function. We show that the algorithm preserves the convergence properties of the traditional trust region algorithms. Numerical results are also given.     

A new regularized quasi-Newton method for unconstrained optimization

In this paper, we propose a new regularized quasi-Newton method for unconstrained optimization. At each iteration, a regularized quasi-Newton equation is solved to obtain the search direction. The step size is determined by a non-monotone Armijo backtracking line search. An adaptive regularized parameter, which is updated according to the step size of the line search, is employed to compute the next search direction. The presented method is proved to be globally convergent. Numerical experiments show that the proposed method is effective for unconstrained optimizations and outperforms the existing regularized Newton method.     

Variable block search with prior information

Consider the problem of optimizing an unknown, unimodal, univariate function by direct function evaluation. This article replaces the classic criterion for evaluating search strategies, minimax, by one we feel to be more practical, minimum expected final interval of uncertainty. This latter measure of effectiveness is useful when the experimenter has some prior knowledge of the underlying function and can specify a probability distribution on the location of the optimum.We show here that for a large class of search strategies under the uniform distribution, minimax is equivalent to minimum expected final interval length, i.e., the uniform distribution represents a ‘worst-case’ prior. In addition, computational procedures are develooed for determining the optimal search strategy for arbitrary a priori distributions. Several examples are included.