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–6]. 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
References
[1]
B. O. Koopman, Search and Screening. General Principles with Historical Applications, Military Operations Research Society, Alexandria, Va, USA, 1999.
[2]
M. Patriksson, “A survey on the continuous nonlinear resource allocation problem,” European Journal of Operational Research, vol. 185, no. 1, pp. 1–46, 2008.
[3]
V. V. Popovich, Y. A. Ivakin, and S. S. Shaida, “Theory of search for moving objects,” in Proceedings of the IEEE Ocean Conference and Exhibition, pp. 1319–1329, Biloxi, Miss, USA, October 2002.
[4]
W. Chen, Y. J. Shi, H. F. Teng, X. P. Lan, and L. C. Hu, “An efficient hybrid algorithm for resource-constrained project scheduling,” Information Sciences, vol. 180, no. 6, pp. 1031–1039, 2010.
[5]
S. M. Stefanov, “Convex quadratic minimization subject to a linear constraint and box constraints,” Applied Mathematics Research Express, vol. 2004, no. 1, pp. 17–42, 2004.
[6]
C. L. Sun, J. C. Zeng, and J. S. Pan, “An improved vector particle swarm optimization for constrained optimization problems,” Information Sciences, vol. 181, no. 6, pp. 1153–1163, 2011.
[7]
A. Fischer, “A special Newton-type optimization method,” Optimization, vol. 24, no. 3-4, pp. 269–284, 1992.
[8]
L. Zhang, S.-Y. Wu, and T. Gao, “Improved smoothing Newton methods for nonlinear complementarity problems,” Applied Mathematics and Computation, vol. 215, no. 1, pp. 324–332, 2009.
[9]
L. P. Zhang and Y. Zhou, “A new approach to supply chain network equilibrium models,” Computers & Industrial Engineering, vol. 63, pp. 82–88, 2012.
[10]
R. Mifflin, “Semismooth and semiconvex functions in constrained optimization,” SIAM Journal on Control and Optimization, vol. 15, no. 6, pp. 959–972, 1977.
[11]
L. Qi, “Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems,” Mathematics of Operations Research, vol. 24, no. 2, pp. 440–471, 1999.
[12]
L. Q. Qi and J. Sun, “A nonsmooth version of Newton's method,” Mathematical Programming, vol. 58, no. 3, pp. 353–367, 1993.
[13]
F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons, New York, NY, USA, 1983.
[14]
X. Chen, L. Qi, and D. Sun, “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities,” Mathematics of Computation, vol. 67, no. 222, pp. 519–540, 1998.
[15]
L. Q. Qi, “Convergence analysis of some algorithms for solving nonsmooth equations,” Mathematics of Operations Research, vol. 18, no. 1, pp. 227–244, 1993.
[16]
C. Wilkinson and S. K. Gupta, “Allocation promotional effort to competing activities: a dynamic programming approach,” in Proceedings of the International Federation of Operational Research Societies Conference (IFORS '69), pp. 419–432, Venice, Italy, 1969.
