Title: Theory / Important / CS / Algo / Convex optimization

Name: An optimization problem
Definition: minimize \(f_0(x)\)
subject to \(f_i(x)\le b_i\), \(i = 1, \dots, m\)
with \(x=(x_1,\dots,x_n)\), \(f_i\mathbb R^n\to\mathbb R\)
Page: 1

Name: The optimization variable
Page: 1
Variables: An optimization problem
minimize \(f_0(x)\)
subject to \(f_i(x)\le b_i\), \(i = 1, \dots, m\)
with \(x=(x_1,\dots,x_n)\), \(f_i\mathbb R^n\to\mathbb R\)
Notation: \(x\)

Name: The objective function
Page: 1
Variables: An optimization problem
minimize \(f_0(x)\)
subject to \(f_i(x)\le b_i\), \(i = 1, \dots, m\)
with \(x=(x_1,\dots,x_n)\), \(f_i\mathbb R^n\to\mathbb R\)
Notation: \(f_0\)

Name: The inequality constraint functions
Page: 1
Variables: An optimization problem
minimize \(f_0(x)\)
subject to \(f_i(x)\le b_i\), \(i = 1, \dots, m\)
with \(x=(x_1,\dots,x_n)\), \(f_i\mathbb R^n\to\mathbb R\)
Notation: \(f_i\)

Name: An optimal vector
Definition: A value \(x\) which satisfies all constraints and such that no other values \(z\) satisfying those constraints satisfy \(f(z)\le f(x)\)
Page: 1
Variables: An optimization problem
minimize \(f_0(x)\)
subject to \(f_i(x)\le b_i\), \(i = 1, \dots, m\)
with \(x=(x_1,\dots,x_n)\), \(f_i\mathbb R^n\to\mathbb R\)
Context: Optimization problem
Notation: \(x^*\)
Name2: A solution to the problem

Name: A linear program
Definition: An optimization problem whose constraint functions are linear
Page: 1

Name: A nonlinear program
Definition: An optimization problem which is not linear
Page: 1

Name: A convex optimization problem
Definition: An optimization problem which objective and constraint functions are convex
Page: 2
Chapter: 1

Smaller0: \(f\) is linear
Greater0: \(f\) is convex
Page: 2
Chapter: 1
Variables: \(f:\mathbb R^m\to\mathbb R\)

Name: Portfolio optimization
Definition: Optimizing investment of capital in various assets, subjects to some constraints
Page: 2
Chapter: 1
Section: 1.1

Name: Device sizing
Definition: Choosing the width and length of each device in an electronic circuit
Page: 2
Chapter: 1
Section: 1.1

Name: Data fitting
Definition: find a model, from a family of potential models,
that best fits some observed data and prior information
Page: 2
Chapter: 1
Section: 1.1

Name: Embedded optimization
Definition: An optimization system serving to act on a product in with no or little human intervention or oversight
Page: 3
Chapter: 1
Section: 1.1

Name: A solution method for \(C\)
Definition: an algorithm that computes a solution of the problem (to some given accuracy), given an instance of \(C\)
Page: 3
Chapter: 1
Section: 1.2
Variables: \(C\) a class of optimization problem

Name: An instance of \(C\)
Definition: A problem belonging to \(C\)
Page: 3
Chapter: 1
Section: 1.2
Variables: \(C\) a class of optimization problem

Name: A sparse problem
Definition: A problem such that each constraint depends on only a small number
Page: 3
Chapter: 1
Section: 1.2

Name: A least-square problem
Definition: without contraint whose minimization function is of the form
\(||Ax-b||^2_2\)
Page: 4
Chapter: 1
Section: 2.1
Definition2: Requiring to solve \((A^TA)x = A^Tb\)
Example: maximum likelihood estimation of a vector x, given linear measurements corrupted by Gaussian measurement errors
Typ: A problem with \(A\in\mathbb R^{k\times n}\) with \(k\ge n\) and \(b\in\mathbb R^k\)

Name: A sparse matrix
Definition: A matrix with far fewer than \(kn\) nonzero entries
Page: 4
Chapter: 1
Section: 2.1
Variables: \(\mathbb R^{k\times n}\)

Name: A weighted least-squares problem
Definition: A problem without constraints, with objective function being \(\sum_{i=1}^kw_i(a_i^Tx-b_i)^2\), with \(w_i\ge0\), \(b_i\in\mathbb R\), \(a_i\in\mathbb R^n\)
Page: 4
Chapter: 1
Section: 2.1
Variables: \(\mathbb R^{k\times n}\)
Example: estimation of a vector x, given linear measurements corrupted by errors with
unequal variances

Name: Chebyshev approximation problem
Definition: A problem of the form
mininize \(\max_{i=1,\dots,k}|a_i^Tx-b_i|\)
with \(x\in\mathbb R^n\), \(a_i\in\mathbb R^n\), \(b_i\in\mathbb R\)
Page: 6
Chapter: 1
Section: 2.2

Question: How to solve:
Chebyshev approximation problem
mininize \(\max_{i=1,\dots,k}|a_i^Tx-b_i|\)
with \(x\in\mathbb R^n\), \(a_i\in\mathbb R^n\), \(b_i\in\mathbb R\)
Answer: solve
minimize \(t\)
subject to:
\(a_i^Tx-t\le b_i\)
\(-a_i^Tx-t\le -b_i\)
Page: 6
Chapter: 1
Section: 2.2

Name: Local optimization
Definition: An optimization problem whose goal is to find a local minimum
Page: 9
Chapter: 1
Section: 4.1

Question: Advantage of local optimization
Answer: Well studied, have a lot of methods
Page: 9
Chapter: 1
Section: 4.1
Answer2: Faster, can handle large-scale problems
Answer3: Widely applicable

Question: Disvantage of local optimization
Answer: Require an initial guess
Page: 9
Chapter: 1
Section: 4.1
Answer2: sensitive to algorithm parameter value

Name: Global optimization
Definition: An optimization problem, with the emphasize that we don't restrict to local optimization
Page: 10
Chapter: 1
Section: 4.2

Question: How to use convex optimization technique for non convex problem
Answer: Approximate with convex problem, solve, then apply a local non-convex solving algorithm
Page: 11
Chapter: 1
Section: 5
Answer2: Transform the problem in a convex one, e.g. minimizing an expectation instead of maximizing a function
Answer3: Relax the problem to a convex problem, find a lower bound on the solution, then apply a non-convex technique using this lower bound

Name: The set of symmetric matrices of dimension \(k\)
Page: 14
Chapter: 1
Section: 6
Notation: \(\mathbf S^k\)

Name: The set of symmetric positive semidefinite matrices of dimension \(k\times k\)
Page: 14
Chapter: 1
Section: 6
Notation: \(\mathbf S^k_+\)
Typ: Convex cone

Name: The set of symmetric positive definite matrices of dimension \(k\times k\)
Page: 14
Chapter: 1
Section: 6
Notation: \(\mathbf S^k_{++}\)

Name: The relative interior of the set \(C\)
Definition: The interior of \(C\), when we restrict consideration to the affine set of \(C\). Formally:
* The set of \(x\in C\) such that there exists \(\epsilon>0\) such that \(B(x,\epsilon)\cap \mathbf{aff} C\) is included in \(C\)
Page: 23
Chapter: 2
Section: 1.3
Variables: \(m\in\mathbb N\)
\(C\subseteq\mathbb R^n\)
Notation: \(\mathbf{relint} C\)

Name: Omitted
Definition: Standard algebra. Affine set, affine hull, dimension, line, convex set, convex hull, cone, subspace, hyperplane, halfspaces, ball, center, radius, polytope, polyhedron
Page: 17-22
Chapter: 2
Section: 1.3
Variables: \(m\in\mathbb N\)
\(C\subseteq\mathbb R^n\)

Name: The relative boundary of \(C\)
Definition: \(\mathbf {cl}C\setminus\mathbf{relint} C\)
Page: 23
Chapter: 2
Section: 1.3
Variables: \(m\in\mathbb N\)
\(C\subseteq\mathbb R^n\)

Name: The closure of \(C\)
Page: 23
Chapter: 2
Section: 1.3
Variables: \(m\in\mathbb N\)
\(C\subseteq\mathbb R^n\)
Notation: \(\mathbf {cl} C\)

Name: A cone
Definition: A set \(C\) such that for each \(x\in C\) and \(\theta\ge0\), \(\theta x\in C\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
Name2: A nonnegative homogeneous set

Name: A conic combinations of the vectors \(x_1,\dots,x_k\)
Definition: A vector of the form \(\sum_{i=1}^k\theta_ix_i\) with \(\theta_i\ge0\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
\(x_1,\dots,x_k\in\mathbb R^k\)

Definition: \(\{v\mid a^Tv=0\}\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
\(a\mathbb R^n\)
Notation: \(a^\bot\)

Name: An ellipsoid
Definition: A set of the form \(\{x\mid (x-x_c)^TP^-{-1}(x-x_c)\le 1\) with \(P\) symmetric positive definite
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
Definition2: A set of the form \(\{x_c+Au\mid ||u||_2\le 2\}\) with \(A\) square and nonsingular
Denoted by: \(\mathcal E\)

Name: The center of \(\mathcal E\)
Definition: \(x_c\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
An ellipsoid \(\mathcal E=\{x\mid (x-x_c)^TP^-{-1}(x-x_c)\le 1\) with \(P\) symmetric positive definite
Context: Ellipsoid

Name: The semi-axes of \(\mathcal E\)
Definition: \(\sqrt{\lambda_i}\) with \(\lambda_i\) an eigenvalue of \(P\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
An ellipsoid \(\mathcal E=\{x\mid (x-x_c)^TP^-{-1}(x-x_c)\le 1\) with \(P\) symmetric positive definite
Context: Ellipsoid

Name: A ball
Definition: An ellipsoid with \(P=r^2I\)
Page: 25
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
Context: Ellipsoid

Name: A degenerate elipsoid
Definition: An elipsoid \(\mathcal E =\{x_c+Au\mid ||u||_2\le 2\}\) with \(A\) square and singular
Page: 30
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
An ellipsoid \(\mathcal E =\{x_c+Au\mid ||u||_2\le 2\}\) with \(A\) square and nonsingular
Context: Ellipsoid

Smaller0: the affine dimension of \(\mathcal E\)
Greater0: the rank of \(A\)
Page: 30
Chapter: 2
Section: 1.5
Variables: \(m\in\mathbb N\)
An ellipsoid \(\mathcal E =\{x_c+Au\mid ||u||_2\le 2\}\) with \(A\) square
Smaller to greater: is equal to
Context: Ellipsoid

Name: The norm cone associated with \(||\cdot||\)
Definition: \(\{(x,t)\mid ||x||\le t\}\)
Page: 30
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
\(||\cdot||\) a norm

Definition: The vector \((1,\dots,1)\in\mathbb R^n\)
Page: 33
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
Notation: \(\mathbf 1\)

Name: A \(n\)-dimensional simplex
Definition: The convex hull of \(n+1\) linearly independant point
Page: 33
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
Example: Point, Line, triangle with interior, tetrahedron with interior...
Example2: Unit simplex
Example3: Probability simplex

Name: The unit simplex
Definition: The simplex determined by the unit vectors and the zero vector
Page: 33
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
Definition2: the set \(x\succeq0\) with \(\mathbf 1^Tx\le 1\)

Name: The \(i\)-th unit vector
Definition: \(0,\dots,0,1,0,\dots,0\) with the 1 in the \(i\)-th position
Page: 33
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
\(0<i\le n\)
Notation: \(e_i\)

Name: The probability simplex
Definition: The simplex generated by the unit vectors
Page: 33
Chapter: 2
Section: 1.5
Variables: \(n\in\mathbb N\)
Definition2: the set \(x\succeq0\) with \(\mathbf 1^Tx= 1\)
Etymology: Can describe a probability space between \(n\) options

Name: Convex set
Page: 36
Section: 3.1
Chapter: 2
Variables: \(n\in\mathbb N\)
Under: intersection
Under2: affine functions
Under3: Inverse image of affine function
Under4: linear-fractional

Name: Slab
Definition: \(\{x\in\mathbb R^m\mid -1\le (\cos t,\dots, \cos mt)^Tx\le 1\})\)
Page: 36
Chapter: 2
Section: 3.1
Variables: \(m\in\mathbb N\)
Notation: \(T_t\)

Question: Example of affine function
Answer: Scaling
Page: 36
Chapter: 2
Section: 3.1
Answer2: translation
Answer3: Projection
Answer4: (Partial) Sum

Name: Hyperbolic cone
Definition: \(\{x\mid x^TPx\le (c^Tx)^2, c^Tx\le 0\}\) where \(P\in\mathbf S_+^n\) and \(c\in\mathbf R^n\)
Page: 39
Chapter: 2
Section: 3.1
Conjdef: convex set

Definition: \(z/t\)
Page: 39
Section: 3.3
Chapter: 2
Variables: \(n\in\mathbb N\)
Name: The perspective function
Domain: \(\mathbb R^n\times\mathbb R^{{\gt}0}\)
Codomain: \(\mathbb R^n\)
Linear: Not even affine
Intuition: Pin-hole camera, sending a point in the 3-d space to a point on the plane
Applied to: \((z,t)\)

Name: A linear-fractional function
Definition: \(P\circ A\) with \(M\) the projective function and \(A\) affine
Page: def39
Chapter: 2
Section: 3.3
Variables: \(n\in\mathbb N\)
Name2: A projective function

Name: A solid set
Definition: A set with non-empty interior
Page: 43
Chapter: 2
Section: 4.1
Variables: \(n\in\mathbb N\)

Name: A pointed cone
Definition: A cone containing no line. I.e. \(x, -x\in C\) implies \(x=0\)
Page: 43
Chapter: 2
Section: 4.1
Variables: \(n\in\mathbb N\)

Name: A proper cone
Definition: convex
Page: 43
Chapter: 2
Section: 4.1
Variables: \(n\in\mathbb N\)
Definition2: closed
Conjdef: A cone
Definition3: solid
Definition4: pointed