Optimization Methods - Recitation 1

Recitation 1 1 Linear Programming 1.1 Linearity The general optimization problem is min s.t. f (x1 , . . . , xn ) (1) gi (x1 , . . . , xn ) ≤ bi , i = 1, m A linear programming problem is an optimization problem with linear functions f and gi , i = 1, m. A linear function has two properties, superposition and homegeneity: - Superposition: f (x + y) = f (x) + f (y) ∀x, y - Homogeneity: f (αx) = αf (x) ∀α What is not a linear programming problem? min s.t. x
Qx Ax = b x≥0 min s.t. �n i=1 ci |xi | Ax ≥ b 1.2 (2) Problem Formulation Steps to formulate a problem: - Analyze input data - Choose decision variables (what is under control) - Formulate objective function - Formulate all constraints 1 (3) Example 1 Multicommodity path-flow formulation In a given network, there are K origin-destination(OD) pair. Each OD pair k has a set of paths P k and a demand dk . Each edge e in the network is associated with a cost ce and a capacity ue . The problem is to minimize the total cost while satisfying the demand. Example 2 2 Formulations with absolute values Geometry of LO 2.1 Convexity and Polyhedra Convex functions A function f : Rn → R is convex if: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ Rn , λ ∈ [0, 1] (4) Convex sets A set S ⊂ Rn is convex if λx + (1 − λ)y ∈ S for all x, y ∈ S, λ ∈ [0, 1]. Convex hulls be k vectors in Rn . The convex hull� of these k vectors is the set of all of their convex Let x1 , . . . , xk � k combinations, ki=1 λi xi , λi ≥ 0 for all i = 1, k and i=1 λi = 1. Polyhedra A polyhedron is a set P = {x ∈ Rn |Ax ≥ b}, A is a m × n matrix and b ∈ Rm . Prove that each polyhedron is a convex set in Rn . 2.2 Extreme Points, Vertices, and Basic Feasible Solutions Let P be a polyhedron, P = {x ∈ Rn |Ax ≥ b}. Extreme points x ∈ P is an extreme point of P if there are no y, z ∈ P , y, z = x and λ ∈ [0, 1] such that x =  λy+(1−λ)z. Vertices x ∈ P is a vertex of P if ∃c ∈ Rn : c
x < c
y ∀y ∈ P, y = x. Basic feasible solutions x ∈ P is a basic feasible solution if: 1. All equality constraints are active 2. There are n active constraints that are linearly independent 3. All constraints are satisfied If P = ∅, then extreme point, vertex, and basic feasible solution definitions are equivalent. 2 3 Simplex Method I 3.1 Basic solutions, basic variables, bases How to construct a basic solution of a polyhedron in standard form, P = {x ∈ Rn |Ax = b, x ≥ 0}? For a standard form polyhedron constructed from P = {x ∈ Rn |Ax ≤ b} using slack variables, how to select basic and nonbasic variables? 3.2 Optimality conditions A basis B is said to be optimal if: 1. B −1 b ≥ 0 (feasibility) 2. c
= c
− c
B B −1 A ≥ 0
(optimality) 3