defs Flashcards
convex set
A set C ⊆ R^n is convex, if for all x, y ∈ C and λ ∈ [0, 1], λx + (1 − λ)y ∈ C.
That is, for any two points in C, the line segment connecting them is also in C.
convex function
A function f : C → R is convex, if C is convex and for all x, y ∈ C and λ ∈ [0, 1]:
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y).
A point x* ∈ R^n is a global minimizer if
for all x ∈ R^n
f(x*) ≤ f(x)
A point x* ∈ R^n is a local minimizer if
if there is an open neighbourhood U of x*
such that f(x*) ≤ f(x) for all x ∈ U
A point x* ∈ R^n is a strict local minimizer if
if there is an open neighbourhood U of x*
such that f(x*) < f(x) for all x ∈ U
A point x* ∈ R^n is a isolated minimizer if
if there is an open neighbourhood U of x*
such that x* is the only local minimizer in U
Let x* be a local minimizer of f and assume that f ∈ C^1(U) for a neighbourhood of U of x*
Then:
∇f(x*) = 0
A is positive semidefinite
if for every x ∈ R^d,
x^TAx ≥ 0
positive definite
if for every x ∈ R^d,
x^TAx > 0
Let f ∈ C^2(U) for some open set U and x* ∈ U.
If x* is a local minimizer, then:
Conversely, if ∇f(x) = 0 and ∇2f(x) is positive definite, then:
∇f(x) = 0 and ∇2f(x) is positive semidefinite
x* is a strict local minimizer
convex body
A convex body is a convex set that is closed and bounded
convex function,
strictly convex function
Let S ⊆ R^n
A function f : S → R is called convex if S is convex and for all x, y ∈ S and λ ∈ [0, 1],
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y).
The function f is called strictly convex if
f(λx + (1 − λ)y) < λf(x) + (1 − λ)f(y).
Let f : R^n → R be a convex function. Then any local minimizer of f is a
global minimizer
Let f ∈ C^1(R^n).
Then f is convex if and only if for all x, y ∈ R^n
f(y) ≥ f(x) + ∇f(x)^T (y − x)
Let f ∈ C^2(R^n).
Then f is convex if and only if
∇2f(x) is positive semidefinite. If ∇2f(x) is positive definite, then f is strictly convex