Linear Programming and Duality Intuition TODO
Concept
Linear programming (LP) maximizes or minimizes a linear objective function subject to linear inequality constraints; the feasible region is a convex polytope, and if an optimum exists, it's achieved at one of its vertices. Every LP has a paired dual problem: weak duality says any feasible dual solution bounds the primal optimum, and strong duality says that when both sides are feasible, the two optimal values coincide. A dual variable represents the shadow price of its constraint — how much the objective improves if that constraint is relaxed by one unit. Complementary slackness ties the two together: a constraint with slack left over has a shadow price of 0, and any constraint with a positive price must be tight. So in an allocation problem, the primal answers who gets how much, while the dual simultaneously produces the prices that support that allocation.
In problems that divide up a scarce resource — auctions, blockspace allocation — the proof that an allocation is optimal and the price charged to participants come out of the same dual structure, and knowing that is what lets you settle an argument with numbers instead of opinions.
Code & Formula
# Day 13: 선형계획과 쌍대성 직관 — 경매·배분 문제의 원문제/쌍대문제
# 2변수 LP를 꼭짓점 열거로 풀고, 쌍대 LP도 같은 방식으로 풀어 강쌍대성(최적값 일치)을 확인한다.
def line_intersections(constraints):
pts = []
for i in range(len(constraints)):
for j in range(i + 1, len(constraints)):
a1, b1, _, c1 = constraints[i]
a2, b2, _, c2 = constraints[j]
det = a1 * b2 - a2 * b1
if abs(det) < 1e-9:
continue
pts.append(((c1 * b2 - c2 * b1) / det, (a1 * c2 - a2 * c1) / det))
return pts
def feasible(pt, constraints, tol=1e-6):
x, y = pt
for a, b, op, c in constraints:
val = a * x + b * y
if op == "<=" and val > c + tol:
return False
if op == ">=" and val < c - tol:
return False
return True
def solve_lp_2d(constraints, obj, maximize):
candidates = [p for p in line_intersections(constraints) if feasible(p, constraints)]
key = lambda p: obj[0] * p[0] + obj[1] * p[1]
best = max(candidates, key=key) if maximize else min(candidates, key=key)
return best, key(best)
# 원문제: maximize x + 2y s.t. x+y<=4, x+3y<=6, x,y>=0 (자원 배분: 두 재화를 두 제약 아래 최대화)
primal_constraints = [(1, 1, "<=", 4), (1, 3, "<=", 6), (1, 0, ">=", 0), (0, 1, ">=", 0)]
p_pt, p_val = solve_lp_2d(primal_constraints, (1, 2), maximize=True)
# 쌍대문제: minimize 4u + 6v s.t. u+v>=1, u+3v>=2, u,v>=0 (쌍대변수 = 각 제약의 잠재가격)
dual_constraints = [(1, 1, ">=", 1), (1, 3, ">=", 2), (1, 0, ">=", 0), (0, 1, ">=", 0)]
d_pt, d_val = solve_lp_2d(dual_constraints, (4, 6), maximize=False)
print(f"원문제 최적해 (x,y) = ({p_pt[0]:.2f}, {p_pt[1]:.2f}), 최적값 = {p_val:.2f}")
print(f"쌍대문제 최적해 (u,v) = ({d_pt[0]:.2f}, {d_pt[1]:.2f}), 최적값 = {d_val:.2f}")
print(f"강쌍대성 확인 (원문제 최적값 == 쌍대문제 최적값): {abs(p_val - d_val) < 1e-6}")
docs/code/algorithms/algorithms-13.py
Exercise
Formulate a small allocation problem with 5 to 10 bids as an LP, solve it with a solver, extract the dual values, then slightly relax one constraint and confirm the change in the objective matches its dual value.
Practical Connection
Batching orders and matching them at a single uniform clearing price can be expressed as an LP where the dual price is exactly that clearing price — a useful exercise for re-reading Verex's CLOB matching logic through an optimization lens.
Where it lands in Jayverse
- Verex: extract the dual value from the CLOB's uniform-clearing-price batch auction and use it as the settlement price. Re-read the matching logic through this lens, and use complementary slackness as a sanity check — a matched order should have a binding constraint, an unmatched one should not.
- OFA: formulate the solver auction's allocation as an LP and pay solvers the dual (shadow) price. The fee/rebate a solver earns should fall out of relaxing its winning bid's constraint by one unit, not an arbitrary schedule.
- Number: publish a small worked LP-duality example (5-10 bids) as a reading. It's directly reusable for auditing Verex's clearing price later, so it earns its place on Number rather than staying a one-off exercise.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| shadow price | 잠재가격(그림자 가격) · 제약을 한 단위 완화했을 때 목적함수가 얼마나 개선되는지 나타내는 값 · "A dual variable represents the shadow price" |
| bounds | (상한·하한을) 정하다, 제한하다 · 실행가능한 해가 특정 값을 넘지 못하게 묶는다는 뜻 · "any feasible dual solution bounds the primal optimum" |
| tight | (제약이) 여유 없이 꽉 찬 상태 · 등호로 딱 맞아떨어져 여유가 없는 제약을 가리킴 · "any constraint with a positive price must be tight" |
| settle an argument with numbers | 숫자로 논쟁을 매듭짓다 · 말이 아니라 계산 결과로 결론을 낸다는 뜻 · "settle an argument with numbers instead of opinions" |
| relaxed by one unit | (제약을) 한 단위 완화하다 · 한계값의 변화를 계산할 때 쓰는 표현 · "if that constraint is relaxed by one unit" |
| coincide | (두 값이) 일치하다 · 서로 다른 방식으로 구한 결과가 같아진다는 뜻 · "the two optimal values coincide" |
| LP | 선형계획법(Linear Programming) · 선형 목적함수를 선형 제약 아래 최적화하는 문제, 이 글의 주제. "Linear programming (LP) maximizes or minimizes" |
| CLOB | 중앙집중형 지정가 주문장(Central Limit Order Book) · 거래소 매칭 엔진 구조, Verex의 주문 매칭 로직을 가리킴. "re-reading Verex's CLOB matching logic" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-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/.