준똘똘
2026. 10. 17. 16:13
2026. 10. 17. 16:13
2.1 Affine set ✍️
- Line: x = θx₁ + (1−θ)x₂, θ ∈ ℝ (내분·외분 모두)
- Affine set: 집합 안 두 점을 지나는 직선 전체가 다시 집합 안에 있는 집합
- 예: { x | Ax = b }
- 판서: Ax₁ = Ax₂ = b 이면 A(θx₁ + (1−θ)x₂) = θb + (1−θ)b = b
- Linear subspace는 0을 지나야 하지만, affine set은 그럴 필요가 없다.
2.2 Convex set
- Line segment: θ ∈ [0, 1]
- 정의: x₁, x₂ ∈ C 이고 0 ≤ θ ≤ 1 이면 θx₁ + (1−θ)x₂ ∈ C
- 예: 육각형은 convex. 오목한 도형, 경계 일부가 빠진 사각형은 convex가 아니다.
2.3 Convex combination, convex hull
- Convex combination: Σ θᵢxᵢ (θᵢ ≥ 0, Σ θᵢ = 1)
- conv S: S의 모든 convex combination의 집합 = S를 포함하는 가장 작은 convex set
- S가 convex이면 conv S = S
2.4 Convex cone ✍️
- Conic combination: θᵢ ≥ 0 만 요구한다. 합이 1이라는 조건은 없다.
- Convex cone: conic combination이 다시 집합 안에 있는 집합
- 판서: αy₁ + (1−α)y₂ 의 계수 αθᵢ + (1−α)θᵢ′ ≥ 0 이므로 convex이기도 하다.
2.5 Hyperplane, halfspace ✍️ ⭐
- Hyperplane: { x | aᵀx = b }, a ≠ 0 (a는 법선벡터). aᵀ(x − x₀) = 0 으로도 쓴다.
- Halfspace: { x | aᵀx ≤ b }
- Hyperplane: aᵀ(θx₁ + (1−θ)x₂) = θb + (1−θ)b = b
- θ ∈ ℝ 에서도 성립하므로 affine이면서 convex
- Halfspace: θaᵀx₁ + (1−θ)aᵀx₂ ≤ b
- θ ≥ 0, 1−θ ≥ 0 일 때만 성립하므로 convex이지만 affine은 아니다.
- ⭐ 교수님이 이 증명 직전에 "연습 시험에 쓸 수도"라고 언급
2.6 Ball, ellipsoid ✍️
- Ball: { x | ‖x − xc‖₂ ≤ r } = { xc + ru | ‖u‖₂ ≤ 1 } (xc는 중심)
- 임의의 norm ball도 convex:
- ‖θx₁ + (1−θ)x₂ − xc‖ ≤ θ‖x₁ − xc‖ + (1−θ)‖x₂ − xc‖ ≤ r
- 중심 xc를 θxc + (1−θ)xc 로 쪼갠 뒤 triangle → homogeneity 순서로 쓴다.
- θ ≥ 0 이라 절댓값을 쓸 필요가 없다.
- 1-norm ball은 다이아몬드, ∞-norm ball은 정사각형
- Ellipsoid: { x | (x − xc)ᵀ P⁻¹ (x − xc) ≤ 1 }, P는 대칭 양정치(S₊₊ⁿ)
- 또는 { xc + Au | ‖u‖₂ ≤ 1 }
- 판서: P = AAᵀ, u = A⁻¹(x − xc) 로 두면 두 표현이 같다.
2.7 Norm, norm cone
- Norm 조건
- ‖x‖ ≥ 0, x = 0 일 때만 0
- ‖tx‖ = |t|‖x‖
- ‖x + y‖ ≤ ‖x‖ + ‖y‖
- Norm cone: { (x, t) | ‖x‖ ≤ t }
- 2-norm이면 second-order cone(아이스크림 콘)
- t를 고정한 단면이 반지름 t인 원
2.8 Polyhedron
- { x | Ax ⪯ b, Cx = d } = 유한 개 halfspace와 hyperplane의 교집합 → convex (2.11)
2.9 PSD cone ✍️
- Sⁿ: 대칭행렬, S₊ⁿ: PSD (zᵀXz ≥ 0), S₊₊ⁿ: PD (z ≠ 0 이면 zᵀXz > 0)
- 판서: zᵀ(θ₁X₁ + θ₂X₂)z = θ₁zᵀX₁z + θ₂zᵀX₂z ≥ 0 → convex cone
- 행렬도 점처럼 볼록성을 따질 수 있다.
2.10 집합이 convex임을 보이는 3가지 방법
- 정의 대입 (아주 단순한 집합에만)
- convex function 이용 (sublevel set, 3장)
- 단순한 convex set에 보존 연산 적용 ← 주로 이 방법
2.11 교집합 ✍️
- 임의 개수의 convex set의 교집합은 convex
- 두 점이 교집합 안 → 각 Cᵢ 안 → 선분도 각 Cᵢ 안 → 교집합 안
- 예: { x | |p(t)| ≤ 1, |t| ≤ π/3 }, p(t) = Σₖ xₖ cos kt
- t를 고정하면 slab(halfspace 2개)
- 모든 t에 대한 slab의 교집합이므로 convex
2.12 Affine mapping ✍️ ⭐
- f(x) = Ax + b 이면 상 f(S)와 역상 f⁻¹(C) 모두 convex를 유지한다.
- 판서:
- yᵢ = f(xᵢ) 인 xᵢ ∈ S 가 존재
- θy₁ + (1−θ)y₂ = f(θx₁ + (1−θ)x₂)
- 괄호 안의 점이 S 안에 있다.
- ⭐ 교수님: "그 점이 S에 속하는 것까지 써야 명확하다."
- 예: scaling·translation, 좌표 projection. cᵀS = { cᵀx | x ∈ S } 는 구간
- LMI 해집합 { x | x₁A₁ + … + xₘAₘ ⪯ B }
- 사상 x ↦ B − Σ xᵢAᵢ 에 대한 PSD cone의 역상
- Hyperbolic cone { x | xᵀPx ≤ (cᵀx)², cᵀx ≥ 0 }
- 사상 x ↦ (P^(1/2)x, cᵀx) 에 대한 second-order cone의 역상
- 교수님은 교집합으로 설명했지만, y ≤ (cᵀx)² 쪽 집합이 convex가 아니다. 답안은 역상 논리로 쓰는 게 안전하다.
2.13 Perspective, linear-fractional
- Perspective: P(x, t) = x/t, t > 0
- 한 점(카메라)에서 본 그림자처럼, 같은 반직선 위의 점이 한 점으로 모인다.
- Linear-fractional: f(x) = (Ax + b)/(cᵀx + d), 분모 > 0
- 둘 다 convex set의 상과 역상이 convex다.
2.14 Proper cone, generalized inequality ✍️
- Proper cone = convex cone + closed + solid(내부가 비지 않음) + pointed(직선을 포함하지 않음)
- 예
- ℝ₊ⁿ
- S₊ⁿ
- [0, 1] 위 비음 다항식의 계수 집합. 판서: θ₁p₁(t) + θ₂p₂(t) ≥ 0
- x ⪯ₖ y ⟺ y − x ∈ K, strict는 y − x ∈ int K
- ℝ₊ⁿ 이면 성분별 부등식, S₊ⁿ 이면 행렬 부등식. 이 두 경우는 첨자 K를 생략한다.
- 실수 부등식과 비슷한 성질: x ⪯ₖ y, u ⪯ₖ v 이면 x + u ⪯ₖ y + v
2.15 Separating, supporting hyperplane (개론)
- Separating: C, D가 nonempty·disjoint·convex이면 a ≠ 0, b가 존재해서
- C 쪽은 aᵀx ≤ b, D 쪽은 aᵀx ≥ b
- Strict 분리에는 추가 조건이 필요 (예: C가 closed, D가 한 점)
- Supporting hyperplane: 경계점 x₀ 에서 모든 x ∈ C 에 대해 aᵀx ≤ aᵀx₀