Optimization by Vector Space Methods

Guest Lecturer: Bahman Gharesifard

In this set of lectures, we study the dual optimization problem in the sense of Fenchel (Werner Fenchel 1953). The solutions to the dual problem, in general, provide a lower bound on the solutions of the primal problem. One of our goals in these lectures is to prove the Fenchel Duality Theorem in normed vector spaces, which states that under mild assumptions, convexity (concavity) of the functionals in the primal problem ensures, further, that dual and primal problems are indeed equivalent. As we will see in future lectures, the Fenchel's Duality Theorem is closely related to Lagrange Duality Theorem and the two essentially capture the same concept.

For the construction of this theory, nevertheless, we need to study some fundamental mathematical theories, including Mazur-Dieudonne's Separation Theorem (known also as the geometric Hahn-Banach theorem). We will prove this theorem after studying, in details, the properties of hyperplanes in normed vector spaces and the Minkowski functionals . After introducing this geometric machinery, we cast convex functional in terms of some geometric objects called epigraphs . We carefully then study the appropriate continuity properties that allows for these geometric objects to have nonempty interior, or being closed. This paves the way for invoking the Mazur-Dieudonne's Separation Theorem. Our final step, will be studying conjugate functionals and their convexity and concavity properties. These objects are the building block of the Fenchel Duality Theorem and are closely related to separating hyperplanes. As a historical background, we relate our discussion with Legendre Transformation in finite-dimensional spaces and motivate the conjugation using some examples, including the duality between Lagrangian and Hamiltonian mechanics. After proving the Fenchel Duality Theorem, time allowing, we give an alternative proof of the celebrated Min-Max Theorem, as an application of the results.