Introduction

(F, c) is an optimization problem, where F is the set of feasible points and c(f) is a real-valued cost function. The goal is to minimize c over F.

If x and y are real n-vectors, λx + (1-λ)y is a convex combination of x and y if 0 ≤ λ ≤ 1.

A set is convex if it is closed under convex combinations.

The intersection of any number of convex sets is convex.

A real-valued function c on a convex set S is convex if

c( λx + (1-λ)y ) ≤ λc(x) + (1-λ)c(y) for 0 ≤ λ ≤ 1.

If c(x) is a convex function on a convex set S, then the set of points in S satisfying c(x) ≤ t is convex.