#eth/cil/theory

Convexity Definition

A set in a vector space or affine space is convex if the line segment connecting any two points in the set is also in the set

A function f is convex over a domain R, if for all x,y∈R $$f(tx + (1-t)y) \leq tf(x) + (1-t)f(y), \quad \forall t \in [0;1]$$

If f is differentiable, convexity is equivalent to the condition:

f(x)≥f(y)+∇f(y)(x−y),∀x,y∈R

if f is twice differentiable, convexity on a convex domain R is equivalent to the condition:

∇2f(x)⪰0,∀x∈Int(R)

Our scalar problem is non-convex (exception: a=0), as there is a saddle point at the origin.

Convexity is a very fundamental property: demarcation line in optimization between tractable and (possibly) intractable problems