Many problems in economics, industry, science, as well as the problems of managing complex technical objects lead to the need to solve optimization problems. The problem of constructing algorithms for the approximate solution of optimization problems is of considerable interest. To do this, the properties of the space of variables are investigated and the regularities of the behavior of functions in this space are revealed. The paper describes the application of greedy algorithms to obtain estimates of functions in special classes. Sparse representations of a function are not only a powerful analytical tool, but they are used in many areas, such as image processing, signal processing, numerical computing, directly in optimization problems, as they significantly increase the ability to process large data sets. The key to the search for sparse representations is the concept of -term approximation of the objective function by the elements of this system of functions. A universal method that allows this is the greedy algorithm, the principle of which is to use the greedy step in search of a new element to be added to this -term approximation. In this work, using approximations by greedy algorithms (ψ, β)-differentiable functions in Lebesgue spaces, the exact order estimates under conditions 1 < < ≤ 2, 1 < ≤ 2 ≤ < ∞ and 2 ≤ p ≤ q < ∞ were found. The estimates obtained allow us to effectively use mathematical models that describe the routes between atomic nodes of the system, which require the use of (ψ, β)-differentiable functions in the space , in optimization problems.
The solution of most real problems in the field of decision-making requires the formalization of the situation when the choice should be made, in the form of an optimization problem of a certain class. The optimal choice of one of several valid alternatives according to a certain criterion corresponds to the assignment of variables to specific values from the range of acceptable approximation, greedy algorithms, best approximations, values. Often variables can take only one of two values - zero or one. The corresponding problems are called optimization problems with Boolean variables or pseudo-Boolean optimization problems. This issue has been actively studied in recent years in the works of many scientists [1-11]. This approach allows to obtain good results for adaptive algorithms for optimal prefix coding of the alphabet with minimal redundancy, algorithms for finding a minimum weight ∑ ̂( ) , ̂( )=
∫ ( ) − For a function ∈ 1, we consider its Fourier ∈ℤ 1 2 −
− spanning tree in a graph and finding a minimum weight spanning tree in a connected graph, and so [− , ]. The norm in this space is defined as follows: on.
In essence, these are greedy algorithms, which implement the following principles: at each step of the algorithm we abstract from the previous and next steps and think only about the optimal solution at this stage. The approach does not provide for the cancellation of the choice already made (return to previous steps) and does not predict anything for the future; the speed of program execution is easy to predict, because the complexity of the algorithm is linear. However, it is necessary to understand when this approach can be used and
when not. Even if the greedy algorithm gives the optimal solution in certain cases, it is difficult to prove that the approach will work in all other possible cases.
Most known optimization methods involve specifying objective functions and constraints in the form of algebraic expressions, while in many real problems some or all functions are given, algorithmically, which
makes it impossible to apply standard algorithms to them; and requires the development of search engine optimization procedures and their evaluation. At the same time, the analysis of many practical problems, to the solution of
which greedy algorithms can be applied, allows to reveal in them some features in the form of constructive properties, inherent both in objective functions, and the restriction imposed by the conditions of the problem. It should also be noted that when solving a specific problem, it is useful to have information about the effectiveness of algorithms, which allows you to get the result with the appropriate accuracy.
Often, when solving practical problems, the researcher deals with a specific problem statement. This paper aims to evaluate the solutions of a class of problems described by certain essentially bounded for = ∞), on the segment are the Fourier coefficients of the function . In what follows, we always assume that the function ∈ 1 satisfies the condition ∫ ( ) = 0.
Further, let
≠ 0, be an arbitrary function of natural argument and let be an arbitrary fixed real number. If a series
∑ ∈ℤ\{0} ̂( ) (| |) ( + 2sign ) is the Fourier series of a summable function, then, following Stepanets [12] we can introduce the ( , )–derivative of the function and denote it by . By
we denote the set of functions
If satisfying this condition. In what follows we assume that the function belongs to the class , if ∈ , and ∈ = { : ∈ , ∥ ∥ ≤ 1},
1 ≤ ≤ ∞.
(| |)= | |− , > 0, ∈ ℤ\{0}, ) in the Weyl–Nagy sense. then the
( , )–derivative of the function coincides with its ( , )–derivative (denoted by ( e 1 2 −
{ ∈[− , ]
sup| ( )| , = series where ∥ ∥ =∥ ∥ = 1 ∫ | ( )| ) , 1 ≤ < ∞, = ∞. arranged in non-increasing order of their absolute ( , )= ∑ ̂( ( )) and if ⊂ is a certain function class, then we set
( ) : = sup ∥ (⋅)− ( ,⋅)∥ . (1) At present, there are many works devoted to the investigation of quantity (1) for important 2) there exists a constant > 0 such that
Thus, the functions 1 , > 0; ln ( +1), ∈ ℝ, > 0, ∈ ℕ, and some other functions belong to the set .
For the quantities and , the notation ≍ means that there exist positive constants 1 and 2 such that 1 ≤
≤ 2 . If ≥ 1 ), than we can write ≪ ≤ 2 ( (
≥ ≫ ). All , = 1,2, . .., encountered in our paper may depend only on the parameters appearing in the definitions of the class and metric in which we determine the error of approximation.
The following assertion is true: Theorem 1. Let < <
≤ , ∈ , ∈ ℝ and let, in addition, there exist > such estimate for the approximation of functions from the classes
, by their Fourier sums [15, p. 215]:
We now determine the lower bounds. We will use the Rudin-Shapiro polinomials ℛ ( ): ℰ ( , )2 =
≍ ( =− satisfying the order estimate (see, e.g., [16, and let = ±1 will be such that where
|Λ | > |Λ− |.
Then for given , we take ∈ ℕ from the relation 2 −2 ≤
< 2 −1, take a small positive parameter and consider a function ( )= 3 (2 )2 (1−1)
1( ), 3 > 0, 1( )= ( )+ ℛ
( ), 0 < ≤ 2 . We now show that, for a certain choice of the constant 3 > 0, the function
belongs to the . To this end, it suffices to verify that
∥ ∥ ≪ 1.
For this purpose, we use the estimate [17]
∥ ∥ ≪ −1( )∥ ∥ well-known relation (see, e.g., [18, p. 66]) (for any polynomial ∈ , 1 < < ∞), and the
∥ 2 ∥ ≍ 2 Hence, we can write
1 (1− ), 1 ≤ ≤ ∞.
(2) (3) ∥ ∥ ≪ −1( )∥ ∥ ≤ ≤ −1( ) (2 )2 (1−1) ∙ ∙ (∥ ∥ + ∥ ℛ ∥ )≤ ≤ −1( ) (2 )2 (1−1) ∙ ∙ (∥ ∥ + ∥ ℛ
∥∞)≪ ≪ −1( ) (2 )2 (1−1) ∙ ∙ (2 (1−1) + 2 (21− )22)≪ 1.
1
This implies that, for a proper choice of the constant 3 > 0, function ∈ , for 1 ≤ ≤ 2 and 1 < ≤ 2
By using the estimate (see, e.g., [14], p. 581) ∥ 1 − ( 1)∥ ≫ 2, . 1 constant 4 > 0, the function 2 belongs to , .
Using the inequality of different metrics, we obtain the ratio
1 1 ∥ ∥ ≪ − ∥ ∥ ,
1 ≤ ≤ ≤ ∞, ∥ 2 − ( 2 )∥ ≫
1 ≫ − ∥ 2 − ( 2 )∥∞≫ 1 ≤ ≤ ∞, (see [14]), and the estimate
∈ ≫ (2 )2 (1−1)∥ 2 − ( 2)∥ ≫ ≫ ( ) 1−1 1−1 = 1 1 = ( ) − . 1 < ≤ 2 ≤ < ∞
(
1 1 , ) ≍ ( ) − . true: increase. Then the following order estimate is Therefore, given (5), we will have (5) Θ
is a set of integers 1,..., arbitrary complex numbers (see [19]).
and are ∥ − ( )∥ ≤ ≤ (1+ 3 21−1) ( ) ≪ ≪ 21−1 ( ) 1−21 = ( ) 1−1.
Therefore 2 −1 ≤ < 2 and consider a function
2( )= 4 (2 )2 (1−1) can write
It is easy to see that the function 2 belongs to , . Indeed, according to relations (2) and (3), we where 2 ( ), 4 > 0.
a function ∥ ( 2) ∥ ≪ −1( )∥ 2 ∥ ≪ ≪ −1( ) (2 )2 (1−1) (1−1)=1.
2
The estimate from below, and with it Theorem 2, Theorem 3. Let 2 ≤ p ≤ q < ∞, ∈ , ∈ ℝ and let, in addition, there exist > 0 such that the sequence ( ) 2
1+ , ∈ ℕ, does not increase.
Then the following order estimate is true:
⊂ ,2, then and therefore, taking into account the ratio (4) for p = 2, we obtain the upper bounds constant 5 > 0, the function 3 belongs to the
.
For this purpose, it suffices to check that
To this end, we use (2) and the known relation (see, e.g., [20, p. 155]) (1−1),
1 < < ∞.
∥ ( 3) ∥ ≪ −1( )∥ 3 ∥ ≤
≤ −1( ) (2 )2−2 ∙ ∙ (∥ ℛ ∥ + ∥ ∥ )≤
≤ −1( ) (2 )2−2 ∙ ∙ (∥ ℛ ∥∞+ ∥ ∥ )≪ ≪ −1( ) (2 )2−2 ∙ ∙ (22 + 2 ( −
This implies that, for a proper choice of the constant 5 > 0, the function 3 belongs to the Further, use the estimate set in [14, p. 582]:
∥ 4 − ( 4)∥ ≫ 1−1, 2 ≤ ≤ ∞.
Taking into account this ratio, we will have 3∈ sup
The possibilities of precise methods are very limited, especially when solving large-scale problems. algorithms is possible only in the presence of a priori information about the properties of the target functional. This leads to the need to develop and study approximate algorithms to obtain the necessary solution. Because if the dimension is close to the
hundredth step, then the exact algorithm is no longer able to find a solution in real time. This paper proposes the use of a greedy algorithm, the essence of which is to select the next element at each step in an optimal way, to effectively solve problems of optimization of functions in the presence of constraints. In particular, we obtain the exact order estimates of approximations by greedy algorithms of the classes
, of periodic functions in the space for some relations between parameters and . Using approximation by greedy algorithms (ψ, β) - differentiable functions in Lebesgue spaces, the exact order estimates under conditions 1 < < ≤ 2, 1 < ≤ 2 ≤
< ∞ and 2 ≤ p ≤ q < ∞ were found. The estimates obtained allow us to effectively use mathematical models that describe the routes between atomic nodes of the system, which require the use of (ψ,β)-differentiable functions in the space , in optimization problems.
[1] S. Yevseiev, R. Korolyov, A. Tkachov,O.
Laptiev,
Opirskyy,
Soloviova, Modification of the algorithm (OFM) S-box, which provides increasing crypto resistance in the post-quantum
period, International Journal of Advanced Trends in Computer Science and
Engineering (IJATCSE) 9
O. Ilin, Detection of Slow DDoS Attacks based on User’s Behavior Forecasting, International [5] O. Laptiev, O. Stefurak, I. Polovinkin, O. [6] O. Laptiev, V. Savchenko, S. Yevseiev, H.
Barabash, S. Vitalii, O. Zelikovska, The method of improving the signal detection quality by accounting for interference, 2020 IEEE
Laptiev, I.
Kovalchuk,
A.
Zidan, Algorithm of control of functionally stable manufacturing processes of enterprises, 2020 IEEE 2nd
International
Conference on Advanced Trends in Information Theory (IEEE ATIT 2020) Conference Proceedings Kyiv, Ukraine, 2020, pp. 206 –211.
doi:10.1109/ATIT50783.2020.9349332 the Digit Inversor for the 3-Representation of the Fractional Part of a Real Number, Its Fractal and Integral Prorerties, Journal of Mathematical Sciences 215 (2016) 323–340. [10] O. Barabash, O. Kopiika, I. Zamrii, V.
Sobchuk, 79 – 95. doi: 10.1007/978-3-319-96755-4_5 Estimates trigonometric of the best
orthogonal approximations and orthoprojective widths of the classes of periodic functions of many variables in a uniform
metric, Journal of Mathematical Sciences 246 (2020) 110-119.
doi:10.1007/s10958-020-04725-0 [12] A. I. Stepanets’, Methods of Approximation Theory. Vols. 1,2, Institute of Mathematics, Ukrainian National Academy of Sciences, Kyiv, 2002. [13] V. N. Temlyakov, Greedy approximation, Cambridge, Cambridge University
Press, 2011. doi: 10.1017/CBO9780511762291 [14] V. N. Temlyakov, Greedy algorithm and mterm trigonometric approximation, Constr.
Approx 14 (1998) 569-587.
Stepanets,
Classification and Approximation of Periodic Functions [in Russian], Naukova Dumka, Kiev (1987). [16] B. S. Kashin, A. A. Sahakyan, Orthogonal series [in Russian], M .: Science, 1984. [17] A. S. Romanyuk, Inequalities for the norms of ( ,β)-derivatives and Kolmogorov widths of the classes of functions of many variables
, in: Investigations in the Approximation Theory of Functions [in Russian],
Proc.
of the
Institute Mathematics, Academy of Sciences of Ukr.
SSR, Kiev (1987), 92–105. [18] V.
Temlyakov,
Approximation functions with bounded mixed derivative, Tr.
Mat. Inst. Akad. Nauk SSSR, 178 (1986). [19] Barabash Oleg, Laptiev Oleksandr, Tkachev of of Volodymyr,
Maystrov
Oleksii,
Krasikov Oleksandr, Polovinkin Igor. The Indirect method of obtaining
Estimates of the Parameters of Radio Signals of covert means of September-Oktober 2020, pp 8725-8729.
DOI: 10.30534/ijatcse/2020/261952020. [21] Vitalii Savchenko, Oleksandr Laptiev, Oleksandr Kolos, Rostyslav Lisnevskyi, Viktoriia Ivannikova, Ivan Ablazov. Hidden Transmitter Localization Accuracy Model Based on Multi-Position Range Measurement. 2020 IEEE 2nd International Conference on Advanced Trends in Information Theory (IEEE ATIT 2020) Conference Proceedings Kyiv, Ukraine, November 25-27. pp.246 –251