{'fraction_non_alphanumeric': 0.04042419973389685, 'fraction_numerical': 0.011583313766924943, 'mean_word_length': 4.486260197509661, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Application and issues in abstract convexity

The theory of abstract convexity, also known as convexity without linearity, is an extension of the classical convex analysis. There are a number of remarkable results, mostly concerning duality, and some numerical methods, however, this area has not found many practical applications yet. In this paper we study the application of abstract convexity to function approximation. Another important research direction addressed in this paper is the connection with the so-called axiomatic convexity.


INTRODUCTION
Abstract convexity appears as a natural extension of the classical convex analysis when linear and affine functions (elementary functions) are "replaced" by other types of functions. This is why abstract convexity is also known as "convexity without linearity".
It was demonstrated that many results from the classical convex analysis: conjugation, duality, subdifferential related issues can be extended to "non-linear" settings [25,31]. In [25] the authors provide a very detailed historical review of the theory and it turned out that the origins of this environment comes back to early 70s, while some specific issues were already in place in the 50s of the twentieth century.
Despite a very productive work done in the development of abstract convexity, there are still several direction for improvements. From the onset of abstract convex theory, much effort has been devoted to study duality, leading to very elegant generalisations of classical convexity results. On the other hand, the geometric aspects of convexity have not received as much attention. Additionally, the theory remains "abstract" and needs practical applications. One of the goals of this paper is to provide some applications and develop a framework on the properties that the elementary functions have to satisfy to be efficient in applications.
There are a number of difficulties to develop efficient computational methods. The first step is to choose the set of elementary functions. This set should be simple enough to construct fast and efficient methods. On another hand, this set has to generate accurate approximations to the functions from the applications. In some cases, the choice of elementary functions is reasonably straightforward (see section 3), but this is rather exceptional and in most applications the choice of a suitable class of elementary functions is a difficult task.
A deep and detailed study on abstract convexity and related issues can be found in [31] and also in [29]. A detailed survey of methods of abstract convex programming can be found in [2]. Many more contributions and developments and results on duality and methods are not mentioned in this paper, but the most recent state of the developments in abstract convexity and a comprehensive literature review can be found in [6].
The paper is organised as follows. In section 2 we provide the essential background of abstract convexity and axiomatic convexity. In the same section, we underline connections and possible cross-feeding between these two types of convexity. Then, in section 3 we illustrate how abstract convexity and axiomatic convexity can be applied to function approximation. Section 4 illustrates the results of numerical experiments. Finally, section 5 provides conclusions and future research directions.

ABSTRACT CONVEXITY
2.1. Definitions and preliminaries. Consider the set of all real-valued functions acting on the domain X, denoted by F and defined by F := { f : X → R}. We called the set of abstract linear functions to any subset of functions L ⊆ F . Following, we introduce some known definitions to state the abstract convexity concept. Suppose that we defined the set of abstract linear functions L ⊆ F . Definition 2.2 (Abstract Convexity [29]). A function f is said to be L-convex if there exists a set U ⊂ H such that for any x ∈ X, f (x) = sup u∈U u(x). Such functions are also called abstract convex with respect to L.
In this paper we denote the set of all L-convex functions by F L . Definition 2.3 (Support Set [29]). The L-support set of a function f ∈ F is defined as: The support sets of L-convex functions are called L-convex sets.
Therefore, informally, convexity without linearity simply means that the "role" of linear functions of the classical convex analysis is held by functions from a certain class. The first (and for some applications this is the most important) question is how to choose the set of elementary function.
The next definition, which will be detailed and used in the next subsection, "helps" the chosen of a "better" set of abstract linear functions.
Definition 2.4 (Supremal generator [14,29]). Let F be a set of functions defined on a set X. A set L ⊂ F is called a supremal generator of F if each f ∈ F is abstract convex with respect to L.

2.2.
Quasiconvexity. The notion of quasiconvexity plays an essential role in abstract convexity. We are now going to explain why.
The notion of quasiconvexity was originally introduced in [11], where the author studied the behaviour of functions with convex sublevel sets, but the term quasiconvexity was introduced much later.
There are several equivalent definitions of quasiconvex functions, but the one we use is convenient for our study.
Note the following important observations.
• Quasiconvex functions do not need to be continuous.
• In the case of univariate functions, quasiaffine functions are monotone functions.
If a function is quasiaffine on R n (unconstrained problems) then, from the definition, that its level sets must be half-spaces, and it is clear that the hyperplanes defining these half-spaces need to be parallel. In the presence of constraints, this observation is not valid and we provide an example in section 4.
There are many studies dedicated to quasiconvex functions and quasiconvex optimisation [5,9,10,14,29,30]. In these studies, the notion of quasiconvexity appears as one of the possible generalisations of convexity.  Essentially, this theorem states that in the case of quasiconvex minimisation problems, quasiaffine functions "replace" the role of linear functions in classical convex settings. Therefore, the choice of elementary functions is clear (all quasiaffine functions).
One main advantage is that the sublevel sets of "new" elementary functions are half-spaces (similar to classical convex analysis). In most practical problems, there are some specific characteristics for the quasiaffine approximations (for example, the class of rational or generalised rational approximations, approximations that are compositions of certain monotone or nondecreasing function with certain affine or quasiaffine functions, etc.). This additional information helps dealing with some specific applications.
In the rest of this section, we clarify the "roles" of quasiaffine functions in the new abstract convex settings. Then section 4 contains the results of computational experiments and illustrations.
2.4. Relation to Axiomatic Convexity. Axiomatic Convexity aims at generalising the notion of convexity using only set-theoretic definitions. Good reviews can be found in [32,33]. Given a set X, a family C of subsets of X is called a convexity if it follows the following axioms: (1) / 0 and V belong to C ; The nested union of sets from C is in C : given an a family of sets D ⊂ C that is totally ordered by inclusion then The pair (X, C ) is called a convex structure (or (abstract) convex space). These axioms (in particular axioms 1 and 2) ensure the existence of the convex hull of any set S ⊂ X, namely the smallest convex set containing S: If F is finite, then co C F is called a polyhedron. Axiomatic Convexity, also called abstract convexity by van de Vel [33], has found applications in combinatorial geometry [13,18], among others. A family C that satisfies the first two axioms above is called a closure space, or ∩-stable [15].
There are clear connections between abstract convexity as defined by Definition 2.3 and axiomatic convexity. Indeed, the notion of abstract convex function (Definition 2.2) first appeared in [15] in the context of closure spaces. The families of sets considered in [15] were the closure of the set of sublevel sets of a given family of functions.
Abstract convex functions (Definition 2.2) and Abstract convex sets (Definition 2.3) were then formally introduced by Kutateladze and Rubinov [17], who showed the equivalence between these sets and the ones considered by Fan [15]. Below we formalise some results on the correspondence between abstract convex sets and closure spaces. Let us start with noting that the support set of any (not necessarily L-convex) function is L-convex. Indeed, the support set of f is also the support set of its L-convex envelope, which is convex. Proposition 2.9. Consider a family of functions L. Then, the set of L-convex sets form a closure space. Furthermore, every closure space is isomorphic to such a set.
Proof. Consider a family of functions L and let C be the set of L-convex sets. We first show that L is closed with respect to inclusion. Indeed, let D ⊂ C be an arbitrary set of L-convex sets. For each A ∈ D, let f A (x) = sup l∈A l(x) and consider the function f (x) = inf A∈D f A (x). We will show that ∩ A∈D A = supp f , which implies that ∩ A∈D A is L-convex (note that supp f is the support set of the lower convex envelope of f ).
The first axiom is clearly verified by C from the fact that / 0 is the support set of sup l∈ / 0 l and L is the support set of sup l∈L l.
The second part of the statement is obtained by considering the set L of indicator functions of the sets in the closure space. More precisely, let C be a closure space, and consider the set The isomorphism between the set of support sets of functions from L and C is evident.
Note that in practice it is not necessary to consider the entire set of indicator functions, but only the set of indicator functions of a basis of C (i.e., a set of functions whose closure is C ), which corresponds to a suppremal generator of the corresponding abstract functions. It can also easily be seen that the set of domains of the L-abstract functions defined as in the above proof, as well as the set of 0-sublevel sets, is precisely C .
On the other hand, not all families of abstract convex sets are a convexity structure.
Example 2.10. Let L be the set of linear functions on R, and consider the functions f α defined by f α (x) = α|x|, for α > 0. These functions are L-convex, and induce a nested sequence of is not a L-convex set. Indeed, f 1 = sup l∈U l is the smallest L-convex function whose support set contains U, but the function x → x ∈ supp f 1 \U, which shows that U cannot be the support set of f 1 and therefore of any L-convex function. This shows that the set of L-convex sets is not a convex structure.
Let us introduce the notion of strict support set, which will enable us to address this issue. The L-strict support set of a function f is defined as: We define the family of sets C L as follows: Definition 2.11 (convexity extension).
We call the set C L the convexity extension of the set of support sets of L-convex functions.
Proposition 2.12. For any family of functions L, the convexity extension of L, C L , forms a convexity structure.
Proof. Since C L contains all L-convex sets, it contains a closure space and therefore by Proposition 2.9, it contains the sets / 0 and X. To see why the second axiom is satisfied consider an arbitrary family of sets D ⊂ C L . For each where the last equality was shown in the proof of Proposition 2.9. Additionally, we have: Finally, to see that the third axiom is also satisfied, let D be an ordered family of sets from C . For each A ∈ D, we define f A as above. The nested nature of the sets in D implies that for Then u / ∈ ∪ A∈D supp f A , and so there exists x ∈ X such that u(x) ≥ f A (x) for any A ∈ D, and therefore that u(x) ≥ sup A∈D f A (x) = f (x). Therefore u / ∈ supp f . This implies that supp f ⊆ S ⊆ supp f , and therefore S is in C L and C L is a convexity structure.
Remark 2.13. Propositions 2.9 and 2.12 imply an equivalence relation between sets of abstract linear functions according to the convexity structure (axioms 1-3) or closure space (axioms 1,2) the induced abstract convex sets are isomorphic to.
Axiomatic convexity has been applied to obtain generalisations of well known geometric results in convexity theory. Of particular interest to this paper are generalisations of Carathéodory's theorems. Much research has been devoted to investigating this topic. We refer to [33] for a review of classical results in the area.
Definition 2.14 ([33, Definition 1.5]). In a given Convexity structure C , a set F is Carathéodory and Carathéodory independent otherwise. Then we can define the Carathéodory number of a convex structure C as the largest cardinality of a Carathéodory independent set (i.e., any set F with cardinality greater than c(x) is Carathéodory dependent). The Carathéodory numbers of several important classes of convexity structures are known and discussed in the literature [33].
Generalisations of Helly's and Radon's theorems were obtained similarly. The Carathéodory number enables the following generalisation of Carathéodory's classical result: Proposition 2.15 ([33, Theorem 1.7]). Consider a convexity structure (C , X) with Carathéodory number c(x), and let A ⊂ C be a convex set from C . Then, for any x ∈ A there exists a set F ⊂ A such that |F| ≤ c(x) and x ∈ coF. This is best possible.

APPLICATION TO APPROXIMATION
3.1. Problem formulation. We are working with uniform (Chebyshev) approximation: where A are the decision variables and X is a compact set. In many computer based applications, this set is a finite grid defined on a convex compact set. If we define L = {A → g(A, x) : x ∈ X}, then it is clear from Formulation (3.1) that the objective function of this problem is H L -convex.
In the case when the approximation function g(A,t) is a polynomial (and its coefficients are subject to optimisation), the optimality conditions are based on maximal deviation points (Chebyshev theorem, see [7]). In the case of univariate function approximation, the conditions are based on the notion of alternating sequence.
Theorem 3.1 (Chebyshev). A polynomial of degree at most n is optimal in uniform (Chebyshev) norm if and only there are n + 2 alternating points.
Essentially, the approximations here are presented as linear combinations of basis functions. In the case of polynomials the basis functions are monomials, but other classes of basis functions can be used. The corresponding optimisation problems are convex as supremum of linear forms. Theorem 3.1 can be proved using convex analysis and the number of alternative point (n + 2) obtained through Carathéodory's theorem. In other words, the following conjecture is true, in the case when L is a set of linear functions: Conjecture 3.2. For a function from L to be an optimal approximation in uniform norm, it is enough that it is optimal at c(C H L ) + 1 extreme points.
We also conjecture that this is best possible, in the sense that the statement is generally not true if we replace c(C H L ) + 1 with c(C H L ).
If true, this conjecture could form the basis for algorithms for best approximation, such a generalisation of Vallée-Poussin's procedure [12]. Later in this section, we discuss an example of families L in the context of this conjecture.
One possible generalisation to polynomial approximation is rational approximation, that is, approximation by the ratio of two polynomials, whose coefficients are subject to optimisation. Note that in some cases, the degree of the denominator and numerator can be reduced without compromising the accuracy: where d = min{ν, µ} is called the defect. Then the necessary and sufficient optimality conditions are as follows [1]. Therefore, similar to polynomial approximation, these conditions are bases the number of alternating points.
In connection to Conjecture 3.2, c(C H L ) is n + m + 2. If n and m are the degrees of the corresponding polynomials, then the total number of the parameters is n+1+m+1 = n+m+2. However, one of the parameters can be fixed (otherwise one can divide the numerator and denominator by the same number). Therefore, there are n + m + 1 "free" parameters and we add one more for c(C H L ) (similar to Carathéodory's theorem from classical convex analysis). We will provide a formal proof in a future paper.
If the basis functions are not restricted to monomials, the approximations are called generalised rational approximations. The term is due to Cheney and Loeb [8].
One way to approach rational approximation is through constructing "near optimal" solutions [24]. This approach is very efficient and therefore very popular. The extension of this approach to non-monomial basis functions and multivariate approximation remains open (an extension to complex domains can be found in [23]).
An alternative way is based on modern optimisation techniques. This approach is preferable when the basis function are not restricted to univariate monomials and when deeper theoretical study is required. The corresponding optimisation problems are quasiconvex and can be solved using a general quasiconvex optimisation methods.
Rational and generalised rational functions are quasiaffine as ratios of linear forms [5,19,26]. It can be solved efficiently by applying a simple, but robust approach, called the bisection method for quasiconvex functions [5].
In [26] the authors use a well-known bisection method for quasiconvex functions (see [5]) to solve these problems. In [22], the authors use a projection-type algorithm for solving these problems.
3.2. Bisection method. Bisection method for quasiconvex functions [5] can be used efficiently for rational and generalised rational approximation, including multivariate settings [21,26]. Can we use abstract convexity to extend this method to a wider class of approximations?
The problem can be formulated as follows:
The idea of this method is based on the fact that all the sublevel sets of quasiconvex functions are convex and therefore the sublevel sets of quasiaffine functions are half-spaces. Essentially, this means that the constraint set (3.3)-(3.5) for a fixedz is an intersection of a finite number of half-spaces (X is a finite grid) and therefore it is a polytope.
The algorithm starts with an upper and lower bound (u and l) for the maximal deviation, then the sublevel set for the maximal deviation at the level z = u+l 2 is a convex set and the algorithm checks if this set is empty. If it is empty, then the upper bound is updated to z, otherwise, the lower bound is updated to z. The algorithm terminates when the upper and lower bounds are within the specified precision.
In general, checking if the convex set (sublevel set of the maximal deviation) is empty or not may be a difficult task (convex feasibility problems). There are a number of efficient methods ( [3,34,35,36,37] just to name a few), but there are still several open problems here. The discussion of these problems is out of scope of the current paper.
In the case of multivariate generalised rational approximation, however, this problem (convex feasibility) can be reduced to solving a linear programming problem [21]. The denominator of the approximation does not change the sign. Assume, for simplicity, that it is positive, then the problem of checking the feasibility is equivalent to solving the following problem: where z = 1 2 (u + l) is the current bisection point (bisecting the possible values of maximal deviation).
If an optimal solutionũ ≤ 0, the corresponding sublevel set of the maximal deviation function is not empty (update the upper bound), otherwise the set is empty (update the lower bound). If X is a finite grid, then (3.6)-(3.9) is a linear programming problem and can be solved efficiently at each step of the bisection method.
To summarise, an efficient implementation of the bisection method for quasiconvex functions, can be extended to approximation by any type of quasiaffine functions, since at each step one needs to check if a polytope (intersection of a finite number of half-spaces) is non-empty. The main problem is how to find this polytope. In the case of rational and generalised rational approximation, this problem is simple, but not for some other types of quasiaffine approximations. In section 4 we give more examples where the construction of this polytope is straightforward (composition of monotone and affine or ratios of affine functions).
One possibility for constructing sublevel sets for smooth quasiaffine approximation is to use their gradients (if it is not vanishing). In the rest section, we give an example demonstrating that this approach may be complicated if there are constraints (even simple linear constraints). In particulra, this approach will not work even in the case of rational approximation due to the requirement for the denominator to be strictly positive.
3.3. Approximation by a quasiaffine function. Suppose that instead of a generalised rational approximation one needs to approximate by a function from a different class, but the approximations are quasiaffine functions with respect to the decision variables. Then the problem is as follows: where g(A, x) is a quasiaffine function. Since the sublevel sets of quasiaffine functions are half-spaces, the constraint set (3.11)-(3.12) is a polytope, since X is a finite grid.
Remark 3.4. A finite number of linear constraints may be added to (3.10)-(3.12), while the constraint set remains a polytope.
Therefore, the constraint set (for any fixedz), with or without additional linear constraints, is a poytope and we only need to check if this polytope is non-empty. However, we still need an efficient approach for finding this polytope. In the case of smooth functions, one can use the gradient as a possible normal vector to the hyperplanes, providing that it is not a zero vector. In section 4 we study the examples where the quasiaffine approximations can be decomposed as a composition of strictly monotone and affine (quasiaffine) functions. Other situations may be harder.
Note that if a function is quasiaffine on the whole space, then the sublevel sets are halfspaces, whose boundary hyperplanes are parallel. Otherwise, two hyperplanes will intersect. If there are additional (even linear) constraints, this observation may not be valid anymore. The following example illustrates that this may happen even in a very simple case of two variables.
where α is a given real number. Then S α can be described as Each sublevel set is still a half-space, but the corresponding hyperplanes (in this example they correspond to level sets) are not parallel. These hyperplanes intersect at (0, 0), but this point is excluded from the domain due to the requirement for the denominator y to be strictly positive.
This example demonstrates that the computation of sublevel sets for quasiaffine functions may be challenging. In the next section we give some examples of the classes of approximations that can be handled efficiently. We also provide the results of the numerical experiments. the maximal absolute deviation is 8.01 (to two decimal places). Figure 1 represents the function f (x, y), figure 2 depicts the best found approximation and figure 3 contains the deviation function f (x, y) − g(A, x, y), which is the error of approximation.
Function f (x, y) is almost flat with an abrupt increase around point (−1, 1). Visually, the approximation resembles the shape of the original function and the magnitude of the deviation confirms that the approximation is reasonably good.

4.2.
Strictly monotone function in composition with a rational function. In this example we approximate the same function by a quasiaffine function in the form where, similar to the previous example, A = (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 ) are the decision variables (the number of decision variables is the same as in the previous example), x and y are on a grid [−1, 1] with the step-size 0.1. The purpose of approximation is to use lower degree polynomials in the composition. The optimal coefficients are (rounded to two decimal places): A = (−1.66, −0.93, 1.05, 2.87, 0.98, 1), the maximal absolute deviation is 11.48 (to two decimal places). Figure 4 contains the best found approximation and figure 5 depicts the deviation function f (x, y) − g 1 (A, x, y), which is the error of approximation. FIGURE 2. Approximation g(A, x, y) = (a 1 + a 2 x + a 3 y + a 4 x 2 + a 5 y 2 + a 6 xy) 3 . f (x, y) − g(A, x, y) = (−x + y 3 + x 4 ) 4 − (a 1 + a 2 x + a 3 y + a 4 x 2 + a 5 y 2 + a 6 xy) 3 .
The new approximation still resembles the shape of the original function, but the maximal deviation is higher.

CONCLUSIONS
The goal of this study is to demonstrate that abstract convexity (in the sense "convexity without linearlity") has several applications in different branches of mathematics, including approximation theory. This application appears naturally in the new settings.
The results of the numerical experiments demonstrate that our approach is computationally efficient. The applications lead to practical applications as well. One potential application is data science and deep learning.
We also touched the connections between "abstract convexity" and "axiomatic convexity". These areas have many overlappings that can be seen as a new way of looking at the problems, in particular, function approximation.