LiveBook :: Optimization Models and Applications

Optimization Models and Applications

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.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.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.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

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

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