15.093 - Recitation 1 1 Convex Functions and Convex Sets A set A is convex if ∀x, y ∈ A, we have λx + (1 − λ)y ∈ A. A function f : R → R is convex if ∀x, y ∈ R, we have f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀λ ∈ [0, 1]. 2 Optimization Problems min s/t f (x) x ∈ X. Commonly X = {x : gi (x) ≤ 0, i = 1, . . . , m}. 2.1 Convex Optimization Problem A convex optimization problem has: • convex objective function f • X a convex set, e.g. constraints gi (x) ≤ 0, where gi is convex 2.2 Linear Optimization Problem An LP (Linear Program) is a special case of a convex programming problem, and has: • linear objective function c� x • linear constraints a�i x ≤ bi then X is a polyhedron – the intersection of a ﬁnite number of halfspaces 1 2.2.1 Standard Form Any LP can be transformed into standard form: min c� x s/t Ax = x ≥ 3 3.1 b 0 Some LP Modeling Tricks Absolute Value Function � Minimizing nj=1 cj |xj |, where cj > 0, ∀j ∈ {1, . . . , n}, subject to Ax = b can be written as the following LP: min c� (x+ + x− ) s/t A(x+ − x− ) = x+ , x− ≥ b 0. ∗ −∗ Check for correctness: when x+ j > 0, xj = 0 and vice-versa. Why? Alternatively, we can write min s/t 3.2 c� z zj ≥ zj ≥ Ax = xj −xj b. Piecewise Linear Convex Functions Minimize f (x) subject to Ax = b, x ≥ 0, where ⎧ ⎨ c1 x − d1 , x ≤ u1 , c2 x − d2 , u1 ≤ x ≤ u2 , f= ⎩ c3 x − d3 , u2 ≤ x. ⎧ 1 x ≤ 2, ⎨ 2 x, x − 1, 2 ≤ x ≤ 3, we can write Letting for example f (x) = ⎩ 3x − 7, 3 ≤ x, min s/t z z z z Ax x ≥ ≥ ≥ = ≥ 2 1 x 2 x−1 3x − 7 b 0. Another interesting approach if x is scalar is to let x = x1 + x2 + x3 , and write min s/t 1 1 x + 2 1 x2 + 3x3 A(x + x2 + x3 ) 1 0 ≤ x ≤ 2, 0 ≤ x2 ≤ 1, x3 ≥ 0. = b Check for correctness: when xi∗ > 0, xi−1∗ = ui−1 . Why? 4 AMPL AMPL (A Mathematical Programming Language) is a high-level programming language for writing and solving mathematical programs (linear and non-linear, in continuous and discrete variables). AMPL itself does not solve the problems, instead it calls an external solver (such as CPLEX) to solve the optimization problem. An AMPL program consists of two parts: • a model ﬁle (.mod ﬁle), and • a data ﬁle (.dat ﬁle) The model ﬁle writes the linear program using the grammar of AMPL and it deﬁnes various sets, parameters, variables, objective and constraints. The data ﬁle provides data for the model ﬁle. 3