Methods for Minimizing the Savage Function with Various Constraints

Abstract

Introduction. When making decisions under uncertainty, Savage's criterion is sometimes used, or the criterion of minimizing regrets [1]. Usually, in the literature, this decision situation is described in matrix language. In other words, both the number of decision alternatives and the number of states of nature are finite. Of particular interest are situations where the admissible domain of decision variants is a convex set, and the regrets with respect to each state of nature are expressed by convex functions. In this paper, we propose numerical methods for minimizing Savage's regret function, constructed based on the subgradient projection method with automatic step size adjustment [2, 3]. The convergence of these methods is demonstrated. Goal. In the article, the Savage function is defined as a function that expresses the maximum regret value, assumed to be a convex function with respect to the decision factors. This function measures the effectiveness of each decision relative to the set of states of nature. It is important to note that computing the values of these functions is complex because of the need to know the optimal solution for each state of nature. This difficulty is successfully overcome in the process of solving the problem of minimizing functions on convex sets, thanks to parallel solutions of m "internal" algorithms based on the number of states of nature, and one external algorithm, aimed at minimizing the Savage function. Each of the m+1 algorithms represent modifications of the subgradient projection method with a programmable way of adjusting the step size. Depending on the complexity of the constraints and the required precision, three theorems have been proven, confirming the convergence of the investigated methods. Results obtained. Constructive numerical algorithms have been developed for determining optimal decision alternatives under uncertainty, when the number of states of nature is finite, the admissible domain of control factors is convex and compact, and the Savage regret function serves as a decision criterion. The convergence of the corresponding algorithms to the set of optimal solutions has been proven, without knowing the exact values of the Savage function. Instead, estimates obtained from parallel runs of algorithms were used, aimed at determining optimal solutions for each state of nature. Conclusions. Uncertainty poses significant difficulties in designing and making decisions. Any decision made under uncertainty represents a certain risk or a certain regret. In cases where the number of states of nature is finite, the decision domain is convex, the target function with respect to each state of nature is convex, and the Savage regret function is adopted as the decision criterion, the decision-making problem can be successfully solved using numerical algorithms based on the generalized gradient method. The implementation of the algorithm is relatively simple, and the fields of application can be very diverse.

Keywords

• uncertainty
• decisions
• savage function
• optimization