Home
Software
Links
Index
Contact
Acknowledgements
1. Introduction
1.1 Overview
1.1.1 About this livebook
1.1.2 Outline
1.2 Optimization Models
1.2.1 Gauss’ bet
1.2.2 Functions and maps
1.2.3 Standard forms
1.2.4 Nomenclature
1.2.5 Hard vs. easy problems
1.2.6 Problem classes
1.2.7 Historical background
12.8 Exercises
2. Linear Algebra
2.1 Vectors
2.1.1 Basics
2.1.2 Scalar product, norms and angles
2.1.3 Projection on a line
2.1.4 Orthogonalization
2.1.5 Hyperplanes and half-spaces
2.1.6 Linear functions
2.1.7 Application in data visualization
2.1.8 Exercises
2.2 Matrices
2.2.1 Basics
2.2.2 Matrix products
2.2.3 Special classes of matrices
2.2.4 QR decomposition
2.2.5 Matrix inverses
2.2.6 Linear maps
2.2.7 Matrix norms
2.2.8 Applications
2.2.9 Exercises
2.3 Linear Equations
2.3.1 Motivating example
2.3.2 Existence and unicity
2.3.3 Solving linear equations
2.3.4 Applications
Temperature distribution
Trilateration
Estimation of traffic flows
2.3.5 Exercises
2.4 Least-Squares
2.4.1 Ordinary least-squares
2.4.2 Variants
2.4.3 Kernels for least-squares
2.4.4 Applications
Linear regression
Times series prediction
2.4.5 Exercises
2.5 Eigenvalues
2.5.1 Quadratic functions and symmetric matrices
2.5.2 Spectral theorem
2.5.3 Positive semi-definite matrices
2.5.4 Principal component analysis
2.5.5 Applications
2.5.6 Exercises
2.6 Singular Values
2.6.1 The SVD theorem
2.6.2 Matrix properties via SVD
2.6.3 Solving linear systems via SVD
2.6.4 Least-squares and SVD
2.6.5 Low-rank approximations
2.6.6 Applications
2.6.7 Exercises
3. Convex Models
3.1 Convex Optimization
3.1.1 Convex sets
3.1.2 Convex functions
3.1.3 Convex problems
3.1.4 Algorithms
3.1.5 Disciplined convex programming
3.3.6 Exercises
3.2 LP and QP
3.2.1 Polyhedra
3.2.2 Standard forms
3.2.3 Minimizing polyhedral functions
3.2.4 Cardinality minimization
3.2.5 Applications
Linear binary classification
3.2.6 Exercises
3.3 SOCP
3.3.1. The second-order cone
3.3.2 Standard forms
3.3.3 Group sparsity
3.3.4 Applications
Minimum surface area
Image restoration
Antenna array design
Image annotation
3.3.5 Exercises
3.4 Robust LP
3.4.1 Tractable cases
3.4.2 Chance programming
3.4.3 Affine recourse
3.4.4 Applications
Robust inventory control
Robust antenna array design
Robust supervised learning
Affine recourse in cash-flow management
3.4.5 Exercises
3.5 GP
3.5.1 Posynomials
3.5.2 Standard forms
3.5.3 Applications
3.5.4 Exercises
3.6 SDP
3.6.1 From LP to conic problems
3.6.2 Linear Matrix Inequalities
3.6.3 Standard forms
3.6.4 Applications
3.6.5 Exercises
3.7 Non-Convex Models
3.7.1 Overview
3.7.2 Coordinate descent
3.7.3 Linearization
3.7.4 Approximation via convexity
3.7.5 Discrete optimization
3.7.6 Applications
3.7.7 Exercises
4. Duality
4.1 Weak Duality
4.1.1 Dual Problem
4.1.2 Geometric interpretation
4.1.3 Minimax inequality
4.2 Strong Duality
4.2.1 Slater condition
4.2.2 Minimax theorem
4.2.2 Optimality
4.2.3 Sensitivity
4.3.4 Applications
4.3.5 Exercises
5. Case Studies
5.1 Senate Voting
5.1.1 Senate voting data
5.1.2 Projections
5.1.3 PCA
5.1.4 Sparse PCA
5.2 Antenna Arrays
5.2.1 Physics of antenna arrays
5.2.2 Diagram shaping
5.2.3 Least-Squares design
5.2.4 SOCP design
5.3 Digital Circuit Design
5.3.1 The problem
5.3.2 GP model
5.3.3 Example
5.3.4 Notes and references
5.4 Localization
5.4.1 The problem
5.4.2 Consistency
5.4.3 Inner approximations
5.4.4 Outer approximations
5.5 Cash-Flow Management
5.5.1 The problem
5.5.2 LP formulation
5.5.3 Robustness
5.5.4 Affine recourse
Appendix
Examples
Temperatures at different airports
Bag-of-words representation of text
Document similarity
A basis in R3
Dimension of an affine subspace
Beer-Lambert law in absorption spectrometry
Absorption spectrometry: using measurements
QR decomposition: example
Two orthogonal vectors
An hyperplane in 3D
Power law model fitting
Gradient of a linear function
Linearization of a non-linear function
Network flow
Image Compression
A 2x2 orthogonal matrix
Incidence matrix of a network
Navigation by range measurement
Singular value decomposition of a 4x5 matrix
SVD: a 4x4 example
A two-dimensional toy optimization problem
A toy 2D optimization problem: geometry
Nomenclature of a toy 2D optimization problem
Eigenvalue decomposition of a 2x2 symmetric matrix
Quadratic functions in two variables
Range of a 4x5 matrix via its SVD
Protein folding
Crew allocation in airline operations
Theorems and proofs
Cauchy-Schwartz Inequality
Dimension of hyperplanes
Fundamental Theorem of Algebra
Spectral theorem
SVD theorem
Rayleigh quotients
Optimal set of LS
Positive semi-definite forms and eigenvalues
Slater's strong duality
Definitions
Sample and weighted mean, expected value
Sample variance and standard deviation
Gram matrix
Rate of return of a financial portfolio
Solving triangular systems of equations
Linear and Affine Maps
Vector norms
Rank-one matrices
Dual Norm
Lines
Euclidean projection on a set
Log-Sum-Exp (LSE) function
Power laws
Linear and Affine Maps
Gradient of a function
Hessian of a function
Sample covariance matrix
Projection of a vector on a line
State-space models of linear dynamical systems
Functions and maps
Determinant of a square matrix
Permutation matrices
Global vs local minima
Backwards substitution for solving triangular linear system
Laplacian matrix of a graph
Edge weight matrix of a graph
Sample average of vectors
Homeworks
Homework 1
Homework 2
Group sparsity and the -norm trickSOCP > Second-order cone
Applications of SOCPSOCP > Second-order cone | Standard for
ExercisesSOCP > ExercisesSecond-order conesA. A single seco
Motivations and Standard FormsRobust LP > Motivations and s
ExercisesRobust LP > Exercises
PosynomialsGP > Posynomials | Standard Forms | Applications
Standard Forms of GPGP > Posynomials | Standard Forms | App
Some Applications of GPGP > Posynomials | Standard Forms |
ExercisesGeometric Programming > Exercises
From LP to Conic OptimizationSDP > Conic Problems | LMIs |
Linear Matrix InequalitiesSDP > Conic problems | LMIs | Sta
Standard Forms of SDPSDP > Conic problems | LMIs | Standard
Some Applications of SDPSDP > Conic problems | LMIs | Stand
ExercisesSemi-Definite Programming > ExercisesA. Optimizati
A convex and a non-convex setThe intuitive idea of a convex
Convex and conic hullConvex hull of a finite set of pointsT
Second-order coneDefinition The set in is a convex cone, ca
Semidefinite conePositive semidefinite matricesA symmetric
Projection of a convex set on a subspaceThe projection of a
Log-Determinant Function and PropertiesThe log-determinant
Convexity of quadratic functions in two variablesWe return
Square-to-linear function
Negative Entropy Function and PropertiesThe negative entrop
Schur Complement LemmaLemma: Schur ComplementLet be a symme
Proving convexity via monotonicityConsider the function , w
Local and Global Optima in Convex OptimizationTheorem: Glob
Minimization of a convex quadratic functionHere we consider
Optimality condition for a convex, unconstrained problemCon
Optimality condition for a convex, linearly constrained pro
A half-space in Consider the set in defined by a single aff
Graph, epigraph, level and sub-level sets of a functionCons
Component-wise inequality convention for vectorsIf are two
A polyhedron in Consider the set in defined by a three affi
Probability simplex in The probability simplex in is the po
A Drug Production ProblemProblem descriptionA company produ
Projection on a polyhedronRecall that a polyhedron is an in
A linear program in 2DConsider the optimization problem The
A Quadratic Program with Two VariablesConsider the problem
LP and QP in conic form The LP can always be represented in
LP Formulation of - and -norm RegressionThe -norm regressio
Cardinality of a vectorThe cardinality of a vector is the n
Linear Binary ClassificationLP and QP > Applications > Clas
Piece-wise constant fittingWe observe a noisy time-series (
Network FlowsLP and QP > Applications> Back | Networks | Ne
LP Relaxations of Boolean ProblemsLP and QP > Applications
Mean-Variance Trade-Off in Portfolio OptimizationLP and QP
Filter DesignFinite Impulse Response filtersFilters. A sing
Magnitude constraints on affine complex vectors
SOCPs include LPs as Special CaseThe linear program (LP)can
Facility LocationConsider the problem of locating a warehou
Robust Least-SquaresWe start from the least-squares problem
Separation of EllipsoidsWe consider the following geometric
SOCPs include QPs as Special CaseThe quadratic program (QP)
SOCPs include QCQPs as a Special CaseThe quadratically cons
Minimum Surface AreaSOCP > Applications > Minimum Surface A
Total Variation Image RestorationSOCP > Applications > Back
Sensor Network LocalizationSOCP > Applications > Back | Sen
Uncertainty in the Drug Production ProblemReturn to the dru
Antenna Array DesignSOCP > SOC inequalities | Standard Form
Implementation Errors in an Antenna Array Design ProblemRet
Robust LP Solution to the Drug Production ProblemReturn to
Scalar Product and NormsVectors, Matrices > Vectors | Scala
Strong Duality for QPPrimal ProblemConsider the QP where ,
Strong Duality for LPConsider the LP
Minimum Euclidean distance to a subspace: strong duality
Projection of a vector on a lineA lineThe line in passing t
A simple matrixMatrices > Basics > Example Consider the mat
A two-dimensional toy optimization problemAs a toy example
Senate Voting Data MatrixMatrices > Basics > Example The da
Gram matrixConsider -vectors
Single factor model of financial price dataConsider a data
The QR decomposition of a matrixBasic ideaCase when the mat
Full Rank MatricesTheoremA matrix isfull column rank if and
Rank-nullity theoremRank-nullity theoremThe nullity (dimens
Orthogonal complement of a subspaceLet be a subspace of
Fundamental theorem of linear algebraFundamental theorem of
Image Compression via Least-SquaresWe can use least-squares
Set of solutions to the least-squares problem via QR decomp
Auto-Regressive (AR) models for time-series predictionA pop
Portfolio Optimization via Linearly Constrained Least-Squar
Portfolio Optimization via Linearly Constrained Least-Squar
Absorption spectrometry: using measurements at different li
Largest singular value norm of a matrixFor a matrix , we de
Control of a unit massConsider the problem if transferring
A squared linear functionSymmetric Matrices > Definitions >
Control of a unit massConsider the problem if transferring
Control of a unit massConsider the problem if transferring
A symmetric matrixSymmetric Matrices > Definitions > Exampl
A symmetric matrixSymmetric Matrices > Definitions > Exampl
Hessian of a quadratic functionSymmetric Matrices > Definit
Hessian of a quadratic functionSymmetric Matrices > Definit
Representation of a two-variable quadratic functionSymmetri
Representation of a two-variable quadratic functionSymmetri
Quadratic Approximation of the Log-Sum-Exp FunctionSymmetri
A diagonal matrix and its associated quadratic formSymmetri
Quadratic Approximation of the Log-Sum-Exp FunctionSymmetri
A squared linear functionSymmetric Matrices > Definitions >
Theorem on positive semi-definite forms and eigenvaluesTheo
Laplacian matrix of a graphAnother important symmetric matr
Singular value decomposition (SVD) theoremTheorem: Singular
Nullspace of a matrix via its SVDReturning to this example,
Nullspace of a matrix via its SVDReturning to this example,
Linear Equations: Definition and Main IssuesLinear Equation
Pseudo-inverse of a matrix via its SVDReturning to this exa
Low-rank approximation of a matrix via its SVDReturning to
Pseudo-Inverse of a MatrixThe pseudo-inverse of a matrix is
Optimal set of Least-Squares via SVDTheorem: optimal set of
Applications of SVD: image compressionSVD > Applications >
Applications of SVD: market data analysisSVD > Applications
Solution set of a linear equationTheoremThe solution set of
Solution ConceptsLinear Equations > Definitions | Propertie
PropertiesLinear Equations > Definitions | Properties | Sol
Edge weight matrix of a graphA symmetric matrix is a way to
Incidence matrix of a networkMathematically speaking, a net
DefinitionsLeast-Squares > Definitions | Solution | Sensiti
Rate of return of a financial portfolioThe rate of return (
Linear regressionA popular example of least-squares problem
Digital Circuit Design: Problem GP > Standard Forms |Applic
ApplicationsMatrices > Basics | Matrix products | Linear ma
Vectors and MatricesVectors are collections of numbers arra
DefinitionsLeast-Squares > Definitions | Solution | Sensiti
A simple Example of A PSD MatrixSDP > LMIs > ExampleConside
A simple Example of A PSD MatrixSDP > LMIs > ExampleConside
Noname
Noname (2)
Other Standard FormsUp | BackInequality formAs seen here, a
Other Standard FormsUp | BackInequality formAs seen here, a
Noname (3)
Bounding Portfolio Risk with Incomplete Covariance Informat
Boolean Quadratic ProgrammingSDP > Conic problems | LMIs |
obust Stability of Linear Dynamical SystemsSDP > Conic prob
Noname (4)
Noname (5)
Noname (6)
Noname (7)
Noname (8)
Noname (9)
Noname (10)
Quadratic functions in two variablesTwo examples of quadrat
Noname (11)
Noname (12)
Noname (13)
Noname (14)
Noname (15)
Auto-regressive models for time series predictionA popular
TTomographyTrace of a matrixTriangle inequalityTriangular m
NNorms: general definition, for vectors, for matrices; see
OOptimal point, optimal value, optimal setOrthogonal: vecto
VectorsVectors, Matrices > Vectors | Scalar products | Matr
MatricesVectors, Matrices > Vectors | Scalar products | Mat
Noname (16)
Noname (17)
Noname (18)
Noname (19)
Noname (20)
Noname (21)
Noname (22)
Noname (23)
Noname (24)
Noname (25)
Noname (26)
AAbsorbtion spectrometryAffine functionAffine setAngle betw
B Backward substition method for solving triangular systems
C CAT scan imagingCauchy-Schwartz inequalityCardinality of
DDeterminant of a square matrixDimension of an affine setDo
EEigenvalue decomposition (EVD) of a square, symmetric matr
Spectral Theorem Symmetric Matrices > Definitions | Spectra
Functions and MapsOptimization Models > Gauss’ Bet | Functi
Sample and weighted mean, expected valueThe sample mean (or
FFeasible point, feasible setFirst-order approximationFrobe
GGeometric program (GP)Global optimumGradient of a function
HHalf-spaceHessian of a functionHyperplane
IImage compressionIncidence matrix of a graphIndependent se
KKernel matrix, kernel trick
LLaplacian of a graphLagragian of an optimization problemLa
MMapsMatrixMatrix-vector productSample MeanMinimax inequali
P Permutation matrixPoint-wise maximum of functionsPolyhedr
Noname (27)
Noname (28)
Noname (29)
Costs of a Water TankGP > Posynomials > Example: Water Tank
Signal to Interference plus Noise Ratio (SINR) in Wireless
Why do we take the log in GP?For a posynomial with valueswh
Optimization of a Water TankGP > Posynomials | Standard For
Optimization of a Water Tank: Convex Form of the GPGP > Pos
Mean and Covariance Matrix of a Random VariableIf is a vect
Noname (30)
Noname (31)
Noname (32)
Noname (33)
Noname (34)
Noname (35)
Noname (36)
Cardinality minimization: the -norm trickLP and QP> Half-Sp
Noname (37)
Noname (38)
Sum of largest components in a vectorDefinitionConvexityEff
Noname (39)
Noname (40)
Surface AreaConsider a surface in that is described by a fu
Noname (41)
JJacobian matrix of a non-linear map
QQuadratic program (QP)Quadratic form, quadratic function
RRange of a matrixRank of a matrixRate of return of a finan
S Sample mean, sample standard deviation, sample covariance
UUnconstrained optimizationUnitary matrix (see also Orthogo
V VectorsSample Variance
W
X
Y
Z
OOptimal point, optimal value, optimal setOrthogonal: vecto
Special MatricesMatrices > Basics | Matrix products | Speci
BasicsVectors > Basics | Scalar product, Norms | Projection
Sample variance and standard deviationThe sample variance o
Algorithms for Convex OptimizationConvex Optimization > Con
DefinitionsSymmetric Matrices > Definitions | Spectral theo
Spectral Theorem Symmetric Matrices > Definitions | Spectra
Slater Condition for Strong DualityStrong Duality > Slater
Sample covariance matrixDefinitionFor a vector , the sample
Noname (42)
Noname (43)
Noname (44)
Noname (45)
Noname (46)
Noname (47)
Noname (48)
Noname (49)
Noname (50)
Noname (51)
Linearly Constrained Least-Squares ProblemsLeast-Squares >
Some Limitations of OLSLeast-Squares > Ordinary least-squar
Sensitivity AnalysisLeast-Squares > Ordinary LS | Variants
Regularized Least-Squares ProblemLeast-Squares > Definition
Noname (52)
Noname (53)
This section under development
Noname (54)
Half-SpacesLP and QP > Half-Spaces | Polyhedra | Standard F
Noname (55)
Noname (56)
Noname (57)
Noname (58)
Noname (59)
Noname (60)
Noname (61)
Digital Circuit Optimization via Geometric ProgrammingS
A orthogonal matrixThe matrix is orthogonal.The vector is t
Senate Voting: Scoring SenatorsWe consider the data matrix
Network flowWe describe a flow (of goods, traffic, charge,
Senate Voting Data MatrixThe data consists of the votes of
A simple matrixConsider the matrix The matrix can be interp
Dimension of an affine subspaceThe set in defined by the li
Basis in The set of three vectors in : is not independent,
Representing temperatures at different airports as a vector
Sample variance and standard deviationThe sample variance o
Sample covariance matrixThe average of given real numbers i
Noname (62)
Sample and weighted average, expected valueThe sample avera
Visualization of High-Dimensional DataVectors, Matrices > A
Robust Principal Component AnalysisSDP > Conic problems | L
Sparse Principal Component AnalysisSDP > Conic problems | L
Standard Forms and GeometryUp | NextLinear ProgramsA linear
Visualization of High-Dimensional DataMatrices > Applicatio
Digital Circuit Design via GPGP > Applications > Circuit De
Digital Circuit Design: GP RepresentationGP > Standard Form
Noname (63)
Noname (64)
Noname (65)
Two orthogonal vectorsThe two vectors in : are orthogonal,
Noname (66)
Noname (67)
ExampleSOCP > SOC inequalities | Standard Forms |Applicatio
Physics of Antenna ArraysSOCP > SOC inequalities | Standard
Image Annotation via Group SparsitySOCP > Applications > Ba
Digital Circuit Design: Notes and References GP > Applicati
Digital Circuit Design: ExampleGP > Standard Forms |Applica
Senate Voting: Visualizing Senators on a Plane
Senate Voting: Scoring SenatorsMatrices > Matrix products >
Antenna Array DesignSOCP > Applications > Back | Antenna Ar
Questions