## The Boosted DC Algorithm for linearly constrained DC programming

F. J. Aragón Artacho *

R. Campoy †

P. T. Vuong ‡

August 3, 2022

Dedicated to Professor Miguel A. Goberna on the occasion of his 70th birthday

## Abstract

The Boosted Difference of Convex functions Algorithm (BDCA) has been recently introduced to accelerate the performance of the classical Difference of Convex functions Algorithm (DCA). This acceleration is achieved thanks to an extrapolation step from the point computed by DCA via a line search procedure. In this work, we propose an extension of BDCA that can be applied to difference of convex functions programs with linear constraints, and prove that every cluster point of the sequence generated by this algorithm is a Karush-Kuhn-Tucker point of the problem if the feasible set has a Slater point. When the objective function is quadratic, we prove that any sequence generated by the algorithm is bounded and R-linearly (geometrically) convergent. Finally, we present some numerical experiments where we compare the performance of DCA and BDCA on some challenging problems: to test the copositivity of a given matrix, to solve one-norm and infinity-norm trust-region subproblems, and to solve piecewise quadratic problems with box constraints. Our numerical results demonstrate that this new extension of BDCA outperforms DCA.

Keywords: Difference of convex functions; boosted difference of convex functions algorithm; global convergence; constrained DC programs; copositivity problem; trust region subproblem.

## 1 Introduction

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

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } & \phi ( x ) \coloneqq g ( x ) - h ( x ) \\ s. t. & \langle a _ { i }, x \rangle \leq b _ { i }, \, i = 1, \dots, p, \end{cases}$$

* Department of Mathematics, University of Alicante, Alicante, Spain.

Email: francisco.aragon@ua.es

† Department of Statistics and Operational Research, Universitat de València, Valencia, Spain.

Email: ruben.campoy@uv.es

‡ Mathematical Sciences School, University of Southampton, UK

Email: t.v.phan@soton.ac.uk

where g : R n → R ∪{ + ¥ } , h : R n → R ∪{ + ¥ } are proper, closed, and convex functions with g being smooth, ai ∈ R n , bi ∈ R for i = 1 , . . . , p , and 〈· , ·〉 denotes an inner product. We use the conventions:

$$( + \infty ) - ( + \infty ) & = + \infty, \\ ( + \infty ) - \lambda & = + \infty \quad \text{and} \quad \lambda - ( + \infty ) & = - \infty, \quad \forall \lambda \in \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \real \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \null \ }$$

Observe that we can rewrite problem ( P ) as an unconstrained nonsmooth DC optimization problem, whose objective function is g + i F -h , where i F denotes the indicator function of the feasible set

$$\mathcal { F } \coloneqq \left \{ x \in \mathbb { R } ^ { n } \, | \, \langle a _ { i }, x \rangle \leq b _ { i }, i = 1, \dots, p \right \}.$$

For solving this problem, one can apply the classical DC Algorithm (DCA) in [28, 15]. DCprogramming and the DCA have been developed and studied for more than 30 years [15]. The DCA has been successfully applied in different fields such as machine learning, financial optimization, supply chain management, and telecommunication, see, e.g. [17, 11, 24]. Nowadays, DCA has become a useful method to solve nonconvex problems.

To accelerate the convergence of DCA, which can be slow for some problems, a new method called Boosted DC Algorithm (BDCA) has been recently proposed in [1, 3]. The key idea of BDCA is to perform an extrapolation step via a line search procedure at the point computed by DCA at each iteration. This step allows the algorithm to take longer steps than the classical DCA, achieving in this way a larger reduction of the objective value per iteration. In addition to accelerating its convergence, BDCA may have better chances to escape from bad local optima thanks to the line search procedure, see [3, Example 3.3]. Therefore, BDCA is not only faster than DCA but also can provide better solutions. Extensive numerical experiments in diverse applications such as biochemistry [1], machine learning [36, 22] and data science [3] have been performed where BDCA clearly outperforms DCA. Note that all these applications are modeled as DC problems with g smooth. However, it is important to emphasize that, for unconstrained DC programs, the BDCA proposed in [1, 3] is not applicable when the function g in ( P ) is nonsmooth (see [3, Example 3.4]).

The aim of this paper is to show that BDCA can still be applied if the nonsmooth function g is the sum of a smooth convex function and the indicator function of a polyhedral set. More precisely, we will show that it is possible to use BDCA for solving DC programs with linear constraints of the form ( P ). To compare the performance of DCA and BDCA, we provide numerical experiments on various challenging problems: to test the copositivity of a given matrix, to solve glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblems, and to find the minimum of a piecewise quadratic function with box constraints. The three first problems have a quadratic objective function and are known to be NP-hard [23] (the first was already heuristically investigated in [8] using DCA), while the last problem has a nonsmooth objective function. Our results confirm that BDCA significantly outperforms DCA in these applications.

The rest of this paper is organized as follows. Section 2 recalls some preliminary results. In Section 3, we propose a new variant of BDCA for solving ( P ) and prove that the objective value of the sequence generated by the algorithm is monotonically decreasing, and that any limit point of the sequence is a KKT point of the problem. The R-linear convergence of any sequence generated by BDCA in the special case of quadratic objective functions is derived in Section 4. In Section 5, we provide some numerical experiments for testing

the copositivity of a given matrix, for solving glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblems and for solving piecewise quadratic problems with box constraints, where we compare BDCA and DCA. Finally, some conclusions and future research are briefly discussed in Section 6.

## 2 Preliminaries

In this section, we state our assumptions imposed on ( P ). We also recall some preliminary and basic results which will be used in the sequel.

Let f : R n → R ∪{ + ¥ } be a proper extended real-valued convex function. The set dom f : = { x ∈ R n | f ( x ) &lt; + ¥ } denotes its (effective) domain , and

$$\partial f ( x ) \coloneqq \{ w \in \mathbb { R } ^ { n } \ | \ f ( y ) \geq f ( x ) + \langle w, y - x \rangle, \ \forall y \in \mathbb { R } ^ { n } \}$$

denotes the subdifferential of f at x . If f is differentiable at x , then ¶ f ( x ) = { GLYPH&lt;209&gt; f ( x ) } , where GLYPH&lt;209&gt; f ( x ) stands for the gradient of f at x . The one-side directional derivative of f at x with respect to the direction d ∈ R n is

$$f ^ { \prime } ( x ; d ) \coloneqq \lim _ { t \searrow 0 } \frac { f ( x + t d ) - f ( x ) } { t }.$$

Recall that f is said to be strongly convex with strong convexity parameter r &gt; 0 if the function f -r 2 ‖ · ‖ 2 is convex. The conjugate of f is the function f ∗ : R n → R ∪{ + ¥ } defined at u ∈ R n as

$$f ^ { * } ( u ) = \sup _ { x \in \mathbb { R } ^ { n } } \{ \langle x, u \rangle - f ( x ) \}.$$

It holds that f ∗∗ : =( f ∗ ) ∗ = f . Moreover, for all x u , ∈ R n ,

$$u \in \partial f ( x ) \quad \Leftrightarrow \quad f ( x ) + f ^ { * } ( u ) = \langle x, u \rangle \quad \Leftrightarrow \quad x \in \partial f ^ { * } ( u ).$$

Given a set C ⊆ R n , its interior , its relative interior and the convex cone generated by C are denoted by int C , ri C and cone C , respectively. The function

$$\iota _ { C } ( x ) \coloneqq \begin{cases} 0, & \text{if $x\in C$,} \\ + \infty, & \text{otherwise;} \end{cases}$$

denotes the indicator function of C , and C is convex if and only if i C is so. Moreover, its subdifferential ¶i C is the normal cone to C , which is given by

$$N _ { C } ( x ) \coloneqq \begin{cases} \ \{ u \in \mathbb { R } ^ { n } \colon \langle u, c - x \rangle \leq 0, & \forall c \in C \}, & \text{if $x\in C$,} \\ \emptyset, & \text{otherwise.} \end{cases}$$

For proving our convergence results, we will make use of the following assumptions.

Assumption 1 . Both g and h are strongly convex on their domain with the same strong convexity parameter r &gt; 0.

glyph[negationslash]

Assumption 2 . The function h is subdifferentiable at every point in dom h ; i.e., ¶ h x ( ) = / 0 for all x ∈ dom h . The function g is continuously differentiable on an open set containing dom h and

$$\inf _ { x \in \mathcal { F } } \phi ( x ) > - \infty.$$

Assumption 3 . The feasible set F has a Slater point, that is, there exists ˆ x ∈ R n such that 〈 ai , ˆ x 〉 &lt; bi , for all i = 1 , . . . , p .

glyph[negationslash]

Remark 2.1 . Assumption 1 is not restrictive, in the sense that any DC decomposition of f as f = g -h , can be expressed as f =( + g r 2 ‖·‖ 2 ) -( h + r 2 ‖·‖ 2 ) for any r &gt; 0. Observe that ¶ h x ( ) = / 0 holds for all x ∈ ri dom h (by [34, Theorem 23.4]), so the first part of Assumption 2 is clearly satisfied if dom h = R n . A key point of our method is the smoothness of g in Assumption 2, which cannot be in general omitted (see [3, Example 3.4]).

Associated with problem ( P ), we can construct its dual as

$$\inf _ { u \in \mathbb { R } ^ { n } } h ^ { * } ( u ) - ( g + \imath _ { \mathcal { F } } ) ^ { * } ( u ),$$

which is also a DC program with the same optimal value. Indeed,

$$\text{mean} \, \text{in} \, \underline { \mathbb { R } } ^ { n } \, \left \{ h ^ { * } ( u ) - ( g + \iota _ { \mathcal { F } } ) ^ { * } ( u ) \right \} & = \inf _ { u \in \mathbb { R } ^ { n } } \left \{ h ^ { * } ( u ) - \sup _ { x \in \mathbb { R } ^ { n } } \left \{ \langle u, x \rangle - g ( x ) - \iota _ { \mathcal { F } } ( x ) \right \} \right \} \\ & = \inf _ { x \in \mathbb { R } ^ { n } } \left \{ g ( x ) + \iota _ { F } ( x ) - \sup _ { u \in \mathbb { R } ^ { n } } \left \{ \langle u, x \rangle - h ^ { * } ( u ) \right \} \right \} \\ & = \inf _ { x \in \mathbb { R } ^ { n } } \left \{ g ( x ) + \iota _ { F } ( x ) - h ( x ) \right \} \\ & = \inf _ { x \in \mathcal { F } } \left \{ g ( x ) - h ( x ) \right \} = \inf _ { x \in \mathcal { F } } \phi ( x ). \\ \text{We can} \, \text{that} \, \overline { v } \sim \mathbb { D } ^ { n } \, \text{frac} \, \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^{ n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon = \mathbb { D } ^ { n } \, \colon$$

glyph[negationslash]

We say that x ∈ R n (resp. u ∈ R n ) is a critical point of ( P ) (resp. ( D )) if GLYPH&lt;209&gt; g x ( ) ∈ ¶ ( h + i F )( x ) (resp. ¶ h ∗ ( u ) ∩ ¶ ( g + i F ) ∗ ( u ) = / ). 0 Recall from [21, Theorem 5.19] that x is called a KKT point of ( P ) if there exist m 1 , m 2 , . . . , m p ∈ R such that

$$\begin{cases} \ 0 \in \nabla g ( \bar { x } ) - \partial h ( \bar { x } ) + \sum _ { i = 1 } ^ { p } \mu _ { i } a _ { i }, \\ \ 0 = \mu _ { i } ( \langle a _ { i }, \bar { x } \rangle - b _ { i } ), \ i = 1, \dots, p, \\ \mu _ { i } \geq 0, \ \langle a _ { i }, \bar { x } \rangle \leq b _ { i }, \ i = 1, \dots, p. \end{cases}$$

The DC algorithm is a primal-dual method in the sense that it is aimed to find solutions for both ( P ) and ( D ), simultaneously. Our goal then is to design a BDCA variant that allow us to find KKT points of ( P ) and critical points of ( D ).

To finish this section, we need to introduce the following notions regarding the geometry of the feasible set F . The cone of feasible directions at x ∈ F is denoted by

$$D ( \bar { x } ) \coloneqq \left \{ d \in \mathbb { R } ^ { n } \, | \, \exists \epsilon > 0 \, \text{such that} \, \bar { x } + t d \in \mathcal { F }, \, \forall t \in [ 0, \epsilon ] \right \}.$$

Due to the polyhedral structure of F , its normal cone coincides with the active cone ; i.e.,

$$N _ { \mathcal { F } } ( \bar { x } ) = A ( \bar { x } ) \coloneqq \text{cone} \left \{ a _ { i }, \ i \in I ( \bar { x } ) \right \}, \quad \text{for} \, \bar { x } \in \mathcal { F },$$

where I ( x ) stands for the set of active constraints at x , i.e.,

$$I ( \bar { x } ) = \{ i \in \{ 1, \dots, p \} \ | \ \langle a _ { i }, \bar { x } \rangle = b _ { i } \}.$$

Since we deal with affine constraints, we have (see e.g. [2, Proposition 4.14])

$$D ( \bar { x } ) = \left \{ d \in \mathbb { R } ^ { n } \ | \ \langle a _ { i }, d \rangle \leq 0, \ i \in I ( \bar { x } ) \right \}.$$

## 3 The Boosted DC Algorithm and its convergence

For solving ( P ), we propose the following method, Algorithm 1, which can tackle more general problems than the Boosted DC Algorithm proposed in [3].

```
<_SQL_>
```

Let us make some comments on Algorithm 1.

- (i) Lines 1 to 6 of Algorithm 1 correspond to the classical DCA for solving ( P ). Thus, when l k = 0 for all k , Algorithm 1 coincides with DCA.
- (ii) Lines 7 to 15 present the boosting step. It first checks if dk is a feasible direction at yk ∈ F . If so, it then performs a line search step along the direction dk which maintains feasibility to improve the objective value f . Otherwise, the boosting step is skipped and we simply use the DCA point yk .
- (iii) In terms of per-iteration complexity, the boosting step requires to check the feasibility of direction dk , which can be done by comparing the sets of active constraints at xk and yk (see Lemma 3.1). It also requires evaluating the objective function and checking the feasibility of the trial step yk + l k dk . The computational effort of this task will depend on the particular structure of f and F . In the case of box constraints, the largest step-size that makes yk + l k dk feasible can be efficiently computed in Line 8,

see Remark 3.1 below. In Section 5 we show some computational results for the trustregion subproblems with glyph[lscript] 1 norm constraints (where feasibility needs to be checked) and glyph[lscript] ¥ norm constraints (where the largest step-size can be readily computed).

- (iv) When h is differentiable, the algorithms introduced by Fukushima and Mine in [10, 20] can be applied in our setting. On the one hand, the algorithm in [10] performs a line search which is similar to the one in Lines 9-11 of Algorithm 1, but with the significant difference that it is performed at the point xk , instead of doing it at the DCA point yk ; that is, it searches for the smallest non-negative integer l such that

$$\phi \left ( x _ { k } + \beta ^ { l } d _ { k } \right ) \leq \phi ( x _ { k } ) - \alpha \beta ^ { l } \| d _ { k } \| ^ { 2 },$$

where 0 &lt; b &lt; 1. Thus, the largest step-size allowed by their algorithm is 1, which corresponds with the point determined by the DCA, since xk + dk = yk . On the other hand, the algorithm defined in [20] performs an exact line search in the direction dk , which may be unaffordable in many practical applications.

Remark 3.1 . An explicit formula to compute the largest step-size that makes yk + l k dk feasible in Line 8 is provided in [9]. More precisely, feasibility of the trial step size is guaranteed if l k is chosen so that glyph[negationslash]

$$\overline { \lambda } _ { k } \leq \widehat { \lambda } _ { k } \coloneqq \min \left \{ \frac { b _ { i } - \langle a _ { i }, y _ { k } \rangle } { | \langle a _ { i }, d _ { k } \rangle | } \, \colon i \not \in I ( x _ { k } ) \text{ with } \langle a _ { i }, d _ { k } \rangle \neq 0 \right \} ;$$

see [9, Lemma 5.4(ii)]. In principle, this permits to avoid the extra time consumed for checking feasibility in Line 8. However, the computation of ̂ l k in (4) may be even more expensive and inefficient than checking feasibility of l k in some applications. This is the case, for instance, of the glyph[lscript] 1-norm trust region subproblem, whose reformulation as a linearly constrained DC program requires an exponential number of constraints (see Section 5.2).

The next auxiliary lemma shows the equivalence between Line 7 of Algorithm 1 and checking the feasibility of the direction generated by DCA.

Lemma 3.1. If xk and yk are generated by Algorithm 1, then

$$I ( y _ { k } ) \subseteq I ( x _ { k } ) \quad \Leftrightarrow \quad d _ { k } \colon = y _ { k } - x _ { k } \in D ( y _ { k } ) \quad \Leftrightarrow \quad d _ { k } \perp a _ { i }, \, \forall i \in I ( y _ { k } ).$$

Proof. Observe that, for any i ∈ I ( yk ) , it holds that

$$\langle a _ { i }, d _ { k } \rangle = \langle a _ { i }, y _ { k } \rangle - \langle a _ { i }, x _ { k } \rangle = b _ { i } - \langle a _ { i }, x _ { k } \rangle \geq 0.$$

Hence, the result easily follows by taking into account (3).

In the following proposition, we collect some key inequalities which are useful in the sequel for the convergence analysis of Algorithm 1.

Proposition 3.1. Under Assumptions 1 and 2, for all k ∈ N , the next statements hold:

$$( \mathbf i ) \ \phi ( y _ { k } ) \leq \phi ( x _ { k } ) - \rho \| d _ { k } \| ^ { 2 } ;$$

$$( \text{ii} ) \ \phi ^ { \prime } ( y _ { k } ; d _ { k } ) \leq - \rho \| d _ { k } \| ^ { 2 } ;$$

$$& \mathcal { + } \, \phi ( y _ { k } ) \leq \phi ( x _ { k } ) - \rho \| d _ { k } \| ^ { 2 } ; \\ & \mathcal { + } \, \phi ^ { \prime } ( y _ { k } ; d _ { k } ) \leq - \rho \| d _ { k } \| ^ { 2 } ;$$

(iii) if the condition at Line 7 of Algorithm 1 holds, then there exists some d k &gt; 0 such that yk + l k dk ∈ F and

$$\phi \left ( y _ { k } + \lambda d _ { k } \right ) \leq \phi ( y _ { k } ) - \alpha \lambda ^ { 2 } \| d _ { k } \| ^ { 2 }, \quad \text{for all } \lambda \in [ 0, \delta _ { k } ].$$

Consequently, the backtracking step at Lines 9-11 of Algorithm 1 terminates after a finite number of iterations.

Proof. The proof of (i) is similar to the one of [1, Proposition 3] and is therefore omitted. To prove (ii), pick any v ∈ ¶ h yk ( ) . Note that the one-sided directional derivative f ′ ( yk ; dk ) is given by

$$\varkappa \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \end{cases}$$

by convexity of h . Since yk is the unique solution of the strongly convex problem ( P k ), we can write down the KKT conditions (see, e.g., [2, Theorem 4.20]) of this problem as

$$\begin{cases} \ \nabla g ( y _ { k } ) + \sum _ { i = 1 } ^ { p } \mu _ { k, i } a _ { i } = u _ { k } \in \partial h ( x _ { k } ), \\ \ \mu _ { k, i } ( \langle a _ { i }, y _ { k } \rangle - b _ { i } ) = 0, \ \mu _ { k, i } \geq 0, \ \langle a _ { i }, y _ { k } \rangle \leq b _ { i }, \ i = 1, \dots, p. \end{cases}$$

The fact that h is strongly convex with a parameter r implies, by [35, Exercise 12.59], that ¶ h is strongly monotone with constant r . Therefore, since v ∈ ¶ h yk ( ) and uk ∈ ¶ h xk ( ) , we have

$$\langle u _ { k } - v, x _ { k } - y _ { k } \rangle \geq \rho \| x _ { k } - y _ { k } \| ^ { 2 }.$$

Hence, combining these expressions, together with the fact that xk ∈ F , we can derive

$$\text{Hence, combining these expressions, together with the fact that $x_{k} \in \mathcal{F}$, we can derive} \\ \langle \nabla g ( y _ { k } ) - v, d _ { k } \rangle & = \left \langle u _ { k } - \sum _ { i = 1 } ^ { p } \mu _ { k, i } a _ { i } - v, y _ { k } - x _ { k } \right \rangle \\ & \leq - \rho \| d _ { k } \| ^ { 2 } - \sum _ { i = 1 } ^ { p } \mu _ { k, i } \langle a _ { i }, y _ { k } - x _ { k } \rangle \\ & = - \rho \| d _ { k } \| ^ { 2 } + \sum _ { i = 1 } ^ { p } \mu _ { k, i } \left ( \langle a _ { i }, x _ { k } \rangle - b _ { i } \right ) + \sum _ { i = 1 } ^ { p } \mu _ { k, i } \left ( b _ { i } - \langle a _ { i }, y _ { k } \rangle \right ) \\ & \leq - \rho \| d _ { k } \| ^ { 2 }, \\ \text{and the result follows by combining the last inequality with (5).}$$

and the result follows by combining the last inequality with (5).

Having in mind the condition at Line 7 of Algorithm 1 and Lemma 3.1, we observe that the proof of (iii) is similar to the one of [3, Proposition 3.1], so we omit it for brevity.

Remark 3.2 (General convex constraints) . Consider a generalized version of ( P ) where the feasible set is formed by arbitrary convex constraints, i.e.,

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } & \phi ( x ) \coloneqq g ( x ) - h ( x ) \\ \text{s.t.} & c _ { i } ( x ) \leq 0, \, i = 1, \dots, p, \end{cases} \quad ( \mathcal { P } ^ { \prime } )$$

where g and h satisfy Assumptions 1 and 2 and ci : R n → R are smooth, proper, closed and convex functions, for i = 1 , . . . , p . Note that problem ( P ) is a particular instance of ( P ′ ) with ci ( x ) : = 〈 ai , x 〉-bi , for i = 1 , . . . , p . The assertion in Proposition 3.1(ii) still holds true for the more general problem ( P ′ ); that is, the direction generated by DCA remains a descent direction provided that xk is feasible for ( P ′ ). To confirm this, one can easily check that the proof can be rewritten by replacing the linearity of the gradients by the inequality

$$c _ { i } ( x _ { k } ) \geq c _ { i } ( y _ { k } ) - \langle \nabla c _ { i } ( y _ { k } ), y _ { k } - x _ { k } \rangle.$$

However, Line 7 of Algorithm 1 is no longer useful to verify if dk is a feasible direction, as the equality in (3) only holds for affine constraints. For general convex constraints, we have the inclusion

$$\{ d \in \mathbb { R } ^ { n } \ | \ \langle \nabla c _ { i } ( \bar { x } ), d \rangle < 0, \ i \in I ( \bar { x } ) \} \subset D ( \bar { x } ).$$

Therefore, one possibility would be to run the boosting step whenever 〈 GLYPH&lt;209&gt; ci ( yk ) , dk 〉 &lt; 0 for all i ∈ I ( yk ) . Nevertheless, this will never be the case because xk is feasible for ( P ′ ). Indeed, from (7), we obtain that

$$\langle \nabla c _ { i } ( y _ { k } ), d _ { k } \rangle \geq - c _ { i } ( x _ { k } ) \geq 0, \quad \text{for all $i\in I(y_{k})$}.$$

In fact, it can be proved that if yk + l dk ∈ F for some particular l &gt; 0, then the points in the segment [ xk , yk + l dk ] must be active for all i ∈ I ( yk ) .

We are now in the position to establish the main convergence result of Algorithm 1.

Theorem 3.1. Under Assumptions 1, 2 and 3, for any x 0 ∈ F , either BDCA returns a KKT point of ( P ) or it generates an infinite sequence such that the following statements hold.

- (i) f ( xk ) is monotonically decreasing and hence convergent to some ¯ f .
- (ii) Suppose that { xk } and { uk } are bounded. Then any limit point of { xk } is a KKT point of ( P ) and any limit point of { uk } is a critical point of ( D ) .
- (iii) We have GLYPH&lt;229&gt; + ¥ k = 0 ‖ dk ‖ 2 &lt; + ¥ . Moreover, if there is some l such that l k ≤ l for all k, then GLYPH&lt;229&gt; + ¥ k = 0 ‖ xk + 1 -xk ‖ 2 &lt; + ¥ .

Proof. If Algorithm 1 is terminated at Line 5 and returns xk , then xk = yk . From (2) and (6), it is clear that xk is a KKT point of ( P ). Otherwise, by Proposition 3.1 and Line 15 of Algorithm 1, we have

$$\phi ( x _ { k + 1 } ) \leq \phi ( y _ { k } ) - \alpha \lambda _ { k } ^ { 2 } \| d _ { k } \| ^ { 2 } \leq \phi ( x _ { k } ) - \left ( \alpha \lambda _ { k } ^ { 2 } + \rho \right ) \| d _ { k } \| ^ { 2 },$$

where l k ≥ 0. Therefore, the sequence { f ( xk ) } converges to some ¯ , f since it is monotonically decreasing and bounded from below, by (1). As a consequence, we obtain

$$\phi ( x _ { k + 1 } ) - \phi ( x _ { k } ) \rightarrow 0, \text{ as } k \rightarrow \infty,$$

which implies ‖ dk ‖ 2 = ‖ yk -xk ‖ 2 → 0, by (8).

Now, if x is a limit point of { xk } , then there exists a subsequence { xkj } converging to x . Then, as ‖ ykj -xkj ‖ → 0, we have ykj → x . From (6), we obtain

$$\begin{cases} \ \nabla g ( y _ { k _ { j } } ) + \sum _ { i = 1 } ^ { p } \mu _ { k _ { j }, i } a _ { i } = u _ { k _ { j } } \in \partial h ( x _ { k _ { j } } ), \\ \ \mu _ { k _ { j }, i } ( \langle a _ { i }, y _ { k _ { j } } \rangle - b _ { i } ) = 0, \ \mu _ { k _ { j }, i } \geq 0, \ \langle a _ { i }, y _ { k _ { j } } \rangle \leq b _ { i }, \ i = 1, \dots, p. \end{cases}$$

Since the sequence { uk } is bounded by assumption, without lost of generality we may assume that ukj → u . It also holds that GLYPH&lt;209&gt; g ykj ( ) → GLYPH&lt;209&gt; g x ( ) by continuity of GLYPH&lt;209&gt; g . The sequence of Lagrange multipliers { m k j } ∈ R p must also be bounded. Indeed, suppose to the contrary that ‖ m k j ‖ → ¥ and assume without loss of generality that lim j → ¥ m k j ‖ m k j ‖ = m ∗ , with m ∗ ∈ R p + (the non-negative orthant) satisfying ‖ m ∗ ‖ = 1. Then, dividing the first equality in (9) by ‖ m k j ‖ and letting j → ¥ , we obtain

$$\sum _ { i = 1 } ^ { p } \mu _ { i } ^ { * } a _ { i } = 0 _ { n }.$$

Performing the same procedure in the second equality in (9) gives

$$\mu _ { i } ^ { * } ( \langle a _ { i }, \bar { x } \rangle - b _ { i } ) = 0,$$

glyph[negationslash]

so we deduce that m ∗ i = 0 for all i ∈ I ( x ) . Thus,

$$\sum _ { i \in I ( \overline { x } ) } \mu _ { i } ^ { * } a _ { i } = 0 _ { n }.$$

Thanks to the Slater Assumption 3, we know that there exists ˆ x ∈ R n such that 〈 ai , ˆ x 〉 &lt; bi for all i ∈ I ( x ) . Hence,

$$0 = \sum _ { i \in I ( \overline { x } ) } \mu _ { i } ^ { * } \langle a _ { i }, \hat { x } - \overline { x } \rangle = \sum _ { i \in I ( \overline { x } ) } \mu _ { i } ^ { * } \left ( \langle a _ { i }, \hat { x } \rangle - \langle a _ { i }, \overline { x } \rangle \right ) = \sum _ { i \in I ( \overline { x } ) } \mu _ { i } ^ { * } \left ( \langle a _ { i }, \hat { x } \rangle - b _ { i } \right ),$$

which implies m ∗ i = 0 for all i ∈ I ( x ) , since m ∗ ∈ R p + . This implies that m ∗ = 0 , a contrap diction with the fact that ‖ m ∗ ‖ = 1.

Therefore, by extracting subsequences if necessary, we can assume that

$$\lim _ { j \to \infty } \mu _ { k _ { j }, i } = \mu _ { i } \geq 0, \quad \text{for all $i=1,2,\dots,p$.}$$

Taking the limit as j → ¥ in (9), thanks to the closedness of the graph of ¶ h (see [34, Theorem 24.4]), we obtain

$$\begin{cases} \ \nabla g ( \bar { x } ) + \sum _ { i = 1 } ^ { p } \mu _ { i } a _ { i } = \bar { u } \in \partial h ( \bar { x } ), \\ \ \mu _ { i } ( \langle a _ { i }, \bar { x } \rangle - b _ { i } ) = 0, \ \mu _ { i } \geq 0, \ \langle a _ { i }, \bar { x } \rangle \leq b _ { i }, \ i = 1, \dots, p, \end{cases}$$

which means that x is a KKT point of ( P ). From (11) we derive that x ∈ ¶ h ∗ ( u ) and also that

$$\bar { u } = \nabla g ( \bar { x } ) + \sum _ { i \in I ( \bar { x } ) } \mu _ { i } a _ { i } \in \nabla g ( \bar { x } ) + A ( \bar { x } ) = \partial ( g + \iota _ { \mathcal { F } } ) ( \bar { x } ),$$

which is equivalent to x ∈ ¶ ( g + i F ) ∗ ( u ) and, hence, u is a critical point of ( D ). The proof of (iii) is similar to that of [1, Proposition 5(iii)] and is thus omitted.

Remark 3.3 . The assertion in Theorem 3.1(ii) remains valid for any limit point of { xk } in the interior of dom h without requiring the dual sequence { uk } to be bounded. Indeed, let x ∈ intdom ( h ) be a cluster point of { xk } and let { xkj } be a subsequence converging to x . We

can apply [34, Corollary 24.5.1] to obtain that for any e &gt; 0, there exists a positive integer j 0 ≥ 1 such that

$$u _ { k _ { j } } \in \partial h ( x _ { k _ { j } } ) \subset \partial h ( \bar { x } ) + \varepsilon \mathbb { B }, \ \forall j \geq j _ { 0 } ;$$

where B denotes the Euclidean unit ball of R n . Hence, since ¶ h x ( ) is a bounded set, the dual subsequence { ukj } is also bounded and the proof of Theorem 3.1(ii) stands.

Remark 3.4 . Similar to [1, Theorem 1] and [3, Theorem 4.3 and Theorem 4.9], if we further assume that the function f satisfies the Kurdyka-Łojasiewicz property, then it can be proved that the sequence { xk } converges to a KKT point of ( P ). Moreover, convergence rates can also be deduced depending on the Łojasiewicz exponent. Especially, when the objective function f is quadratic (e.g., in some of our numerical experiments), it was proved [18, Theorem 4.2] that the function f + i F satisfies the Kurdyka-Łojasiewicz property with exponent 1 2 . Combining this with the technique in [1, Theorem 1], it is a routine task to derive the linear convergence of the sequence { xk } when the sequence has a cluster point. The purpose of the next section is to prove, using a similar technique to [32, Theorem 2.1], that the latter condition is not needed: for quadratic functions, BDCA always generates a sequence which is linearly convergent to a KKT point of the problem without requiring the existence of a cluster point.

## 4 Linear convergence for quadratic objective functions

In this section we prove the R-linear convergence of BDCA when the objective function f of ( P ) is quadratic, that is, for problems of the form

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } & \phi ( x ) \coloneqq \frac { 1 } { 2 } \langle Q x, x \rangle + \langle q, x \rangle \\ \text{s.t.} \quad \langle a _ { i }, x \rangle \leq b _ { i }, \, i = 1, \dots, p, \end{cases} \quad ( \mathcal { P } _ { Q } )$$

where Q ∈ R n × n is a symmetric matrix, q ∈ R n , and ai ∈ R n and bi ∈ R , for i = 1 , . . . , p . In this setting, x is a KKT point of ( P Q ) if there exist multipliers m 1 , m 2 , . . . , m p ∈ R such that

$$\begin{cases} \ 0 = Q \bar { x } + q + \sum _ { i = 1 } ^ { p } \mu _ { i } a _ { i }, \\ \ 0 = \mu _ { i } ( \langle a _ { i }, \bar { x } \rangle - b _ { i } ), \ \ i = 1, \dots, p, \\ \mu _ { i } \geq 0, \ \langle a _ { i }, \bar { x } \rangle \leq b _ { i }, \ \ i = 1, \dots, p. \end{cases}$$

We denote by F the set of all KKT points of ( P ).

As Q is not required to be positive semidefinite, ( P Q ) is a nonconvex problem. However, the matrix Q can be easily decomposed as Q = Q 1 -Q 2, with Q 1 and Q 2 positive definite. Indeed, one can take

$$Q _ { 1 } \coloneqq \sigma I \text{ \ and \ } Q _ { 2 } \coloneqq \sigma I - Q,$$

for s &gt; max 0 { , l max ( Q ) } , where l max ( Q ) is the largest eigenvalue of Q and I denotes the identity matrix. Thus, ( P Q ) can be equivalently written in the form of ( P ) as

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } \ g ( x ) - h ( x ) = \phi ( x ) \\ s. t. \quad \langle a _ { i }, x \rangle \leq b _ { i }, \ i = 1, \dots, p, \end{cases}$$

with

$$g ( x ) \coloneqq \frac { \sigma } { 2 } \| x \| ^ { 2 } + \langle q, x \rangle \quad \text{and} \quad h ( x ) \coloneqq \frac { 1 } { 2 } \langle ( \sigma I - Q ) x, x \rangle.$$

Observe that both functions g and h are strongly convex with parameters s and s -l max ( Q ) , respectively. Thus, Assumption 1 holds for

$$\rho \coloneqq \min \{ \sigma, \sigma - \lambda _ { \max } ( Q ) \},$$

while Assumption 2 trivially holds.

By using the indicator function i F of the feasible set F , we can rewrite problem ( P Q ) as an unconstrained nonsmooth DC optimization problem, which can be tackled by the DCA. In this case, the DCA becomes the projected gradient method from convex programming [30]

$$x _ { k + 1 } = P _ { \mathcal { F } } \left ( x _ { k } - \frac { 1 } { \sigma } ( Q x _ { k } + q ) \right ),$$

where P F denotes the projection mapping onto the feasible set F .

To derive the R-linear convergence of the iterative sequence generated by the BDCA, we will use the following lemmas. The first one is a classical result regarding the connected components of the KKT set F and can be found in [19, Lemma 3.1].

Lemma 4.1. Let F F 1 , 2 , . . . , F r be the connected components of the KKT set F . Then we have

$$\overline { \mathcal { F } } = \bigcup _ { i = 1 } ^ { r } \mathcal { F } _ { i },$$

and the following properties hold:

- (i) each F i is the union of finitely many polyhedral convex sets;
- (ii) the sets F i , i = 1 2 , , . . . , r , are properly separated from each others, that is

glyph[negationslash]

$$\inf \left \{ d ( x, \mathcal { F } _ { i } ), x \in \mathcal { F } _ { j } \right \} > 0, \quad \text{for all $i\neq j$;}$$

(iii) f is constant on each F i .

The second one is a local error bound result originally stated in [19, Theorem 2.3] and later extended in [32, Lemma 2.1].

Lemma 4.2. There exist scalars e &gt; 0 and t &gt; 0 such that

$$d ( x, \overline { \mathcal { F } } ) \leq \tau \left \| x - P _ { \mathcal { F } } \left ( x - \frac { 1 } { \sigma } ( Q x + q ) \right ) \right \|,$$

for all x ∈ F with

$$\left \| x - P _ { \mathcal { F } } \left ( x - \frac { 1 } { \sigma } ( Q x + q ) \right ) \right \| \leq \varepsilon.$$

We are now in a position to establish the R-linear (aka geometric) convergence of the iterative sequence { xk } generated by BDCA. Geometric convergence is a special type of Rlinear convergence, which is implied by Q-linear convergence (see, e.g. [2, Section 5.2.1]). The next result extends [32, Theorem 2.1] to the BDCA. Its proof employs similar techniques, which are originally based on [19].

Theorem 4.1. If ( P Q ) has a solution and Assumption 3 holds, then the sequence { xk } generated by BDCA converges geometrically to a KKT point x of ( P Q , that is, there exist ) some constants C &gt; 0 and h ∈ ] 0 1 , [ such that

$$\| x _ { k } - \bar { x } \| \leq C \eta ^ { k }, \ \text{ for all large $k$}.$$

Proof. First, observe that by (8) we have

$$( \rho + \alpha \lambda _ { k } ^ { 2 } ) \| d _ { k } \| ^ { 2 } \leq \phi ( x _ { k } ) - \phi ( x _ { k + 1 } ).$$

By Theorem 3.1(i), we know that the right-hand side of this inequality converges to zero as k → ¥ . Thus,

$$\lim _ { k \to \infty } \| y _ { k } - x _ { k } \| = \lim _ { k \to \infty } \| d _ { k } \| = 0 = \lim _ { k \to \infty } \lambda _ { k } \| d _ { k } \|,$$

which implies

$$\lim _ { k \to \infty } \| x _ { k + 1 } - x _ { k } \| = \lim _ { k \to \infty } ( 1 + \lambda _ { k } ) \| d _ { k } \| = 0.$$

Let e &gt; 0 and t &gt; 0 be such that (16) and (17) hold. Since yk = P F ( xk -1 s ( Qxk + ) q ) , there exists some k 0 ∈ N such that

$$\left \| x _ { k } - P _ { \mathcal { F } } \left ( x _ { k } - \frac { 1 } { \sigma } ( Q x _ { k } + q ) \right ) \right \| = \| y _ { k } - x _ { k } \| \leq \epsilon, \quad \forall k \geq k _ { 0 }.$$

Hence, we obtain

$$d ( x _ { k }, \overline { \mathcal { F } } ) \leq \tau \left \| x _ { k } - P _ { \mathcal { F } } \left ( x _ { k } - \frac { 1 } { \sigma } ( Q x _ { k } + q ) \right ) \right \| = \tau \| x _ { k } - y _ { k } \| = \tau \| d _ { k } \|, \quad \forall k \geq k _ { 0 }.$$

Due to the fact that F is nonempty and closed, there exists zk ∈ F , for each k ∈ N , such that d xk ( , F ) = ‖ xk -zk ‖ . Thus

$$\| x _ { k } - z _ { k } \| \leq \tau \| d _ { k } \|, \quad \forall k \geq k _ { 0 },$$

which implies

Since

$$\| z _ { k + 1 } - z _ { k } \| \leq \| z _ { k + 1 } - x _ { k + 1 } \| + \| x _ { k + 1 } - x _ { k } \| + \| x _ { k } - z _ { k } \|,$$

it follows from (19) and (21) that

$$\lim _ { k \to \infty } \| z _ { k + 1 } - z _ { k } \| = 0.$$

Now, let F F 1 , 2 , . . . , F r be the connected components of F . By Lemma 4.1(ii) and (22) there exists F 0 ∈ { F F 1 , 2 , . . . , F r } and k 1 ≥ k 0 such that zk ∈ F 0 for all k ≥ k 1. The last assertion of Lemma 4.1 implies that

$$\phi ( z _ { k } ) = c, \quad \forall k \geq k _ { 1 }.$$

$$\lim _ { k \to \infty } \| x _ { k } - z _ { k } \| = 0.$$

Note that, since zk is a KKT point of ( P Q ), we have 〈 Qzk + q xk , -zk 〉 ≥ 0. Then,

$$\alpha, \underset { \lambda } { \min } \times \tilde { \lambda } _ { k } \, \text{is a $x$ } \, \text{pom $v\cup Q$}, \, \text{w\times} \, \mathcal { U } \tilde { \lambda } _ { k } \, \top q, x _ { k } - \tilde { \lambda } _ { k } / \leq \, \varphi. \, \text{in}, \\ \phi ( z _ { k } ) - \phi ( x _ { k } ) & = \frac { 1 } { 2 } \langle Q z _ { k }, z _ { k } \rangle - \frac { 1 } { 2 } \langle Q x _ { k }, x _ { k } \rangle + \langle q, z _ { k } - x _ { k } \rangle \\ & \leq \frac { 1 } { 2 } \langle Q z _ { k }, z _ { k } \rangle - \frac { 1 } { 2 } \langle Q x _ { k }, x _ { k } \rangle + \langle Q z _ { k }, x _ { k } - z _ { k } \rangle \\ & = \frac { 1 } { 2 } \langle Q ( x _ { k } - z _ { k } ), z _ { k } - x _ { k } \rangle \\ & \leq \frac { 1 } { 2 } \| Q \| \| x _ { k } - z _ { k } \| ^ { 2 }. \\ \text{heorem $3.1(\i$} \, \text{we know that} \, \lim _ { \ell \, \underset { \lambda } { \mu } \, \sim \, \tilde { \phi } } ( x _ { \ell } ) = \tilde { \phi }. \, \text{ Hence}. \, \text{ for all} \, k > k _ { 1 }.$$

From Theorem 3.1(i) we know that lim k → ¥ f ( xk ) = ¯ . f Hence, for all k ≥ k 1,

$$c = \phi ( z _ { k } ) \leq \phi ( x _ { k } ) + \frac { 1 } { 2 } \| Q \| \| z _ { k } - x _ { k } \| ^ { 2 } \to \bar { \phi }, \text{ as } k \to \infty.$$

We prove now that ¯ f ≤ c . Indeed, on the one hand, from (8) and (23), we have for all k ≥ k 1 that

$$\cdot \\ \phi ( x _ { k + 1 } ) - c & \leq \phi ( y _ { k } ) - c = \phi ( y _ { k } ) - \phi ( z _ { k } ) \\ & = \frac { 1 } { 2 } \left \langle Q y _ { k }, y _ { k } \right \rangle + \left \langle q, y _ { k } \right \rangle - \frac { 1 } { 2 } \left \langle Q z _ { k }, z _ { k } \right \rangle - \left \langle q, z _ { k } \right \rangle \\ & = \left \langle Q z _ { k } + q, y _ { k } - z _ { k } \right \rangle + \frac { 1 } { 2 } \left \langle Q ( y _ { k } - z _ { k } ), y _ { k } - z _ { k } \right \rangle \\ & \leq \left \langle Q z _ { k } + q, y _ { k } - z _ { k } \right \rangle + \frac { 1 } { 2 } \| Q \| \| y _ { k } - z _ { k } \| ^ { 2 }. \\ \intertext { h a other hand } \, \text{in} a. \, - \, D \sim \left ( v. \quad 1 \left ( \alpha _ { v } + \alpha \right \rangle \, \text{and} \,. \, \text{$\mathbb{ }C}$} \, \text{$\mathbb{ }V$} \, \text{$\mathbb{ }u$} \, \text{$\mathbb{ }delta} \, \text{in} a. \, \text{$\mathbb{ }a.o. $} \, \alpha \, \text{in} \, $} \, \text{in}$$

On the other hand, since yk = P F ( xk -1 s ( Qxk + ) q ) and zk ∈ F , we deduce (see, e.g., [4, Theorem 3.16]) that

$$\left \langle x _ { k } - \frac { 1 } { \sigma } ( Q x _ { k } + q ) - y _ { k }, y _ { k } - z _ { k } \right \rangle \geq 0.$$

Therefore,

$$\langle Q z _ { k } + q, y _ { k } - z _ { k } \rangle & = \langle Q x _ { k } + q, y _ { k } - z _ { k } \rangle + \langle Q ( z _ { k } - x _ { k } ), y _ { k } - z _ { k } \rangle \\ & \leq \sigma \langle x _ { k } - y _ { k }, y _ { k } - z _ { k } \rangle + \| Q \| \| x _ { k } - z _ { k } \| \| y _ { k } - z _ { k } \| \\ & \leq ( \sigma \| x _ { k } - y _ { k } \| + \| Q \| \| x _ { k } - z _ { k } \| ) \, \| y _ { k } - z _ { k } \|.$$

Combining (25) and (26), we obtain for all k ≥ k 1 that

$$\phi \left ( x _ { k + 1 } \right ) - c \leq \left ( \sigma \| x _ { k } - y _ { k } \| + \| Q \| \| z _ { k } - x _ { k } \| + \frac { 1 } { 2 } \| Q \| \| y _ { k } - z _ { k } \| \right ) \| y _ { k } - z _ { k } \|.$$

From (20), we have

$$\| y _ { k } - z _ { k } \| \leq \| y _ { k } - x _ { k } \| + \| x _ { k } - z _ { k } \| \leq ( 1 + \tau ) \| d _ { k } \|, \quad \forall k \geq k _ { 1 }.$$

Hence, we deduce from (27) that

$$\phi ( x _ { k + 1 } ) - c \leq \beta \| d _ { k } \| ^ { 2 }, \quad \forall k \geq k _ { 1 },$$

$$\text{where } \beta \coloneqq ( 1 + \tau ) \left ( \sigma + \| Q \| \tau + \frac { 1 + \tau } { 2 } \| Q \| \right ). \, \text{ Passing } ( 2 8 ) \, \text{ to the limit as } k \to \infty, \, \text{ we get} \\ \bar { \phi } = \lim _ { k \to \infty } \phi ( x _ { k + 1 } ) \leq c.$$

$$k \rightarrow \infty$$

The latter together with (24) imply that ¯ f = c . Therefore, it follows from (28) and (8) that

$$\phi ( x _ { k + 1 } ) - \bar { \phi } \leq \beta \| d _ { k } \| ^ { 2 } \leq \frac { \beta } { \rho } \left ( \phi ( x _ { k } ) - \phi ( x _ { k + 1 } ) \right ), \quad \forall k \geq k _ { 1 },$$

or, equivalently,

$$\left ( 1 + \frac { \beta } { \rho } \right ) \left ( \phi ( x _ { k + 1 } ) - \bar { \phi } \right ) \leq \frac { \beta } { \rho } \left ( \phi ( x _ { k } ) - \bar { \phi } \right ), \quad \forall k \geq k _ { 1 }.$$

Since { f ( xk ) } is monotonically decreasing to ¯ , f we deduce from the last inequality that

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdot \\ \phi ( x _ { k } ) - \phi ( x _ { k + 1 } ) & = ( \phi ( x _ { k } ) - \bar { \phi } ) + ( \bar { \phi } - \phi ( x _ { k + 1 } ) ) \\ & \leq \phi ( x _ { k } ) - \bar { \phi } \leq ( \phi ( x _ { k _ { 1 } } ) - \bar { \phi } ) \left ( \frac { \beta } { \rho + \beta } \right ) ^ { k - k _ { 1 } } \\ & = M _ { 0 } \eta ^ { 2 k }, \quad \forall k \geq k _ { 1 }, \quad \quad \ \text{$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$\quad$$$

where M 0 : = ( f ( xk 1 ) -¯ f ) ( r + b ) k 1 b -k 1 and h : = √ b r + b ∈ ] 0 1 . Consider now , [

$$M _ { 1 } \coloneqq \max _ { \lambda \geq 0 } \frac { ( 1 + \lambda ) ^ { 2 } } { \alpha \lambda ^ { 2 } + \rho } = \frac { \alpha + \rho } { \alpha \rho }.$$

Hence, from (8) and (29), we obtain

$$\begin{array} { c c } \lambda & \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \  \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \ \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \ \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \,
 \quad \quad \quad$$

which implies

$$\| x _ { k + 1 } - x _ { k } \| \leq M \eta ^ { k }, \quad \forall k \geq k _ { 1 },$$

with M : = √ M M 1 0. Then, for all k ≥ k 1 and m ≥ 1, we have

$$\| x _ { k + m } - x _ { k } \| & \leq \| x _ { k + m } - x _ { k + m - 1 } \| + \dots + \| x _ { k + 1 } - x _ { k } \| \\ & \leq ( \eta ^ { m - 1 } + \dots + \eta + 1 ) M \eta ^ { k } \leq \frac { M } { 1 - \eta } \eta ^ { k }.$$

This implies that { xk } is a Cauchy sequence and hence converges to a point x ∈ F . According to Theorem 3.1(ii) and Remark 3.3, combined with the fact that dom h = R n is an open set, we must have that x is a KKT point of ( P Q ). Moreover, passing the inequality (30) to the limit as m → ¥ , we obtain

$$\| \bar { x } - x _ { k } \| \leq \frac { M } { 1 - \eta } \eta ^ { k }, \quad \forall k \geq k _ { 1 },$$

which concludes the proof.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-c9dcff97-d7cc-4a49-92ed-fceaabbb75a6.jpg)

## 5 Numerical experiments

The purpose of this section is to compare the performance of BDCA (Algorithm 1) against the classical DCA. We refrain from comparing the algorithms against other methods, as our only aim here is to show that it is more advantageous to apply BDCA than DCA whenever this is possible, not to show that these methods are the most efficient for the problems that we consider. Consequently, we tested both algorithms in the three different settings that can occur, depending on whether the feasible set is unbounded, bounded with general constraints, and bounded with box constraints (so the feasibility in the line search step can be ensured). We applied both algorithms for testing copositivity [8] (unbounded) and for solving the glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblem [7, 12] (bounded, with box constraints in the case of glyph[lscript] ¥ ). In our last experiment we test the performance on piecewise quadratic problems with box constraints, whose objective function is thus nonsmooth. All these problems clearly satisfy Assumptions 1-3 and admit a DC decomposition with g being a quadratic function. Thus, subproblem ( P k ) can be solved by computing a projection onto the feasible set F , analogous to that stated in equation (15). The projector onto the feasible set in our applications can be directly computed.

All the codes were written in Python 3.7 and the tests were run on an Intel Core i7-4770 CPU 3.40GHz with 32GB RAM, under Windows 10 (64-bit).

## 5.1 Testing copositivity

Recall that a given n × n matrix A is said to be copositive if

$$\langle A x, x \rangle \geq 0, \quad \text{for all } x \in \mathbb { R } _ { + } ^ { n },$$

where R n + stands for the non-negative orthant. Copositivity has recently attracted considerable attention in mathematical optimization, see e.g. [5, 6, 8, 25]. The problem of determining whether a given matrix is not copositive is known to be NP-complete [23] and it can be recast as the following non-convex optimization problem

$$\min _ { x \in \mathbb { R } _ { + } ^ { n } } \, \phi ( x ) \coloneqq \langle A x, x \rangle.$$

The copositivity of A is now equivalent to min x ∈ R n + f ( x ) = 0. In [8], the authors reformulated (31) as a DC problem according to the decomposition in (12)-(13), and applied DCA as a heuristic for testing whether a matrix is not copositive. To be more specific, given s &gt; max { l max ( A ) , 0 , the reformulation of problem (31) as a DC problem becomes }

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } \ g ( x ) - h ( x ) = \phi ( x ) \\ s. t. \quad x _ { i } \geq 0, \, i = 1, \dots, n, \end{cases}$$

with

$$g ( x ) \coloneqq \frac { \sigma } { 2 } \| x \| ^ { 2 } \quad \text{and} \quad h ( x ) \coloneqq \frac { 1 } { 2 } \langle ( \sigma I - A ) x, x \rangle.$$

Under this decomposition, DCA is applied as a heuristic to determine the copositivity of a given matrix as follows: if at some iterate f ( xk ) &lt; 0, then the matrix is non-copositive; otherwise, if a critical point is reached, the instance is undecidable.

Copositive matrices play an important role in graph theory. The size of the largest complete subgraph contained in a given graph G , denoted by g ( G ) , is known as the clique number of G . If A and E are the adjacency matrix of G and the matrix of all ones, respectively, it can be shown (see [14, Corollary 2.4]) that

$$\gamma ( G ) = \min \left \{ \mu \, \colon \mu ( E - A ) - E \text{ is copositive} \right \}.$$

Therefore, the matrix m ( E -A ) -E will be copositive if m ≥ g ( G ) and non-copositive otherwise. Furthermore, in the latter case, the matrix will be closer to the copositive cone as m approaches g ( G ) from the left.

In our tests we considered matrices constructed as follows. Let G be the cycle graph of n nodes whose adjacency matrix, A cycle =( aij ) ∈ R n × n , is given component-wise by

$$a _ { i j } \coloneqq \begin{cases} \ 1, & \text{if $|i-j|\in \{1,n-1\}$,} \\ 0, & \text{otherwise.} \end{cases}$$

Its clique number is clearly g ( G ) = 2. Hence, the matrix

$$Q _ { n } ^ { \mu } \coloneqq \mu ( E - A _ { \text{cycle} } ) - E \in \mathbb { R } ^ { n \times n }$$

is copositive for all m ≥ 2 and non-copositive for m &lt; 2. In fact, when m = 2 it coincides with the so-called Horn matrix Hn (see, e.g., [13, Section 4]). For instance, the Horn matrix H 5 takes the form

$$H _ { 5 } \coloneqq Q _ { 5 } ^ { 2 } = \left ( \begin{array} { c c c c c } 1 & - 1 & 1 & 1 & - 1 \\ - 1 & 1 & - 1 & 1 & 1 \\ 1 & - 1 & 1 & - 1 & 1 \\ 1 & 1 & - 1 & 1 & - 1 \\ - 1 & 1 & 1 & - 1 & 1 \end{array} \right ).$$

Experiments In our numerical tests we used the parameter setting as

$$\alpha \coloneqq 0. 0 1 \text{ \ and \ } \beta \coloneqq 0. 1.$$

The trial step-size l k in the boosting step of BDCA (Line 8 of Algorithm 1) was chosen to be self-adaptive as in [3]. This technique proceeds as follows. At the first iteration, choose any l 0 &gt; 0. Then, for k ≥ 1, if the line search has never been used, we take l k = l 0. Otherwise, if the two previous trial step-sizes have been directly accepted (without being reduced by the backtracking step), then the last accepted positive l is scaled by a factor of g &gt; 1 and used as the current trial step-size. If that is not the case, the trial step-size is set as the last positive value of l accepted in previous iterations. In our tests we used

$$\bar { \lambda } _ { 0 } \coloneqq 1 \ \text{ and } \ \gamma \coloneqq 2.$$

In our first numerical experiment, we considered Horn matrices of different sizes, Hn , for n ∈ { 1000 1250 , , . . . , 5000 } . For each size, DCA and BDCA were run from the same 100 starting points randomly generated in the intersection of the non-negative orthant with the unit ball. We stopped the algorithms when ‖ dk ‖ ≤ 10 -9 for the first time. The results are shown in Figure 1, where we can observe that, on average, BDCA was more than 15 times faster than DCA for all sizes. As expected, since Horn matrices are copositive, both

algorithms converged to critical points with a positive objective value very close to 0. It is worth to mention that the objective function at the points found by BDCA was usually smaller than at the ones found by DCA. We also show in Figure 2 the percentage of iterations at which the boosting step was activated, that is, when condition in line 7 of Algorithm 1 was fulfilled. We observed that, for all sizes, the linesearch was performed in around the 45% of the iterations. In Figure 3 we show the behavior of both algorithms in a particular instance for testing the copositivity of H 1000.

Figure 1: Comparison between DCA and BDCA for checking the copositivity of Horn matrices of order n ∈ { 1000 1250 , , . . . , 5000 } . For each size, we represent the ratios of the running time between DCA and BDCA for 100 random starting points (blue crosses) and the median ratio among all of them (white circle).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-14368e8e-ae5a-46f3-84d2-bb2fe2becf02.jpg)

Figure 2: Ratio of the number of iterations at which the boosting step of BDCA was activated with respect the number of iterations performed for testing the copositivity of Horn matrices of order n ∈ { 1000 1250 , , . . . , 5000 } . For each size, we represent this ratio for 100 random starting points (green crosses) and the median ratio among all of them (white circle).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-778fd7d1-e197-483f-819d-73d8203fb328.jpg)

Figure 3: Value of the objective function of DCA and BDCA (using logarithmic scale in the left axis) as well as the step-size used in BDCA (right axis, dotted blue line), with respect to the iteration, for checking the copositivity of the Horn matrix of order n = 1000 from the same random starting point.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-9cd235e9-2cd5-4473-9a1e-44add5c5857c.jpg)

In our second experiment we considered matrices of the form Qn m as defined in (32). In order to generate hard instances (those which are close to be copositive) we took m : = 1 9. . For each size n ∈ { 1000 1250 , , . . . , 5000 } , DCA and BDCA were run from the same 100 random starting points generated as in our previous experiment. In this case, we let the algorithms run until they find a negative objective value (which exists because of the noncopositivity of the matrices). We used two stopping criteria, whose results are depicted in Figure 4: on the left, the algorithms were stopped when any negative objective value was found; on the right, the objective value was required to be smaller than -10 -4 . We do not show any results on the second criterion for n greater than 2000 because DCA becomes extremely slow (for n = 2000, the instances solved by DCA required more than 5 minutes on average). This time the advantage of BDCA with respect to DCA increased with the size n , and was significantly greater than in the previous experiment when the second criterion was used.

Remark 5.1 . Clearly, BDCA iterations will be more time consuming than those of DCA due to the need of checking condition in Line 7 and the linesearch procedure. Note that the linesearch requires of function evaluations of f , which may be expensive at some applications. For this reason, in our experiments we compare the total CPU running time of the algorithm, as it includes the possibly wasted extra time of the boosting step.

## 5.2 Solving the glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblem

The trust-region subproblem (TRSP) arises in trust-region methods, which are optimization algorithms that consist in replacing the original objective function by a model which is a good approximation of the original function at the current iterate. The models are usually defined to be a quadratic function, in which case the task consists in solving nonconvex

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-c30babc7-40aa-4947-a45e-fc836c2be212.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-e1ffab75-8581-4c32-860a-fc7aebede463.jpg)

(a) Stopping criterion: f ( x ) &lt; 0

(b) Stopping criterion: f ( x ) &lt; -10 -4

Figure 4: Comparison between DCA and BDCA for detecting the non-copositivity of matrices of various orders n . For each size, we represent the ratios of the running time between DCA and BDCA for 100 random starting points (blue crosses) and the median ratio among all of them (white circle).

quadratic optimization problems of the type

$$\min _ { \| x \| \leq r } \frac { 1 } { 2 } \langle A x, x \rangle + \langle b, x \rangle,$$

where A is an n × n real symmetric matrix, b ∈ R n , r is a positive number and | | |·| | | is any given norm. Of course, the choice of the norm has a serious impact on the difficulty for solving the subproblems.

The application of the DCA for solving the Euclidean trust-region subproblem (the most common choice for the norm) was first proposed in [29] and its convergence was further studied in [16, 31, 33]. Thanks to the structure of the trust-region subproblem, the implementation of the DCA is very simple and efficient, as the iterations are given by (15) and only require matrix-vector products. On the other hand, as observed in [7, Section 7.8] and [12], the choice of the Euclidean norm for the definition of the trust-region has several drawbacks, especially when the problem at hand is box-constrained, in which case the intersection of the Euclidean ball of the trust region with the feasible set has a complicated structure. The choice of the glyph[lscript] ¥ norm ‖·‖ ¥ for the trust-region when the problem involves bounds of the type l ≤ x ≤ u permits to ensure feasibility by simply requiring similar bounds on the trust-region subproblem. Unfortunately, the glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblem are NP-hard [23], a class of problems for which it is commonly believed that there are no polynomial time algorithms.

In this subsection we compare the performance of DCA and BDCA on the challenging glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblems. To this aim, we consider the DC decomposition (12)-(13) of the (possibly) nonconvex part of the objective function. Thus, given s &gt; max { l max ( A ) , 0 , the subproblems for the } glyph[lscript] 1 norm take the form

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } \ g ( x ) - h ( x ) = \phi ( x ) \\ \text{s.t.} \quad \sum _ { i = 1 } ^ { n } | x _ { i } | \leq r, \end{cases} \quad ( \mathcal { P } _ { 1 } )$$

with

$$g ( x ) \coloneqq \frac { \sigma } { 2 } \| x \| ^ { 2 } + \langle b, x \rangle \quad \text{and} \quad h ( x ) \coloneqq \frac { 1 } { 2 } \langle ( \sigma I - A ) x, x \rangle,$$

while for the glyph[lscript] ¥ norm these problems are

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } & g ( x ) - h ( x ) = \phi ( x ) \\ s. t. & - r \leq x _ { i } \leq r, \, i = 1, \dots, n. \end{cases} \quad \left ( \mathcal { P } _ { \infty } \right )$$

Observe that the feasible set of ( P 1) can be equivalently written in terms of 2 n linear constraints of the type ± x 1 ± x 2 ±···± xn ≤ r , so the problem is a particular instance of ( P ). In principle, as mentioned in Remark 3.1, the largest step-size derived in [9] ensuring feasibility could be computed. However, as the feasible set has 2 n linear constraints, computing (4) would be very time-consuming. Nonetheless, given a point yk and a feasible direction dk , an upper bound of the maximum value of the step-size l k for ( P 1) is given by the Euclidean norm, since

$$\| y _ { k } + \lambda d _ { k } \| _ { 1 } \geq \| y _ { k } + \lambda d _ { k } \| > r, \text{ for all } \lambda > \lambda _ { k },$$

where

$$\widehat { \lambda } _ { k } \coloneqq \frac { \langle y _ { k }, d _ { k } \rangle + \sqrt { \langle y _ { k }, d _ { k } \rangle ^ { 2 } - \| d _ { k } \| ^ { 2 } ( \| y _ { k } \| ^ { 2 } - r ^ { 2 } ) } } { \| y _ { k } \| ^ { 2 } },$$

so one must always choose l k ≤ ̂ l k to avoid extra time in checking feasibility. On the other hand, for the glyph[lscript] ¥ norm, the situation is more favorable, as feasibility can be guaranteed whenever glyph[negationslash]

glyph[negationslash]

$$0 \leq \lambda \leq \min _ { i \not \in I ( x _ { k } ) } \left \{ \frac { r } { | d _ { k, i } | } - \frac { y _ { k, i } } { d _ { k, i } } \, \Big | \, d _ { k, i } \neq 0 \right \},$$

which coincides with (4), so no time will be wasted in Step 8 of Algorithm 1 if one takes l k satisfying the latter inequalities.

Experiments We used the same parameter setting as in the previous section for Algorithm 1, except for the value of g , which was increased to 20. The matrix A and the vector b were generated with coordinates randomly and uniformly chosen in ] -1 1 , while the , [ value of r was randomly and uniformly chosen in the range ] 0 , √ n / 4 [ for ( P 1) and ] 0 1 , / 4 [ for ( P ¥ ). For each size n ∈ { 1000 1500 , , . . . , 5000 } , DCA and BDCA were run from the same 100 starting points randomly picked inside the trust-region. We stopped the algorithms when ‖ dk ‖ / ‖ xk ‖ ≤ 10 -8 for the first time. The time comparison for both norms are summarized in Figure 5. BDCA was consistently faster than DCA. On average, it was 3.8 times faster for solving ( P 1) and 3.65 times faster for ( P ¥ ).

We also show in Figure 6 the percentage of iterations at which the boosting step was activated. We observe that, for all sizes, the linesearch was performed on average in around 80% of the iterations for the case of the glyph[lscript] 1 norm, and 40% for the glyph[lscript] ¥ norm.

When applied to ( P 1), both algorithms obtained the same value in 875 instances, BDCA reached a smaller objective value in 18 instances, while DCA did so in 7. When applied to ( P ¥ ), BDCA obtained a smaller objective value in 461 instances, while DCA did so in 417 (the value was the same in 22 instances). In Figure 7 we show the behavior of both algorithms for a particular instance with n = 1000, which was chosen so that both algorithms attained the same objective value.

We conclude this section with some comments about the rate of convergence of DCA and BDCA. According to Theorem 4.1, both methods are R-linearly convergent, so by (18),

$$\lim _ { k \to \infty } \| x _ { k } - \bar { x } \| ^ { \frac { 1 } { k } } \leq \eta,$$

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-cfe0d440-4ae0-4b1d-8c4e-7fe89eab62f5.jpg)

n

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-a925e15f-0146-473d-9748-42b8fa2a25e2.jpg)

n

Figure 5: Comparison between DCA and BDCA for solving randomly generated glyph[lscript] 1 (left) and glyph[lscript] ¥ (right) trust-region subproblems in R n , with n ∈ { 1000 1250 , , . . . , 5000 } . For each size, we represent the ratios of the running time between DCA and BDCA for 100 random starting points (blue crosses) and the median ratio among all of them (white circle).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-407824b5-ba61-47b0-a1a1-123d6cf8c434.jpg)

Figure 6: Ratio of the number of iterations at which the boosting step of BDCA was activated with respect the number of iterations performed for solving randomly generated glyph[lscript] 1 (left) and glyph[lscript] ¥ (right) trust-region subproblems in R n , with n ∈ { 1000 1250 , , . . . , 5000 } . For each size, we represent this ratio for 100 random starting points (green crosses) and the median ratio among all of them (white circle).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-f5785dac-ef04-4c2e-8877-cc3c910586b5.jpg)

for some h ∈ ] 0 1 . , [ In Figure 8, for a particular random instance, we have represented the sequence {‖ xk - ‖ x 1 / k } , which was computed for both algorithms after obtaining the limit point x with a higher precision. We observe that the value of h is very close to 1 for DCA, while line-searches clearly helped improving this slow rate. A possible explanation about the bad R-linear convergence rate of DCA can be deduced from the proof of Theorem 4.1. The upper bound obtained there is b r + b , with b &gt; s . When l max ( Q ) &gt; 0, Assumption 1 holds for r as in (14), which would then be equal to s -l max ( Q ) . Therefore,

$$\frac { \beta } { \rho + \beta } = \frac { \beta } { \sigma - \lambda _ { \max } ( Q ) + \beta } > \frac { \sigma } { 2 \sigma - \lambda _ { \max } ( Q ) },$$

where the last inequality holds since the left term is an increasing function with respect to b . In our numerical tests we took s -l max ( Q ) = 0 01 (we numerically observed how larger .

Figure 7: Value of the objective function of DCA and BDCA (using logarithmic scale in the left axis) as well as the step-size used in BDCA (right axis, dotted blue line), with respect to the iteration, for solving a randomly generated glyph[lscript] 1 (top) and glyph[lscript] ¥ (bottom) trustregion subproblem in R 1000 from the same random starting point. Both algorithms attained the same objective value ¯ . f

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-de958170-50ef-450e-a9eb-237dd7b77090.jpg)

values slowed down both DCA and BDCA). In the random instances shown in Figure 8 l max ( Q ) was equal to 25 77 for the . glyph[lscript] 1 norm and 25 89 for the . glyph[lscript] ¥ norm, which would give upper bounds on the R-linear convergence rate of 0 9996 for both problems. . According to the figures, these bounds seem to be tight, particularly for the glyph[lscript] ¥ norm.

## 5.3 Piecewise quadratic problems with box constraints

Finally, we test BDCA on optimization problems with nonsmooth objective function. To this aim, we consider piecewise quadratic problems with linear constraints of the form

$$\begin{cases} \min _ { x \in \mathbb { R } ^ { n } } \ \phi ( x ) \coloneqq \min _ { j \in \{ 1, \dots, m \} } \left \{ \frac { 1 } { 2 } \| x - c ^ { j } \| ^ { 2 } \right \} \\ \text{s.t.} \quad l _ { i } \leq x _ { i } \leq u _ { i }, \, i = 1, \dots, n ; \end{cases}$$

for given l =( l 1 , . . . , l n ) , u =( u 1 , . . . , un ) ∈ R n and c 1 , . . . , c m ∈ R n .

Figure 8: Comparison on the rate of R-linear convergence of DCA and BDCA for solving the same randomly generated glyph[lscript] 1 (top) and glyph[lscript] ¥ (bottom) trust-region subproblems in R 1000 from Figure 7.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-c1ba7e55-393f-4a3d-9625-8f9c24f348a2.jpg)

As discussed in [26, § 6.3], the objective function of this problem admits the DC decomposition f ( x ) = g x ( ) -h x ( ) with glyph[negationslash]

$$g ( x ) \coloneqq \frac { 1 } { 2 } \sum _ { j = 1 } ^ { m } \| x - c ^ { j } \| ^ { 2 } \quad \text{and} \quad h ( x ) \coloneqq \max _ { l \in \{ 1, \dots, m \} } \left \{ \frac { 1 } { 2 } \sum _ { \substack { j = 1 \\ j \neq l } } ^ { m } \| x - c ^ { j } \| ^ { 2 } \right \}.$$

Experiments For our numerical tests, we generated problems of the form (33) as follows. First, the vector l ∈ R n was generated with coordinates randomly chosen in ] -5 5 . Then, , [ we randomly generated a vector e ∈ R n with coordinates in ] 0 5 , [ and we set u : = l + e . Finally, the points c 1 , . . . , cm ∈ R n were generated so that they became unfeasible for all constraints as follows: each component i ∈ { 1 , . . . , n } of each of these vectors was randomly picked in one of the intervals ] l i -10 , l i [ or ] ui , ui + 10 . [ In our experiment, for each n ∈ { 100 150 , , . . . , 1000 } and each m ∈ { 100 150 , , . . . , 1000 } , DCA and BDCA were run from the same 100 starting points randomly picked inside the feasible set. We used the same parameter setting and stopping criterion for the algorithms as in the previous TRSP experiments. The time comparison is shown in Figure 9, where we represent the median ration between DCA and BDCA among the 100 instances. Detailed results for all 100 runs

are shown in Figure 10(a) for fixed n = 500 and Figure 10(b) for fixed m = 500. From the results of this comparison we infer that the superiority of BDCA increases as m does, while it stabilizes as n increases. As in previous experiments, we show in Figure 11 the percentage of iterations at which the boosting step was activated. The objective value attained by DCA and BDCA were the same in all instances.

Figure 9: Comparison between DCA and BDCA for solving randomly generated piecewise quadratic problems with m pieces in R n , for n ∈ { 100 200 , , . . . , 1000 } and m ∈ { 100 200 , , . . . , 1000 } . For each pair ( n m , ) , we represent the median of the ratios of the running time between DCA and BDCA for 100 random starting points.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-1ec8c8f7-65d3-49c6-bf72-49bf896fef72.jpg)

## 6 Concluding remarks

We have extended the Boosted DC Algorithm for solving linearly constrained DC programming. The algorithm is proved to provide KKT points of the constrained problem. In addition, we have shown why this approach cannot be extended to more general convex constraints. The theoretical results were confirmed by some numerical experiments for testing the copositivity of matrices and for solving glyph[lscript] 1 and glyph[lscript] ¥ trust-region subproblems. For copositive matrices, BDCA was on average fifteen times faster than DCA; for non-copositive ones, this advantage was much more superior; and for trust-region subproblems, BDCA was more than three times faster than DCA. We also considered piecewise quadratic problems with box constraints, which thus have nonsmooth objective functions. We observed again that BDCA was faster than DCA and, further, that the advantage was more noticeable as the number of pieces of the objective function increased. Future research includes investigation of alternative approaches to derive a Boosted DCA that permits to address any type of constrained DC programs. It would also be interesting to combine BDCA with the inertial technique employed in [27].

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-d2f0c92a-49e7-49f7-90a8-e6de9fdc3d12.jpg)

200

400

600

800

1000

16

14

12

10

8

6

4

2

0

m

(b) n = 500 and m ∈ { 100 200 , , . . . , 1000 }

Figure 10: Comparison between DCA and BDCA for solving randomly generated piecewise quadratic problems with m pieces in R n , for n ∈ { 100 200 , , . . . , 1000 } and m = 500 (left), and for n = 500 and m ∈ { 100 200 , , . . . , 1000 } (right). For each problem, we represent the ratios of the running time between DCA and BDCA for 100 random starting points (blue crosses) and the median ratio among all of them (white circle).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01138v4-figure-6ec184fd-9200-4365-a835-92335ab1c4b0.jpg)

Figure 11: Ratio of the number of iterations at which the boosting step of BDCA was activated with respect the number of iterations performed for solving randomly generated piecewise quadratic problems with m pieces in R n , for n ∈{ 100 200 , , . . . , 1000 } and m = 500 (left), and for n = 500 and m ∈{ 100 200 , , . . . , 1000 } (right). For each size, we represent this ratio for 100 random starting points (green crosses) and the median ratio among all of them (white circle).

Acknowledgments FJAA and RC were partially supported by the Ministry of Science, Innovation and Universities of Spain and the European Regional Development Fund (ERDF) of the European Commission (PGC2018-097960-B-C22), and by the Generalitat Valenciana (AICO/2021/165). PTV was supported by Vietnam Ministry of Education and Training Project hosting by the University of Technology and Education, Ho Chi Minh City Vietnam (2023-2024).

Time DCA / Time BDCA

## References

- [1] Aragón Artacho, F.J., Fleming, R., Vuong, P.T.: Accelerating the DC algorithm for smooth functions. Math. Program. 169(1), 95-118 (2018)
- [2] 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)
- [3] Aragón Artacho, F.J., Vuong, P.T.: The boosted difference of convex functions algorithm for nonsmooth functions. SIAM J. Optim. 30(1), 980-1006 (2020)
- [4] Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in Hilbert spaces, 2nd ed. Springer, Berlin (2017)
- [5] Bomze, I.M.: Copositive optimization-recent developments and applications. European J. Oper. Res. 216(3), 509-520 (2012)
- [6] Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479-495 (2009)
- [7] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods . MPS/SIAM Series on Optimization (2000)
- [8] Dür, M., Hiriart-Urruty, J.-B.: Testing copositivity with the help of difference-of-convex optimization. Math. Program. 140(1), 31-43 (2013)
- [9] Ferreira, O.P., Santos, E.M., Souza, J.C.O.: Boosted scaled subgradient method for DC programming. ArXiv: https://arxiv.org/abs/2103.10757 (2021)
- [10] Fukushima, M., Mine, H.: A generalized proximal point algorithm for certain nonconvex minimization problems. Int. J. Syst. Sci. 12(8), 989-1000 (1981)
- [11] Geremew, W., Nam, N.M., Semenov, A., Boginski, V., Pasiliao, E.: A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique. J. Glob. Optim. 72(4), 705-729 (2018)
- [12] Geremew, S., Mouffe, M., Toint, P.L., Weber-Mendonça, M.: A recursive glyph[lscript] ¥ -trustregion method for bound-constrained nonlinear optimization. IMA J. Numer. Anal. 28(4), 827-861 (2008)
- [13] Johnson, C.R., Reams, R.: Constructing copositive matrices from interior matrices. Electron. J. Linear Al. , 17, 9-20 (2008)
- [14] de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875-892 (2002)
- [15] Le Thi, H.A., Pham Dinh, T.: DC Programming and DCA: Thirty Years of Developments. Math. Program. 169(1), 5-68 (2018)
- [16] Le Thi, H.A., Pham Dinh, T., Yen, N.D.: Behavior of DCA sequences for solving the trust-region subproblem. J. Global Optim. 53(2), 317-329 (2012)

| [17] Le Thi, H.A., Pham Dinh, T.: The DC (difference of convex functions) programming and DCArevisited with DCmodels of real world nonconvex optimization problems. Ann. Oper. Res. 133(1-4), 23-46 (2005)                    |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [18] Le Thi, H.A., Huynh V.N., Pham Dinh, T.: Convergence analysis of Difference-of- Convex Algorithm with subanalytic data. J. Optim. Theory Appl. 179(1), 103-126 (2018)                                                    |
| [19] Luo, Z.Q., Tseng, P: Error bound and convergence analysis of matrix splitting algo- rithms for the affine variational inequality problem. SIAM J. Optim. 2(1), 43-54 (1992)                                              |
| [20] Mine, H., Fukushima, M.: A minimization method for the sum of a convex function and a continuously differentiable function. J. Optim. Theory Appl. 33(1), 9-23 (1981)                                                    |
| [21] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, vol. II . Springer-Verlag Berlin Heidelberg (2006)                                                                                             |
| [22] Moosaei, H., Bazikar, F., Ketabchi, S., Hladík, M.: Universum parametric-margin v -support vector machine for classification using the difference of convex functions algo- rithm. Appl. Intell. 52(3), 2634-2654 (2022) |
| [23] Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117-129 (1987)                                                                                        |
| [24] Nam, N.M., Geremew, W., Reynolds, R., Tran, T.: Nesterov's smoothing technique and minimizing differences of convex functions for hierarchical clustering. Optim. Lett. 12(3), 455-473 (2018)                            |
| [25] Nie, J., Yang, Z., Zhang, X.: A complete semidefinite algorithm for detecting coposi- tive matrices and tensors. SIAM J. Optim. 28(4), 2902-2921 (2018)                                                                  |
| [26] de Oliveira, W.: Proximal bundle methods for nonsmooth DCprogramming. J. Global Optim. 75(2), 523-563 (2019)                                                                                                             |
| [27] de Oliveira, W., Tcheou, M.P.: An inertial algorithm for DCprogramming. Set-Valued Var. Anal. 27(4), 895-919 (2019)                                                                                                      |
| [28] Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289-355 (1997)                                                                  |
| [29] Pham Dinh, T., Le Thi, H.A.: A D.C. optimization algorithm for solving the trust- region subproblem. SIAM J. Optim. 8(2), 476-505 (1998)                                                                                 |
| [30] Pham Dinh, T., Le Thi, H.A., Akoa, F. : Combining DCA(DCAlgorithms) and interior point techniques for large-scale nonconvex quadratic programming. Optim. Methods Softw. 23(4), 609-629 (2008)                           |
| [31] Tuan H.N.: Convergence rate of the Pham Dinh-Le Thi algorithm for the trust-region subproblem. J. Optim. Theory Appl. 154(3), 904-915 (2012)                                                                             |
| [32] Tuan H.N.: Linear convergence of a type of iterative sequences in nonconvex quadratic programming. J. Math. Anal. Appl. 423(2), 1311-1319 (2015)                                                                         |

- [33] Tuan H.N., Yen, N.D.: Convergence of the Pham Dinh-Le Thi's algorithm for the trust-region subproblem. J. Glob. Optim. 55(2), 337-347 (2013)
- [34] Rockafellar, R.T.: Convex Analysis . Princeton University Press (1972)
- [35] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis , Grundlehren Math. Wiss. 317, Springer, New York (1998)
- [36] Xu, H.M., Xue, H., Chen, X.H., Wang, Y.Y.: Solving indefinite kernel support vector machine with difference of convex functions programming. Proceedings of the ThirtyFirst AAAI Conference on Artificial Intelligence (2017)
Francisco J. Aragón Artacho Rubén Campoy Phan T. Vuong
The Boosted DC Algorithm for linearly constrained DC programming
The Boosted Difference of Convex functions Algorithm (BDCA) has been recently
introduced to accelerate the performance of the classical Difference of Convex
functions Algorithm (DCA). This acceleration is achieved thanks to an
extrapolation step from the point computed by DCA via a line search procedure.
In this work, we propose an extension of BDCA that can be applied to difference
of convex functions programs with linear constraints, and prove that every
cluster point of the sequence generated by this algorithm is a
Karush--Kuhn-Tucker point of the problem if the feasible set has a Slater
point. When the objective function is quadratic, we prove that any sequence
generated by the algorithm is bounded and R-linearly (geometrically)
convergent. Finally, we present some numerical experiments where we compare the
performance of DCA and BDCA on some challenging problems: to test the
copositivity of a given matrix, to solve one-norm and infinity-norm
trust-region subproblems, and to solve piecewise quadratic problems with box
constraints. Our numerical results demonstrate that this new extension of BDCA
outperforms DCA.