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

Ziyou Gao, Hing Keung William Lam, S. C. Wong, H. Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalApplied Mathematics and Computation
Volume148
Issue number1
DOIs
Publication statusPublished - 20 Jan 2004

Keywords

  • Convex combination algorithm
  • Equilibrium assignment
  • Global convergence
  • Non-monotone line search

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this