Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary

Gabriel Haeser, Hongcheng Liu, Yinyu YeMath. Program 2019 · DOI

TL;DR

This paper introduces new, stronger optimality conditions for a class of optimization problems where the objective function might not be smooth, especially near the boundaries of the feasible region. The authors then develop novel algorithms that efficiently find solutions satisfying these conditions, achieving state-of-the-art complexity bounds for a broader range of problems.

What Problem Does This Paper Address?

Many real-world optimization problems involve minimizing a function subject to constraints. A common challenge arises when the objective function is not "nice" – it might not be differentiable everywhere, particularly at the boundaries of the allowed solution space. This lack of differentiability makes it difficult to define and find optimal solutions using standard mathematical tools like the Karush-Kuhn-Tucker (KKT) conditions. Existing methods often rely on concepts like subdifferentials, which can lead to weaker optimality conditions, or they are tailored to very specific problem structures. This paper tackles the problem of finding robust optimality conditions and efficient algorithms for linearly-constrained optimization problems where the objective function can be non-differentiable on the boundary of the feasible region.

Methods

The core of the paper lies in two main contributions:

  • Novel Optimality Conditions: The authors propose new first- and second-order optimality conditions that are derived without relying on subdifferentials. A key feature is that these conditions reduce to the standard KKT conditions when the function is differentiable. This makes them stronger than existing conditions for non-differentiable problems, especially when only non-negativity constraints are present. They also introduce "perturbed" versions of these conditions, which are crucial for analyzing the performance of algorithms.
  • Interior Trust-Region Point (ITRP) Algorithms: To find solutions satisfying these new conditions, the authors develop two interior trust-region point algorithms. These algorithms are designed to work in the challenging setting of non-differentiable functions and are theoretically guaranteed to find approximate solutions (ɛ-perturbed stationary points) within optimal complexity bounds. The algorithms leverage an interior point technique and can be run in either a first-order or a second-order mode, with the second-order mode offering faster convergence rates.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm development for a general class of optimization problems, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Stronger Conditions Without Subdifferentials: The ability to define stronger optimality conditions without resorting to subdifferentials is a significant theoretical advancement. This simplifies the analysis and potentially leads to more reliable solution characterization.
  • Bridging Theory and Practice with Perturbed Conditions: The introduction of "perturbed" optimality conditions is key to connecting theoretical optimality with the practical limitations of numerical algorithms. These perturbed conditions allow for meaningful complexity analysis.
  • Unified Framework for Non-differentiability: The proposed optimality conditions and algorithms are designed to handle non-differentiability on the boundary, a common issue in many applications, making them applicable to a wider range of problems than previous methods.
  • Optimal Complexity for a Broader Class: The algorithms achieve the best-known complexity bounds for finding approximate stationary points, even for problems with weaker regularity assumptions on the objective function. This suggests that these bounds might be more universally achievable than previously thought.

Key Results

The paper presents theoretical results on optimality conditions and algorithmic complexity:

  • New Optimality Conditions: The paper defines new first- and second-order optimality conditions that are shown to be stronger than existing ones for non-differentiable problems and reduce to KKT conditions for smooth problems.
  • Algorithm Complexity:
    • The first-order ITRP algorithm achieves an iteration complexity of $O(\varepsilon^{-2})$ for finding an $\varepsilon$-perturbed first-order stationary point.
  • The second-order ITRP algorithm achieves iteration complexities of $O(\varepsilon^{-3/2})$ for first-order stationarity and $O(\varepsilon^{-3})$ for second-order stationarity.
  • Special Case (Quadratic Objective): For quadratic objective functions, the second-order ITRP achieves a significantly faster complexity of $O(\varepsilon^{-1})$ for both first- and second-order stationary points.

Limitations and Future Work

  • Linear Constraints: The algorithms and complexity analysis are primarily presented for linearly constrained problems. The authors suggest that generalization to non-linear constraints is a promising future direction.
  • Feasible Initialization: While the algorithms are designed for feasible initialization, exploring their behavior with infeasible starting points is also mentioned as a potential area for future research.
  • Higher-Order Stationary Points: The authors believe their approach could be extended to find higher-order stationary points, building upon existing work.
  • Quadratic Case: While the quadratic case shows remarkable efficiency, further insights into why this specific structure allows for such speedups could be explored.

Summary updated

BibTeX
@article{haeser2019optimality,
  author = {Gabriel Haeser and Hongcheng Liu and Yinyu Ye},
  title = {{Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary}},
  journal = {Math. Program},
  year = {2019},
  doi = {10.1007/s10107-018-1290-4},
}
Figure