%0 Journal Article
%T A Newton-Type Algorithm for Solving Problems of Search Theory
%A Liping Zhang
%J Advances in Operations Research
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/513918
%X In the survey of the continuous nonlinear resource allocation problem, Patriksson pointed out that Newton-type algorithms have not been proposed for solving the problem of search theory in the theoretical perspective. In this paper, we propose a Newton-type algorithm to solve the problem. We prove that the proposed algorithm has global and superlinear convergence. Some numerical results indicate that the proposed algorithm is promising. 1. Introduction We consider the problem where , , , and is the vector of ones. The problem described by (1) is called the theory of search by Koopman [1] and Patriksson [2]. It has the following interpretation: an object is inside box with probability , and is proportional to the difficulty of searching inside the box. If the searcher spends time units looking inside box , then he/she will find the object with probability . The problem described by (1) represents the optimum search strategy if the available time is limited to time units. Such problems in the form of (1) arise, for example, in searching for a lost object, in distribution of destructive effort such as a weapons allocation problem [3], in drilling for oil, and so forth [2]. Patriksson [2] surveyed the history and applications as well as algorithms of Problem (1); see [2, Sections 2.1.4, 2.1.5, and 3.1.2]. Patriksson pointed out that Newton-type algorithms have not been theoretically analyzed for the problem described by (1) in the references listed in [2]. Recently, related problems and methods were considered in many articles, for example, [4¨C6]. For example, a projected pegging algorithm was proposed in [5] for solving convex quadratic minimization. However, the question proposed by Patriksson [2] was not answered in the literature. In this paper, we design a Newton-type algorithm to solve the problem described by (1). We show that the proposed algorithm has global and superlinear convergence. According to the Fischer-Burmeister function [7], the problem described by (1) can be transformed to a semismooth equation. Based on the framework of the algorithms in [8, 9], a smoothing Newton-type algorithm is proposed to solve the semismooth equation. It is shown that the proposed algorithm can generate a bounded iteration sequence. Moreover, the iteration sequence superlinearly converges to an accumulation point which is a solution to the problem described by (1). Numerical results indicate that the proposed algorithm has good performance even for . The rest of this paper is organized as follows. The Newton-type algorithm is proposed in Section 2. The global
%U http://www.hindawi.com/journals/aor/2013/513918/