Abstract
In this paper, we consider a class of optimization problems with a strongly convex objective function and the feasible set given by an intersection of a simple convex set with a set given by a number of linear equality and inequality constraints. Quite a number of optimization problems in applications can be stated in this form, examples being entropy-linear programming, ridge regression, elastic net, regularized optimal transport, etc. We extend the Fast Gradient Method applied to the dual problem in order to make it primal-dual, so that it allows not only to solve the dual problem, but also to construct nearly optimal and nearly feasible solution of the primal problem. We also prove a theorem about the convergence rate for the proposed algorithm in terms of the objective function residual and the linear constraints infeasibility.
Introduction
Many fundamental problems in machine learning, economics, and physics—such as ridge regression, elastic net, and optimal transport—are formulated as constrained optimization problems. Specifically, these problems often involve minimizing a strongly convex cost function $f(x)$ subject to linear constraints of the form $Ax = b$ or $Ax \leq b$. For large-scale applications, researchers frequently turn to the Lagrange dual problem, which can be easier to solve than the primal. However, a significant gap remains: finding an optimal dual solution does not automatically yield a primal solution that is both optimal and feasible.
This paper introduces a robust extension of Nesterov’s Fast Gradient Method (FGM) to a primal-dual setting. This framework allows for the simultaneous resolution of the dual problem and the construction of a nearly optimal, nearly feasible primal solution, even when the dual feasible set is unbounded.
Addressing the Challenges of Dual Methods
Traditional first-order methods for dual problems face two primary hurdles:
- Unboundedness: Standard FGM implementations typically assume the search space is bounded. In dual formulations, Lagrange multipliers can often tend toward infinity, which invalidates the theoretical convergence guarantees of conventional algorithms.
- Primal Recovery: Translating dual iterates back into a primal solution that satisfies original constraints (feasibility) is computationally non-trivial and often lacks rigorous convergence bounds.
To overcome these, the proposed method utilizes a Dual-to-Primal Mapping. Instead of merely updating dual variables, the algorithm maintains a running weighted average of primal iterates. This averaged point, $\hat{x}_k$, is mathematically shown to converge toward the true primal solution. Furthermore, the authors prove that as long as an optimal dual solution exists, the algorithm will converge at a specific rate regardless of the unboundedness of the feasible set.
The Fast Primal-Dual Gradient Method
The proposed algorithm leverages the $\nu$-strong convexity of the objective function. Strong convexity implies a lower bound on the function's curvature, which allows for accelerated convergence compared to general convex functions.
Key features of the method include:
- Weighted Averaging: The primal solution is reconstructed by averaging the solutions to the subproblems encountered during each dual step. This process effectively "smooths" the trajectory toward the feasible region.
- Online Stopping Criterion: The algorithm is equipped with a practical stopping rule. Iterations continue until both the primal objective error and the constraint violations (infeasibility) fall below a user-defined threshold $\epsilon$. This is crucial because the theoretical number of iterations required often depends on the unknown norm of the optimal dual variables.
Numerical Experiments: Regularized Optimal Transport
The effectiveness of the method was evaluated using Regularized Optimal Transport (ROT) problems. ROT is a classic problem of finding the most efficient way to move mass between two distributions given a cost matrix.
Experimental Setup
Experiments were conducted on synthetic 2D image data with grids ranging from $16 \times 16$ to $81 \times 81$ pixels. The cost matrix was defined by the squared Euclidean distance between grid points. The objective included a regularization term $\gamma$ to ensure strong convexity.
Performance and Scalability
The proposed FGM was compared against the Conjugate Gradient Method (CGM) and the Balancing Method (BAL). The results demonstrated several key advantages:
- Stability at Low Regularization: Many algorithms, including the Sinkhorn-based Balancing Method, become unstable as the regularization parameter $\gamma$ approaches zero. The Fast Primal-Dual method remained stable and efficient in these high-precision regimes.
- Complexity: The method’s complexity depends nearly linearly on $1/\gamma$, making it highly competitive for large-scale problems.
- Convergence Rate: The authors proved that both the objective function error and the constraint violations decrease at a rate of $O(1/k^2)$, where $k$ is the number of iterations. This represents the "gold standard" for first-order optimization methods.
Conclusion and Future Work
The Fast Primal-Dual Gradient Method provides a theoretically grounded and practically efficient framework for solving strongly convex problems with linear constraints. By eliminating the requirement for a bounded dual set and providing a clear mechanism for primal recovery, it addresses the primary limitations of previous dual-based approaches.
While the current framework requires strong convexity, future research may extend this to purely convex or non-smooth problems by incorporating proximal terms. Additionally, the framework's success in handling millions of dimensions suggests its broad applicability to modern large-scale data science and high-dimensional physics simulations.
Summary updated