Introduction to the Language of Convex Optimization

Elan Frenkel

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2015-249
December 17, 2015

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-249.pdf

These notes were written as part of a Masters Project to help introduce computer science undergraduates to the world of convex optimization. Convex Optimization is a relatively new field that has seen many applications, but the math required to understand it is rarely taught at the undergraduate level.

The notes are aimed at introducing the mathematics required of convex modeling, rather than algorithms. Convexity is a universal phenomenon in tractable problems, but recognizing it is hard. The material is largely synthesized from 3 sources-- I make no claim to the novelty of content:

(1) Professor Boyd and Professor Vandenberghe's Convex Optimization(primary source for my first section on Convex Sets and Functions) (2) Professor El Ghaoui's notes, hyper-textbook, and class for EE 227 A-B (primary source for my second section on Convex Optimization, and in particular the historical anecdotes ) (3) Professor Bartlett lecture notes from CS 289 (primary source for applications in machine learning)

In the first section I cover convex functions and convex sets. I also cover the spectral decomposition theorem and the separating hyperplane theorem. In the second section I cover convex optimization models, with applications in machine learning and Boolean optimization.

Advisor: Satish Rao


BibTeX citation:

@mastersthesis{Frenkel:EECS-2015-249,
    Author = {Frenkel, Elan},
    Title = {Introduction to the Language of Convex Optimization},
    School = {EECS Department, University of California, Berkeley},
    Year = {2015},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-249.html},
    Number = {UCB/EECS-2015-249},
    Abstract = {These notes were written as part of a Masters Project to help introduce computer science undergraduates to the world of convex optimization. Convex Optimization is a relatively new field that has seen many applications, but the math required to understand it is rarely taught at the undergraduate level. 

The notes are aimed at introducing the mathematics required of convex modeling, rather than algorithms. Convexity is a universal phenomenon in tractable problems, but recognizing it is hard. 
The material is largely synthesized from 3 sources-- I make no claim to the novelty of content: 

(1) Professor Boyd and Professor Vandenberghe's Convex Optimization(primary source for my first section on Convex Sets and Functions) 
(2) Professor El Ghaoui's notes, hyper-textbook, and class for EE 227 A-B  (primary source for my second section on Convex Optimization, and in particular the historical anecdotes )
(3) Professor Bartlett lecture notes from CS 289 (primary source for applications in machine learning)

In the first section I cover convex functions and convex sets. I also cover the spectral decomposition theorem and the separating hyperplane theorem. In the second section I cover convex optimization models, with applications in machine learning and Boolean optimization.}
}

EndNote citation:

%0 Thesis
%A Frenkel, Elan
%T Introduction to the Language of Convex Optimization
%I EECS Department, University of California, Berkeley
%D 2015
%8 December 17
%@ UCB/EECS-2015-249
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-249.html
%F Frenkel:EECS-2015-249