A line-search method for Lagrangian relaxation ascent algorithms

Zhao Gong Yun and Zhuangwei Liu

The Lagrangian relaxation strategy (or dualization) is one of the most important methodologies of optimization for solving structured large-scale mathematical programming problems. The line search procedure is often encountered in solving the dual problem by using some ascent method, such as bundle methods, interior point method, etc.. The existing line search methods, for example, Armijo's method, need to evaluate the dual objective function many times, in which each evaluation of the dual objective is to solve a relaxed subproblem, and therefore are time-consuming. In this short report we will propose an efficient line search method which is applicable to the Lagrangian relaxation ascent algorithms. The advantage of the new method is that the line search is embedded in evaluation of the dual function.

Technical Report No. 644, Department of Mathematics, National University of Singapore, 0511, SINGAPORE

Contact: Zhuangwei Liu ([email protected]), Zhao Gong Yun ([email protected])

[DVI] [IP PAGE] [SEARCH AGAIN]