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.     

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.     

Co-ordinating Two Searchers for an Object Hidden on an Interval

Two unit-speed searchers starting at 0 seek a stationary target hidden according to a known bounded symmetric distribution. The objective is to minimize the expected time for the searchers to return to 0 after one of them has found the target. We find a general optimality condition and use it to solve the problem when the target has a uniform, triangular, or truncated, exponential distribution. The problem has applications to parallel processing and to the optimal choice of drilling depths in the search for an underground mineral.     

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.     

Coordinated search for an object hidden on the line

We consider the coordinated search problem faced by two searchers who start together at zero and can move at speed one to find an object symmetrically distributed on the line. In particular we fully analyze the case of the negative exponential distribution given by the density f(x) = e^−|x|μ/(2μ), μ > 0. The searchers wish to minimize the expected time to find the object and meet back together (with the object) at zero. We give necessary and sufficient conditions for the existence of an optimal search strategy when the target density is continuous and decreasing. We show that for the negative exponential distribution the optimal time is between 4.728μ and 4.729μ. A strategy with expected time in this interval begins with the searchers going in opposite directions and returning to the origin after searching up to successive distances 0.745μ, 2.11μ, 3.9μ, 6μ, 8.4μ,…. These results extend the theory of coordinated search to unbounded regions. It has previously been studied for objects hidden on a circle (by Thomas) and on an interval (by the author).     

More on the linear search problem

The linear search problem concerns a search made in the real line for a point selected according to a given probability distribution. The search begins at zero and is made by continuous motion with constant speed along the line, first in one direction and then the other. The problem is to search in such a manner that the expected time required for finding the point according to the chosen plan of search is a minimum. This plan of search is usually conceived of as having a first step, a second,etc., and in that case, this author has previously shown a necessary and sufficient condition on the probability distribution for the existence of a search plan which minimizes the expected searching time. In this paper, we define a notion of search in which there is no first step, but the steps are instead numbered from negative to positive infinity. These new rules change the problem, and under them, there is always a minimizing search procedure. In those cases which satisfy the earlier criterion, the solutions obtained are essentially the same as those obtained previously. The research work for this paper was supported by the National Science Foundation under grant No. GP 2559 to the University of Wisconsin.     

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 large population job search game with discrete time

A job search problem is considered, in which there is a large population of jobs initially available and a large population of searchers. The ratio of the number of searchers to the number of jobs is α. Each job has an associated value from a known distribution. At each of N moments the searchers observe a job, whose value comes from the distribution of the values of currently available jobs. If a searcher accepts a job, s/he ceases searching and the job becomes unavailable. Hence, the distribution of the values of available jobs changes over time. Also, the ratio of the number of those still searching to the number of available jobs changes. The model is presented and Nash equilibrium strategies for such problems are considered. By definition, when all the population use a Nash equilibrium strategy, the optimal response of an individual is to use the same strategy. Conditions are given that ensure the existence of a unique Nash equilibrium strategy. Examples are given to illustrate the model and present different approaches to solving such problems.     

A continuous time,deterministic, nonstationary model of economic ordering

The paper considers the problem of economic ordering for a deterministic, nonstationary environment in continuous time. Previous work on the topic is reviewed. The specification of the cost criterion common in inventory theory is called in question for nonstationary situations as far as interest cost is concerned. It is proposed to account for interest by discounting rather than in a holding cost expression. The main interest of the paper is in three versions of the problem: First an unconstrained version, for which inventory is allowed to become negative (backlogging model), second a model in which inventory is constrained to be nonnegative (non-backlogging model), and third a nonbacklogging model with a storage space constraint. For the first two problems necessary optimality conditions are derived which are based on control theory for continuous time systems with jumps in the state trajectories, especially on Blaquière's impulsive maximum principle. These conditions reduce the problem of finding an optimal ordering plan, i.e. an unknown number of optimal ordering times and for each of them an optimal order size to a one parameter search problem. Due to the possibility of multiple solutions of the optimality conditions for each ordering time, one cannot in general identify a unique candidate ordering plan for each value of the search parameter, but only a tree-structured set of such plans. The optimality conditions for the first two problem versions and for a fourth one with a storage space constraint but without a non-backlogging constraint are eventually combined to yield a solution of the storage space constrained non-backlogging version.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

First passage models for denumerable semi-Markov decision processes with nonnegative discounted costs

This paper considers a first passage model for discounted semi-Markov decision processes with denumerable states and nonnegative costs.The criterion to be optimized is the expected discounted cost incurred during a first passage time to a given target set.We first construct a semi-Markov decision process under a given semi-Markov decision kernel and a policy.Then,we prove that the value function satisfies the optimality equation and there exists an optimal(or e-optimal) stationary policy under suitable conditions by using a minimum nonnegative solution approach.Further we give some properties of optimal policies.In addition,a value iteration algorithm for computing the value function and optimal policies is developed and an example is given.Finally,it is showed that our model is an extension of the first passage models for both discrete-time and continuous-time Markov decision processes.     

Constrained Markov decision processes with first passage criteria

This paper deals with constrained Markov decision processes (MDPs) with first passage criteria. The objective is to maximize the expected reward obtained during a first passage time to some target set, and a constraint is imposed on the associated expected cost over this first passage time. The state space is denumerable, and the rewards/costs are possibly unbounded. In addition, the discount factor is state-action dependent and is allowed to be equal to one. We develop suitable conditions for the existence of a constrained optimal policy, which are generalizations of those for constrained MDPs with the standard discount criteria. Moreover, it is revealed that the constrained optimal policy randomizes between two stationary policies differing in at most one state. Finally, we use a controlled queueing system to illustrate our results, which exhibits some advantage of our optimality conditions.     

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.     

Digraph searching, directed vertex separation and directed pathwidth

The four digraph search models, directed search, undirected search, strong search, and weak search, are studied in this paper. There are three types of actions for searchers in these models: placing, removing, and sliding. The four models differ in the abilities of searchers and intruders depending on whether or not they must obey the edge directions when they move along the directed edges. In this paper, we investigate the relationships between these search models. We introduce the concept of directed vertex separation for digraphs. We also discuss the properties of directed vertex separation, and investigate the relations between directed vertex separation, directed pathwidth and search numbers in different search models.     

基于Stein-Stein波动率和动态VaR约束下DC型养老基金的最优投资策略

研究了确定缴费型养老基金在退休前累积阶段的最优资产配置问题.假设养老基金管理者将养老基金投资于由一个无风险资产和一个价格过程满足Stein-Stein随机波动率模型的风险资产所构成的金融市场.利用随机最优控制方法,以最大化退休时刻养老基金账户相对财富的期望效用为目标,分别获得了无约束情形和受动态VaR (Value at Risk)约束情形下该养老基金的最优投资策略,并获得相应最优值函数的解析表达形式.最后通过数值算例对相关理论结果进行数值验证并考察了最优投资策略关于相关参数的敏感性.     

A production–recycling–inventory system with imprecise holding costs

This paper presents an optimal control recycling production inventory system in fuzzy environment. The used items are bought back and then either put on recycling or disposal. Recycled products can be used for the new products which are sold again. Here, the rate of production, recycling and disposal are assumed to be function of time and considered as control variables. The demand inversely depends on the selling price. Again selling price is serviceable stock dependent. The holding costs (for serviceable and non-serviceable items) are fuzzy variables. At first we define the expected values of fuzzy variable, then the system is transferred to the fuzzy expected value model. In this paper, an optimal control approach is proposed to optimize the production, recycling and disposal strategy with respect so that expected value of total profit is maximum. The optimum results are presented both in tabular form and graphically.     

Less is more: Increasing retirement gains by using an upside terminal wealth constraint

We solve a portfolio selection problem of an investor with a deterministic savings plan who aims to have a target wealth value at retirement. The investor is an expected power utility-maximizer. The target wealth value is the maximum wealth that the investor can have at retirement.By constraining the investor to have no more than the target wealth at retirement, we find that the lower quantiles of the terminal wealth distribution increase, so the risk of poor financial outcomes is reduced. The drawback of the optimal strategy is that the possibility of gains above the target wealth is eliminated.     

离散时间马氏决策过程的首达目标准则

本文考虑可数状态离散时间马氏决策过程的首达目标模型的风险概率准则.优化的准则是最小化系统首次到达目标状态集的时间不超过某阈值的风险概率.首先建立最优方程并且证明最优值函数和最优方程的解对应,然后讨论了最优策略的一些性质,并进一步给出了最优平稳策略存在的条件,最后用一个例子说明我们的结果.     

Optimal prevention strategies in the classical risk model

In this paper, we propose and study a first risk model in which the insurer may invest into a prevention plan which decreases claim intensity. We determine the optimal prevention investment for different risk indicators. In particular, we show that the prevention amount minimizing the ruin probability maximizes the adjustment coefficient in the classical ruin model with prevention, as well as the expected dividends until ruin in the model with dividends. We also show that the optimal prevention strategy is different if one aims at maximizing the average surplus at a fixed time horizon. A sensitivity analysis is carried out. We also prove that our results can be extended to the case where prevention starts to work only after a minimum prevention level threshold.     

Variable target value subgradient method

Polyak's subgradient algorithm for nondifferentiable optimization problems requires prior knowledge of the optimal value of the objective function to find an optimal solution. In this paper we extend the convergence properties of the Polyak's subgradient algorithm with a fixed target value to a more general case with variable target values. Then a target value updating scheme is provided which finds an optimal solution without prior knowledge of the optimal objective value. The convergence proof of the scheme is provided and computational results of the scheme are reported.Most of this research was performed when the first author was visiting Decision and Information Systems Department, College of Business, Arizona State University.