Convex Optimization I: Convexity and Examples

Series Division:

• Part 1: Fundamentals, Convexity Criteria, and Examples.
• Part 2: Duality, KKT Conditions, and Advanced Applications.
• Part 3: Convex Loss Functions.

1. Identifying Convex Functions

A function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if and only if, for all $x, y \in \mathbb{R}^n$ and all $\theta \in [0,1]$,

For a function defined on a smaller domain, the domain must itself be convex, and the inequality is required for points in that domain. The derivative tests below apply on an open convex domain. These definitions and tests follow Boyd and Vandenberghe's convex-functions notes.

1.1 First-Order and Second-Order Criteria

1. First-Order Test (if $f$ is differentiable):

   $$f(y) \;\ge\; f(x) \;+\; \nabla f(x)^\top (\,y - x\,), \quad \forall\,x, y.$$

   Scroll to see the full equation →

   This criterion says that the function lies above each of its first-order approximations. At a fixed point $x$, define the affine approximation $\ell_x(y)=f(x)+\nabla f(x)^\top(y-x)$. Convexity requires $f(y)\ge\ell_x(y)$ throughout the domain; equality holds at $y=x$.

2. Second-Order Test (if $f$ is twice differentiable):

   $$\nabla^2 f(x) \;\succeq\; 0, \quad \forall\, x.$$

   Scroll to see the full equation →

   That is, the Hessian is positive semidefinite at every point $x$.

How to check:

• Eigenvalue Method: Compute the eigenvalues of $A$. If all eigenvalues are nonnegative, $A$ is PSD.
• Principal Minors: For a symmetric matrix, PSD is equivalent to every principal minor being nonnegative. A principal submatrix uses the same index set for its rows and columns. Checking only the leading, top-left submatrices is not sufficient for PSD.

Below are some important examples demonstrating these criteria in action—some are convex, one is not.

1.2 Preserving Convexity

• Nonnegative Weighted Sum: If $f_i$ are convex and $\alpha_i \ge 0$, then $\sum_{i}\alpha_i f_i$ is convex.

• Affine Transformation: If $f$ is convex, then $g(x) = f(Ax + b)$ is convex for any matrix $A$ and vector $b$.

• Pointwise Maximum: If $f_i$ are convex, then $\max_i f_i(x)$ is convex.

• Composition with a Nondecreasing Convex Function: If $f:\mathbb{R}^m\to\mathbb{R}$ is convex and nondecreasing in each argument, and every component of $g$ is convex on a common convex domain, then $x\mapsto f(g(x))$ is convex. For restricted domains, the composition must also satisfy the relevant domain conditions.

---

2. Examples

2.1 Quadratic Function

Consider the univariate quadratic

or the multivariate version

where $A$ is symmetric and $A \succeq 0$ (positive semidefinite).

Step-by-step check:

• Gradient (multivariate):
  $$\nabla f(x) = 2A\,x + b.$$

  Scroll to see the full equation →
• Hessian (multivariate):
  $$\nabla^2 f(x) = 2A.$$

  Scroll to see the full equation →
• Because $A \succeq 0,$ we have $2A \succeq 0.$ Hence, $\nabla^2 f(x)$ is positive semidefinite for all $x,$ implying convexity.

Interpretation: A PSD coefficient matrix gives nonnegative curvature in every direction. Zero curvature in some directions is allowed, so convexity here does not imply a unique minimizer.

---

2.2 Log-Sum-Exp

Define

Step-by-step check (Hessian test):

1. Gradient of $f(x)$:
   If we let $z = \sum_{i=1}^n e^{x_i}$, then

   $$\frac{\partial f}{\partial x_j} = \frac{1}{z} \, e^{x_j}.$$

   Scroll to see the full equation →

   So the gradient is

   $$\nabla f(x) = \frac{1}{z}\,\bigl(e^{x_1}, e^{x_2}, \dots, e^{x_n}\bigr)^\top.$$

   Scroll to see the full equation →

2. Hessian of $f(x)$:
   For $j,k=1,\dots,n$,

   $$\frac{\partial^2 f}{\partial x_j \partial x_k} = \frac{\partial}{\partial x_k} \Bigl(\tfrac{ e^{x_j} }{ \sum_{\ell=1}^n e^{x_\ell} }\Bigr) = \delta_{jk}\frac{e^{x_j}}{z} -\frac{e^{x_j}e^{x_k}}{z^2},$$

   Scroll to see the full equation →

   where $z = \sum_{\ell=1}^n e^{x_\ell}$ and $\delta_{jk}$ is $1$ if $j=k$ and $0$ otherwise.

   The matrix form of the Hessian is

   $$\nabla^2 f(x) = \frac{1}{z}\,\mathrm{diag}(e^{x_1},\dots,e^{x_n}) \;-\; \frac{1}{z^2}\, \bigl(e^{x}\bigr)\bigl(e^{x}\bigr)^\top,$$

   Scroll to see the full equation →

   where $e^x$ is the column vector of exponentials. To see why this matrix is positive semidefinite, write $p_i=e^{x_i}/z$. For any vector $v$, its quadratic form is

   $$v^\top\nabla^2f(x)v =\sum_i p_i v_i^2-\left(\sum_i p_i v_i\right)^2\ge0,$$

   Scroll to see the full equation →

   the variance $\operatorname{Var}_{I\sim\operatorname{Categorical}(p_1,\ldots,p_n)}(v_I)$. Here $x$ and $v$ are fixed; only the auxiliary index $I$ is random. Its probabilities are the displayed softmax weights, so nonnegativity follows from the definition of variance.

Thus, $\nabla^2 f(x)\succeq 0$, so $f$ is convex.

Interpretation: Log-sum-exp gives a smooth alternative to $\max_i x_i$. Its convexity follows from the nonnegative variance just derived, not merely from approximating a convex function.

It is convex but not strictly convex on all of $\mathbb{R}^n$: adding the same constant to every coordinate gives $f(x+c\mathbf{1})=f(x)+c$, an affine direction.

---

2.3 Euclidean Norm ($p=2$)

Consider

Step-by-step check (first-order or second-order approach):

1. Second-Order tests do not apply at $x=0$ because the norm is not differentiable there. We therefore use the more general fact that norms are convex.

   • Geometric argument: The unit ball of $\|\cdot\|_2$ is a disk or ball, which is convex. The norm $\|x\|_2$ measures how much we must scale this unit ball to include a point. This scaling function, called its Minkowski functional, is convex because the unit ball is convex and symmetric.

2. Subgradient at $x\neq 0$:

   $$\nabla f(x) = \frac{x}{\|x\|_2},$$

   Scroll to see the full equation →

   whereas a subgradient approach is needed at $x=0$.

Thus, the Euclidean norm is convex.

General fact: $\|x\|_p$ is convex for all $p \ge 1$.

---

2.4 Non-Convex Example: $\sin(x)$

Consider $f(x) = \sin(x)$ (univariate, for simplicity).

Step-by-step check:

• First derivative: $f'(x) = \cos(x).$
• Second derivative: $f''(x) = -\sin(x).$

Global convexity would require $f''(x) \ge 0$ for all $x$. However, $-\sin(x)$ changes sign. In particular, for $x \in (0, \pi)$, $f''(x) = -\sin(x) < 0,$ so $f$ is concave on that interval. At $x=0$, we have $f''(0)=0$, but the value at a single point does not establish convexity. Therefore, $\sin(x)$ is not convex over $\mathbb{R}$.

Interpretation: $\sin(x)$ oscillates, so it curves up and down infinitely often, violating any global convexity requirement.

---

Notes

1. Quadratic + PSD → Convex.
2. Log-sum-exp: Convex, but not strictly convex on its full domain.
3. ℓ₂-norm: Convex (more generally, ℓₚ-norms for $p \ge 1$ are convex).
4. $\sin(x)$: Not convex, since its second derivative changes sign.

General thinking process when Verifying Convexity:

• Definition Check: Confirm that for any two points $x$ and $y$ in the domain and any $\theta \in [0,1]$,

  $$f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y).$$

  Scroll to see the full equation →

  This is the fundamental property of convex functions.

• First-Order Condition: For differentiable functions, verify that the function always lies above its tangent lines. In other words, check that

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

  Scroll to see the full equation →

  holds for all $x$ and $y$.

• Second-Order Condition: For twice differentiable functions, check that the Hessian matrix is positive semidefinite everywhere in the domain. This guarantees that the curvature is non-negative throughout (and watch for points of non-differentiability).

• Composition Rules: Many functions are built from simpler components. Convexity is preserved under operations such as:

  • Sum: If $f(x)$ and $g(x)$ are convex, then

    $$h(x) = f(x) + g(x)$$

    Scroll to see the full equation →

    is convex.

  • Scaling: If $f(x)$ is convex and $a \ge 0$ is a scalar, then

    $$g(x) = a \, f(x)$$

    Scroll to see the full equation →

    is convex.

  • Affine Transformation: If $f$ is convex and $g(x) = A x + b$ is an affine mapping, then

    $$h(x) = f(A x + b)$$

    Scroll to see the full equation →

    is convex.

  • Nondecreasing/Nonincreasing Composition:
    If $f:\mathbb{R}\to\mathbb{R}$ is convex and nondecreasing and $g:\mathbb{R}^n\to\mathbb{R}$ is convex, then

    $$h(x) = f(g(x))$$

    Scroll to see the full equation →

    is convex.
    Similarly, if $f$ is convex and nonincreasing and $g$ is concave, then $h(x)=f(g(x))$ is convex.

  • Pointwise Maximum: The pointwise maximum of convex functions is also convex. If $f_i(x)$ are convex for $i = 1, 2, \dots, n$, then

    $$h(x) = \max\{f_1(x), f_2(x), \dots, f_n(x)\}$$

    Scroll to see the full equation →

    is convex.

  • Perspective Function: Given a convex function $f:\mathbb{R}^n\to\mathbb{R}$, its perspective

    $$g(x,t) = t \, f\Bigl(\frac{x}{t}\Bigr)$$

    Scroll to see the full equation →

    is convex on $\{(x,t) \in \mathbb{R}^{n+1}: t > 0\}$. This is particularly useful for scaling or normalization.

  • Elementwise Composition: A convex outer function alone does not guarantee a convex composition. For example, $h(x)=\|g(x)\|_2$ is convex if each component of $g$ is convex and nonnegative: the Euclidean norm is convex and coordinatewise nondecreasing on the nonnegative orthant.

• Reformulation: If the convexity of the original function is not immediately clear, try to reformulate it as a combination of simpler convex components. This can often reveal the hidden structure.

• Convex Relaxation: Replacing a nonconvex problem by a convex relaxation changes the problem. It can provide a bound or a tractable approximation, but it does not establish convexity of the original problem or automatically preserve its optimizer.

• Additional Tools: Numerical checks can expose counterexamples or suggest an argument, but checking finitely many points does not prove global convexity. Symbolic calculations can support a proof when their domain and assumptions are explicit.

Use the expression and domain to choose the proof. Derivative tests require differentiability throughout the domain; closure properties can also cover corners such as the origin of a norm. A numerical check can suggest a counterexample, but cannot replace either argument.

References & Further Reading

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.
3. Schölkopf, B., & Smola, A. (2001). Learning with Kernels. MIT Press.