On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

Key Points

• The paper investigates the challenges in determining locally optimal solutions within bilevel linear optimization frameworks.
• Analyzes existing algorithms for bilevel optimization problems
• Explores theoretical limitations of current approaches
• Compares complexities of different solution strategies
• Identifies specific scenarios where finding local optima is computationally difficult
• Establishes lower bounds for the complexity of local solution algorithms
• Suggests conditions under which optimization becomes tractable