University:
The University Of Western Ontario
Course:
MATH 3020A | Introduction to Abstract Algebra
Academic year:

2024
Views:

86

Pages:

4
Author:

Kyuwon J.

1. Convex Sets A set C ⊆ Rn is convex if, for any x1 , x2 ∈ C and λ ∈ [0, 1], the point λx1 + (1 − λ)x2 ∈ C. Examples of convex sets: • A line segment or plane. • A polygon without holes. • A disk or sphere. 2. Convex and Concave Functions A function f : B → R is: • Convex if: f (λb0 + (1 − λ)b1 ) ≤ λf (b0 ) + (1 − λ)f (b1 ). • Concave if: f (λb0 + (1 − λ)b1 ) ≥ λf (b0 ) + (1 − λ)f (b1 ). 3. Linear Programming (LP) Linear programming is the process of optimizing (maximizing or minimizing) a linear objective function subject to linear constraints. Standard Form: maximize cT x, subject to Ax = b, x ≥ 0. Dual Problem: For a primal LP, the dual is: minimize bT y, subject to AT y ≥ c. 1 4. Subgradients For a concave function g(b), a vector −ȳ is a subgradient of g(b) at b if: g(z) ≥ g(b) − ȳ T (z − b), ∀z ∈ B. 5. Strong Duality If the primal and dual problems are both feasible, the optimal values of the primal and dual are equal: Optimal value of primal = Optimal value of dual. Practice Problems and Solutions Problem 1: Convex Sets Question: Verify whether the set C = {(x1 , x2 ) | x21 + x22 ≤ 4} is convex. Solution: 1. Consider two points (x1 , x2 ), (y1 , y2 ) ∈ C. 2. For λ ∈ [0, 1], calculate: λ(x1 , x2 ) + (1 − λ)(y1 , y2 ) = (λx1 + (1 − λ)y1 , λx2 + (1 − λ)y2 ). 3. Check the condition: (λx1 + (1 − λ)y1 )2 + (λx2 + (1 − λ)y2 )2 ≤ 4. 4. Expand and simplify: λ(x21 + x22 ) + (1 − λ)(y12 + y22 ) ≤ 4, which is true since (x21 + x22 ) ≤ 4 and (y12 + y22 ) ≤ 4. 5. Therefore, C is convex. 2 Problem 2: Duality and Optimality Question: Solve the following LP and its dual: maximize 2x1 + 3x2 x1 + 2x2 ≤ 6, subject to 3x1 + 2x2 ≤ 12, x1 , x2 ≥ 0. Solution: 1. Step 1: Write the dual. The dual problem is: y1 + 3y2 ≥ 2, subject to 2y1 + 2y2 ≥ 3, y1 , y2 ≥ 0. minimize 6y1 + 12y2 2. Step 2: Solve the primal. • Convert inequalities to equations using slack variables: x1 + 2x2 + s1 = 6, 3x1 + 2x2 + s2 = 12, x1 , x2 , s1 , s2 ≥ 0. • Use the Simplex Method to find the optimal solution: x1 = 2, x2 = 2, optimal value = 2(2) + 3(2) = 10. 3. Step 3: Solve the dual. • Solve the dual problem using constraints: y1 = 0.5, y2 = 1, optimal value = 6(0.5) + 12(1) = 10. • Verify strong duality: Primal optimal value = Dual optimal value = 10. 3 Problem 3: Subgradients Question: Prove that −ȳ is a subgradient of g(b) = −f (b) for b ∈ B and ȳ optimal for the dual. Solution: 1. By strong duality: bT ȳ = f (b) = −g(b). 2. For any z ∈ B, we need to show: g(z) ≥ g(b) − ȳ T (z − b). 3. Substituting g(b) = −f (b), the inequality becomes: −f (z) ≥ −f (b) − ȳ T (z − b). 4. Simplify: f (z) ≤ f (b) + ȳ T (z − b). 5. Since f (z) = cT x and ȳ T A ≥ cT , we conclude: g(z) ≥ g(b) − ȳ T (z − b). 4