Category Archives: Optimization tricks

Lagrange duality via the Fenchel conjugate. The dual of ERM

Posted on October 28, 2015 by

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

Posted on October 24, 2014 by

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

Posted on April 22, 2014 by

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