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

2024
Views:

342

Pages:

4
Author:

Kyuwon J.

1 Module 1: Optimization Basics Definition of Optimization An optimization problem involves selecting the best solution from a set of feasible solutions. This can be expressed as: Optimize f (x) subject to gi (x) ≤ 0, hj (x) = 0. Feasibility - A solution is feasible if it satisfies all constraints gi (x) ≤ 0 and hj (x) = 0. - The set of all feasible solutions forms the feasible region. Optimal Solution - An optimal solution is a feasible solution that minimizes (or maximizes) the objective function f (x). 2 Module 2: Linear Programs (LPs) Definition of Linear Programs A Linear Program (LP) is defined as: Optimize cT x subject to Ax ≤ b, x ≥ 0. Canonical Form An LP is in canonical form for basis B if: 1. AB = I, where AB is the submatrix of A corresponding to basis B. 2. cB = 0, where cB are the coefficients of the basic variables in the objective function. Key Proposition If a linear program has a feasible solution, the Simplex method will: 1. Terminate with an optimal solution, or 2. Prove the problem is unbounded. 1 Geometric Interpretation - The feasible region of an LP is a polyhedron. - Basic solutions correspond to the vertices (extreme points) of this polyhedron. 3 Module 3: Duality Theory Weak Duality Theorem For any feasible solutions x (primal) and y (dual), the following holds: cT x ≤ bT y. If cT x = bT y, then both x and y are optimal. Strong Duality Theorem If the primal problem has an optimal solution, the dual also has an optimal solution, and their objective values are equal: cT x = bT y. Complementary Slackness Primal and dual solutions are optimal if and only if: yi · si = 0, where si is the slack variable for the i-th constraint. 4 Module 4: Integer Programming (IP) Definition of Integer Programming An Integer Program (IP) is an optimization problem where some or all decision variables are required to take integer values. Proposition Integer programming is NP-hard, meaning it is computationally challenging and often unsolvable in polynomial time for large instances. Meyer’s Theorem The convex hull of all integer points in a rational polyhedron is itself a polyhedron. 2 Convex Hulls The convex hull of a set of points C is the smallest convex set that contains C. It can be visualized as the ”tightest” convex shape that encloses all points in C. 5 Module 5: Nonlinear Programming (NLP) Definition of Nonlinear Programs A Nonlinear Program (NLP) is expressed as: Optimize f (x) subject to gi (x) ≤ 0, hj (x) = 0, where f (x) or gi (x) are nonlinear. Proposition: Convexity and Global Optima If: 1. The feasible region is convex, and 2. f (x) is a convex function, then any local optimum is also a global optimum. 6 Module 6: Convexity and KKT Theorem Convex Functions A function f (x) is convex if: f (λa + (1 − λ)b) ≤ λf (a) + (1 − λ)f (b), ∀λ ∈ [0, 1]. Supporting Hyperplane Proposition For a convex set C, there exists a hyperplane that touches C at one point and lies entirely on one side of C. Karush-Kuhn-Tucker (KKT) Conditions For a convex optimization problem, if a solution satisfies the KKT conditions, it is optimal. The conditions are: 3 1. Primal feasibility: gi (x) ≤ 0, hj (x) = 0. 2. Dual feasibility: λi ≥ 0. 3. Complementary slackness: λi gi (x) = 0. P P 4. Stationarity: ∇f (x) + i λi ∇gi (x) + j µj ∇hj (x) = 0. 4