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.
Where it lands in Jayverse
- Verex: test the LMSR cost function's convexity whenever b or the outcome set changes. Numerically verify the Hessian stays PSD as a guard, so an accidental non-convex variant never reaches the quote centers.
- Verex: decide whether the CLOB layer enforces the same convexity guarantee. No-crossed-quotes-create-arbitrage is a design invariant that follows from convexity, so encode it as a check rather than assuming it holds.
- Auditor: publish the convexity check as a documented invariant. "LMSR's cost function is convex, verified by [test]" belongs in the methodology file — arbitrage-freeness is only checkable by users if the check itself is published.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| lie within | ~ 안에 놓이다, 포함되다 · 두 점을 잇는 선분이 집합 안에 완전히 들어갈 때. "lies entirely within C" |
| preserved under | ~ 연산에서도 보존되는 · 어떤 성질이 특정 연산을 거쳐도 유지될 때. "Convexity is preserved under several operations" |
| fall back on | ~에 의지하다, 차선책으로 쓰다 · 더 나은 방법이 없을 때 대안으로 쓸 수밖에 없는 상황. "have to fall back on an initialization-dependent heuristic" |
| at the modeling stage | 모델링 단계에서 · 문제를 수식으로 세우는 초기 단계를 가리킬 때. "at the modeling stage" |
| fork in the road | 갈림길, 결정적 분기점 · 이후 전략이 완전히 달라지는 선택 지점을 비유할 때. "the key fork in the road for optimization work" |
| well understood | 잘 알려져 있는, 이론적으로 정리된 · 학계에서 이미 충분히 규명된 조건을 말할 때. "duality holds are well understood" |
| a global lower bound on | ~에 대한 전역 하한 · 어떤 함수 전체 영역에서 항상 성립하는 최솟값 경계. "a global lower bound on the function" |
| PSD | 양의 준정부호(Positive Semidefinite) · 헤시안 행렬이 이 조건을 만족하면 함수가 볼록(convex)임을 보장하는 2차 조건. "the Hessian is positive semidefinite (PSD)" |
| LMSR | 로그 시장 스코어링 규칙(Logarithmic Market Scoring Rule) · 예측시장에서 흔히 쓰는 자동화 마켓메이커 비용함수, 로그-합-지수 형태를 가짐. "LMSR's cost function has the log-sum-exp form" |
| epigraph | 에피그래프(함수 그래프 위쪽 영역 전체를 포함하는 집합) · 함수가 볼록임을 기하학적으로 정의하는 동치 조건. "f's epigraph is a convex set" |
| Hessian | 헤시안 행렬(함수의 2차 편미분들로 이루어진 행렬) · 두 번 미분 가능한 함수의 볼록성을 판별하는 2차 조건에 쓰임. "if f is twice differentiable, there's a second-order test" |
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/.