Convex Optimization III: A Reference to Convex Functions

Series Division:

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

4. Common Convex Loss Functions

Recap: The convexity tests used below

The entries reuse the following results from Part 1. Choose a test that applies on the function's entire convex domain:

• 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 →
• First-Order Condition (if differentiable): Verify $f(y) \ge f(x) + \nabla f(x)^T (y-x)$ holds for all $x, y$.
• Second-Order Condition (if twice differentiable): Check the Hessian is positive semidefinite everywhere.
• Composition Rules: Recognize that sums, nonnegative scalings, affine transformations, pointwise maxima of convex functions, and suitable compositions preserve convexity.
• Reformulation & Relaxation: Rewriting the same function can reveal its convexity. Replacing it by a convex surrogate changes the function and does not prove that the original was convex.

Derivative tests below apply where the derivatives exist. At nondifferentiable points, we use the subdifferential $\partial f$, the set of slopes defining supporting affine functions.

4.1 Linear and Affine Functions

• Linear Function
  $f(\mathbf{x}) = \mathbf{a}^\top \mathbf{x}, \quad \mathbf{a} \in \mathbb{R}^n\;.$
  This is convex in $\mathbf{x}$ because its Hessian is zero. Gradient: $\nabla f(\mathbf{x}) = \mathbf{a}$.

Why It’s Convex: A linear function has zero curvature (its Hessian is the zero matrix). By the Second-Order Condition, a zero Hessian is positive semidefinite, hence convex. Also, by Definition Check, linear functions satisfy the convexity inequality exactly.

• Affine Function
  $f(\mathbf{x}) = \mathbf{a}^\top \mathbf{x} + b, \quad \mathbf{a} \in \mathbb{R}^n,\; b \in \mathbb{R}.$
  Affine functions are both convex and concave (their Hessian is zero).
  Gradient: $\nabla f(\mathbf{x}) = \mathbf{a}$.

Why It’s Convex: An affine function is just a linear function plus a constant shift. The same reasoning (zero Hessian, or direct verification by definition) shows it is convex. In fact, it’s both convex and concave.

4.2 Quadratic Functions

• Univariate Quadratic
  $f(x) = ax^2 + bx + c, \quad a \ge 0.$
  Convex if $a \ge 0$.
  Gradient: $\nabla f(x) = 2ax + b$.

Why It’s Convex: The second derivative is $2a$, which is nonnegative when $a\ge0$.

• Multivariate Quadratic
  $f(\mathbf{x}) = \mathbf{x}^\top A \mathbf{x} + \mathbf{b}^\top \mathbf{x} + c,\quad A \succeq 0.$
  Here $A$ is real symmetric and positive semidefinite. Gradient: $\nabla f(\mathbf{x}) = 2 A \mathbf{x} + \mathbf{b}$.

Why It’s Convex: By the Second-Order Condition, we check the Hessian $2A$, which is positive semidefinite if $A \succeq 0$. Hence, $f$ is convex.

4.3 Norm Functions

• $\ell_1$-Norm
  $f(\mathbf{x}) = \|\mathbf{x}\|_1 = \sum_{i=1}^n |x_i|.$
  Subdifferential: A vector $g$ belongs to $\partial f(\mathbf{x})$ when $g_i=\operatorname{sign}(x_i)$ for $x_i\ne0$ and $g_i\in[-1,1]$ for $x_i=0$.

Why It’s Convex: Each absolute value $|x_i|$ is convex by the triangle inequality. A sum of these convex functions is convex.

• $\ell_2$-Norm
  $f(\mathbf{x}) = \|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2}.$
  Gradient, for $\mathbf{x}\ne0$: $\nabla f(\mathbf{x})=\mathbf{x}/\|\mathbf{x}\|_2$. At zero, $\partial f(0)=\{g:\|g\|_2\le1\}$.

Why It’s Convex: For a convex combination of two vectors, the triangle inequality and positive homogeneity give the defining convexity inequality. This argument also covers the origin, where the gradient does not exist.

• Max Norm ($\ell_\infty$-Norm)
  $f(\mathbf{x}) = \|\mathbf{x}\|_\infty = \max_i |x_i|.$
  Subdifferential: For $\mathbf{x}\ne0$, it is the convex hull of $\operatorname{sign}(x_i)e_i$ over coordinates attaining the largest absolute value, where $e_i$ is the $i$th coordinate vector. At zero, it is $\{g:\|g\|_1\le1\}$.

Why It’s Convex: A maximum of convex functions $\{\,|x_1|,\dots,|x_n|\}$ is still convex by the Pointwise Maximum rule. Since $|x_i|$ is convex, $\max_i |x_i|$ must be convex.

4.4 Exponential and Logarithmic Functions

• Exponential Function
  $f(x) = e^x.$
  Convex in $x$.
  Gradient: $\nabla f(x) = e^x$.

Why It’s Convex: The Second-Order Condition shows its second derivative $e^x$ is positive for all $x$. Thus, the Hessian (in one dimension) is always > 0, satisfying convexity.

• Logarithmic Function
  $f(x) = \log(x), \quad x > 0.$
  $\log(x)$ is concave, but $-\log(x)$ is convex.
  Gradient: $\nabla f(x) = 1/x$.

Curvature: The logarithm is concave, whereas its negative is convex. The second-derivative test gives $\frac{d^2}{dx^2}(-\log(x)) = \frac{1}{x^2} \ge 0$ on the stated domain, establishing convexity of $-\log(x)$.

4.5 Power Functions

• Power Function
  $f(x) = x^p, \quad x \ge 0, \; p \ge 1.$
  Convex in $x$.
  Gradient: $\nabla f(x) = p x^{p-1}$.

Why It’s Convex: On $x>0$, the second derivative $p(p-1)x^{p-2}$ is nonnegative for $p\ge1$. Continuity extends convexity to $x=0$. At that boundary, the right derivative is zero for $p>1$ and one for $p=1$.

• Reciprocal Function
  $f(x) = \frac{1}{x}, \quad x > 0.$
  Convex in $x$.
  Gradient: $\nabla f(x) = -\frac{1}{x^2}$.

Why It’s Convex: Its second derivative $\frac{2}{x^3}$ is positive for $x>0$. This establishes convexity on the stated domain; monotonicity alone would not establish it.

4.6 Entropy and Related Functions

• Negative Entropy
  $f(\mathbf{p}) = \sum_{i=1}^n p_i \log(p_i),\quad p_i \ge 0,\; \sum_i p_i = 1.$
  Convex in $\mathbf{p}$.
  Use $0\log0=0$. Gradient in the positive orthant: $\nabla f(\mathbf{p})=\mathbf{1}+\log(\mathbf{p})$ (elementwise). This formula is not defined at a zero coordinate.

Why It’s Convex: Each term has second derivative $1/p_i>0$ in the interior, and the sum extends continuously to the boundary. Thus negative entropy is convex; entropy, with the opposite sign, is concave.

• Log-Sum-Exp Function
  $f(\mathbf{x}) = \log \bigl(\sum_{i=1}^n e^{x_i}\bigr).$
  Convex, but not strictly convex on all of $\mathbb{R}^n$. Gradient: $\nabla f(\mathbf{x}) = \frac{e^{\mathbf{x}}}{\sum_{i=1}^n e^{x_i}}$ (elementwise).

Why It’s Convex: If $p_i=e^{x_i}/\sum_j e^{x_j}$, the Hessian is $\operatorname{diag}(p)-pp^\top$. For fixed $x,v$, its quadratic form is $\operatorname{Var}_{I\sim\operatorname{Categorical}(p_1,\ldots,p_n)}(v_I)\ge0$, as derived in Part 1. Only the auxiliary index $I$ is random. The identity $f(\mathbf{x}+c\mathbf{1})=f(\mathbf{x})+c$ shows why strict convexity fails on the full space. Being a smooth approximation to a convex function would not, by itself, prove convexity.

4.7 Hinge Loss Function

• Hinge Loss
  

  $$f(x) = \max(0,\, 1 - y \cdot x),\quad y \in \{-1, +1\}.$$

  Scroll to see the full equation →

  
  Convex in $x$.
  Subdifferential:

  $$\partial f(x) = \begin{cases} \{-y\}, & \text{if } 1-yx>0,\\[1mm] \{0\}, & \text{if } 1-yx<0,\\[1mm] \{-ty:0\le t\le1\}, & \text{if } 1-yx=0. \end{cases}$$

  Scroll to see the full equation →

Why It’s Convex: The hinge loss is the pointwise maximum of the two affine functions $0$ and $1-yx$, with the label held fixed.

4.8 Absolute Value and Piecewise Linear Functions

• Absolute Value
  $f(x) = |x|.$
  Convex in $x$.
  Subdifferential: $\partial f(x)=\{\operatorname{sign}(x)\}$ for $x\ne0$, while $\partial f(0)=[-1,1]$.

Why It’s Convex: Using the Definition Check and the triangle inequality,

where $\alpha, \beta \in \mathbb{R}_{\ge 0}$ with $\alpha + \beta = 1$.
This directly satisfies the definition of convexity. Alternatively, one can note $|x| = \max(x, -x)$, which is a pointwise maximum of two affine (linear) functions, ensuring convexity. And away from $x=0$, the Second-Order Condition also holds (the function is piecewise linear with zero curvature).

• ReLU
  $f(x) = \max(0, x).$
  Convex in $x$.
  Subdifferential: $\partial f(x) = \begin{cases} \{1\}, & x>0,\\ [0,1], & x=0,\\ \{0\}, & x<0. \end{cases}$

Why It’s Convex: ReLU is a Pointwise Maximum of the linear function $x$ and constant $0$. Hence, by that rule, it is convex.

4.9 Log-Barrier and Soft Constraints

A log barrier is defined only in the interior of the feasible region and diverges as the boundary is approached. It is therefore different from a finite penalty that allows constraint violations.

For example, consider minimizing a quadratic while requiring a positive variable:

A log barrier function adds a penalty term to the objective that grows large as $x$ approaches the boundary $x=0$. In this case, the barrier term is:

where $\mu > 0$ is a parameter that controls the strength of the barrier. The modified objective function becomes:

As $x$ approaches zero from above, the term $-\mu\ln(x)$ tends to infinity. The objective is undefined for nonpositive inputs, so an algorithm must retain $x>0$. A positive barrier parameter also changes the minimizer; it does not leave the original objective unchanged.

• Log-Barrier Function
  $f(x) = -\log(x), \quad x > 0.$
  Convex in $x$.
  Gradient: $\nabla f(x) = -\frac{1}{x}$.

Why It’s Convex: As above, $\log(x)$ is concave, so $-\log(x)$ is convex. The Second-Order Condition reveals its Hessian $\frac{1}{x^2}$ is > 0 for $x>0$.

• Softplus Function
  $f(x) = \log(1 + e^x).$
  Convex in $x$.
  Gradient: $\nabla f(x) = \frac{1}{1 + e^{-x}}$.

Why It’s Convex: Its second derivative is $e^x/(1+e^x)^2>0$. Equivalently, it is log-sum-exp evaluated at the affine input $(0,x)$. The argument is not that logarithms preserve convexity in general; they do not.

4.10 Distance Functions

• Squared Euclidean Distance
  $f(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_2^2 = (\mathbf{x} - \mathbf{y})^\top (\mathbf{x} - \mathbf{y}).$
  Jointly convex in $(\mathbf{x},\mathbf{y})$. Gradient w.r.t. $\mathbf{x}$: $\nabla f(\mathbf{x}) = 2(\mathbf{x} - \mathbf{y})$.

Why It’s Convex: The difference is an affine function of the pair of vectors, and the squared Euclidean norm is convex. Their composition is therefore jointly convex.

4.11 Matrix Norms and Functions

• Frobenius Norm
  $f(X) = \|X\|_F = \sqrt{\sum_{i,j} X_{ij}^2},\quad X \in \mathbb{R}^{m \times n}.$
  Convex in $X$.
  Gradient, for $X\ne0$: $\nabla f(X)=X/\|X\|_F$. At zero, $\partial f(0)=\{G:\|G\|_F\le1\}$.

Why It’s Convex: The Frobenius norm is the Euclidean norm of the vector containing all matrix entries. The same norm argument therefore applies.

• Log-Determinant Function
  $f(X) = -\log(\det(X)), \quad X \succ 0,\; X \in \mathbb{R}^{n \times n}.$
  Convex on the cone of real symmetric positive-definite matrices. Gradient: $\nabla f(X) = -X^{-1}$.

Why It’s Convex: Along a symmetric perturbation $H$, the second directional derivative is $\operatorname{Tr}(X^{-1}HX^{-1}H)=\|X^{-1/2}HX^{-1/2}\|_F^2\ge0$. This establishes convexity in the matrix argument on the positive-definite cone, not merely in the determinant viewed as a scalar.

4.12 Cross-Entropy Loss Function

• Cross-Entropy Loss
  $f(\mathbf{p};\mathbf{y})=-\sum_{i=1}^n y_i\log(p_i),$ where the target vector is fixed, $y_i\ge0$, and $\sum_i y_i=1$. A one-hot target represents an observed class. We take $p_i>0$ and $\sum_i p_i=1$. Gradient in the positive orthant: $\nabla f(\mathbf{p})=-\mathbf{y}/\mathbf{p}$, with elementwise division.

Why It’s Convex: The Hessian is diagonal with entries $y_i/p_i^2\ge0$. Restricting this convex function to the probability simplex preserves convexity. This is a claim about the probability vector, not arbitrary model parameters.

Final Thoughts

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.