Information Technology Reference
In-Depth Information
21.3 Convex Optimization
When we solve a machine learning problem, it is almost unavoidable that we will
use some optimization techniques. In this section, we will introduce some basic
concepts and representative algorithms for convex optimization.
21.3.1 Convex Set and Convex Function
n
Aset
C
⊆
R
is a
convex set
if
∀
x,y
∈
C
and
∀
θ
∈[
0
,
1
]
, there holds
θx
+
(
1
−
θ)y
∈
C,
i.e., the line segments between any pairs of
x
and
y
lies in
C
.
A function
f
n
is a
convex function
if the domain of
f
(denoted by
dom
f
) is a convex set and there holds
:
R
→
R
f
θx
θ)y
≤
+
(
1
−
θf (x)
+
(
1
−
θ)f(y)
∀
x,y
.
Note that (i) function
f
is
concave
if
∈
dom
f
and
θ
∈[
0
,
1
]
f
is convex; (ii) function
f
is
strictly
convex
if dom
f
is convex and there holds
f(θx
−
+
(
1
−
θ)y) < θf(x)
+
(
1
−
θ)f(y)
,
∀
; (iii) from the definition of a convex function
one can conclude that
any local minimum is a global minimum for convex functions
.
Here are some examples of convex functions:
x,y
∈
dom
f
,
x
=
y
, and
θ
∈[
0
,
1
]
•
affine:
ax
+
b
on
x
∈
R
,
∀
a,b
∈
R
exponential:
e
ax
•
on
x
∈
R
,
∀
a
∈
R
powers:
x
α
•
on
x
∈
(
0
,
+∞
)
,for
α
∈
(
−∞
,
0
]∪[
1
,
+∞]
p
•
powers of absolute value:
|
x
|
on
x
∈
R
,
∀
p
∈[
1
,
+∞]
•
negative logarithm:
−
log
x
on
x
∈
(
0
,
+∞
)
•
negative entropy:
x
log
x
on
x
∈
(
0
,
+∞
)
affine function:
a
T
x
n
,
n
•
+
b
on
x
∈
R
∀
a,b
∈
R
x
p
=
(
i
=
1
|
x
i
|
p
)
1
/p
n
•
norms:
on
x
∈
R
for
p
∈[
1
,
+∞]
;
x
∞
=
max
i
|
x
i
|
n
on
x
∈
R
quadratic:
x
2
•
+
bx
+
c
on
x
∈
R
,
∀
b, c
∈
R
Here are some examples of
concave
functions:
•
affine:
ax
+
b
on
x
∈
R
,
∀
a,b
∈
R
powers:
x
α
•
on
x
∈
(
0
,
+∞
)
,for
α
∈[
0
,
1
]
•
logarithm: log
x
on
x
∈
(
0
,
+∞
)
