Saddle point formulation of linear programs (LPs)
Consider the linear program of the form
where , , and . The Lagrangian for this problem is
where the domain of is (elements of must be non-negative).
In this previous post, we introduced the saddle point theorem for convex optimization. Here is that same saddle point theorem, but for LPs:
Theorem. If is a saddle point for the Lagrangian , then solves the primal problem. Conversely, if is a finite solution to the primal problem, then there is a such that is a saddle point for .
Finding the saddle point of an LP Lagrangian can be written as either of the two (equivalent) formulations:
Primal-Dual Hybrid Gradient (PDHG) method
The saddle point formulation of the LP allows us to use primal-dual methods to solve the problem. One such method is called the Primal-Dual Hybrid Gradient (PDHG) method introduced by Chambolle & Pock (2011) (Reference 1). PDHG solves the more general problem
where are finite-dimensional real vector spaces, is a continuous linear operator with induced norm , and are proper, convex, lower-semicontinuous functions.
The PDHG algorithm simply loops over the following 3 steps until convergence:
- (Dual step) .
- (Primal step) .
- (Over-relaxation) .
In the above, and are hyperparameters to be chosen by the user. (Note: Reference 1 doesn’t have proximal operators but has resolvent operators instead. See this post for why we can rewrite the algorithm with prox operators.) It is also possible to switch the order of the dual and primal steps, which gives rise to the following 2 steps until convergence (see Reference 2):
PDHG for LPs
Recall the LP problem is equivalent to
To map this problem onto the PDHG problem, we need , , , , . With this, the PDHG algorithm becomes
Note that for such that , we have . (See this post for the proof.) Hence, we can replace the prox operators above with Euclidean projection operators:
- Chambolle, A., and Pock, T. (2011). A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging.
- Pock, T., and Chambolle, A. (2011). Diagonal preconditioning for first order primal-dual algorithms in convex optimization.