Quasi-Newton methods: L-BFGS

BFGS In this previous post, we described how Quasi-Newton methods can be used to minimize a twice-differentiable function whose domain is all of . BFGS is a popular quasi-Newton method. At each iteration, we take the following steps: Solve for in . Update with . Update according to the equation where and . Limited memory […]

Quasi-Newton methods: L-BFGS

Affine hull vs. convex hull

The affine hull and convex hull are closely related concepts. Let be a set in . The affine hull of is the set of all affine combinations of elements of : The convex hull of is the set of all convex combinations of the elements of : Putting the definitions side by side, we see […]

Affine hull vs. convex hull

What are the KKT conditions?

Consider an optimization problem in standard form: with the variable . Assume that the ‘s and ‘s are differentiable. (At this point, we are not assuming anything about their convexity.) As before, define the Lagrangian as the function Let and be the primal and dual optimal points respectively (i.e. points where the primal and dual […]

What are the KKT conditions?

Lagrange dual, weak duality and strong duality

Consider an optimization problem in standard form: with the variable . Let be the domain for , i.e. the intersection of the domains of the ‘s and the ‘s. Let denote the optimal value of the problem. The Lagrange dual function is the function defined as the minimum value of the Lagrangian over : The […]

Lagrange dual, weak duality and strong duality