Category Archives: Optimization tricks

Lagrange duality via the Fenchel conjugate. The dual of ERM

A recurring trick in optimization is the characterization of Lagrange dual problem in terms of the much simpler Fenchel duality. This trick is used in dual methods for Machine Learning and Signal Processing, ADMM, Augmented Lagrangian, etc.

Posted in Optimization tricks | 1 Comment

Switching the objective and the constraint

The time has come to publish a post, yet unfinished, with an optimization trick back from the last spring. Suppose we have the following family of convex optimization problems: parametrized by    for fixed    Denote    the value of the problem corresponding … Continue reading

Posted in Convex Optimization, Optimization tricks | Leave a comment

Farkas’ lemma

Farkas’ lemma  is a simple (and very useful) statement in convex analysis. Theorem (Farkas’ lemma) For any matrix    and vector  ,  exactly one of the following holds: (1)     linear system    has a solution    in the first … Continue reading

Posted in Convex Optimization, Memos, Optimization tricks | Leave a comment