A TRUST REGION ALGORITHM VIA BILEVEL LINEAR PROGRAMMING FOR SOLVING THE GENERAL MULTICOMMODITY MINIMAL COST FLOW PROBLEMS

摘要

This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems. Using the duality theory of the linear programming and convex theory, the generalized directional derivative of the general multicommodity minimal cost flow problems is derived. The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.