Using positive spanning sets to achieve d-stationarity with the Boosted DC Algorithm
Francisco J. Aragón Artacho Rubén Campoy Phan T. Vuong
math.OC cs.LG








Using positive spanning sets to achieve d-stationarity with the Boosted DC Algorithm
    F. J. Aragón Artacho^*
R. Campoy[Department of Mathematics, University of Alicante, Alicante, Spain.    Email:  and ]


 P. T. Vuong[Department of Mathematics, University of Vienna, Austria and School of Mathamtical Sciences, University of Southampton, SO17 1BJ, Southampton, UK.    Email: ]
 
    December 30, 2023
 This paper is dedicated to Professor Marco A. López Cerdá
 
 on the occasion of his 70th birthday
=========================================================================================================================================================================================================================================================================================================






The Difference of Convex functions Algorithm (DCA) is widely used for minimizing the difference of two convex functions. A recently proposed accelerated version, termed BDCA for Boosted DC Algorithm, incorporates a line search step to achieve a larger decrease of the objective value at each iteration. Thanks to this step, BDCA usually converges much faster than DCA in practice. The solutions found by DCA are guaranteed to be critical points of the problem, but these may not be local minima. Although BDCA tends to improve the objective value of the solutions it finds, these are frequently just critical points as well. In this paper we combine BDCA with a simple Derivative-Free Optimization (DFO) algorithm to force the d-stationarity (lack of descent direction) at the point obtained. The potential of this approach is illustrated through some computational experiments on a Minimum-Sum-of-Squares clustering problem. Our numerical results demonstrate that the new method provides better solutions while still remains faster than DCA in the majority of test cases.



Keywords:
Difference of convex functions;  boosted difference of convex functions algorithm; positive spanning sets; d-stationary points; derivative-free optimization.






§ INTRODUCTION

In this paper, we are interested in solving the following unconstrained DC (difference of convex functions) optimization problem:

    𝒫min_x∈^m{ϕ(x) := g(x) - h(x)}

where g:^m→∪{+∞} and h:^m→∪{+∞} are proper, closed and convex functions, and g is smooth, with the conventions:

    (+∞)-(+∞)=+∞,
    
    (+∞)-λ=+∞  and  λ-(+∞)=-∞,  ∀λ∈]-∞,+∞[.


Problem (<ref>) can be tackled by the well-known DC algorithm (DCA) <cit.>. DC programming has become an active research field for the last few decades <cit.> and DCA has been successfully applied to many real-world problems arising in different fields (see, e.g., <cit.>). Although DCA performs well in practice, its convergence can be fairly slow for some particular problems. In order to speed up the scheme, an accelerated version of the algorithm, called Boosted DC algorithm (BDCA), has been recently proposed in <cit.>. The BDCA performs a line search at the point generated by the classical DCA, which allows to achieve a larger decrease in the objective value at each iteration. In the numerical experiments reported in <cit.> it was shown that BDCA was not only faster than DCA, but also often found solutions with lower objective value. However, although both algorithms are proved to converge to critical points of (<ref>), there is no guarantee that these points are local minima. For this reason, a simple trick to achieve better solutions consists in running the algorithms from different starting points. Another approach has been recently used in <cit.>, where the authors incorporated an inertial term into the algorithm making it converge to better critical points. In the recent work <cit.>, the author proposed a DC scheme which is able to compute d-stationary points. Although this algorithm permits to address problems where the function g is nonsmooth, the second component function h needs to be the pointwise maximum of finitely many differentiable functions.

The aim of this paper is to show that it is possible to combine BDCA with a simple DFO (Derivative-Free Optimization) routine to guarantee d-stationarity  at the limit point obtained by the algorithm.
As a representative application, we perform a set of numerical experiments on the Minimum Sum-of-Squares Clustering problem studied in <cit.> to illustrate this observation.
This problem has many critical points, where both DCA and BDCA tend to easily get trapped in.
As a byproduct of the DFO step, we observe that in some problems a single run of the new algorithm is able to provide better solutions than those obtained by multiple restarts of DCA.

The rest of this paper is organized as follows. In Section <ref> we recall some preliminary results. We propose a new variant of BDCA, named BDCA+, in Section <ref>. The results of some numerical experiments are presented in Section <ref>, where we compare the performance of DCA, BDCA and BDCA+ on several test cases. We finish with some conclusions in Section <ref>.






§ PRELIMINARIES


Throughout this paper, ⟨ x, y⟩ denotes the inner product of x,y∈^m, and · corresponds to the induced norm given by x=√(⟨ x,x⟩). For any extended real-valued function f:^m→∪{+∞}, the set f := x∈^m | f(x) < +∞ denotes the (effective) domain of f. A function f is proper if its domain is nonempty. The function f is coercive if f(x)→ +∞ whenever x→ +∞, and it is said to be convex if

    f(λ x+(1-λ)y)≤λ f(x) +(1-λ)f(y),   for all  x,y∈^m  and λ∈[0,1].

Further, f is strongly convex with strong convexity parameter ρ>0 if f-ρ/2·^2 is convex, i.e., when

    f(λ x+(1-λ)y)≤λ f(x) +(1-λ)f(y)-ρ/2λ(1-λ)x-y^2,

for all x,y∈^m and λ∈[0,1]. For any convex function f, the subdifferential of f at x∈^m is the set

    ∂f(x) :=  w∈^m | f(y) ≥ f(x) + w,y-x, ∀ y∈^m.

If f is differentiable at x, then ∂ f(x)={∇ f(x)}, where ∇ f(x) denotes the gradient of f at x. The one-sided directional derivative of f at x with respect to the direction d∈^m is defined by

    f'(x;d):=lim_t↘ 0f(x+td)-f(x)/t.


Before going to the main contribution of this paper in Section <ref>, we state our assumptions imposed on (<ref>). We also recall some preliminary notions and basic results  which will be used in the sequel.



 §.§ Basic Assumptions





Both functions g and h  in (<ref>) are strongly convex on their domain for the same strong convexity parameter ρ >0.



	The function h is subdifferentiable at every point in h; that is, ∂ h(x)≠∅ for all x∈h.


	The function g is continuously differentiable on an open set containing h  and
	
    ϕ^⋆ := inf_x∈^mϕ(x) > -∞.




<Ref> is not restrictive, as one can always rewrite the objective function as ϕ = (g+q) - (h+q) for any strongly convex function q (e.g., q=ρ/2·^2). Observe that <Ref> holds for all x∈h (by <cit.>). A key property for our method is the smoothness of g in <Ref>, which cannot be in general omitted (see <cit.>).



 §.§ Optimality Conditions







Under <ref> the following well-known necessary condition for local optimality holds.

[First-order necessary optimality condition]
If x^⋆∈ϕ is a local minimizer of problem (<ref>), then

    ∂h(x^⋆)={∇g(x^⋆)}.




See <cit.>.


Any point satisfying condition (<ref>) is called a d(irectional)-stationary point of (<ref>). We say that x^⋆ is a critical point of (<ref>) if

    ∇g(x^⋆) ∈∂h(x^⋆).

Clearly, d-stationary points are critical points, but the converse is not true in general (see, e.g., <cit.>). In our setting, the notion of critical point coincides with that of Clarke stationarity, which requires that zero belongs to the Clarke subdifferential at x^⋆ (see, e.g., <cit.>). The next result establishes that the d-stationary points of (<ref>) are precisely those points for which the directional derivative is zero for every direction.


A point x^⋆∈ϕ is a d-stationary point of (<ref>) if and only if

    ϕ'(x^⋆; d)= 0,  for all  d∈^m.



If x^⋆ is a d-stationary point of (<ref>), then by <cit.> we know that h is differentiable at x^⋆. Therefore, for any d∈^m, we have

    ϕ'(x^⋆; d) = ⟨∇g(x^⋆), d ⟩- ⟨∇h(x^⋆), d ⟩=0.


For the converse implication, pick any v∈∂ h(x^⋆)≠∅ (by <Ref>) and observe that, for any d∈^m, we have that

    ϕ'(x^⋆; d)     = g'(x^⋆;d)-h'(x^⋆;d)
        = ⟨∇g(x^⋆), d ⟩ -lim_t↘ 0h(x^⋆+td)-h(x^⋆)/t
       ≤⟨∇g(x^⋆)-v, d ⟩ .

Hence, if x^⋆ satisfies (<ref>), one must have

    ⟨∇g(x^⋆)-v, d ⟩≥ 0,  for all  d∈^m,

which is equivalent to ∇g(x^⋆)-v = 0.
As v was arbitrarily chosen in ∂ h(x^⋆), we conclude that ∂ h(x^*)={∇ g(x^⋆)}.




 §.§ DCA and Boosted DCA


In this section, we recall the iterative procedure DCA and its accelerated extension, BDCA, for solving problem (<ref>). The DCA iterates by solving a sequence of approximating convex subproblems, as described next in Algorithm <ref>.



The key feature that makes the DCA work, stated next in <Ref><Ref>, is that the solution of (<ref>) provides a decrease in the objective value of (<ref>) along the iterations. Actually, an analogous result holds for the dual problem, see <cit.>. In <cit.>, the authors showed that the direction generated by the iterates of DCA, namely d_k:=y_k-x_k, provides a descent direction of the objective function at y_k when the functions g and h in (<ref>) are assumed to be smooth. This result was later generalized in <cit.> to the case where h satisfies <Ref>. The following result collects these properties.


Let x_k and y_k be the sequences generated by <Ref> and set d_k:=y_k-x_k, for all k∈. Then the following statements hold:


  * ϕ(y_k)≤ϕ(x_k)-ρd_k^2;

  * ϕ'(y_k;d_k)≤ -ρd_k^2;

  * there exists some δ_k>0 such that

    ϕ(y_k+λ d_k)≤ϕ(y_k)-αλ^2d_k^2,  for all λ∈[0,δ_k[.




See <cit.>.


Thanks to <Ref>, once y_k has been found by DCA, one can achieve a larger decrease in the objective value of (<ref>) by moving along the descent direction d_k. Indeed, observe that

    ϕ(y_k+λ d_k)≤ϕ(y_k)-αλ^2d_k^2≤ϕ(x_k)-(ρ+αλ^2)d_k^2,  for all λ∈[0,δ_k[.

This fact is the main idea of the BDCA <cit.>, whose iteration is described next in <Ref>.



Algorithmically, the BDCA is nothing more than the classical DCA with a line search procedure using an Armijo type rule. Note that the backtracking step in <Ref> (lines 6–9) terminates finitely thanks to <Ref><Ref>.

We state next the basic convergence results for the sequences generated by BDCA (for more, see <cit.>). Observe that DCA can be seen as a particular case of BDCA if one sets λ_k=0, so the following result applies to both <Ref>.


For any x_0∈^m, either <Ref> (BDCA) 
with ε=0 returns a critical point of (<ref>), or it generates an infinite sequence such that the following properties hold.


  * {ϕ(x_k)} is monotonically decreasing and convergent to some ϕ^⋆.

  * Any limit point of {x_k} is a critical point of (<ref>). In addition, if ϕ is coercive then there exists a subsequence of {x_k} which converges to a critical point of (<ref>).

  * It holds that ∑_k=0^+∞d_k^2<+∞. Furthermore, if there is some λ such that λ_k≤λ for all k≥ 0, then ∑_k=0^+∞x_k+1-x_k^2<+∞.



See <cit.>.




 §.§ Positive Spanning Sets


Most directional direct search methods are based on the use of positive spanning sets (see, e.g., <cit.> and <cit.>). Let us recall this concept here.


We call positive span of a set of vectors {v_1,v_2,…,v_r}⊂^m the convex cone generated by this set, i.e.,

    {v∈^m: v=α_1v_1+⋯+α_rv_r,   α_i≥ 0,  i=1,2,…,r}.

A set of vectors in ^m is said to be a positive spanning set if its positive span is the whole space ^m. A set {v_1, v_2, …, v_r} is said to be positively dependent if one of the vectors is in the positive span generated by the remaining vectors; otherwise, the set is called positively independent. A positive basis in ^m is a positively independent set whose positive span is ^m.


Three well-known examples of positive spanning sets are given next.

[Positive basis]
Let e_1,e_2,…,e_m be the unit vectors of the standard basis in ^m. Then the following sets are positive basis in ^m:

 	
    D_1    :={± e_1,± e_2,…,± e_m}, 
    
     	D_2    :={e_1,e_2,…,e_m, -∑_i=1^m e_i }, 
    
     	D_3     :={ v_1,v_2,…,v_m,v_m+1∈^m,   with [ v_i^Tv_j=-1/m,  if  i≠ j,;     v_i=1,   i=1,2,…,m+1. ]} .


A possible construction for D_3 is given in <cit.>.



Recall that the BDCA provides critical points of (<ref>) which are not necessarily d-stationary points (<Ref>). Theoretically, see <cit.>, if x^⋆ is a critical point which is not d-stationary, one could restart BDCA by taking x_0:=x^⋆ and choose y_0∈∂ h(x_0)∖{∇ g(x_0)}. Nonetheless, observe that this is only applicable when the algorithm converges in a finite number of iterations to x^⋆, which does not happen very often in practice (except for polyhedral DC problems, where even a global solution can be effectively computed if h is a piecewise linear function with a reasonable small number of pieces, see <cit.>). Because of that, our goal is to design a variant of BDCA that generates a sequence converging to a d-stationary point. The following key result, proved in <cit.>, asserts that using positive spanning sets one can escape from points which are not d-stationary. We include its short proof.












Let {v_1,v_2,…,v_r} be a positive spanning set of ^m. A point x^⋆∈ϕ is a d-stationary point of (<ref>) if and only if

    ϕ'(x^⋆; v_i)≥ 0,  for all  i=1,2,…,r.



The direct implication is an immediate consequence of <Ref>. For the reverse implication, pick any x^⋆∈ϕ verifying (<ref>) and choose any d∈^m. Since {v_1,v_2,…,v_r} is a positive spanning set, there are α_1,α_2,…,α_r≥ 0 such that

    d=α_1v_1+α_2v_2+⋯+α_rv_r.

According to <cit.>, we have that

    h'(x^⋆;d)≤α_1h'(x^⋆;v_1)+⋯+α_rh'(x^⋆;v_r).

Hence, we obtain

    ϕ'(x^⋆;d)     =  g'(x^⋆;d)-h'(x^⋆;d)
        = ⟨∇g(x^⋆), α_1v_1+α_2v_2+⋯+α_rv_r ⟩-h'(x^⋆;d) 
       ≥∑_i=1^r α_i ⟨∇g(x^⋆); v_i⟩ - ∑_i=1^r α_i h'(x^⋆;v_i)
        = ∑_i=1^r α_iϕ'(x^⋆;v_i)≥ 0.

Since d was arbitrarily chosen, then (<ref>) holds and x^⋆ is a d-stationary point of (<ref>).







§ FORCING BDCA TO CONVERGE TO D-STATIONARY POINTS


In this section we propose a new variant of BDCA  to solve problem (<ref>), called BDCA+. The idea  is to combine BDCA with a basic DFO routine which uses positive spanning sets. The first scheme aims at achieving a fast minimization of the objective function ϕ, while the second one is used to avoid converging to critical points for which there is at least a descent direction (i.e., they are not d-stationary points and, thus, they cannot be local minima). Let us make some comments about the new scheme BDCA+, which is stated in Algorithm <ref>.


  * Subproblem (<ref>) in line 3 corresponds to the classical DCA step for solving (<ref>).

  * Lines 5 to 10 encode the boosting line search step used in BDCA. If the current iterate is (numerically) not a critical point, then the algorithm performs a line search step at y_k along the direction d_k to improve the objective values of (<ref>).

  * Line 11 to 19 correspond to a direct search DFO technique. It is run only when BDCA was stopped, in order to check if the point obtained is d-stationary. To this aim, it performs a backtracking search along each of the directions belonging to a positive spanning set D of ^m. If it reaches a point whose objective value is smaller, then we move to that point and run BDCA again from there. Otherwise, there is not descent direction in D and, according to <Ref>, the point we have found must be (numerically) d-stationary.

  * The choice λ_k=0 for all k is allowed, which corresponds to adding a direct search step to DCA.












The following constructive example serves to illustrate the different behavior of DCA, BDCA and BDCA+.

[<cit.>]
Consider the function ϕ:^2→ defined by

    ϕ(x,y):=x^2+y^2+x+y-|x|-|y|.

Consider a corresponding DC decomposition ϕ=g-h of ϕ with

    g(x,y):=3/2(x^2+y^2)+x+y   and   h(x,y):=|x|+|y|+1/2(x^2+y^2).

Observe that g and h satisfy <Ref>. It can be easily checked that ϕ has four critical points, namely (0,0), (-1,0), (0,-1) and (-1,-1), of which only the latter is a d-stationary point (and also the global minimum).

In <Ref> we show the iterations generated by DCA (<Ref>) and BDCA+ (<Ref>) from the same starting point x_0=(0,1). The DCA converges to the critical point (0,0). The BDCA escapes from this point but still gets stuck at (0,-1), which is also a critical point which is not d-stationary. After applying once the DFO scheme (dashed line), we observe that BDCA successfully converges to the d-stationary point (-1,-1), which is in fact the global minimum of the problem.



To demonstrate the advantage of BDCA+ we compute the number of instances, out of one million random starting points uniformly distributed in [-1.5,1.5]×[-1.5,1.5], that each algorithm has converged to each of the four critical points. The results are summarized in <Ref>.



From Table <ref>, we observe that DCA converged to each of the four critical points with the same probability, while BDCA converged to the global minimum in 99.6% of the instances. The best results where obtained by BDCA+, which always converged to the global minimum (-1,-1).











§ NUMERICAL EXPERIMENTS

In this section, we provide the results of some numerical tests to compare the performance of BDCA+ (<Ref>) and the classical DCA (<Ref>). To this aim we turn to the same challenging clustering problem tested in <cit.>, where both algorithms have troubles for finding good solutions due to an abundance of critical points. A different algorithm based on the DC programming approach to solve this problem was introduced in <cit.>. This algorithm is also proved to converge to d-stationary points.

All the codes were written in Python 2.7 and the tests were run on a desktop of Intel Core i7-4770 CPU 3.40GHz with 32GB RAM, under Windows 10 (64-bit). The following strategies have been followed in all the experiments:



  * The trial step size λ_k in the boosting step of BDCA (line 6 in <Ref>) was chosen to be self-adaptive, as in <cit.>, which proceeds as follows:



  * Set λ_0=0 and fix any γ>1.

  * Choose any λ_1>0 and obtain λ_1 by backtracking.

  * For k≥ 2,

    if   (λ_k-2=λ_k-2 and λ_k-1=λ_k-1)  then
           set λ_k:=γλ_k-1; 
       else set λ_k:=λ_k-1;

and obtain λ_k by backtracking.



  * In our numerical tests we observed that the accepted step sizes μ in the DFO step of <Ref> usually decrease (nearly always).
For this reason,  we used η:=1/β_2 and τ:=ε_2 in the choice of the initial value of μ at line 12 in <Ref>.
By this way, we allow a slight increase in the value of the step size with respect to the previous one, while  we can avoid wasting too much time in this backtracking.


  * We tested the three positive basis presented in <Ref>. Surprisingly, the basis with equally spaced angles D_3 in (<ref>) performs worse than the others in our test problem. In fact, the best choice was the basis D_1 in (<ref>), and this is the one we have employed in all the experiments throughout this section.

  * We used the parameter setting as α:=0.0001, ε_1:=10^-8, ε_2:=10^-4, μ:=10, γ=2, λ_1:=10, β_1:=0.25 and β_2:=0.5.





  
The Minimum Sum-of-Squares Clustering Problem: Given a collection of n points, {a^1,a^2,…,a^n∈^m}, the goal of clustering is to group them in k disjoint sets (called clusters), {A^1,A^2,…,A^k}, under an optimal criterion. For each cluster A_j, j=1,2,…,k, consider its centroid x^j as a representative. The Minimum Sum-of-Squares Clustering criterion asks for the configuration that minimizes the sum of squared distances of each point to its closest centroid, i.e. the solution to the optimization problem

    min_x^1,…,x^k∈^m{φ(x^1,…,x^k):= 1/n∑_i=1^nmin_j=1,…,kx^j-a^i^2}.

We can rewrite the objective in (<ref>) as a DC function (see <cit.>) with

    g(x^1,…,x^k)   :=1/n∑_i=1^n∑_j=1^kx^j-a^i^2+ρ/2∑_j=1^kx^j^2,
    
    h(x^1,…,x^k)   :=1/n∑_i=1^nmax_j=1,…,k∑_t=1,t≠ j^kx^t-a^i^2+ρ/2∑_j=1^kx^j^2;

where g and h satisfy <Ref> for all ρ>0 (in our tests, we took ρ=1/nk).




  
Data Set and Experiments: Our data set is the same one considered in <cit.>, which consists of the location of 4001 Spanish cities in the peninsula with more than 500 inhabitants[The data can be retrieved from the Spanish National Center of Geographic Information at http://centrodedescargas.cnig.eshttp://centrodedescargas.cnig.es.]. In <Ref> we compare the iterations generated by DCA and BDCA+ for finding a partition into 20 clusters from the same random starting point x_0∈^2× 20 (marked with a black cross). We observe that DCA converges to a critical point which is far from being optimal, as there are three clusters without any cities assigned. On the other hand, although BDCA apparently converges to the same critical point, the DFO step allows BDCA+ to escape from points which are not d-stationary and reach a better solution.












To corroborate these results, we repeated the experiment for different number of clusters k∈{20,40,60,80}. For each of these values, we run DCA and BDCA+ from 50 random starting points. The results are shown in <Ref>, where we can clearly observe that BDCA+ outperforms DCA, not only in terms of the objective value attained, but even in running time. Observe that it is not really fair to compare the running time of DCA and BDCA+, because DCA simply stops at a critical point without incorporating the time-consuming DFO step that guarantees d-stationarity. Nonetheless, the speedup obtained by the line search of BDCA allows BDCA+ to still converge faster than DCA in most of the instances. As expected, BDCA+ becomes slower as the size of the problem increases, due to the DFO step. Despite that, notice that for 80 clusters the best solution provided by DCA among the 50 instances is still worse than the worst solution obtained by BDCA+. That is, any of the runs of BDCA+ was able to obtain a better solution than 50 restarts of DCA.



























§ CONCLUDING REMARKS

We have proposed a combination between the Boosted DC Algorithm (BDCA) and a simple direct search Derivative-Free Optimization (DFO) technique for minimizing the difference of two convex functions, the first of which is assumed to be smooth. The BDCA is used for minimizing the objective function, while the DFO step permits to force the iteration to converge to d-stationary points (i.e. to points where there exists no descent direction), rather than just critical points.

The good behavior of the new algorithm, called BDCA+, has been demonstrated by numerical experiments in a clustering problem. The new scheme generates better solutions than the classical DCA in nearly all the instances tested. Moreover, this improvement in the quality of the solutions has not caused an important loss in the time spent by the algorithm. In fact, BDCA+ was faster than DCA in most of the cases, thanks to the large acceleration achieved by the line search boosting step of BDCA.





  
Acknowledgements
We thank the referees for their constructive comments which helped us improve the presentation of the paper.
The first author was supported by MINECO of Spain and ERDF of EU, as part of the Ramón y Cajal program (RYC-2013-13327) and the grants MTM2014-59179-C2-1-P and PGC2018-097960-B-C22.
The second author was supported by MINECO of Spain and ESF of EU under the program “Ayudas para contratos predoctorales para la formación de doctores 2015” (BES-2015-073360).
The last author was supported by FWF (Austrian Science Fund), project M2499-N32 and Vietnam National Foundation for
Science and Technology Development (NAFOSTED) project 101.01-2019.320.



99




book
Aragón, F.J., Goberna, M.A., López, M.A., Rodríguez, M.M.L.:
Nonlinear Optimization, Springer Undergraduate Texts in Mathematics and Technology (2019)

BDCA2018
Aragón Artacho, F.J., Fleming, R., Vuong, P.T.:
Accelerating the DC algorithm for smooth functions.
Math. Program. 169(1), 95–118 (2018)


nBDCA
Aragón Artacho, F.J., Vuong, P.T.:
The boosted DC algorithm for nonsmooth functions.
To appear in SIAM J. Optim. ArXiv preprint: https://arxiv.org/abs/1812.060701812.06070 (2019)






BTU16
Bagirov, A.M., Taheri, S., Ugon, J.:
Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems.
Pattern Recogn. 53, 12–24 (2016)

GGMB18
Gaudioso, M., Giallombardo, G., Miglionico, G., Bagirov, A.M.:
Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations.
J. Glob. Optim. 71(1), 37–55 (2018)

BH18
Beck, A., Hallak, N.:
On the convergence to stationary points of deterministic and randomized feasible descent directions methods.
SIAM J. Optim. 30(1), 56–79 (2020)

DFO
Conn, A.R., Scheinberg, K., Vicente, L.N.:
Introduction to derivative-free optimization, MPS-SIAM Series on Optimization vol. 8 (2009)

CYY18
Cuong, T.H., Yao, J.C., Yen, N.D.:
Qualitative properties of the Minimum Sum-of-Squares Clustering problem.
ArXiv preprint: https://arxiv.org/abs/1810.020571810.02057 (2018)


An2018
Le Thi, H.A., Pham Dinh, T.:
DC Programming and DCA: Thirty years of developments.
Math. Program. 169(1), 5–68 (2018)

tao2005dc
Le Thi, H.A., Pham Dinh, T.:
The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems.
Ann. Oper. Res. 133(1-4), 23–46 (2005)










OB15
Ordin, B., Bagirov, A.M.:
A heuristic algorithm for solving the minimum sum-of-squares clustering problems. J. Glob. Optim. 61, 341–361 (2015)

WelingtonJogo
de Oliveira, W.:
Proximal bundle methods for nonsmooth DC programming. J. Glob. Optim. 75, 523–563 (2019)

Welington
de Oliveira, W., Tcheou, M.P.:
An inertial algorithm for DC programming. Set-Valued Var. Anal. 27, 895–919(2019)

TT97
Pham Dinh, T., Le Thi, H.A.:
Convex analysis approach to DC programming: theory, algorithms and applications. Acta Mathematica Vietnamica, 22, 289–355 (1997)

DC86
Pham Dinh T., Souad, E.B.:
Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients. In J.-B. Hiriart-Urruty, editor, FERMAT Days 85: Mathematics for Optimization, volume 129 of North-Holland Mathematics Studies, pp. 249–271. Elsevier (1986)


Toland79
Toland, J.F.:
On subdifferential calculus and duality in non-convex optimization.Bull. Soc. Math. Fr. Mém. 60 (Proc. Colloq., Pau 1977), 177–183 (1979)

RT Rockafellar, R.T.:
Convex Analysis, Princeton University Press (1972)







