Convex and Concave Functions

Convex and concave functions are central concepts in optimization, machine learning, economics, and statistics. They describe how a function “curves” and determine whether optimization problems are easy or difficult to solve.

---

1. Convex Functions

1.1 Definition

A function

$$f:\mathbb{R}^n \rightarrow \mathbb{R}$$

is called convex if for all $x_1, x_2 \in \mathbb{R}^n$ and for all $\lambda \in [0,1]$,

$$\boxed{ f(\lambda x_1 + (1-\lambda)x_2) \;\le\; \lambda f(x_1) + (1-\lambda)f(x_2) }$$

This inequality is known as Jensen’s inequality (two-point form).

---

1.2 Geometric Interpretation

• The graph of a convex function lies below the straight line (chord) joining any two points on the graph.

• In 1D, the curve is cup-shaped (opens upward).

• In higher dimensions, the surface curves upward.

📌 Key consequence:

Every local minimum of a convex function is a global minimum.

---

1.3 Examples of Convex Functions

Basic Examples

• Linear (affine) functions:

  $$f(x) = ax + b$$
  

• Quadratic functions:

  $$f(x) = x^2,\quad f(x)=x^TQx \ (Q \succeq 0)$$
  

• Norms:

  $$\|x\|_1,\ \|x\|_2$$

• Exponential:

  $$f(x) = e^x$$
  

• Log-sum-exp:

  $$f(x) = \log\left(\sum_i e^{x_i}\right)$$
  

---

1.4 Identification Tests for Convex Functions

(a) First-Order Condition

If $f$ is differentiable, then $f$ is convex iff

$$f(y) \ge f(x) + \nabla f(x)^T (y - x)$$

for all $x,y$

(b) Second-Order Condition

If $f$ is twice differentiable, then

$$\boxed{ f \text{ is convex } \iff \nabla^2 f(x) \succeq 0 \quad \forall x }$$

(Hessian matrix is positive semidefinite.)

---

1.5 Convex Functions in Optimization & ML

• Linear regression (MSE loss)

• Logistic regression (log-loss)

• Support Vector Machines (hinge loss)

• Regularization ($\ell_1$, $\ell_2$)

✔ Guarantees:

• Unique global optimum

• Fast convergence

• Stable algorithms

2. Concave Functions

2.1 Definition

A function

$$f:\mathbb{R}^n \rightarrow \mathbb{R}$$

is concave if for all $x_1,x_{\mathrm{2\; and }}$$\lambda \in [0,1]$,

$$\boxed{ f(\lambda x_1 + (1-\lambda)x_2) \;\ge\; \lambda f(x_1) + (1-\lambda)f(x_2) }$$

📌 A function is concave if and only if its negative is convex:

$$f \text{ is concave } \iff -f \text{ is convex}.$$

---

2.2 Geometric Interpretation

• The graph lies above the chord connecting any two points.

• In 1D, the curve is cap-shaped (opens downward).

📌 Key consequence:

Every local maximum of a concave function is a global maximum.

---

2.3 Examples of Concave Functions

• Linear functions (both convex and concave)

• Logarithmic function:

  $$f(x) = \log x,\quad x>0$$
  

• Square root:

  $$f(x) = \sqrt{x},\quad x \ge 0$$
  

• Negative quadratic:

  $$f(x) = -x^2$$
  

---

2.4 Identification Tests for Concave Functions

• First-order:

  $$f(y) \le f(x) + \nabla f(x)^T (y-x)$$
  

• Second-order:

  $$\boxed{ f \text{ is concave } \iff \nabla^2 f(x) \preceq 0 }$$

(Hessian is negative semidefinite.)

---

3. Relationship Between Convex and Concave Functions

Property	Convex	Concave
Shape	Cup-shaped	Cap-shaped
Inequality	≤ (Jensen)	≥ (reverse Jensen)
Hessian	PSD	NSD
Optimization	Minimize	Maximize
Local optimum	Global minimum	Global maximum

---

4. Strict Convexity and Concavity

Strictly Convex

$$f(\lambda x_1 + (1-\lambda)x_2) < \lambda f(x_1) + (1-\lambda)f(x_2)$$

for $x_1 \ne x_2$.

📌 Leads to unique minimizer.

Strictly Concave

Reverse inequality with strict $>$.

---

5. Convexity of Sets vs Functions (Key Link)

• Sublevel sets of convex functions are convex:

  $$\{x : f(x) \le c\}$$
  

• Superlevel sets of concave functions are convex:

  $$\{x : f(x) \ge c\}$$
  

---

6. Applications

Machine Learning

• Loss functions → convex

• Regularization → convex

• Likelihood functions → concave (maximization)

Economics

• Utility functions → concave

• Cost functions → convex

Summary: Convex vs Concave Functions

Feature	Convex Function	Concave Function
Definition (Geometric)	Lies below or on the chord joining any two points on the graph	Lies above or on the chord joining any two points on the graph
Mathematical Condition	$𝑓(𝜆{𝑥}_1+(1-𝜆){𝑥}_2)\le 𝜆𝑓({𝑥}_1)+(1-𝜆)𝑓({𝑥}_2)$ $\lambda \in [0,1]$	$𝑓(𝜆{𝑥}_1+(1-𝜆){𝑥}_2)\ge 𝜆𝑓({𝑥}_1)+(1-𝜆)𝑓({𝑥}_2)$$<br>$
First Derivative Test (1D)	${𝑓}^{\mathrm{\prime }}(𝑥)$ is non-decreasing	${𝑓}^{\mathrm{\prime }}(𝑥)$ non-increasing
Second Derivative Test (1D)	${𝑓}^{\mathrm{\prime }\mathrm{\prime }}(𝑥)\ge 0$	${𝑓}^{\mathrm{\prime }\mathrm{\prime }}(𝑥)\le 0$
Graphical Representation	Curve bends upward (U-shaped); surface is bowl-shaped in higher dimensions	Curve bends downward (∩-shaped); surface is dome-shaped
Tangent Line Property	Tangent line lies below or on the graph	Tangent line lies above or on the graph
Optimization Problem	Used in minimization problems	Used in maximization problems
Local Optimum	Every local minimum is a global minimum	Every local maximum is a global maximum
Relation Between Them	—	$\mathrm{<br>}$ is concave ⇔ $-𝑓$ is convex

---