Convex Sets and Testing for Convex Functions TODO
Concept
A set C is convex if the line segment joining any two points of C lies entirely within C, and a function f is convex if its domain is convex and f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y) holds for any two points and any θ between 0 and 1. An equivalent, geometric characterization is that f's epigraph is a convex set. If f is differentiable, there's a first-order test — the tangent plane at any point is a global lower bound on the function — and if f is twice differentiable, there's a second-order test: the Hessian is positive semidefinite (PSD). Convexity is preserved under several operations, notably non-negative weighted sums, composition with affine maps, pointwise supremum, and composition with a convex, non-decreasing function. In convex problems, a local minimum is automatically the global minimum, and the conditions under which strong duality holds are well understood — so whether a problem can be made convex is often the key fork in the road for optimization work.
Whether a problem is convex determines whether you can use a solver that guarantees a global optimum or have to fall back on an initialization-dependent heuristic, so you need to be able to tell at the modeling stage.
Code & Formula
# Day 34 — 볼록집합/볼록함수 판별
# 정의(선분 부등식)와 2차 조건(Hessian이 준정부호)으로 볼록함수 여부를 판별한다.
import numpy as np
def is_convex_by_definition(f, x, y, n_thetas=11):
"""f(theta*x + (1-theta)*y) <= theta*f(x) + (1-theta)*f(y) 가 모든 theta에서 성립하는지 확인."""
for theta in np.linspace(0, 1, n_thetas):
lhs = f(theta * x + (1 - theta) * y)
rhs = theta * f(x) + (1 - theta) * f(y)
if lhs > rhs + 1e-9:
return False
return True
def f_convex(x): # f(x) = x^2, 볼록함수
return x ** 2
def f_nonconvex(x): # f(x) = -x^2 + sin(4x)*3, 오목/비볼록 성격
return -(x ** 2) + 3 * np.sin(4 * x)
x1, x2 = -2.0, 3.0
print(f"f(x)=x^2 은 [{x1},{x2}]에서 볼록? -> {is_convex_by_definition(f_convex, x1, x2)}")
print(f"f(x)=-x^2+3sin(4x) 는 [{x1},{x2}]에서 볼록? -> {is_convex_by_definition(f_nonconvex, x1, x2)}")
# 다변수: Hessian이 준정부호(고유값이 모두 0 이상)이면 볼록
def hessian_psd(H):
eigenvalues = np.linalg.eigvalsh(H)
return np.all(eigenvalues >= -1e-9), eigenvalues
# g(x,y) = x^2 + 2y^2 의 Hessian은 상수: [[2,0],[0,4]]
H_convex = np.array([[2.0, 0.0], [0.0, 4.0]])
psd, eigs = hessian_psd(H_convex)
print(f"\ng(x,y)=x^2+2y^2 의 Hessian 고유값 = {eigs} -> 준정부호(볼록)? {psd}")
# h(x,y) = x^2 - y^2 (안장점 형태) 의 Hessian
H_saddle = np.array([[2.0, 0.0], [0.0, -2.0]])
psd2, eigs2 = hessian_psd(H_saddle)
print(f"h(x,y)=x^2-y^2 의 Hessian 고유값 = {eigs2} -> 준정부호(볼록)? {psd2}")
Exercise
Derive the Hessian of the log-sum-exp function by hand and numerically verify vᵀHv ≥ 0 for arbitrary vectors v, then separately confirm the same conclusion using only the convexity-preservation rules.
Practical Connection
LMSR's cost function has the log-sum-exp form, so it's convex — and that convexity is exactly what guarantees prices are well-defined as per-outcome probabilities and that no risk-free arbitrage exists in the structure.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.