New estimate for the curvature of an order-convex set and related questions

• Autorzy: Ramazanov Ali B.
• Języki publikacji: EN

Abstrakty

EN

It is well known that in discrete optimization problems, gradient (local) algorithms do not always guarantee an optimal solution. Therefore, the problem arises of finding the accuracy of the gradient algorithm. This is a fairly well-known problem and numerous publications have been devoted to it. In establishing accuracy, various approaches are used. One of these approaches is to obtain guaranteed estimates of the accuracy of the gradient algorithm in terms of the curvature of the admissible domain. With this approach, it is required to find the curvatures of the admissible region. Since finding the exact value of curvature is a difficult problem to solve, curvature estimates in terms of more or less simply calculated parameters of the problem are relevant. A new improved bound for the curvature of an order-convex set is found and is presented in this paper in terms of the steepness and parameters of strict convexity of the function.

Słowa kluczowe

EN

gradient; estimates; curvature; convexity; algorithm

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2020
• Tom: Vol. 49, No. 2
• Strony: 233--240
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Ramazanov Ali B.

• Institute of Applied Mathematics, Baku State University, Baku, Azerbaijan

Bibliografia

• Emelichev, V.A., Kovalev, M.M. and Ramazanov, A.B. (1992) Errors of gradient extrema of a strictly convex function of discrete argument. J. Discrete Mathematics and Applications, 2(2), 119-131.
• Emelichev, V.A. and Ramazanov, A.B. (2016) About the steepness of the function of discrete argument. TWMS Journal of Pure and Applied Mathematics 7(1), 105–111.
• Hausman, D. and Korte, B. (1978) k-Greedy algorithms for independence system. Z. Oper. Res., 22, 219–228.
• Kovalev, M.M. (2003) Matroids in Discrete Optimization. URSA, Moscow. (In Russian).
• Murota, K. (2003) On steeppest descent algorithms for discrerte convex functions. SIAM J. Optim., 14(3), 699–707.
• Ramazanov, A.B. (2008) An Estimate for the Curvature of an Order-Convex Set in the Integer Lattice and Related Questions. Math. Notes, 84(1), 147–151.
• Ramazanov, A.B. (2011) On stability of the gradient algorithm in convex discrete optimisation problems and related questions. Discrete Mathematics and Applications, 21(4), 465–476.
• Ramazanov, A.B. (2018) New of Accuracy of Gradient Algorithm in the Jordan-Dedekinds Structure. Applied and Computational Mathematics, 17(1), 109–113.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).