Convex analysis for optimization

Preface
	Acknowledgements
Introduction
	References
Contents
1 Convex Sets: Basic Properties
	1.1 *Motivation: Fair Bargains
	1.2 Convex Sets and Cones: Definitions
	1.3 Chapters 1–4 in the Special Case of Subspaces
	1.4 Convex Cones: Visualization by Models
		1.4.1 Ray Model for a Convex Cone
		1.4.2 Sphere Model for a Convex Cone
		1.4.3 Hemisphere Model for a Convex Cone
		1.4.4 Top-View Model for a Convex Cone
	1.5 Convex Sets: Homogenization
		1.5.1 Homogenization: Definition
		1.5.2 Non-uniqueness Homogenization
		1.5.3 Homogenization Method
	1.6 Convex Sets: Visualization by Models
	1.7 Basic Convex Sets
		1.7.1 The Three Golden Convex Cones
		1.7.2 Convex Hull and Conic Hull
		1.7.3 Primal Description of the Convex Hull
	1.8 Convexity Preserving Operations
		1.8.1 Definition of Three Operations
		1.8.2 Preservation of Closedness and Properness
	1.9 Radon\'s Theorem
	1.10 Helly\'s Theorem
	1.11 *Applications of Helly\'s Theorem
	1.12 Carathéodory\'s Theorem
	1.13 Preference Relations and Convex Cones
	1.14 *The Shapley–Folkman Lemma
	1.15 Exercises
	1.16 Hints for Applications of Helly\'s Theorem
	References
2 Convex Sets: Binary Operations
	2.1 *Motivation and Preparation
		2.1.1 *Why Binary Operations for Convex Sets Are Needed
		2.1.2 *Crash Course in Working Coordinate-Free
	2.2 Binary Operations and the Functions +X, X
	2.3 Construction of a Binary Operation
	2.4 Complete List of Binary Operations
	2.5 Exercises
	References
3 Convex Sets: Topological Properties
	3.1 *Crash Course in Topological Notions
	3.2 Recession Cone and Closure
	3.3 Recession Cone and Closure: Proofs
	3.4 Illustrations Using Models
	3.5 The Shape of a Convex Set
	3.6 Topological Properties Convex Set
	3.7 Proofs Topological Properties Convex Set
	3.8 *Applications of Recession Directions
		3.8.1 Certificates for Unboundedness of a Convex Set
		3.8.2 Certificates for Insolubility of an Optimization Problem
	3.9 Exercises
4 Convex Sets: Dual Description
	4.1 *Motivation
		4.1.1 Child Drawing
		4.1.2 How to Control Manufacturing by a Price Mechanism
		4.1.3 Certificates of Insolubility
		4.1.4 The Black-Scholes Option Pricing Model
	4.2 Duality Theorem
	4.3 Other Versions of the Duality Theorem
		4.3.1 The Supporting Hyperplane Theorem
		4.3.2 Separation Theorems
		4.3.3 Theorem of Hahn–Banach
		4.3.4 Involution Property of the Polar Set Operator
		4.3.5 Nontriviality Polar Cone
	4.4 The Coordinate-Free Polar Cone
	4.5 Polar Set and Homogenization
	4.6 Calculus Rules for the Polar Set Operator
	4.7 Duality for Polyhedral Sets
	4.8 Applications
		4.8.1 Theorems of the Alternative
		4.8.2 *The Black-Scholes Option Pricing Model
		4.8.3 *Child Drawing
		4.8.4 *How to Control Manufacturing by a Price Mechanism
	4.9 Exercises
	References
5 Convex Functions: Basic Properties
	5.1 *Motivation
		5.1.1 Description of Convex Sets
		5.1.2 Why Convex Functions that Are Not Nice Can Arise in Applications
	5.2 Convex Function: Definition
	5.3 Convex Function: Smoothness
	5.4 Convex Function: Homogenization
	5.5 Image and Inverse Image of a Convex Function
	5.6 Binary Operations for Convex Functions
	5.7 Recession Cone of a Convex Function
	5.8 *Applications
		5.8.1 Description of Convex Sets by Convex Functions
		5.8.2 Application of Convex Functions that Are Not Specified
	5.9 Exercises
6 Convex Functions: Dual Description
	6.1 *Motivation
	6.2 Conjugate Function
	6.3 Conjugate Function and Homogenization
	6.4 Duality Theorem
	6.5 Calculus for the Conjugate Function
	6.6 Duality: Convex Sets and Sublinear Functions
	6.7 Subgradients and Subdifferential
	6.8 Norms as Convex Objects
	6.9 *Illustration of the Power of the Conjugate Function
	6.10 Exercises
7 Convex Problems: The Main Questions
	7.1 Convex Optimization Problem
	7.2 Existence and Uniqueness of Optimal Solutions
		7.2.1 Existence
		7.2.2 Uniqueness
		7.2.3 Illustration of Existence and Uniqueness
	7.3 Smooth Optimization Problem
	7.4 Fermat\'s Theorem (Smooth Case)
	7.5 Convex Optimization: No Need for Local Minima
	7.6 Fermat\'s Theorem (Convex Case)
	7.7 Perturbation of a Problem
	7.8 Lagrange Multipliers (Smooth Case)
	7.9 Lagrange Multipliers (Convex Case)
	7.10 *Generalized Optimal Solutions Always Exist
	7.11 Advantages of Convex Optimization
	7.12 Exercises
8 Optimality Conditions: Reformulations
	8.1 Duality Theory
	8.2 Karush–Kuhn–Tucker Theorem: Traditional Version
	8.3 KKT in Subdifferential Form
	8.4 Minimax and Saddle Points
	8.5 Fenchel Duality Theory
	8.6 Exercises
	Reference
9 Application to Convex Problems
	9.1 Least Squares
	9.2 Generalized Facility Location Problem
	9.3 Most Likely Matrix with Given Row and Column Sums
	9.4 Minimax Theorem: Penalty Kick
	9.5 Ladies Diary Problem
	9.6 The Second Welfare Theorem
	9.7 *Minkowski\'s Theorem on Polytopes
	9.8 Duality Theory for LP
	9.9 Solving LP Problems by Taking a Limit
	9.10 Exercises
Appendix A
	A.1 Symbols
		A.1.1 Set Theory
		A.1.2 Some Specific Sets
		A.1.3 Linear Algebra
		A.1.4 Analysis
		A.1.5 Topology
		A.1.6 Convex Sets
		A.1.7 Convex Sets: Conification
		A.1.8 Convex Functions
		A.1.9 Convex Functions: Conification
		A.1.10 Optimization
Appendix B
	B.1 Calculus Formulas
		B.1.1 Convex Sets Containing the Origin
		B.1.2 Nonempty Convex Cones
		B.1.3 Subspaces
		B.1.4 Convex Functions
		B.1.5 Proper Sublinear Functions p,q and Nonempty Convex Sets A
		B.1.6 Subdifferentials of Convex Functions
		B.1.7 Norms
Index