A modified augmented Lagrangian method for a class of monotone variational inequalities

Bingsheng He, Hai Yang, Chen-Song ZhangEur. J. Oper. Res 2004 · DOI

TL;DR

This paper introduces a novel "modified augmented Lagrangian method" for solving a specific type of mathematical problem called monotone variational inequalities. The key innovation is a computational approach that significantly reduces the workload in each iteration, making it more efficient for large-scale problems compared to existing methods.

What Problem Does This Paper Address?

The paper tackles the challenge of solving a class of monotone variational inequalities (VIs), which are fundamental to many optimization and equilibrium problems in fields like economics, engineering, and operations research. A common approach for these problems is the augmented Lagrangian method, but it often requires solving computationally expensive sub-problems in each iteration. This becomes a bottleneck for large-scale problems where the number of variables is very high. The authors aim to develop a method that retains the benefits of augmented Lagrangians but drastically reduces the computational burden per iteration.

Methods

The core of the paper is a "modified augmented Lagrangian method." The standard augmented Lagrangian method involves solving a sub-variational inequality in each step. The proposed modification simplifies this by replacing a complex term in the sub-problem with a readily available value from the previous iteration. This leads to a simpler update rule for the variables.

Specifically, the method iteratively updates a pair of variables $(x, y)$. In each step, it first computes an "auxiliary" point $(\tilde{x}, \tilde{y})$ using projection operators and the current function values. Then, it updates the main iterate $(x, y)$ using another projection and the function evaluated at the auxiliary point. This "prediction-correction" structure, with simplified sub-problems, is the main algorithmic contribution. The paper also provides a detailed convergence analysis for this new method, establishing conditions under which it is guaranteed to find a solution.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical testing using established examples from the literature.

Key Insights and Ideas

  • Computational Efficiency: The primary insight is that by modifying the sub-problem structure, the computational cost per iteration can be significantly reduced, making the method practical for large-scale problems where traditional augmented Lagrangian methods struggle.
  • Simplicity of Updates: The modified method replaces a complex projection onto a solution set with simpler projection operations, making the implementation and computation more straightforward.
  • Prediction-Correction Framework: The algorithm adopts a prediction-correction approach, where an intermediate point is computed (prediction) and then used to refine the current iterate (correction). This is a common and effective strategy in optimization.
  • Adaptive Parameter Tuning: The paper highlights the importance of parameter tuning (specifically, the penalty parameter $\beta$) and proposes a self-adaptive technique to adjust it automatically, which is crucial for practical performance.

Key Results

The paper presents a theoretical framework and numerical results demonstrating the effectiveness of the proposed method.

  • Convergence: The authors prove that the proposed modified augmented Lagrangian method converges to a solution for monotone variational inequalities under standard assumptions.
  • Numerical Examples: The method was tested on several benchmark problems, including convex nonlinear programming and traffic network equilibrium problems.
  • For the tested examples (5.1-5.7), the method achieved high accuracy (e.g., $||x^k - x^*||_\infty < 10^{-8}$) with a "medium" number of iterations.
  • In comparisons with other methods (like the extra-gradient method for nonlinear complementarity problems), the proposed method showed competitive or superior performance in terms of computational cost (CPU time). For instance, it required less than 50% of the computational cost of the extra gradient method for certain problems.
  • The traffic network equilibrium problem, a complex real-world application, was solved efficiently, demonstrating the method's practical applicability.

Limitations and Future Work

  • Parameter Sensitivity: While the paper proposes a self-adaptive technique for the penalty parameter $\beta$, the choice of other parameters (like the relaxation factor $\gamma$) can still influence convergence speed. The paper notes that finding optimal parameters can be problem-dependent.
  • Generalization: The current work focuses on monotone variational inequalities. Extending the method to more general classes of VIs (e.g., pseudomonotone) could be a future research direction.
  • Further Parameter Rules: The authors suggest that developing more general adjusting rules for variable parameters, based on the quantitative convergence analysis, is an ongoing research topic. This could lead to even more robust and efficient implementations.

Summary updated

BibTeX
@article{he2004modified,
  author = {Bingsheng He and Hai Yang and Chen-Song Zhang},
  title = {{A modified augmented Lagrangian method for a class of monotone variational inequalities}},
  journal = {Eur. J. Oper. Res.},
  year = {2004},
  doi = {10.1016/s0377-2217(03)00385-0},
}
Figure