A walkthrough of the Proportional Integral Projected Gradent (PIPG) algorithm for conic optimization
Proportional Integral Projected Gradient or PIPG is a first-order primal-dual algorithm for conic optimization problems. First-order refers to the fact that PIPG only uses gradient information about the objective function at each iteration as opposed to second-order methods which use both gradient and Hessian information. As a result, PIPG requires more iteration than a second-order method to converge, but each iteration requires much less time. Primal-dual means that PIPG computes iterates of both the primal and dual variables. Conic optimization problems are the most general class of convex optimization problems.
PIPG is also a customizable algorithm which means that although it can solve generic conic optimization problem, extra performance can be gained by tailoring the implementation to the specific problem structure at hand. Typically, PIPG has been customized to the structure of optimal control problems. The figure below which is from
INSERT ABHI’S FIGURE HERE
In this section we will constructively build an algorithm to solve inequality and equality constrained optimization problems. I would argue that PIPG might be the most intuitive optimization algorithm for optimization problems.
Firstly we will consider the following optimization problem
Only works if you have closed form projection since projection in general is another convex optimization problem
Insert animation of a pipg iterations for a bivariate problem
Choice of putting constraints into D or K
Insert animation of xpipg iterations for a bivariate problem