defs Flashcards

1
Q

convex set

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

convex function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

A point x* ∈ R^n is a global minimizer if

A

for all x ∈ R^n

f(x*) ≤ f(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A point x* ∈ R^n is a local minimizer if

A

if there is an open neighbourhood U of x*

such that f(x*) ≤ f(x) for all x ∈ U

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

A point x* ∈ R^n is a strict local minimizer if

A

if there is an open neighbourhood U of x*

such that f(x*) < f(x) for all x ∈ U

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A point x* ∈ R^n is a isolated minimizer if

A

if there is an open neighbourhood U of x*

such that x* is the only local minimizer in U

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Let x* be a local minimizer of f and assume that f ∈ C^1(U) for a neighbourhood of U of x*
Then:

A

∇f(x*) = 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

A is positive semidefinite

A

if for every x ∈ R^d,

x^TAx ≥ 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

positive definite

A

if for every x ∈ R^d,

x^TAx > 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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:

A

∇f(x) = 0 and ∇2f(x) is positive semidefinite

x* is a strict local minimizer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

convex body

A

A convex body is a convex set that is closed and bounded

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

convex function,

strictly convex function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Let f : R^n → R be a convex function. Then any local minimizer of f is a

A

global minimizer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Let f ∈ C^1(R^n).

Then f is convex if and only if for all x, y ∈ R^n

A

f(y) ≥ f(x) + ∇f(x)^T (y − x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Let f ∈ C^2(R^n).

Then f is convex if and only if

A

∇2f(x) is positive semidefinite. If ∇2f(x) is positive definite, then f is strictly convex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

gradient descent search direction:

A

pk = −∇f(xk)

17
Q

gradient descent direction deriv:

A

<p></p>

18
Q

sufficient decrease condition

A

f(xk + αpk) ≤ f(xk) + c α =: l(α),

19
Q

Assume that a sequence of vectors {xk}, k ≥ 0, converges to x*
Then the sequence {xk}, k ≥ 0, is said to converge

linearly
superlinearly
with order p

A

if there exist an r ∈ (0, 1) such that for sufficiently
large k,
||xk+1 − x|| ≤ r ||xk − x||

lim || xk+1 -x || =0
k→∞ ||xk - x ||

if there exists a constant M > 0, such that for sufficiently large k,

||xk+1 − x|| ≤ M ||xk − x*||^p (p=2 quad conv)