2025, issue 3, p. 53-58
Received 09.07.2025; Revised 19.08.2025; Accepted 02.09.2025
Published 29.09.2025; First Online 30.09.2025
https://doi.org/10.34229/2707-451X.25.3.4
Regret Function Minimization Algorithms
Anatolie Baractari 1 
, Borys Chumakov 2 , Anatol Godonoaga 1 *
1 Academy of Economic Studies of Moldova, Chisinau
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The article addresses the problem of making optimal decisions under uncertainty by minimizing the Savage regret function. This function, which evaluates the difference between the actual outcome and the best possible outcome across all states of nature, is particularly useful in contexts where decision-makers are risk-averse and sensitive to potential loss. The authors propose two algorithms grounded in the subgradient projection method, adapted to handle a large number of possible states and constraints in a computationally efficient manner.
Unlike classical approaches where all states of nature and constraints are evaluated at each iteration, the developed algorithms focus on reduced, representative subsets. This significantly reduces the computational load without sacrificing convergence to the optimal solution. The first algorithm deals with problems that include uncertainty but are unconstrained or lightly constrained. The second extends the approach to more general constraint sets. In both cases, theoretical guarantees regarding convergence are established under specific step-size and selection sequence conditions.
The paper highlights how the algorithms avoid the need for computing exact values of the Savage function and its subgradients by using approximations that converge to the true values. This characteristic enhances the applicability of the methods to real-world scenarios where exact modeling of every possible state of nature is infeasible.
Future research will focus on implementing and testing these methods on practical problems from economics and operations research, where decision-making under uncertainty is frequent and the number of constraints or states is high. These algorithms offer a practical balance between computational feasibility and decision quality.
The purpose of the paper is to develop and justify effective algorithms for regret function minimization in decision-making processes under uncertainty, while ensuring convergence through reduced computational effort by operating on selected subsets of constraints and states.
Results. Two algorithms are proposed, each using a modified subgradient projection technique. The first addresses unconstrained or lightly constrained decision problems, while the second handles more general constraints. In both cases, convergence to the optimal regret-minimizing solution is theoretically proven. The computational complexity is significantly reduced without loss of accuracy, thanks to the iterative use of partial subsets at each step.
Conclusions. The proposed algorithms provide a reliable and efficient framework for solving regret-based decision problems. They are particularly suitable for large-scale applications where traditional methods are computationally intensive or infeasible. The techniques allow approximation of regret values and subgradients with sufficient accuracy to guarantee convergence.
Keywords: decision-making, uncertainty, regret minimization, Savage function, subgradient method, convex optimization.
Cite as: Baractari A., Chumakov B., Godonoaga A. Regret Function Minimization Algorithms. Cybernetics and Computer Technologies. 2025. 3. P. 53–58. https://doi.org/10.34229/2707-451X.25.3.4
References
1. Hamdy A. T. Operations Research. Collier Macmillan Publishers, London ,1982.
2. Savage L.J. The theory of statistical decision. J. Amer. Statist. Assoc. 1951. 46 (1). P. 55–67. https://doi.org/10.1080/01621459.1951.10500768
3. Godonoaga A.F., Blanutsa S.A., Chumakov B.M. Methods for minimizing the Savage function with various constraints. Cybernetics and Computer Technologies. 2024. 1. P. 18–26. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.1.2
4. Shor N.Z. Nondifferentiable optimization and polynomial problems. Boston, Kluwer Academic Publishers, 1998. https://doi.org/10.1007/978-1-4757-6015-6
5. Yermolyev Yu.M. Methods of stochastic programming. M.: Nauka, 1976. 240 p. (in Russian)
6. Godonoaga A.F., Chumakov B.M. Deterministic and stochastic schemes of the subgradient projection method. Theory of optimal solutions. 2015. 14. P. 90–97. (in Russian) http://jnas.nbuv.gov.ua/article/UJRN-0000475038
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)