A new modified deflected subgradient method

1 Introduction

In this paper we consider the following integer linear program:

It is easy to prove that $w(\lambda )⩽z$ for all $\lambda ⩾0$ (weak duality (Bazaraa et al., 2006)). The best choice for $\lambda$ would be the optimal solution of the following problem, called the dual problem:

With some suitable assumptions, the dual optimal value $w^{\ast }$ is equal to $z^{\ast }$ (strong duality (Bazaraa et al., 2006)). In general, $w^{\ast }$ provides a tighter lower bound of $z^{\ast }$ . These bounds may be useful in nodes evaluation in exact methods such as Branch and Bound algorithm to find the optimal solution of $(\mathit{IP})$ . The function $w\left(\lambda \right)$ is continuous and concave but non-smooth. The most widely adopted method for solving the dual problem is the subgradient optimization, see for instance Polyak (1967), Shor (1985), Nedic and Bertsekas (2010), Nesterov (2014) and Hu et al. (2015). The pure subgradient optimization method is an iterative procedure that can be used to solve the problem of maximizing (minimizing) a non-smooth concave (convex) function $w\left(\lambda \right)$ on a closed convex set $\mathrm{\Omega }$ . This procedure is summarized in Algorithm 1, and it is used in various fields in science and engineering (Sra et al., 2012).

In the context of Lagrangian relaxation, computing the subgradient direction $s^k$ and the projection $P_{\mathrm{\Omega }}\left({\lambda }^k+t_k{s}^k\right)(\mathrm{\Omega }={\mathbb{R}}_{+}^m)$ is a relatively easy problem. Since the subgradient $s^k$ is not necessarily a descent direction, the step-length rule (4) differs from those given in the area of descent methods. In fact, this choice assures the decreasing of the subsequence ${\left(‖{\lambda }^k-{\lambda }^{\ast }‖\right)}_k$ as well as the convergence of ${\left({\lambda }^k\right)}_k$ to ${\lambda }^{\ast }$ . However, it is impossible to know in advance the value of $w^{\ast }$ for most problems. To this end, the most effective way is to use the variable target value methods developed in Kim et al. (1990), Fumero (2001) and Sherali et al. (2000).

Another challenge in subgradient optimization is the choice of direction search that affects the computational performance of the algorithm. It is known that choosing the subgradient direction $s^k$ , leads to the zigzagging phenomenon that might cause slow the procedure to crawl towards optimality (Bazaraa et al., 2006). To overcome this situation, in the spirit of conjugate gradient method (Nocedal and Wright, 2006; Fletcher and Reeves, 1964), we can adopt a direction search that deflects the subgradient pure direction. Accordingly, the direction search $d^k$ at ${\lambda }^k$ is computed as:

Some promising deflection algorithms of this type are the Modified Gradient Technique (MGT) (Camerini et al., 1975) and the Average Direction Strategy (ADS) (Sherali and Ulular, 1989). The MGT method was found to be superior to the pure subgradient method when used in concert with a specially designed step-length selection rule. The deflection parameter ${\mathrm{\Psi }}_k^{\mathit{MGT}}$ is computed according to:

The ADS strategy recommends to make the deflection at each iteration point by choosing the direction search which simply bisects the angle between the current subgradient $s^k$ and the previous direction search $d^{k-1}$ . To get this direction, the deflection parameter is computed according to:

With this choice of the deflection parameter, the direction becomes:

Nowadays, the deflected subgradient method remains an important tool for nonsmooth optimization problems, especially for linear integer programming, due to its simple formulation and low storage requirement. In this paper, we present a new deflected direction search as a convex combination of the direction $d_{\mathit{MGT}}^k$ (8) and the direction $d_{\mathit{ADS}}^k$ (10). Our main result is the identification of the convex combination parameter which forces the algorithm to have a better deflection search than those given in the pure subgradient, MGT and ADS. For a numerical comparison of our approach and the two concurrent techniques MGT and ADS, we opted for the Travelling Salesman Problem (TSP) where its importance comes from the richness of its application and the fact that it is a typical of other problems of combinatorial optimization (Diaby and Karwan, 2016; El-Sherbeny, 2010).

The remainder of the paper is organized as follows: in Section 2, we describe our deflected subgradient method with convergence analysis. The computational tests, conducted on the Lagrangian relaxation of TSP of different sizes are described in Section 3. In Section 4 we conclude the paper.

2 A new modified deflected subgradient method

In this section, we present a new modified deflected subgradient method $(\mathit{NMDS})$ which determines the direction search as follows:

We then obtain the following deflection parameter:

Consider the deflected subgradient method algorithm given in Algorithm 2. The following proposition extends important properties of the subgradient vector $s^k$ and the deflected subgradient direction $d_{\mathit{MGT}}^k$ to the new deflected subgradient direction $d^k$ (11). With a best choice of the parameter $t_k\text{,}{d}^k$ make an acute angle with ${\lambda }^{\ast }-{\lambda }^k$ and $d^{k-1}$ . We also get the decreasing of the subsequence ${(\parallel {\lambda }^{\ast }-{\lambda }^k\parallel )}_k$ .

Close

Fig. 1

Illustration in a two-dimensional case.

Export to PPT

The importance of Proposition 1 lies on the fact that choosing the deflection parameter ${\mathrm{\Psi }}_k$ using the rule (12) with $0<{\eta }_k⩽2$ forces the current deflected subgradient direction to form always an acute angle with the previous step direction and hence, this method eliminates the zigzagging of the pure subgradient procedure. Note that the choice of the vector of deflected direction $d_{\mathit{MGT}}^k$ is always at least as good as the direction of the subgradient vector $s^k$ . If $1⩽{\eta }_k⩽2$ , then $d_{\mathit{MGT}}^k{d}_{\mathit{MGT}}^{k-1}⩾0$ (Camerini et al., 1975).

The theorem below shows that with a particular choice of the convex combination parameter ${\alpha }_k$ and the parameter ${\eta }_k$ , the deflected subgradient vector direction $d^k$ is always at least as good as the direction $d_{\mathit{MGT}}^k$ in a sense that $d^k$ can form a more acute angle with the best direction towards an optimal solution than $d_{\mathit{MGT}}^k$ does (see Fig. 2), which enhances the speed of convergence. The two lemmas below are necessary for the proof of our principal result.

Close

Fig. 2

Case where $s^k$ is deflected since it has formed an obtuse angle with $d^{k-1}$ and the direction $d_{\mathit{NMDS}}^k$ is better as compared to other directions $d_{\mathit{ADS}}^k$ and $d_{\mathit{MGT}}^k$ .

Export to PPT

3 Computational results

The proposed algorithm has been applied to one of the standard integer linear programming problems in the field of operational research, namely the symmetric travelling salesman problem (TSPs). The travelling salesman problem is a classical NP-Hard combinatorial optimization problem (Garey and Johnson, 1990). It can be formulated as follows: giving a set of cities, and distances between them, the goal is to find the shortest tour visiting every city only once and returning to the starting city. More details on this problem may be found in Lawler et al., 1985. The TSPs can be stated as follows (where $c_{\mathit{ij}}$ is the cost of link $(i\text{,}j)$ ):

From this, one obtains the following dual function, which has to be maximized:

Given a vector $\bar{\lambda }$ , if $\bar{x}$ optimizes $w\left(\bar{\lambda }\right)$ , then a vector $\bar{s}$ whose $i\text{th}$ component

To validate the feasibility and effectiveness of the proposed approach, we have applied it on some TSPs instances taken from TSPLIB.¹ The proposed algorithm, MGT and ADS were implemented in Matlab and executed on an Intel(R) Core(TM) i517U CPU @ 1.70 GHz 1.70 GHz RAM 4.00GO.

For all symmetric instances and for a fair comparison between the three algorithms, the following parameter settings were chosen:

• The same initial multiplier ${\lambda }^1={(0\text{,}0\text{,}\dots \text{,}0)}^T$ was used for the three algorithms.

• The stop conditions are the maximum number of iteration $\mathit{iterMAX}=1000$ , or $\mid w^{\ast }-w({\lambda }^k)\mid ⩽\epsilon$ , where $\epsilon$ is a small tolerance $(\epsilon ={10}^{-2})$ .

• The step size $t_k$ is defined according to formula (4).

• The parameter ${\delta }_k$ follows the Held et al. (1974) suggestion, that makes $0<{\delta }_k⩽2$ , beginning with ${\delta }_k=2$ . If after 20iterations $w({\lambda }^k)$ not increases, ${\delta }_k$ is updated to ${\delta }_k=\frac{{\delta }_k}{2}$ .

• For MGT algorithm, as mentioned in Camerini et al. (1975), the use of ${\eta }_k=1.5$ is recommended and its intuitive justification together with computational results are also given, which indicates that in practise, the performance of MGT strategy is superior to that of the pure subgradient algorithm.

• For our algorithm the value of ${\eta }_k$ depends on the optimal convex combination parameter ${\alpha }_k$ as indicated in Lemma 1, where ${\alpha }_k=-\cos (s^k\text{,}{d}^{k-1})$ if $s^k{d}^{k-1}<0$ . We used ${\eta }_k=\frac{1}{2-{\alpha }_k}-\epsilon$ , where $\epsilon$ is an arbitrary small value.

Table 1 shows the experimental results obtained by: MGT strategy, ADS strategy and by applying our NMDS algorithm proposed in this paper with 11 symmetric benchmark instances between n = 6 and n = 101 vertices taken from TSPLIB. For the three strategies, the duality GAP for these 11 examples is null. However, always NMDS algorithm outperforms the others in number of iterations and execution time. Table 2 gives the computational results for 19 symmetric benchmark instances between 131 and 3056 vertices. This table also shows that our algorithm gives near optimal results for several instances. The column headers are as follows:

• Name: Indicate the instance name.

• n: Indicate the problem size.

• $w^{\ast }$ : The best known optimal solution.

• LB: The best value (lower bound) obtained by each strategy.

• Iter: Number of iterations at which the best value LBis obtained (limited to 1000).

• $\mathit{GAP}=\frac{w^{\ast }-\mathit{LB}}{w^{\ast }}$ .

• CPU: Total computer time, in second for calculating the best value LBobtained by each strategy.

4 Conclusion

By identifying the optimal convex combination parameter, a new deflected direction is given as convex combination of the deflected direction of MGT and ADS. This direction, at each iteration reduces the zigzagging phenomenon and hence getting closer and faster to the optimal solution. The analysis studies are consistent with the numerical experiments. Moreover, this method can be used to improve convergence in the area of deflected subgradient method using augmented Lagrangian duality (Burachik and Kaya, 2010) and dual subgradient methods (Gustavsson et al., 2015). One can also follow Lim and Sherali (2006) and combine this method with a variable target technique in order to have a good performance. Finally, the subgradient method is usually used as subroutine in exact, heuristic and metaheuristic optimization, which justifies the large spectrum of applications of our approach.