primaldual

Primal-dual refers to a framework in optimization that treats the primal problem and its dual problem jointly. The primal problem minimizes an objective function subject to constraints, while the dual problem maximizes a function derived from the Lagrangian. Under convexity and regularity conditions, strong duality holds and the optimal primal and dual values coincide. The KKT conditions provide necessary and, under suitable conditions, sufficient conditions for optimality, linking primal and dual solutions through stationarity, primal feasibility, dual feasibility, and complementary slackness.

In algorithms, primal-dual methods maintain both primal variables and dual multipliers and update them iteratively to improve feasibility and optimality. They are well suited to problems that decompose into simpler subproblems via proximal operators or splitting. Examples include primal-dual interior-point methods, which traverse a path in the combined space; augmented Lagrangian and proximal methods that introduce penalties to enforce constraints; and primal-dual splitting methods such as the Chambolle-Pock algorithm (PDHG). ADMM, while primarily an alternating scheme, can be interpreted as a practical primal-dual method.

Applications are broad, ranging from linear and convex programming to image reconstruction, compressed sensing, machine learning, and control. Primal-dual approaches are valued for exploiting problem structure, enabling scalable solutions to large-scale, constrained problems. The field emphasizes convergence guarantees, duality gap as a stopping criterion, and the use of proximal operators to handle non-smooth terms.