Vinh Thanh Ho

Hoai An Le Thi
email: hoai-an.le-thi@univ-lorraine.fr

Tao Pham Dinh

An Le Thi

Tao Pham Dinh

DCA-based algorithms for DC Fitting

Keywords: DC programming, DCA, DCA with successive DC decomposition, DC fitting, Piecewise-linear fitting

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The fundamental problem of fitting a certain mathematical function to a given set of data points has been studied extensively. The fitting problem often involves, e.g., smoothing to remove noise from datasets but preserve important patterns, or interpolation/extrapolation to construct new data points within/beyond the range of the given datasets. The obtained fitting models can be used for data visualization, for estimating the relationships among variables, and for predicting values of a function at unavailable data points.

The related works considered many fitting functions: for example, linear/polynomial functions, convex/nonconvex continuous piecewise-linear functions, exponential functions, logarithms, etc. In this paper, we take into account a DC (Difference of Convex functions) fitting function that covers most of all existing fitting functions. Here, a function F is called a DC function if it takes the form F = G -H (with G, H being convex functions); and G -H is called a DC decomposition of F , while G and H are DC components of F (see, e.g., [START_REF] Pham Dinh | Algorithms for solving a class of nonconvex optimization problems. methods of subgradients[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF][START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF]).

Let us introduce the so-called DC fitting problem that fits a given set of m points (x i , y i ) ∈ R p × R by a DC function φ : R p → R with the form φ(x) := f(x, α), where, for two variables x ∈ R p and α ∈ R n , the function f : R p × R n → R is DC in each variable when the other variable is fixed. The set of such functions φ is denoted by F .

With the least-squares fitting criterion, the objective of DC fitting problem is to find the parameter vector α ∈ R n such that the mean-square error, defined by 1

m m i=1 [φ(x i ) -y i ] 2 = 1 m m i=1 [f(x i , α) -y i ] 2 , (1)
is as small as possible. It can be expressed as the following squared 2 -norm (or Euclidean norm) optimization formulation min F (α) :

= m i=1 [f(x i , α) -y i ] 2 : α ∈ R n . (2)
Note that the optimization problem (2) is, in general, nonconvex and nonsmooth. Thus, globally solving such a problem is very difficult in large-scale setting.

The backbone of our approach for solving the problem ( 2) is DC programming and DCA (DC Algorithm) (see, e.g., [START_REF] Pham Dinh | Algorithms for solving a class of nonconvex optimization problems. methods of subgradients[END_REF][START_REF] Le | Analyse numérique des algorithmes de l'optimisation DC. approches locale et globale. codes et simulations numériques en grande dimension. applications[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF][START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF][START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF][START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF][START_REF] Pham Dinh | Recent advances in DC programming and DCA[END_REF] and the references in [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF]) which are well-known as powerful nonsmooth, nonconvex optimization tools. DCA aims to solve a standard DC program that consists in minimizing a DC function F = G -H over a convex set or on the whole space. The idea of standard DCA is, at each iteration k, approximating the second DC component H by its affine minorant H k and then solving the resulting convex subproblem. In other words, one approximates the DC function F by the convex majorization F k := G -H k . It is clear that the closer to F the function F k is, the better DCA could be. The recent work [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF] has introduced a modified version of the standard DCA scheme, named DCA with successive DC decomposition. In this version, the DC decomposition of F is successively updated during DCA iterations in order to better approximate the DC function F i.e. F := G k -H k at each iteration k and its corresponding convex majorization is

F k := G k -H k k .
The "successive DC decomposition" idea has been used in the recent works [START_REF] Le Thi | A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning[END_REF][START_REF] Ho | DCA with successive DC decomposition for convex piecewise-linear fitting[END_REF]. Le Thi et al. [START_REF] Le Thi | A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning[END_REF][START_REF] Ho | DCA with successive DC decomposition for convex piecewise-linear fitting[END_REF] have investigated the standard/modified DCA scheme for minimizing the sum of squared convex (piecewise-linear) functions, which is a particular case of this work.

Contributions: We investigate DC programming and DCA for solving the general DC fitting problem [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF]. Particularly, the problem (2) is formulated as a DC program for which a standard DCA scheme is developed. A modified version of DCA with successive DC decomposition for the problem (2) is proposed to better approximate the DC objective function. Next, we apply the proposed DCA schemes for solving a class of continuous piecewiselinear fitting problems. We provide numerical experiments of our DCA-based algorithms on both synthetic and real datasets with small-to-large size of data points in comparison to the existing approaches for constructing the piecewise-linear models.

The rest of the paper is organized as follows. Section 2 shows how to apply DC programming and DCA for solving the squared 2 -norm optimization formulation of DC fitting problem. In Section 3, we develop two DCAbased algorithms for solving a continuous piecewise-linear fitting problem. Section 4 reports the numerical results on several test problems. Finally, Section 5 concludes the paper.

Solution methods based on DC programming and DCA

DC programming and DCA were introduced by Pham Dinh Tao in a preliminary form in 1985 as a natural and logical extension of his previous works on convex maximization since 1974 (see e.g. [START_REF] Dinh | Elements homoduaux dune matrice a relatifs un couple de normes (φ, ψ). applications au calcul de s (φ,ψ) (a)[END_REF][START_REF] Dinh | Contribution la théorie de normes et ses applications l'analyse numérique[END_REF]), and have been extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1994. DCA is well-known as an efficient approach in the nonconvex programming framework. In recent years, numerous DCA-based algorithms have successfully solved large-scale nonsmooth/nonconvex problems arising in several application areas (see, e.g., [START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF][START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF][START_REF] Le Thi | A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning[END_REF][START_REF] Phan | Group variable selection via p,0 regularization and application to optimal scoring[END_REF][START_REF] Phan | Accelerated difference of convex functions algorithm and its application to sparse binary logistic regression[END_REF][START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF][START_REF] Le Thi | DC programming and DCA for sparse Fisher linear discriminant analysis[END_REF][START_REF] Le Thi | DCA based algorithms for feature selection in multi-class support vector machine[END_REF][START_REF] Phan | Sparse covariance matrix estimation by DCA-based algorithms[END_REF] and the list of references in [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF]). For a comprehensive survey on thirty years of development of DCA, the reader is referred to the recent paper [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF].

The original key idea of DCA relies on the DC structure of the objective function F . The standard DCA scheme is described as follows.

Standard DCA scheme

Initialization: Let α 0 ∈ R n be a best guess. Set k = 0. repeat 1. Calculate β k ∈ ∂H(α k ). 2. Calculate α k+1 ∈ argmin{G(α) -H(α k ) -α -α k , β k : α ∈ R n }. 3. k = k + 1. until convergence of {α k } k .
Convergence properties of the standard DCA are described completely in [START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF][START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF].

Standard DCA for solving the problem (2)

The squared 2 -norm formulation (2) of DC fitting problem can be rewritten as min

F (α) = m i=1 [p i (α)] 2 : α ∈ R n (3)
where for i = 1, . . . , m, the function p i : R n → R is defined as

p i (α) := f(x i , α) -y i .
From the definition of F , we assume that f(x i , α) is a DC function, for i = 1, . . . , m, with DC decomposition

f(x i , α) = g i (α) -h i (α),
where g i and h i are continuous convex functions. Thus, p i is also a DC function with DC components

p i1 (α) = g i (α) -y i and p i2 (α) = h i (α).
Knowing that (see, e.g., [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF]) if the function p i is DC with a nonnegative DC decomposition then [p i ] 2 is DC too, we will exploit the convexity of p ij (j ∈ {1, 2}) to highlight a nonnegative DC decomposition of p i . In particular, we define the affine minorization of p i1 and p i2 (i = 1, . . . , m) at an arbitrary point α ∈ R n as follows:

l ij (α) := p ij (α) + α -α, γ ij with γ ij ∈ ∂p ij (α), j ∈ {1, 2}. (4)
Let us define

l i := max{-l i1 , -l i2 }.
Then the functions p i1 + l i and p i2 + l i are nonnegative and convex on R n , and so are [p i1 + l i ] 2 and [p i2 + l i ] 2 . We consider the following nonnegative DC decomposition of p i :

p i = [p i1 + l i ] -[p i2 + l i ] .
Applying the equality (ab) 2 = 2(a 2 + b 2 ) -(a + b) 2 for a = p i1 + l i and p i2 + l i , we get a DC decomposition of [p i ] 2 , that is,

[p i ] 2 = 2 [p i1 + l i ] 2 + [p i2 + l i ] 2 -[p i1 + p i2 + 2l i ] 2 .
As a result, F is a DC function. We thus derive the DC formulation of (3) as follows:

min{F (α) := G(α) -H(α) : α ∈ R n } (5)
where

G = m i=1 2 [p i1 + l i ] 2 + [p i2 + l i ] 2 , H = m i=1 [p i1 + p i2 + 2l i ] 2 .
Applying the standard DCA scheme to (5) leads us, at the iteration k, to compute a subgradient β k ∈ ∂H(α k ) and find an optimal solution α k+1 to the following convex subproblem min

m i=1 2 [p i1 (α) + l i (α)] 2 + [p i2 (α) + l i (α)] 2 -β k , α : α ∈ R n . ( 6
)
Standard DCA for solving (5) (DCA)

Initialization: Let α 0 ∈ R n . Set k = 0. repeat 1. Compute β k ∈ ∂H(α k ).
2. Solve the convex program [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF] to obtain α k+1 .

3. k = k + 1. until Stopping criteria are satisfied.

Finally, standard DCA applied to ( 5) is summarized below. As direct consequences of the convergence properties of standard DC programs (see, e.g., [START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF]), we have the convergence properties of DCA in Theorem 1.

Theorem 1. Convergence properties of DCA i) DCA generates the sequence {α k } such that the sequence {F (α k )} is nonincreasing. ii) If the sequences {α k } and {β k } are bounded, then every limit point α * of the sequence

{α k } is a critical point of G -H i.e. ∂G(α * ) ∩ ∂H(α * ) = ∅.
2.2. DCA with successive DC decomposition for solving the problem [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF] We see from (4) that for i = 1, . . . , m, j ∈ {1, 2}, the affine minorization l ij of p ij can be computed easily with any point α. From the fact that the closer to p ij the function l ij is, the better DCA could be, we suggest a modified DCA with successive DC decomposition for the problem (2), i.e. l ij is updated during DCA iterations by choosing α = α k . Particularly, at the iteration k, we set

γ k ij ∈ ∂p ij (α k ), l k ij (α) := p ij (α k ) + α -α k , γ k ij .
Let us define l k i := max{-l k i1 , -l k i2 }. The resulting DC formulation of (2) takes the form

min{F (α) := G k (α) -H k (α) : α ∈ R n } (7)
where

G k = m i=1 2 p i1 + l k i 2 + p i2 + l k i 2 , H k = m i=1 p i1 + p i2 + 2l k i 2 .
Similarly, DCA with successive DC decomposition applied to [START_REF] Pham Dinh | Recent advances in DC programming and DCA[END_REF], named DCA k , consists in computing two sequences {β k } and {α k } such that β k ∈ ∂H k (α k ) and α k+1 is an optimal solution to the following convex subproblem

min m i=1 2 p i1 (α) + l k i (α) 2 + p i2 (α) + l k i (α) 2 -β k , α : α ∈ R n . (8)
DCA with successive DC decomposition for solving [START_REF] Pham Dinh | Recent advances in DC programming and DCA[END_REF]

(DCA k ) Initialization: Let α 0 ∈ R n . Set k = 0. repeat 1. Compute β k ∈ ∂H k (α k ). 2. Solve the convex program (8) to obtain α k+1 . 3. k = k + 1. until Stopping criteria are satisfied.
Especially, the convergence properties of DCA is still valid for DCA k as stated in Theorem 2.

Theorem 2. Convergence properties of DCA k i) DCA k generates the sequence {α k } such that the sequence {F (α k )} is nonincreasing. ii) If the sequences {α k } and {β k } are bounded, then every limit point α * of the sequence

{α k } is a critical point of F = G ∞ -H ∞ where G ∞ = m i=1 2 [p i1 + l ∞ i ] 2 + [p i2 + l ∞ i ] 2 , H ∞ = m i=1 [p i1 + p i2 + 2l ∞ i ] 2 ,
and

for i = 1, . . . , m, j ∈ {1, 2}, l ∞ ij is the affine minorization of p ij at α * , l ∞ i := max{-l ∞ i1 , -l ∞ i2 }. Proof. i) DCA k consists in constructing two sequences {α k } and {β k } such that β k ∈ ∂H k (α k ) and α k+1 ∈ argmin{G k (α) -α, β k }, which is equiv- alent to β k ∈ ∂H k (α k ) and α k+1 ∈ ∂(G k ) * (β k ), where the conjugate of G, denoted G * , is defined by G * (w) = sup{ α, w -G(α) : α ∈ R n }. The first inclusion β k ∈ ∂H k (α k ) implies that H k (α k+1 ) ≥ H k (α k ) + α k+1 -α k , β k .
Consequently,

G k (α k+1 ) -H k (α k+1 ) ≤ G k (α k+1 ) -H k (α k ) -α k+1 -α k , β k . (9)
Similarly, we derive from the second inclusion

α k+1 ∈ ∂(G k ) * (β k ) that G k (α k+1 ) -H k (α k ) -α k+1 -α k , β k ≤ (G k -H k )(α k ). ( 10
)
As a result, we have

F (α k+1 ) = (G k -H k )(α k+1 ) ≤ (G k -H k )(α k ) = F (α k ). That is, the sequence F (α k ) is non-increasing.
ii) For the sake of simplicity, we write lim k→+∞ α k = α * . Since the sequence {β k } is bounded, we imply that for i = 1, . . . , m and j = 1, 2, the sequence {γ k ij } is bounded too. We can suppose (by extracting a subsequence if necessary) that

{β k } k (resp. {γ k ij }) converges to β * (resp. γ * ij ). From Theorem 24.4 in [18] and γ k ij ∈ ∂p ij (α k ), we get γ * ij ∈ ∂p ij (α * ). Let us define the affine minorization l ∞ ij of p ij at α * as l ∞ ij (α) = p ij (α * ) + α -α * , γ * ij . From the definition of l k i (k ≥ 1, i = 1, . . . , m
) and the continuity of p ij (i = 1, . . . , m, j = 1, 2), we derive that

lim k→+∞ l k i (α k ) = lim k→+∞ p ij (α k ) = p ij (α * ) = l ∞ i (α * ),
and for each α,

lim k→+∞ l k i (α) = lim k→+∞ max j=1,2 (-l k ij (α)) = max j=1,2 (-l ∞ ij (α)) = l ∞ i (α).
Similarly, we also have:

lim k→+∞ G k (α k ) = G ∞ (α * ), lim k→+∞ H k (α k ) = H ∞ (α * ).
From the definition of both convex functions G ∞ and H ∞ , we see that

F = G ∞ -H ∞ i.e. G ∞ -H ∞ is a DC decomposition of F .
We derive from Lemma 2 in [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF] and the convergence properties of a series of conjugate convex functions (see e.g. [START_REF] Koshi | Convergence of convex functions and duality[END_REF][START_REF] Salinetti | On the relations between two types of convergence for convex functions[END_REF]) that

lim k→+∞ (G k ) * (β k ) = (G ∞ ) * (β * ), lim k→+∞ (H k ) * (β k ) = (H ∞ ) * (β * ). Now, we will show that α * is a critical point of G ∞ -H ∞ . From the inclusions β k ∈ ∂H k (α k ) and α k+1 ∈ ∂(G k ) * (β k ), we get α k+1 , β k = G k (α k+1 ) + (G k ) * (β k ) and α k , β k = H k (α k ) + (H k ) * (β k ).
(11) By taking the limit of the second equality of (11), we get

α * , β * = H ∞ (α * ) + (H ∞ ) * (β * ). Therefore, we yield β * ∈ ∂H ∞ (α * ).
To indicate the inclusion β * ∈ ∂G ∞ (α * ), it suffices to show that

lim k→+∞ {(G k ) * (β k ) + G k (α k ) -α k , β k } = 0. ( 12
)
It results from i) and F (α) ≥ 0 for all α ∈ R n that the sequence {(G k -H k )(α k )} is non-increasing and converges to the limit δ ≥ 0. We imply from [START_REF] Dinh | Contribution la théorie de normes et ses applications l'analyse numérique[END_REF] that

(H k ) * (β k ) -(G k ) * (β k ) = G k (α k+1 ) -H k (α k ) -α k+1 -α k , β k . ( 13
)
Combining ( 13) with ( 9) and ( 10), we see that the sequence

{[(H k ) * - (G k ) * ](β k
)} is non-increasing and also converges to the limit δ ≥ 0. Taking (13) and the same limit of two above sequences into account, we have

lim k→+∞ {G k (α k+1 )-H k (α k )-α k+1 -α k , β k } = lim k→+∞ {(G k )(α k )-(H k )(α k )}. Thus, lim k→+∞ {G k (α k+1 ) -G k (α k ) -α k+1 -α k , β k } = 0.
From [START_REF] Dinh | Contribution la théorie de normes et ses applications l'analyse numérique[END_REF], we obtain [START_REF] Phan | Group variable selection via p,0 regularization and application to optimal scoring[END_REF]. The proof of ii) is complete.

DCA and DCA k for continuous piecewise-linear fitting problem

The piecewise-linear fitting problem is finding a piecewise-linear function that furnishes the smallest mean-square fitting error (1) to a given set of data points. The importance of using a piecewise-linear function has been emphasized in many real-world applications due to a number of its merits: they are compact, easy to compute, visualize, interpret, and able to approximate even highly complex nonlinear functions (e.g., concave/convex function) [START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF].

Its application areas include from mathematical modeling/optimization (see, e.g., [START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF][START_REF] Balázs | Max-affine estimators for convex stochastic programming[END_REF][START_REF] Boyd | A tutorial on geometric programming[END_REF][START_REF] Magnani | Convex piecewise-linear fitting[END_REF][START_REF] Pham Dinh | DC programming and DCA for solving Brugnano-Casulli piecewise linear systems[END_REF][START_REF] Taccari | Optimization methods for piecewise affine model fitting[END_REF][START_REF] Toriello | Fitting piecewise linear continuous functions[END_REF][START_REF] Wang | Fast model predictive control using online optimization[END_REF]) to econometrics, transportation, prediction and forecasting (see, e.g., [START_REF] Apps | Optimal piecewise linear income taxation[END_REF][START_REF] Campra | Trend analysis by a piecewise linear regression model applied to surface air temperatures in southeastern spain (1973-2014[END_REF][START_REF] Choi | Piecewise linear regression networks and its application to time series prediction[END_REF][START_REF] Reiss | Household electricity demand, revisited[END_REF][START_REF] Toriello | Decomposing inventory routing problems with approximate value functions[END_REF]), and to statistics, machine learning and data mining (see, e.g., [START_REF] Yang | Mathematical programming for piecewise linear regression analysis[END_REF][START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF][START_REF] Balázs | Convex regression: Theory, practice, and applications[END_REF][START_REF] Goel | Reliably learning the relu in polynomial time[END_REF][START_REF] Hannah | Multivariate convex regression with adaptive partitioning[END_REF][START_REF] Martinez | Global optimization of non-convex piecewise linear regression splines[END_REF] and references therein), etc. In machine learning, developing regression techniques using the piecewise-linear function plays an important role for practical problems such as energy storage optimization with a solar source, beer brewery optimization, customer demand forecasting (see, e.g., [START_REF] Yang | Mathematical programming for piecewise linear regression analysis[END_REF][START_REF] Balázs | Convex regression: Theory, practice, and applications[END_REF][START_REF] Hannah | Multivariate convex regression with adaptive partitioning[END_REF] for more practical problems). Previous and relevant works for piecewise-linear fitting functions are given completely in several works (see, e.g., [START_REF] Yang | Mathematical programming for piecewise linear regression analysis[END_REF][START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF][START_REF] Magnani | Convex piecewise-linear fitting[END_REF][START_REF] Taccari | Optimization methods for piecewise affine model fitting[END_REF][START_REF] Toriello | Fitting piecewise linear continuous functions[END_REF][START_REF] Balázs | Convex regression: Theory, practice, and applications[END_REF][START_REF] Hannah | Multivariate convex regression with adaptive partitioning[END_REF]).

Piecewise-linear fitting problems can be classified into two categories: discontinuous and continuous ones. As for the discontinuous category, the problem focuses on constructing the general piecewise-linear model whose each affine submodel tries to fit the data points on the corresponding continuous subdomain. In related works (see, e.g., [START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF][START_REF] Taccari | Optimization methods for piecewise affine model fitting[END_REF]), the problem can be divided into two sequential subproblems. The first is a clustering problem for partitioning the data points and building the affine fitting submodels while the second is a classification problem for partitioning the domain with respect to the obtained submodels and the corresponding point partition. The recent work [START_REF] Amaldi | Discrete optimization methods to fit piecewise affine models to data points[END_REF] considered the problem of minimizing the mean-absolute error with a piecewise-linearly separable domain partition. The authors proposed a mix-integer linear program formulation with big-M for small-scale instances and then developed a four-step heuristic algorithm for solving it in medium-to-large-scale datasets.

Works in the class of continuous piecewise-linear fitting problems can be found in, e.g., [START_REF] Toriello | Fitting piecewise linear continuous functions[END_REF][START_REF] Bagirov | An algorithm for the estimation of a regression function by continuous piecewise linear functions[END_REF][START_REF] Friedman | Multivariate adaptive regression splines[END_REF]. The work [START_REF] Friedman | Multivariate adaptive regression splines[END_REF] proposed the well-known Multivariate Adaptive Regression Splines (MARS) method which consists in constructing the continuous fitting model in the form of an expansion in a set of basis functions (see, e.g., [START_REF] Yang | Mathematical programming for piecewise linear regression analysis[END_REF][START_REF] Friedman | Multivariate adaptive regression splines[END_REF][START_REF] Andrés | Bankruptcy forecasting: A hybrid approach using fuzzy c-means clustering and multivariate adaptive regression splines (mars)[END_REF][START_REF] Jekabsons | Areslab: Adaptive regression splines toolbox for matlab/octave[END_REF]). There are three forms of basis functions: a constant, a hinge function, and the multiplication of a number of hinge functions. Jekabsons [START_REF] Jekabsons | Areslab: Adaptive regression splines toolbox for matlab/octave[END_REF] developed an open source Matlab/Octave toolbox for building piecewise-linear and piecewise-cubic regression models using the MARS method. Another approach for solving this problem is based on discrete optimization and mixed-integer programming. The authors in [START_REF] Toriello | Fitting piecewise linear continuous functions[END_REF] introduced mixed-binary models under various conditions with the additional convexity-enforcing constraints. A drawback of this approach is the scalability of the obtained models. In addition, the work [START_REF] Bagirov | An algorithm for the estimation of a regression function by continuous piecewise linear functions[END_REF] considered the continuous piecewise-linear fitting problem with the MSE criterion over the class of maxima of minima of linear functions. In general, this problem is nonsmooth, nonconvex. Exploiting the semismooth, quasidifferentiable and piecewise partially separable properties of the objective function, the authors described a technique to approximate its subdifferential and then applied the Discrete Gradient Method (DGM) for directly solving the minimization problem. This method is impractical for large datasets. In the same direction but with the use of another method based on DC optimization, Bagirov et al. [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF] indicated that the objective function is, in general, a DC function without highlighting a DC decomposition. The authors designed a descent algorithm with a line search to find critical points. It computes search directions by calculating the distance between two polytopes approximating subdifferentials of DC components (without knowing the explicit form of these DC components). However, the computation of these subdifferentials stated in Proposition 2 of [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF] is not correct. A counterexample is given in Appendix A.

In this section, we consider the class of continuous piecewise-linear fitting problems. We show that these fitting problems can be formulated as the DC fitting problem (2) for which two proposed algorithms DCA and DCA k in Section 2 are applied.

Problem formulation

It is well-known from [START_REF] Gorokhovik | Piecewise affine functions and polyhedral sets[END_REF] that any continuous piecewise-linear function can be represented as a DC function:

φ(x) = f(x, α) = max j=1,...,K { x, a j + b j } -max q=1,...,M { x, a K+q + b K+q },
where the parameters a 1 , . . . ,

a K+M ∈ R p , b 1 , . . . , b K+M ∈ R, n = (K + M)(p + 1), and α = (a 1 , b 1 , . . . , a K , b K , a K+1 , b K+1 , . . . , a K+M , b K+M ) ∈ R n .
Obviously, φ ∈ F . Thus, the continuous piecewise-linear fitting problem can be rewritten as a DC fitting problem [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF] min

F (α) = m i=1 [(g i (α) -y i ) -h i (α)] 2 : α ∈ R n , (14)
where g i (α) := max j=1,...,K α, u (i,j) , h i (α) := max q=1,...,M α, v (i,q) , and for i = 1, . . . , m, j = 1, . . . , K, q = 1, . . . , M, the vectors

u (i,j) = (u (i,j) 1 , . . . , u (i,j) K , u (i,j) K+1 , . . . , u (i,j) K+M ) ∈ R n , v (i,q) = (v (i,q) 1 , . . . , v (i,q) K , v (i,q) K+1 , . . . , v (i,q) K+M ) ∈ R n , with u (i,j) r = (x i , 1) if r = j, (0, 0) if r = j; v (i,q) r = (x i , 1) if r = K + q, (0, 0) if r = K + q.
Next, we apply DCA and DCA k for solving the continuous piecewiselinear fitting problem [START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF]. In particular, we first show how to compute a subgradient, then solve the convex subproblem, and finally derive the resulting algorithms, named DCA-PL and DCA k -PL respectively.

DCA for solving the problem (14)

Compute a subgradient β k ∈ ∂H(α k ):

By the definition of H in ( 5), the subdifferential of H is defined as

∂H = m i=1 ∂[p i1 + p i2 + 2l i ] 2 .
Applying the inclusion 2r i (α)∂r i (α) ⊂ ∂[r i (α)] 2 for r i = p i1 + p i2 + 2l i , and summing this inclusion over i = 1, ..., m, we have

m i=1 2[p i1 (α) + p i2 (α) + 2l i (α)][∂p i1 (α) + ∂p i2 (α) + ∂(2l i )(α)] ⊂ ∂H(α).
Thus, we can choose a subgradient β k ∈ ∂H(α k ) as follows:

β k ∈ m i=1 2[p i1 (α k ) + p i2 (α k ) + 2l i (α k )][∂p i1 (α k ) + ∂p i2 (α k ) + ∂(2l i )(α k )]. Now, we need to compute subgradients γ i1 ∈ ∂p i1 (α), γ i2 ∈ ∂p i2 (α), γ k i1 ∈ ∂p i1 (α k ), γ k i2 ∈ ∂p i2 (α k ).
In particular, by the definition of p i1 , p i2 , l i and according to the rule of computing the subdifferential of a function being the maximum of a finite family of convex functions [START_REF] Valadier | Sous-différentiels dune borne supérieure et dune somme continue de fonctions convexes[END_REF], we have

∂l i (α) = {-γ i1 } if l i1 (α) < l i2 (α), {-γ i2 } if l i1 (α) > l i2 (α), [-γ i1 , -γ i2 ] otherwise, ∂p i1 (α) = ∂ max j=1,...,K α, u (i,j) -y i = co{u (i,j i ) : j i ∈ I i1 (α)}, ∂p i2 (α) = ∂ max q=1,...,M
α, v (i,q) = co{v (i,q i ) : q i ∈ I i2 (α)}, and

I i1 (α) := argmax j=1,...,K α, u (i,j) , I i2 (α) := argmax q=1,...,M α, v (i,q) .
Here [a, b] is a line segment between a and b, co denotes the convex hull of a set of points. Thus, we can take

γ i1 = u (i,j i ) , γ i2 = v (i,q i ) , γ k i1 = u (i,j k i ) , γ k i2 = v (i,q k i ) where j i ∈ I i1 (α), q i ∈ I i2 (α), j k i ∈ I i1 (α k ), q k i ∈ I i2 (α k ), i = 1, . . . , m. Finally, the subgradient β k ∈ ∂H(α k ) is computed as β k = 2 m i=1 [p i1 (α k ) + p i2 (α k ) + 2l i (α k )]× [γ k i1 + γ k i2 -2γ i1 -2(γ i2 -γ i1 )1 {l i1 (α)>l i2 (α)} (α k )]. (15)
Here the function 1 A (α) = 1 if α ∈ A, 0 otherwise.

Solve the convex subproblem (6):

The convex subproblem (6) can be reformulated as min

       m i=1 2(t i ) 2 + m i=1 2(τ i ) 2 -β k , α : t i ≥ -l i1 (α) + p i1 (α), i = 1, . . . , m, t i ≥ -l i2 (α) + p i1 (α), i = 1, . . . , m, τ i ≥ -l i1 (α) + p i2 (α), i = 1, . . . , m, τ i ≥ -l i2 (α) + p i2 (α), i = 1, . . . , m       
which is in fact a convex quadratic program of the form

               min α,t,τ m i=1 2(t i ) 2 + m i=1 2(τ i ) 2 -β k , α , s.t. t i ≥ α, u (i,j) -u (i,j i ) , i = 1, . . . , m, j = 1, . . . , K, t i ≥ α, u (i,j) -v (i,q i ) -y i , i = 1, . . . , m, j = 1, . . . , K, τ i ≥ α, v (i,q) -u (i,j i ) + y i , i = 1, . . . , m, q = 1, . . . , M, τ i ≥ α, v (i,q) -v (i,q i ) , i = 1, . . . , m, q = 1, . . . , M. (16)
Algorithm 1 DCA for the problem ( 14) (DCA-PL) [START_REF] Le Thi | DC programming and DCA for sparse Fisher linear discriminant analysis[END_REF]. 2. Solve the convex quadratic program [START_REF] Le Thi | DCA based algorithms for feature selection in multi-class support vector machine[END_REF] to obtain (α k+1 , t k+1 , τ k+1 ).

Initialization: Let α 0 ∈ R n . Set k = 0. repeat 1. Compute β k ∈ ∂H(α k ) using
3. k = k + 1. until Stopping criteria are satisfied.

DCA k for solving the problem (14)

At the iteration k in DCA k , we choose α = α k . In this case, j i = j k i , q i = q k i , and [START_REF] Le Thi | DC programming and DCA for sparse Fisher linear discriminant analysis[END_REF] as follows:

l ij (α k ) = p ij (α k ), γ ij = γ k ij . The computation of β k ∈ ∂H k (α k ) becomes simpler than
β k = 2 m i=1 p i (α k )[u (i,j k i ) -v (i,q k i ) ], j k i ∈ I i1 (α k ), q k i ∈ I i2 (α k ). ( 17
)
And the convex program in DCA k is the same as the convex quadratic program ( 16) with the indexes j i (resp. q i ) replaced by j k i (resp.

q k i ):                min α,t,τ m i=1 2(t i ) 2 + m i=1 2(τ i ) 2 -β k , α , s.t. t i ≥ α, u (i,j) -u (i,j k i ) , i = 1, . . . , m, j = 1, . . . , K, t i ≥ α, u (i,j) -v (i,q k i ) -y i , i = 1, . . . , m, j = 1, . . . , K, τ i ≥ α, v (i,q) -u (i,j k i ) + y i , i = 1, . . . , m, q = 1, . . . , M, τ i ≥ α, v (i,q) -v (i,q k i ) , i = 1, . . . , m, q = 1, . . . , M. (18)
Hence, DCA k differs from DCA by computing the subgradient β k and solving the convex quadratic program in the step 1 and step 2 respectively. The algorithm, named DCA k -PL, can be described as follows.

Starting point for the proposed DCA algorithms

In this section, we suggest a deterministic strategy to compute the starting point α 0 ∈ R n for the proposed DCA algorithms. From the fact that

f(x i , α) -y i = (g(x i , α) -y i /2) -(h(x i , α) + y i /2),
the idea is to fit the convex functions g(x, α) (resp. h(x, α)) to the data points {(x i , y i /2)} i=1,...,m (resp. {(x i , -y i /2)} i=1,...,m ), by the following strategy which is quite similar to the random version in [START_REF] Magnani | Convex piecewise-linear fitting[END_REF]: [START_REF] Phan | Sparse covariance matrix estimation by DCA-based algorithms[END_REF].

Algorithm 2 DCA k for the problem (14) (DCA k -PL) Initialization: Let α 0 ∈ R n . Set k = 0. repeat 1. Compute β k ∈ ∂H k (α k ) using
2. Solve the convex quadratic program [START_REF] Rockafellar | Convex Analysis[END_REF] to obtain (α k+1 , t k+1 , τ k+1 ).

3. k = k + 1. until Stopping criteria are satisfied.

Step 1: generate the set X 1 of K points in X = {x i } i=1,...,m using the KKZ method [START_REF] Katsavounidis | A new initialization technique for generalized lloyd iteration[END_REF] with the first point x = 1 m m i=1 x i ; then, similarly generate the set X 2 of M points in the set X \ X 1 with the same first point x in the KKZ method.

Step 2: find an index j 1 i ∈ {1, . . . , K} (resp. j 2 i ∈ {1, . . . , M}) (i = 1, . . . , m) such that the j 1 i -th point in X 1 (resp. the j 2 i -th point in X 2 ) is closest the point x i (see Voronoi partitions in [START_REF] Magnani | Convex piecewise-linear fitting[END_REF] for more details).

Step 3: compute the starting point

α 0 = (a 0 1 , b 0 1 , . . . , a 0 K , b 0 K , a 0 K+1 , b 0 K+1 , . . . , a 0 K+M , b 0 K+M )
where for j = 1, . . . , K, (a 0 j , b 0 j ) is an optimal solution to the linear leastsquare problem min

(a j ,b j ) i∈J 1 (j) ( a j , x i + b j -y i /2) 2 ,
with J 1 (j) := {i ∈ {1, . . . , m} : j 1 i = j}; and for j = 1, . . . , M, (a 0 K+j , b 0 K+j ) is an optimal solution to the linear least-square problem min

(a K+j ,b K+j ) i∈J 2 (j) ( a K+j , x i + b K+j + y i /2) 2 ,
with J 2 (j) := {i ∈ {1, . . . , m} : j 2 i = j}.

Numerical experiments

In this section, our experiments aim to show the efficiency of our DCAbased approach for solving the continuous piecewise-linear fitting problem [START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF]. In particular, we make a comparison between our algorithms DCA-PL and DCA k -PL with two methods mentioned in Section 3: Discrete Gradient Method (DGM) [START_REF] Bagirov | An algorithm for the estimation of a regression function by continuous piecewise linear functions[END_REF] for directly solving the problem [START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF] and Multivariate Adaptive Regression Splines (MARS) [START_REF] Friedman | Multivariate adaptive regression splines[END_REF] for constructing a piecewise-linear model. We test the four algorithms on two synthetic datasets D1-D2 and seven real datasets D3-D9, which are summarized in Table 1. We generate a synthetic dataset of the points {(x i , y i = ϕ(x i ))} i=1,...,m where x i ∈ X = {-v, -v + 1, . . . , v -1, v} 3 and the function ϕ : R 3 → R is defined as

ϕ(x) = ϕ(x 1 , x 2 , x 3 ) = ln(exp(x 1 ) + 2 exp(x 2 )) -ln(exp(x 2 ) + exp(x 3 )).
Two synthetic datasets, named log-exp6, log-exp7, corresponds to the value of v ∈ {6, 7}, respectively. Their numbers of data points, m, are 3375, 9261, respectively. The real datasets in many areas are taken from UCI machine learning repository1 and LIBSVM website2 . and the CPU time (in seconds).

Set up experiments: All experiments were performed on a PC Intel(R) Xeon(R) CPU E5-2630 v2, @2.60GHz of 32GB RAM and implemented in Matlab R2016b. The software CPLEX 12.8 was used for solving convex quadratic programs in DCA-PL, DCA k -PL, and DGM. The parameters of DGM are set the same as in [START_REF] Bagirov | An algorithm for the estimation of a regression function by continuous piecewise linear functions[END_REF]. The MARS method is implemented in a Matlab toolbox ARESLab [START_REF] Jekabsons | Areslab: Adaptive regression splines toolbox for matlab/octave[END_REF] and its parameters are set by default for piecewise-linear models. The stopping criterion at the iteration k for DCA-PL and DCA k -PL is

|MSE(α k ) -MSE(α k-1 )| ≤ ε(1 + MSE(α k-1 ))
or the CPU time exceeds the maximum time. The default tolerance ε is set to 10 -4 . The maximum time for all algorithms is set to 3600 seconds for D9 and 1800 seconds for the others. As for the synthetic datasets D1-D2, the pair (K, M) belongs to the set [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF][START_REF] Le | Analyse numérique des algorithmes de l'optimisation DC. approches locale et globale. codes et simulations numériques en grande dimension. applications[END_REF], [START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF][START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF], [START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF], [START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF][START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF], [START_REF] Le | Analyse numérique des algorithmes de l'optimisation DC. approches locale et globale. codes et simulations numériques en grande dimension. applications[END_REF][START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF], [START_REF] Le | Analyse numérique des algorithmes de l'optimisation DC. approches locale et globale. codes et simulations numériques en grande dimension. applications[END_REF][START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF], [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF][START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF], [START_REF] Le Thi | DC programming and DCA: thirty years of developments[END_REF][START_REF] Pham Dinh | Recent advances in DC programming and DCA[END_REF], [START_REF] Le Thi | A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning[END_REF][START_REF] Le Thi | The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems[END_REF], [START_REF] Le Thi | A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning[END_REF][START_REF] Pham Dinh | Recent advances in DC programming and DCA[END_REF] while it is set to [START_REF] Pham Dinh | DC optimization algorithms for solving the trust region subproblem[END_REF][START_REF] Pham Dinh | Convex analysis approach to DC programming: theory, algorithms and applications[END_REF] for the real datasets D3-D9 due to the best trade-off between rapidity and quality of solutions on synthetic datasets. The same starting point of three algorithms DCA-PL, DCA k -PL, and DGM is described in Section 3.4. The point α in DCA-PL is set to α 0 . We perform a validation procedure on real datasets to evaluate the piecewise-linear model obtained by the algorithm. In particular, each dataset is divided into two subsets: training set containing 80% of dataset, and test set containing 20% of dataset. First, we learn a piecewise-linear model on the training set. Then, we use that piecewise-linear model on the test set to compute the MSE.

Descriptions of results' tables: The comparative results of all four algorithms on two synthetic datasets in terms of the MSE and the CPU time with different pairs of (K, M) are reported in Table 2. As for seven real datasets, we report the MSE and the CPU time of our notable algorithm DCA k -PL and two existing algorithms DGM, MARS in Table 3. Comments on computational results: a) On two synthetic datasets D1-D2 (see Table 2): our DCA-based approach is more efficient than the others on both datasets with different pairs of (K, M). Indeed, the MSE of DCA-PL is better than that of DGM and MARS in most cases of D1-D2 -the ratio of gain of DCA-PL versus DGM and MARS in D1 (resp. D2) varies from 7.21% to 84.1% in 9/10 cases (resp. from 6.98% to 99.5% in 9/10 cases) and from 99.4% to 99.9% (resp. from 99.3% to 99.9%) in all cases, respectively. Meanwhile, DCA k -PL usually obtains the best fitting error with the ratio of gain versus DCA-PL, DGM, and MARS in D1 (resp. D2) from 32.7% to 87.9% in 8/10 cases (resp. from 28.2% to 96.4% in 9/10 cases), from 43.6% to 97.6% (resp. from 25.2% to 99.7%) in all cases, and from 99.5% to 99.9% (resp. from 99.7% to 99.9%) in all cases, respectively. On these two datasets, the MSE of DGM is smaller than that of MARS in all cases; MARS furnishes the worst MSE. In terms of CPU times, MARS runs the fastest while DCA k -PL is the best among three algorithms DCA k -PL, DCA-PL, and DGM for solving the same problem [START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF]. The ratio of gain of DCA k -PL versus DCA-PL and DGM on the dataset D1 (resp. D2) varies from 2.88 times to 6.36 times (resp. from 3.50 times to 6.94 times) and from 12.8 times to 51.3 times (resp. from 3.44 times to 15.9 times), respectively. DCA-PL is faster than DGM in all cases of D1 (resp. in 6/10 cases of D2) with the ratio from 2.18 times to 12.5 times (resp. from 1.52 times to 2.84 times). Note that DGM always exceeds the limited time (1800 seconds) on both datasets. b) On seven real datasets D3-D9 (see Table 3): concerning the MSE, DCA k -PL is more efficient than DGM and MARS on all seven datasets, specially large-scale datasets D7-D9. The ratio of gain of DCA k -PL versus DGM and MARS in terms of MSE varies from 0.59% to 97.1% and from 4.65% to 37.8%, respectively. Meanwhile, MARS is better than DGM on 4/7 datasets and runs the fastest. Regarding the CPU time for solving the problem [START_REF] Le Thi | Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification[END_REF], DGM consumes more time than DCA k -PL on all datasetsthe ratio of gain of DCA k -PL versus DGM varies from 1.09 times to 33.9 times.

Conclusions

We have investigated DC programming and DCA for solving a wide class of DC fitting problems. Two DCA schemes have been developed: a standard DCA and its modified version DCA k with successive DC decomposition. The DCA k differs from the DCA in that the DC decompositions are updated during DCA iterations in order to better approximate the DC objective function. These two DCA-based algorithms have been deployed for solving the continuous piecewise-linear fitting problem. The numerical results on nine synthetic and real datasets with small-to-large sizes have turned out that, on both quality and rapidity, the proposed DCAs outperform the related existing approaches and the DCA k is better than the standard DCA. We plan in future works to develop our DC programming and DCA-based approach for fitting applications. As stated in Proposition 1 in [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF], the function F is a DC function without its explicit DC representation. The functions ψ ik and ϕ i are DC, and their DC decompositions are ψ ik (x, y) = ψ 1 ik (x, y)ψ 2 ik (x, y), ϕ i (x, y) = ϕ i1 (x, y)ϕ i2 (x, y). Proposition 2 in [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF] was stated as follows.

Let F 1 and F 2 be DC components of the function F : F (x, y) = F 1 (x, y)-F 2 (x, y), (x, y) ∈ R nq × R q . Then subdifferentials of the functions F 1 and F 2 at (x, y) can be expressed as: We see that this proposition is not true for any DC components F 1 and F 2 of F , and the following is a counterexample. We consider the linear regression problem, a special case of the considered problem when K = 1 and M K = 1. The problem (A. we have that ϕ i (x, y) = ψ i1 (x, y) = x, a i + y, ψ 1 i1 (x, y) = ψ i1 (x, y), ψ 2 i1 (x, y) = 0, ϕ i1 (x, y) = ϕ i (x, y), and ϕ i2 (x, y) = 0. It is obvious that F is a convex function and thus, we have trivial DC components of F : F 1 = F and F 2 = 0. (A.4)

Consequently, the subdifferential ∂F 2 (x, y) = {0} for all (x, y), which contradicts the fact from (A.3) that ∂F 2 (x, y) = -i∈I-(x,y) (ϕ i (x, y)-b i )∂ϕ i (x, y).

It concludes that the subdifferentials (A.2) and (A.3) do not hold for any DC components of F -that is to say, Proposition 2 is false.

  Comparison criteria: We are interested in the following criteria to evaluate the effectiveness of DCA-PL and DCA k -PL when comparing with DGM and MARS: the mean-square error (MSE) defined as MSE

where x = x 11 1 , 1 ,

 11 . . . , x 11 n , . . . , x KM K . . . ,x KM K n ∈ R nq , y = (y 11 , . . . , y KM K ) ∈ R q , q = K k=1 M k , ϕ i (x, y) = max k=1,...,K ψ ik (x, y), ψ ik (x, y) = min j=1,...,M k { x kj , a i + y kj }, i = 1, . . . , m, k = 1, . . . , K.Let us define the functionsψ 1 ik (x, y) = M k j=1 ( x kj , a i + y kj ), i = 1, . . . , m, k = 1, . . . , K, ψ 2 ik (x, y) = max j=1,...,M k k t=1,t =j ( x kt , a i + y kt ), i = 1, . . . , m, k = 1, . . . , K, ϕ i1 (x, y) = maxk=1,...,K ψ 1 ik (x, y) + K j=1,j =k ψ 2 ij (x, y) , i = 1, . . . , m, ϕ i2 (x, y) = K j=1 ψ 2 ij (x, y), i = 1, . . . , m.

∂F 1

 1 (x, y) = 2   i∈I+(x,y) (ϕ i (x, y)b i )∂ϕ i1 (x, y)-i∈I-(x,y) (ϕ i (x, y)b i )∂ϕ i2 (x, y)   , (A.2) ∂F 2 (x, y) = 2   i∈I+(x,y) (ϕ i (x, y)b i )∂ϕ i2 (x, y)-i∈I-(x,y) (ϕ i (x, y)b i )∂ϕ i1 (x, y)   . (A.3) Here I + (x, y) = {i ∈ I : ϕ i (x, y) > b i }, I -(x, y) = {i ∈ I : ϕ i (x, y) < b i }.

  a i + y)b i 2 ,

Table 1 :

 1 Descriptions of datasets: p is the dimension of the space; m is the number of data points.

	Data Name	m p
	D1	log-exp6	3375	3
	D2	log-exp7	9261	3
	D3	Yacht hydrodynamics	308	6
	D4	housing	506 13
	D5	abalone	4177	8
	D6	White wine quality	4898 11
	D7	Combined cycle power plant	9568	4
	D8	cadata	20640	8
	D9	Physicochemical properties of 45730	9
		protein tertiary structure

Table 2 :

 2 Comparative results of four algorithms DCA-PL, DCA k -PL, DGM and MARS on two synthetic datasets D1 and D2 in terms of Mean-Square Error (MSE) and CPU time (in seconds). Bold values indicate the best results for each pair (K,M ).

			Mean-Square Error MSE	CPU (in seconds)
	Data K M	DCA-PL DCA k -PL	DGM	DCA-PL DCA k -PL	DGM
	D1	2 4	2.19e-02 1.33e-02 2.36e-02	2.94e+02 4.78e+01 1.80e+03
		2 6	1.92e-02 1.29e-02 2.64e-02	3.28e+02 5.81e+01 1.80e+03
		3 2	1.89e-02 1.93e-02	4.32e-02	1.44e+02 3.51e+01 1.80e+03
		3 3	6.92e-03 7.71e-03	2.37e-02	2.37e+02 3.73e+01 1.80e+03
		4 3	8.18e-03 2.75e-03 2.42e-02	2.49e+02 6.81e+01 1.80e+03
		4 5	8.13e-03 4.31e-03 2.40e-02	3.00e+02 7.60e+01 1.80e+03
		6 5	7.73e-03 1.48e-03 2.25e-02	6.16e+02 1.05e+02 1.80e+03
		6 7	1.68e-02 2.03e-03 1.22e-02	8.25e+02 1.40e+02 1.80e+03
		8 5	3.74e-03 5.63e-04 2.37e-02	4.06e+02 9.32e+01 1.80e+03
		8 7	6.03e-03 1.05e-03 2.33e-02	3.46e+02 1.20e+02 1.80e+03
		MARS	MSE = 4.26e+00	CPU = 2.43e-01
	D2	2 4	2.38e-02 1.30e-02 2.56e-02	1.18e+03 1.70e+02 1.80e+03
		2 6	1.81e-02 1.30e-02 4.27e+00	1.16e+03 2.21e+02 1.80e+03
		3 2	1.89e-02 1.92e-02	2.57e-02	6.34e+02 1.13e+02 1.80e+03
		3 3	1.82e-02 5.94e-03 2.53e-02	7.27e+02 1.27e+02 1.80e+03
		4 3	5.72e-03 2.47e-03 2.56e-02	9.59e+02 2.38e+02 1.80e+03
		4 5	7.59e-03 4.12e-03 3.19e-02	1.16e+03 2.84e+02 1.80e+03
		6 5	1.15e-02 1.40e-03 2.39e-02	1.81e+03 3.32e+02 1.80e+03
		6 7	5.78e-02 2.04e-03 4.80e-02	1.80e+03 4.12e+02 1.80e+03
		8 5	6.53e-03 4.76e-04 2.82e-02	1.80e+03 2.95e+02 1.80e+03
		8 7	9.43e-03 9.88e-04 2.36e-02	1.83e+03 5.23e+02 1.80e+03
		MARS	MSE = 8.97e+00	CPU = 5.13e-01

Table 3 :

 3 Comparative results of our algorithm DCA k -PL, MARS and DGM on seven real datasets in terms of the mean-square error (MSE) and CPU time (in seconds). Bold values indicate the best results.

	MSE	CPU (in seconds)

http://www.ics.uci.edu/ ~mlearn/MLRepository.html

https://www.csie.ntu.edu.tw/ ~cjlin/libsvmtools/datasets/

Acknowledgment

This research is funded by Foundation for Science and Technology Development of Ton Duc Thang University (FOSTECT), website: http://fostect.tdtu.edu.vn, under Grant FOSTECT.2017.BR.10.

Appendix A.

In this appendix, we indicate a falsehood of Proposition 2 from the article [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF]. Before doing that, we briefly introduce the maxima of minima of linear fitting problem presented in [START_REF] Bagirov | A difference of convex optimization algorithm for piecewise linear regression[END_REF].

Given the set of data A = {(a i , b i ) ∈ R n × R : i ∈ I := {1, . . . , m}}, the optimization problem can take of the form

where the set of continuous piecewise linear functions, denoted F , is defined as: for K ∈ N, M 1 , . . . , M K ∈ N,

It can be reformulated as


Sonesimmaly Soukhasem

Pierre-Marie Sannikone

Farid Preux

Boumédiène

Mayoura Bounlu

Dr Emilie Auditeau
email: emilie.auditeau@unilim.fr

Somchit Vorachit

Phetvongsinh Chivorakoun

Vimalay Souvong

Thidachanh Soukhasem

Sonesimmaly Sannikone

Pierre-Marie Preux

Farid Boumediene

Management of epilepsy in Laos: Perceptions of healthcare professionals from Vientiane Capital province and traditional healers in Southern Laos

Keywords: Neurological disease, traditional medicine, conventional medicine, treatment gap, Southeast Asia epilepsy, traditional medicine, conventional medicine, traditional healer, treatment gap

Introduction

Epilepsy is a chronic brain disorder that affects about 70 million people worldwide [START_REF] Anthony | Estimation of the burden of active and life-time epilepsy: A meta-analytic approach[END_REF] . Epilepsy affects about 1% of the population in Southeast Asia region; thus, there are approximately 15 million people with epilepsy in the region. Only 10-20% of all people living with epilepsy (PWEs) receive appropriate treatment; communities in Southeast Asia continue to believe in many myths and misconceptions about epilepsy [START_REF]Epilepsy in the WHO South-East Asian Region: Bridging the Gap. The Global Campaign Against Epilepsy "Out of the Shadows[END_REF] . In Eastern and South Eastern Asian languages, such as Chinese, Japanese, Korean, Malay, Lao, Thai, Burmese, and Khmer (Cambodia) epilepsy is associated with madness [START_REF] Lim | Name of epilepsy, does it matter?[END_REF] . In many cultures, including in Africa and Asia, people with epilepsy (PWEs) are viewed with hostility and denied access to medical and social care. PWEs are excluded from society: exposed to social and religious taboos, isolated, sometimes with no right to have children or marry [START_REF] Moselhy | Psychosocial and Cultural Aspects of Epilepsy[END_REF] , are excluded from jobs, and are not allowed to have contact or to share meals with other people [START_REF] Tran | Epilepsy in Laos: knowledge, attitudes, and practices in the community[END_REF] .

Epilepsy is a controllable disease in the majority of PWEs. The goal of treatment is to maintain a healthy lifestyle, ideally by complete seizure control with no or minimal side effects. Antiepileptic drugs (AEDs) are the main treatment [START_REF] Prilipko | Atlas : Epilepsy Care in the World[END_REF] , and are the usual first line step in the management of epilepsy for the majority of PWEs [START_REF] Glauser | ILAE Treatment Guidelines: Evidencebased Analysis of Antiepileptic Drug Efficacy and Effectiveness as Initial Monotherapy for Epileptic Seizures and Syndromes[END_REF] . In Asian countries, the treatment gap is 64.0% [START_REF] Trinka | Epilepsy in Asia: Disease burden, management barriers, and challenges[END_REF] , and higher in rural areas than in urban areas, particularly because of a lack of knowledge on epilepsy and the low availability of AEDs [START_REF] Mac | Epidemiology, aetiology, and clinical management of epilepsy in Asia: a systematic review[END_REF] .

In developing countries, traditional healthcare systems compete or complement conventional medicine [START_REF] Danesi | Use of Alternative Medicine By Patients With Epilepsy -a Survey of 265 Epileptic Patients in a Developing-Country[END_REF] . Faith healers have strong social and religious connections; they also play an essential role in the management of epilepsy in some countries. Especially in communities in Southeast Asia, where PWEs are sometimes more likely to consult traditional healers than conventional doctors [START_REF]Epilepsy in the WHO South-East Asian Region: Bridging the Gap. The Global Campaign Against Epilepsy "Out of the Shadows[END_REF] . Despite a lack of national policy program on epilepsy in Laos, recent research studies in collaboration with several centers provided an overview of the state of knowledge [START_REF] Barennes | The challenge of epilepsy in low-income countries insights from Laos[END_REF] . The overall prevalence of epilepsy was 7.7 cases per thousand inhabitants in 2006 [START_REF] Tran | Prevalence of Epilepsy in a Rural District of Central Lao PDR[END_REF] . The treatment gap was 90% or more, the low level of knowledge of epilepsy on the part of health workers may be contributing to the wide treatment gap in Laos [START_REF] Tran | Prevalence of Epilepsy in a Rural District of Central Lao PDR[END_REF] . A low availability of AEDs throughout the country was reported with an annual importation of phenobarbital allowing to treat around 2% of PWEs and a price of annual treatment 4-to 10-fold higher than the international price [START_REF] Barennes | Epilepsy in Lao PDR: From research to treatment intervention[END_REF] . Only a mean of one PWE per month per hospital is being cared in Lao hospitals [START_REF] Barennes | The challenge of epilepsy in low-income countries insights from Laos[END_REF] . PWEs face many challenges to get access to appropriate healthcare: a study in 2013 showed that PWEs combined conventional and traditional medicines treatments [START_REF] Harimanana | Is insufficient knowledge of epilepsy the reason for low levels of healthcare in the Lao PDR?[END_REF] Our study aimed to understand the perceptions of healthcare professionals and traditional healers regarding the management of epilepsy in Laos, and their reciprocal views on traditional and conventional medicines, in order to improve the management of epilepsy.

Method

Study Area

An observational descriptive study was carried out from February to May 2017 by using semi directive questionnaires. The selection procedure of participants was concentrated in 2 areas of Laos.

First, in Vientiane Capital (Figure 1), a well-known area included in the Domestic Health Visitors for improving access to care for people with epilepsy in Laos (DHeVeLoP project 2014-2016) [START_REF] Boumédiène | Development of an interventional strategy for the management of epilepsy in South-east Asia[END_REF] . Most of participants were the members of the Lao Association for Patients with Epilepsy (APE), and lived in the capital. The APE was established in 2011 with four main activities: organizing scientific conferences on epilepsy, providing three days training on epilepsy to health personal at both provincial and district levels, supporting the provision of antiepileptic drugs through a revolving drug fund at provincial and district hospitals, and promoting the dissemination of information on epilepsy to the public [START_REF] Akkhavong | The Lao People's Democratic Republic Health System Review[END_REF] . There are also market trade centers for traditional medicine (sellers of medicinal plants). The second area was Champasak Province, which located in the South of Laos, it is about 700 kms away from Vientiane Capital (Figure 1). This province has a strong cultural and religious environment, the largest number of traditional healers, and there is a Traditional Medicine Centre site in the Provincial Hospital.

Participants

Healthcare professionals

The participants in the conventional group were selected from the list of healthcare professionals from the Lao Association for Patient with Epilepsy 17 .

We performed an exhaustive sampling: all healthcare professionals (nurses and general practitioners) of the list from the association for people living with epilepsy that have been found in both study areas (Vientiane Capital and Champasak Province) were included. Then, we also automatically included health personnel in the neurology and mental health services who provided epilepsy treatment although they were not a member of the association.

Traditional Healers

With the assistance of the Provincial and District Health Units, and especially the Provincial Hospital Traditional Medicine Centre, as well as through the herbal market, we were able to identify traditional healers. In addition, a snowball sampling technique was used, allowing recruiting traditional healers who were familiar and lived in the same villages as PWEs.

All participants had to know at least one traditional remedy for treating epilepsy. We included all types of traditional medicine players (traditional healers and sellers of medicinal plants). They had to be present at the time of our survey and willing to participate.

Semi-structured interviews

We organized individual interviews using two semi-structured questionnaires and interview guides, one for healthcare professionals and one for traditional healers. The questionnaire for healthcare professionals consisted of four sections: sociodemographics, knowledge (epilepsy training), attitudes and practices regarding epilepsy and its treatments. It included seven questions in total, two closed questions, and five open-ended questions. The questionnaire for traditional healers consisted of five sections: sociodemographic data, experience with conventional medicine, knowledge, attitudes, and practices regarding epilepsy and its treatments. There were in total eight open-ended questions to allow a good free expression on these topics.

Questionnaires were initially developed in English with the agreement of the research team, and then they were translated in Lao language. The Lao questionnaires were field tested in Vientiane capital with 10 participants prior to conducting field work.

Before starting the interview, the researcher explained in detail the topic and the objective of the discussion. All individual interviews were conducted by the first author (bilingual, native of Laos) at the residence of participant from the traditional healers' group. For the conventional group, they could choose the place where it was most convenient for them. The researcher allowed participants to share their opinions without influencing the answers. If necessary, more specific questions were then asked. We worked closely with local healthcare professionals (who acted as mediators) for better communicating and comprehensive of a local term, so the participants would be able to provide rich information. Each individual interview would take a minimum of 50 minutes; interviews were recorded after seeking authorization from the participants. Interviews recorded in Lao were then translated in English.

Ethical considerations

Written consent was systematically obtained before the interviews. Our study was authorized by the Lao National County of Ethics for Health Research (No 032/NIOPH/NECHE and No044/NECHR) and the Ministry of Health, Laos (Agreement No 0397 dated 04/03/2016).

Data analysis

Our main objective was focused on understanding the perceptions of traditional healers and healthcare professionals on epilepsy management by using two different analytical approaches.

Qualitative analyses

Thirteen open-ended questions, reverse translations, and transcriptions were carried out by the bilingual interviewer, a native of Laos (1 st author). We used the thematic analysis methodology, first identifying key themes within data, and encoding before interpretation. The lexical analysis was based on semantic occurrences, which allowed coding (in qualitative value) according to the most frequently cited modalities and was presented by a proportion. The validity of the coding was based on the consensual coding of two researchers (1 st and 2 nd author). When differences emerged, a consensus was sought with a third researcher. These questions were then analyzed as closed multiple-choice questions by proportion analysis.

We used semiotic square in order to highlight relationships between attitudes of traditional healers and healthcare professionals through the negative and positive answers.

Quantitative analyses

Transcriptions and coding of the lexical segments of interest were carried out using the functionalities of the Word software; then the coded data were stored in Microsoft Excel. The statistical analyses were performed using STATA 13 software. For dichotomous and closed-ended questions, the proportions were reported, and the tests used were Chi2 or Fisher's test. Their mean and standard deviation expressed the quantitative variables, and the Student's t-test was used. The significance threshold for all analyses was set at 0.05.

Results

Sociodemographic data

Fifty-six participants were interviewed: 34 healthcare professionals and 22 traditional healers (Figure 1). Women represented 61.8% in the group of healthcare professionals in contrast with the traditional healers' group, where the male population was predominant (95.5%); the difference between two groups was significant (p<0.0001). The participants were mostly Buddhists (98.2%) and in the traditional healers' group, they were significantly older than in the conventional group (p<0.0001). Only one traditional healer (4.6%) had completed a university degree compared to 100% of subject in the healthcare professionals' group (p<0.0001) (Table 1).

Knowledge and practice of traditional healers on epilepsy

Epilepsy was cited by 91% of traditional healers as a convulsive disease with saliva or urine, followed by a neurological disease (41%). The perception of a supernatural disease was not found in the participants of the survey. Fifty-four percent had learned about traditional medicine from their family and they stated this practice was a Lao folk custom. When we questioned if the participant knew another remedy to treat epilepsy beside a traditional remedy, about 41% mentioned biomedical medicine as a treatment for epilepsy. Forty-one percent had no restriction if patient would like to combine antiepileptic drugs with traditional remedy.

Epilepsy remedy of traditional healers

Herbal medicines were predominantly used by traditional healers (86.4%) and 31.8% of them used bone or teeth from animals. The participant explained the reason of using traditional remedies by a familiarity and a tradition behavior (54.5%). Food restrictions were mentioned for PWEs being treated with traditional medicine (68.2%). For some traditional healers, the only advice given to PWEs was to be careful about epileptic seizures (31.2%). Regarding the combination of traditional and biomedical treatments, 45.5% of traditional healers said it was the patient's decision. Forty-one percent stated that patients could combine a traditional remedy with AEDs with no restriction (Table 2).

Attitudes of healthcare professionals on epilepsy care pathway

Thirty-four healthcare professionals were interviewed about their opinion on epilepsy management in Laos (Table 3). Only 21% reported that they received initial training in epilepsy as part of their medical curriculum. Sixty one percent mentioned that continuous training had improved their knowledge on epilepsy and 50% stated they had the capacity to diagnose and prescribe antiepileptic drugs (AEDs).

Very few participants pointed out that they knew treatments other than AEDs (26.5%): among those who knew, 20.6% mentioned traditional ceremonies and 11.5% herbal medicines, only one healthcare professional mentioned surgery. Otherwise, 41.2% of participants stated that only AEDs could treat epilepsy, and that traditional remedies or herbal medicine were ineffective. Anyhow, if PWEs would like to combine, they could (38.2%).

Conventional doctor and traditional healers' attitudes on epilepsy treatment

We synthesized participants' attitudes according to semiotic squares in Figure 2 (A&B). Regarding the opinions on AEDs, the figures were categorized in more positive and more negative attitudes for better understanding. In the conventional group, 61.8% mentioned that AEDs were available and affordable, but some of them (44.1%) stated AEDs geographical availability could be limited, potentially leading to low adherence to treatment for PWEs (32.4%). For the traditional healers' group, AEDs were considered by 68.2% of participants to increase the pharmacological effect of traditional remedies. Although, 13.6% of participants thought AEDs were used to control the epileptic seizures, not to treat epilepsy cause.

The second question was focused on the perception regarding traditional remedies. Participants in the conventional group had more negative attitudes on traditional medicine: 76.5% mentioned that epilepsy was a neurological disease which only AEDs could treat. Only 14.7% said it could be combined with AEDs as traditional medicine was about providing psychosocial support to PWEs. In the traditional healers' group, traditional medicine was considered as more natural (organic means) and moreover, it could cure completely epilepsy when used over the long-term (54.5%). Thirty-six percent of traditional healers stated that the effectiveness of traditional remedies was unpredictable.

For the collaboration between conventional and traditional medicine, 90.9% of traditional healers said it was a good idea. In contrast, with the conventional group in which 44.1% stating, it was complicated.

Discussion

Conventional and traditional medicine for epilepsy management

Traditional medicine remains an important part of the health care system, particularly in Asian and African countries [18][START_REF] Sydara | Use of traditional medicine in Lao PDR[END_REF][START_REF] Abdullahi | Trends and Challenges of Traditional Medicine in Africa[END_REF] . Traditional healers showed a positive attitude regarding the collaboration with healthcare professionals for epilepsy treatment. Most of them said the cooperation was an excellent approach but only 13.0% of traditional healers recommend PWEs taking a traditional remedy and an AED at the same time. A study in Burkina Faso demonstrated that most healers (more than 90.0%) wished to be integrated into the modern healthcare system and considered that both kinds of treatments were complementary [START_REF] Millogo | Epilepsy and traditional medicine in Bobo-Dioulasso (Burkina Faso)[END_REF] . A study conducted in Cape Town in 2015 showed that traditional healers were supportive of collaboration with western-trained practitioners [START_REF] Keikelame | A Thing Full of Stories': Traditional healers' explanations of epilepsy and perspectives on collaboration with biomedical health care in Cape Town[END_REF] . Conversely, the study in Ivory Coast highlighted that traditional healers would recommend the sudden discontinuation of modern medicines in preference to traditional treatment, this attitude reflecting their relative ignorance about modern treatments [START_REF] François | Tradipraticiens et épilepsies en Côte d'Ivoire[END_REF] . In our study, almost half healthcare professionals thought that collaboration with traditional healers was complicated and only thirty-eight percent stated it was good. We noticed that they were likely to not recommend complementary treatment, unlike patients in Peru, in which it was showed the traditional medicine has been chosen by PWEs instead of conventional treatment (p=0.024) [START_REF] Auditeau | Herbal medicine uses to treat people with epilepsy: A survey in rural communities of northern Peru[END_REF] .

It is interesting to discuss why they had a different perspective, especially because our study shows a contradictory perception between the two groups. First, if we consider sex and age, we observed that the participants' traditional groups were significantly older than those of the conventional group. Older adults perceive pictures differently than younger adults; older adults focus more on positive affect [START_REF] Neiss | Age differences in perception and awareness of emotion[END_REF] . There was also a greater proportion of males in the group of traditional healers similar to the study in Burkina Faso by Abdullahi et al. (2011), regarding traditional healers' knowledge and attitudes towards epilepsy, all traditional practitioners were male and most of them were above 50 years of age [START_REF] Millogo | Epilepsy and traditional medicine in Bobo-Dioulasso (Burkina Faso)[END_REF] . In Lao context, men are considered culturally superior because of their ability to become monks. Men are generally recognized as the household head for religious and political purposes [START_REF] Leigh | Lao Culture and Profile[END_REF] . Being a traditional healer in Laos means they have to respect many cultural rules, so it is not too different from being a religious leader.

Knowledge, Attitudes and Practices regarding on epilepsy care

Epilepsy was seen largely as a convulsive disease with saliva or urine flowing out by traditional healers. The perception that epilepsy has a supernatural origin was not found for traditional healers and healthcare professionals but was previously reached by PWE, their families and villagers [START_REF] Tran | Epilepsy in Laos: knowledge, attitudes, and practices in the community[END_REF] . A study in Ivory Coast demonstrated that for more than 80.0% of traditional practitioners, epilepsy was a supernatural disease [START_REF] François | Tradipraticiens et épilepsies en Côte d'Ivoire[END_REF] . Our results, and those of the study in Ivory Coast [START_REF] François | Tradipraticiens et épilepsies en Côte d'Ivoire[END_REF] , suggest that herbal treatments are the main remedy used by traditional practitioners, 86.4% and 97.0% respectively. In Latin America, a study conducted in Peru showed the traditional healers were more frequently consulted than healthcare professionals for first-line antiepileptic treatment. More than 60.0% of PWEs and 80.0% of traditional healers, used herbal remedies in this survey, and supernatural etiologies were mentioned by 23.4% of PWEs [START_REF] Auditeau | Herbal medicine uses to treat people with epilepsy: A survey in rural communities of northern Peru[END_REF] . By contrast, in Malaysia in 2008, Razali et al. showed that 75.0% of epileptic patients used Holy water and only 12.5% herbal medicine [START_REF] Razali | Complementary Treatment of Psychotic and Epileptic Patients in Malaysia[END_REF] .

Awareness campaigns provided by healthcare system mentioned 38.2% of PWEs and their families had limited understanding about epilepsy and medicals staff in rural areas had poor knowledge on epilepsy (23.5%) [START_REF] Odermatt | Availability and Costs of Antiepileptic Drugs and Quality of Phenobarbital in Vientiane Municipality, Lao PDR[END_REF] . More than half of healthcare professionals mentioned that continuous professional training could be applied to increase knowledge on epilepsy treatment and allowed them to have the ability to diagnose and prescribe antiepileptic drugs (AEDs). The professional training that they referred to was the activities of the program DHeVeLoP (2014-2016) and of the Lao Association for patients living with epilepsy (Lao APE) [START_REF] Chivorakoun | Lao Association for Patient with Epilepsy: Report of activity 2011-2014[END_REF] . This suggested a positive outcome of the intervention activities compared to the previous study conducted in 2013 which indicated a low knowledge of epilepsy for healthcare workers in Laos [START_REF] Harimanana | Is insufficient knowledge of epilepsy the reason for low levels of healthcare in the Lao PDR?[END_REF] . Two important changes in the management of epilepsy were made between the studies: the APE provided AEDs and the domestic health visitors were trained about the disease in the second study. A randomly selected health workers study conducted in 2009 reported only 2.5% of them recalled ever having received training on epilepsy and our study highlighted a poor knowledge of the medical staff for less than 25% of the healthcare professionals surveyed. The majority of the health workers (59.9%) were unaware of any available AEDs at the health facilities [START_REF] Tran | Prevalence of Epilepsy in a Rural District of Central Lao PDR[END_REF] and 55.9% perceived difficulties of AEDs management and accessibility in the present study.

The availability of antiepileptic drugs (AEDs) seems to be a serious barrier to the management of epilepsy: participants in the conventional group mentioned that AEDs were available and affordable with some of them stating that their geographical availability across the country could be limited.

Many studies in Laos already highlighted that AEDs had very low availability especially in rural areas 28,29 . Traditional or herbal medicines were considered as ineffective (41.2%) but the study conducted in 2018 in Laos suggested that more than 50% of PWEs had already consulted a traditional practitioner to treat their epilepsy 30 . Only thirty-eight percent agreed about the combination of conventional and traditional medicines based on patient's needs.

Strengths and limitations

Our study was the first study in Laos conducted to understand the perceptions of healthcare professionals and traditional healers regarding epilepsy treatment. Exploratory research is effective in laying the foundation for future studies. All information collected was original data; individual interviews helped participants to discuss contentious issues in more depth, allowing flexibility, and adaptability to the local context.

A rather modest number of subjects in the samples, which may not adequately represent the target population, was surveyed. The identification of participants, especially traditional healers was not easy because not every Traditional Medicine Centre has a list of registered traditional healers resulting in a lower number of traditional healers answered in comparison with healthcare professionals. Thus our sample has a limited representativeness, which makes extrapolation of the results in the national context difficult. Additionally, it could have been interesting to interview traditional healers from the North of Laos who have different cultural background and medicine healthcare, influenced by Chinese traditional medicine.

Exploratory studies generate qualitative information and interpretation of such type of information is subject to biases. That is the reason why we combined qualitative and quantitative approaches: some qualitative answers were then categorized into quantitative variables (after consultation with several authors). Although it can lead to a loss of information from interviews, it has the benefit of allowing quantitative analyses.

The healthcare seeking behavior of mixing remedies has long been observed. It is time for healthcare professionals to be more willing to accept complementary and alternative remedies.

Implications for practice and conclusion

Most traditional healers said the collaboration with healthcare professionals was a good idea and nearly half of the healthcare professionals believed it would be complicated. Healthcare professionals reported than AEDs have a low compliance, mainly due to occasional availability. For them, traditional medicine could be used in association with AEDs as non-medical remedies and could play a psychotherapeutic role. Traditional healers mentioned that traditional medicine provides unpredictable effectiveness. Most of them indicated that AEDs will be interesting in order to increase the efficacy of the traditional remedy. For both groups of caregivers, it would be relevant to use the effects of traditional medicine coupled with those of AEDs.

Understanding the attitudes of the conventional doctor towards traditional medicine will be useful in implementing future integration of complementary and alternative medicine (CAM). The institutional recognition of traditional medicine, recommended by the WHO in its strategy 2014-2023, promote the safe and effective use of CAM through the regulation of products, practices, and practitioners.

Healthcare professionals need to be aware of their presence and their role as a potential referral to healthcare, considering the holistic, humanitarian and individualized views of the traditional healer, and the interesting therapeutic and palliative effect of CAM in chronic diseases.

This study showed steps forward in epilepsy management in the Lao medical context. Further research on the combination of traditional and conventional medicine for epilepsy is required and will bring us closer to the patient. A better understanding of the care pathway will help reduce the treatment gap. This research did not receive any specific grant from funding agencies in the public, commercial, or not-forprofit sectors.

Healthcare professionals

Conventional medicine

Traditional medicine

Traditional healers

  . Traditional practices are deeply rooted in Lao people's perceptions and beliefs about health and illness. The use of traditional medicine has recently become more popular and accessible, and in response, the Ministry of Health has launched a policy in support of integrating traditional medicine with Western medicine. The Centre for Research on Medicinal Plants and Traditional Medicine was upgraded to a national institute in 2009. In 2014, the Food and Drug Department provided a census of traditional medicines but guidelines for the safe use have not yet been formulated. The first national traditional medicine policy and strategy are under discussion 15 .

Table 1 :

 1 30. Bounlu M, Auditeau E, Vorachit S, et al. Explanatory factors of adherence to community-based management of epilepsy in Lao PDR. Epilepsy Behav. 2018;88:74-80. Sociodemographic characteristics of participants interviewed

	1

Table 2 :

 2 Knowledge and practices towards epilepsy of traditional healers

	Traditional healers
	N=22

on epilepsy and epilepsy remedy What is epilepsy, also called mad pig disease?

	(multiple answers)
	Convulsive disease with saliva/urine	(90.9%)
	Neurological disease	(40.9%)
	Disease of the blood system	(31.8%)
	Disease of nerve fibers /tendons	(27.3%)
	Hereditary disease	(27.3%)
	Do

you know epilepsy remedies other than your epilepsy treatment methods?

	Yes	(50.0%)
	Biomedical medicine	(40.9%)
	Acupuncture	(9.1%)
	No	(50.0%)
	How did you learn about traditional medicine? (multiple answers)
	Family knowledge	(54.5%)
	Learned at the temple (learned with a monk)	(18.2%)
	Learned by ancient traditional healer	(13.6%)
	The only one remedy access to care in rural area	(13.7%)
	Have been chosen by a spirit to become a healer	(13.7%)
	Practices on epilepsy
	Which methods do you use to treat epilepsy? (multiple answers)
	Herbal medicines	(86.4%)
	Animals (bone, teeth)	(31.8%)
	Other	(18.2%)
	Why do you use traditional remedy? (multiple answers)
	This is a tradition/ these traditions exist in Lao folk custom	(54.5%)
	Generation-to-generation knowledge	(36.4%)
	Fewest side effects	(31.8%)
	Restrictions? Yes
	Food diet	(68.2%)
	No restrictions, just advise him to be careful about the seizures	(31.2%)
	Drinking alcohol	(18.2%)

Advice for PWEs who want to use antiepileptic drugs

	Patient's preference	(45.5%)
	In association with no restriction	(40.9%)
	One after the other	(13.6%)

Table 3 :

 3 Opinion of healthcare professionals on epilepsy care

	Healthcare
	professionals
	(N=34)

Opinion on the epilepsy care system in Laos Positive attitude

		Continuous training enabling to increase knowledge	(61.8%)
		Capacity of diagnosis & prescription of AEDs	(50.0%)
		Improvement of the patient's quality of life	(23.5%)
		Difficulty of AEDs management and accessibility	(55.9%)
	Negative attitude	Misunderstanding of patients and their families about epilepsy Poor knowledge of the medical staff	(38.2%) (23.5%)
		Complexity of doctor-patient coordination	(14.7%)
	Do you know any other remedy to treat epilepsy?
	Yes (multiple answer)	(26.5%)
	Traditional ceremony		(20.6%)
	Herbal medicines		(11.8%)
	Surgery		(2.9%)
	No		(67.6%)
	Advice

for PWEs who want to use herbal medicine

	Knowledge (
	Only AEDs, other remedies are not effective	(41.2%)
	In association	(38.2%)
	Patient's preference	(20.6%)

epilepsy training), Attitudes & Practices regarding epilepsy and its treatments Qualitative analyses Quantitative analyses Healthcare system Healthcare pathway 86

.0% used medical plants 91.0% : willing to collaborate 76.5% mentioned only antiepileptic drugs 44.1%: collaboration was complicated

funding agencies in the public, commercial, or not-for-profit sectors.

Type of Article