The convergence of equilibrium algorithms with non-monotone line search technique

Abstract

The slow-convergence characteristics of the regular convex combination algorithm (such as Frank-Wolfe method) are well known particularly when the optimal solution is being reached. In this paper, a new convex combination algorithm with non-monotone line search technique proposed for solving the equilibrium assignment problem, together with the proof of its global convergence. Moreover, it should be pointed out that the conditions which ensure the global convergence of the algorithm proposed in this paper are much milder than those suggested by Bonnans et al.; Grippo et al.; Panier and Tits; Xu et al. [SIAM J. Number. Anal. 29 (4) (1992) 1187; SIAM J. Number. Anal. 23 (4) (1986) 707; SIAM J. Number. Anal. 28 (4) (1991) 1183; Comput. Optimiz. Appl. 18 (2001) 221]. The new algorithm can be viewed as a generalization of the regular convex combination algorithm. Numerical results indicate that the proposed algorithm would lead to a considerable saving both in the number of line searches and in the number of function evaluations. © 2002 Elsevier Inc. All rights reserved.