Abstract

This paper investigates the application of the Kiefer-Wolfowitz (KW) algorithm, a stochastic approximation technique, to solve the newsvendor problem under uncertain demand. The proposed approach enables the newsvendor to learn from observed profits and converge to the optimal order quantity, even when the demand distribution is unknown. Numerical experiments demonstrate the algorithm's effectiveness in handling stochastic demand and provide insights into its convergence properties. The paper highlights the potential of stochastic approximation methods in tackling inventory management challenges and discusses future research directions.

1. Introduction

The newsvendor problem, also known as the single-period inventory management problem, is a classic model in operations research and management science. It describes a scenario where a decision-maker needs to determine the optimal order quantity of a product with uncertain demand to maximize expected profit. The problem can be formulated as follows.

A newsvendor needs to order newspapers in advance from the post office and determine the quantity of newspapers to order, denoted as copies, at a price of per copy. The selling price of each newspaper is known to be per copy. If the newsvendor does not sell all the newspapers on that day, the recycling center will buy back the newspapers at a price of per copy. Let the daily demand for newspapers be . If , the daily remainder of newspapers is ; otherwise, it is 0. Thus, the newsvendor's profit is:

(1)

In practical problems, the demand for newspapers is usually a random variable, which leads to the profit function also being a random variable. Since it is not possible to accurately predict the actual profit from ordering newspapers, a natural method is to consider the expected profit:

(2)

where represents the probability density function of the demand . The newsvendor problem is to find the optimal order quantity that maximizes the expected profit .

The newsvendor model has been widely applied in various industries, such as retail, fashion, and perishable goods, to guide inventory decisions. Extensive research has been conducted on the newsvendor problem since its introduction. Arrow et al. ¹ laid the foundation for the newsvendor model by deriving the optimal order quantity under stochastic demand. Subsequently, numerous extensions and variations of the model have been proposed to capture different real-world settings. For example, Khouja ² provided a comprehensive review of the single-period inventory problem and its extensions, considering factors such as pricing, discounting, and supplier credits. Qin et al. ³ reviewed the newsvendor problem under supply chain coordination, addressing issues like contracts, information sharing, and risk management.

The original work in recursive stochastic algorithms was by Robbins and Monro, who developed and analyzed a recursive procedure for finding the root of a real-valued function of a real variable . The function is not known, only noise-corrupted observations could be taken at any values of selected by the experimenter. If the analytic form of were known and continuously differentiable, then the problem would be classical in numerical analysis, and many procedures, such as Newton's method, could be used. However, in many practical problems, people do not know the form of the nonlinear function in the equation and can only observe the function values with random errors at given values of the independent variable. In this case, how to find the zero point of this unknown nonlinear function is an important problem from both practical and theoretical perspectives. If is the value of the independent variable taken at the measurement, then the observed value of the function is:

(3)

where is a sequence of measurement errors that may depend on . In 1951, Robbins and Monro first proposed and studied a stochastic approximation algorithm. They took the sequence as:

(4)

The approximation to the zero point is:

(5)

where is obtained from (3). This is the well-known Robbins-Monro (RM) algorithm.

In the year following the proposal of the RM algorithm, the Kiefer-Wolfowitz (KW) algorithm appeared, which is an algorithm for finding the extreme value of . The basic idea of the KW algorithm is similar as the RM algorithm. In essence, it seeks the zero point of the derivative of . The difference quotient of the measured values of is used to estimate the value of the derivative of . Therefore, compared with the RM algorithm, except for some changes in the measurement points, the basic form of the algorithm and the basic ideas of theoretical research are consistent.

Stochastic approximation problems have consistently attracted the attention of many applied mathematicians, statisticians, and systems and control experts. The involved fields include process statistics, system identification and parameter estimation, adaptive control, stochastic optimization and decision-making, and signal processing. Relevant papers and monographs can be referred to ⁶ and its references.

This paper aims to tackle the newsvendor problem using stochastic approximation, a powerful technique for solving stochastic optimization problems. The key advantage of stochastic approximation is its ability to handle uncertain parameters, making it suitable for dynamic inventory control settings.

The remainder of this paper is organized as follows. Section 2 shows the motivation and implementation of applying the stochastic approximation method to the newsvendor problem. Section 3 provides numerical experiments to demonstrate the effectiveness of the proposed approach. Finally, Section 4 concludes the paper and discusses future research directions.

2. Applying Stochastic Approximation to the Newsvendor Problem

As discussed in the Introduction, the common approach to solving the Newsvendor Problem is to find the maximum value of equation (2). When is known and simple, we can obtain an analytical solution. When is complex, we can use Monte-Carlo integration or genetic algorithms to calculate the integral and solve (2). However, in most real-life situations, is unknown. In such cases, we cannot compute the integral in (2) and can only calculate the "contaminated" profit from (1). This is precisely the type of problem that stochastic approximation algorithms excel at solving. Motivated by this, we will employ the Kiefer-Wolfowitz (KW) algorithm to find the optimal solution.

The stochastic approximation algorithm for solving the Newsvendor Problem is as follows:

Step 0: Estimate the number of newspapers to order on the first day, , based on experience.

Repeat:

Step 1: Let be the number of newspapers ordered on the day. Calculate:

(6)

Step 2: Calculate the number of newspapers to order on the day:

(7)

End Repeat.

In Step 1, is the difference estimate of the derivative of :

(8)

We take here because the number of newspapers ordered must be an integer. Since we know the profit for , it is very easy to calculate the profit for ordering one more and one less newspaper order.

3. Numerical Examples

We consider several scenarios in this section.

Example 1: We consider the newspaper selling price, buy back price , and order price . If the daily demand for newspapers follows a uniform distribution on [0, 40], calculating (2), we can obtain the best order number . Using the KW algorithm and setting , we obtain the graph shown in Figure 1.

As evident from Figure 1, the algorithm gradually converges to the vicinity of and fluctuates between 29 and 31. The average value is 29.95.

Remark: The graph reveals that the convergence speed of to the optimal value is relatively slow. In practical situations, the following method can be employed to accelerate convergence: after collecting demand quantities for approximately 100 days, we can use the bootstrap method to simulate the entire distribution of through resampling, and then substitute the results into the algorithm for iteration.

Example 2: We consider the selling price , buy back price , and order price . If follows a normal distribution , the optimal solution given in the literature ⁷ is . Using the KW algorithm and setting , we obtain the graph shown in Figure 2.

The graph illustrates that the algorithm gradually converges to the vicinity of . The average value is 95.87.

4. Conclusion

In this paper, we have demonstrated the effectiveness of applying stochastic approximation algorithms, specifically the Kiefer-Wolfowitz (KW) algorithm, to solve the newsvendor problem under uncertain demand. The proposed approach offers a practical solution for determining optimal order quantities in real-world settings where the demand distribution is unknown or complex.

Through numerical examples, we have shown that the KW algorithm can successfully converge to the optimal order quantity, even when the demand follows various probability distributions. The algorithm's ability to handle stochastic demand and learn from observed profits makes it a valuable tool for dynamic inventory management.

However, our numerical experiments also reveal that the convergence speed of the algorithm can be relatively slow in certain cases. This highlights the need for further research on accelerating the convergence of stochastic approximation algorithms in the context of the newsvendor problem. Potential avenues for improvement include incorporating bootstrap methods to simulate demand distributions and using the results to guide the algorithm's iterations.

Moreover, theoretical analysis of the convergence properties and performance guarantees of the KW algorithm in the newsvendor setting is an important direction for future research. Establishing rigorous convergence results and deriving bounds on the algorithm's performance would provide a stronger foundation for its application in practice.

In conclusion, this paper opens up new possibilities for tackling the newsvendor problem under uncertainty using stochastic approximation techniques. The promising results obtained through numerical experiments motivate further exploration of this approach, both in terms of theoretical analysis and the development of more efficient algorithms. By advancing research in this direction, we can enable better inventory decision-making in a wide range of industries facing stochastic demand.

ACKNOWLEDGEMENTS

The authors are grateful to the reviewers to review this research article and also given great suggestions for improvement this research article.

References