Convex Optimization — Boyd & Vandenberghe 4. Convex optimization problems • optimization problem in standard form • convex optimization problems • quasiconvex optimization • linear optimization • quadratic optimization • geometric programming • generalized inequality constraints • semidefinite programming • vector optimization 4–1Optimization problem in standard form minimize f0(x) subject to fi(x) ≤ 0, i = 1, . . . , m hi(x) = 0, i = 1, . . . , p • x ∈ Rn is the optimization variable f0 : Rn R is the objective or cost function • →fi : Rn R, i = 1, . . . , m, are the inequality constraint f unctions • →hi : Rn R are the equality constraint functions • →optimal value: ⋆ p = inf{f0(x) | fi(x) ≤ 0, i = 1, . . . , m, hi(x) = 0, i = 1, . . . , p} ⋆ • p = ∞ if problem is infeasible (no x satisfies the constraints) ⋆ • p = −∞ if problem is unbounded below Convex optimization problems 4–2Optimal and locally optimal points x is feasible if x ∈ dom f0 and it satisfies the constraints a feasible x is optimal if f0(x) = p ⋆ ; Xopt is the set of optimal points x is locally optimal if there is an R > 0 such that x is optimal for minimize ( over z) f0(z) subject to fi(z) ≤ 0, i = 1, . . . , m, hi(z) = 0, i = 1, . . . , p �z −x�2 ≤ R examples (with n = 1, m = p = 0) ⋆ • f0(x) = 1/x, dom f0 = R++: p = 0, no optimal point ⋆ • f0(x) = −log x, dom f0 = R++: p = −∞ ⋆ • f0(x) = x log x, dom f0 = R++: p = −1/e, x = 1/e is optimal f0(x) = x3 − 3x, p ⋆ = −∞, local optimum at x = 1• Convex optimization problems 4–3� � Implicit constraints the standard form optimization problem has an implicit constraint mp x ∈ D = dom fi ∩ dom hi, i=0 i=1 • we call D the domain of the problem • the constraints fi(x) ≤ 0, hi(x) = 0 are the explicit constraints • a problem is unconstrained if it has no explicit constraints (m = p = 0) example: minimize f0(x) = − �ik =1 log(bi − aiTx) is an unconstrained problem with implicit constraints aiTx < bi Convex optimization problems 4–4Feasibility problem find x subject to fi(x) ≤ 0, i = 1, . . . , m hi(x) = 0, i = 1, . . . , p can be considered a special case of the general problem with f0(x) = 0: minimize 0 subject to fi(x) ≤ 0, i = 1, . . . , m hi(x) = 0, i = 1, . . . , p ⋆ • p = 0 if constraints are feasible; any feasible x is optimal ⋆ • p = ∞ if constraints are infeasible Convex optimization problems 4–5Convex optimization problem standard form convex optimization problem minimize f0(x) subject to fi(x) ≤ 0, i = 1, . . . , m aiTx = bi, i = 1, . . . , p • f0, f1, . . . , fm are convex; equality constraints are affine • problem is quasiconvex if f0 is quasiconvex (and f1, . . . , fm convex) often written as minimize f0(x) subject to fi(x) ≤ 0, i = 1, . . . , m Ax = b important property: feasible set of a convex optimization problem is convex Convex optimization problems 4–6example minimize f0(x) = x21 + x22 subject to f1(x) = x1/(1 + x22) ≤ 0 h1(x) = (x1 + x2)2 = 0 • f0 is convex; feasible set {(x1, x2) | x1 = −x2 ≤ 0} is convex • not a convex problem (according to our definition): f1 is not convex, h1 is not affine • equivalent (but not identical) to the convex problem minimize x12 + x22 subject to x1 ≤ 0 x1 + x2 = 0 Convex optimization problems 4–7Local and global optima any locally optimal point of a convex problem is (globally) optimal proof: suppose x is locally optimal and y is optimal with f0(y) < f0(x) x locally optimal means there is an R > 0 such that z feasible, �z − x�2 ≤ R = ⇒ f0(z) ≥ f0(x) consider z = θy + (1 − θ)x with θ = R/(2�y −x�2) • �y − x�2 > R, so 0 < θ < 1/2 • z is a convex combination of two feasible points, hence also feasible • �z −x�2 = R/2 and f0(z) ≤ θf0(x) + (1 − θ)f0(y) < f0(x) which contradicts our assumption that x is locally optimal Convex optimization problems 4–8Optimality criterion for differentiable f0 x is optimal if and only if it is feasible and ∇f0(x)T(y − x) ≥ 0 for all feasible y −∇f0(x) X x if nonzero, ∇f0(x) defines a supporting hyperplane to feasible set X at x Convex optimization problems 4–9� • unconstrained problem: x is optimal if and only if x ∈ dom f0, ∇f0(x) = 0 • equality constrained problem minimize f0(x) subject to Ax = b x is optimal if and only if there exists a ν such that x ∈ dom f0, Ax = b, ∇f0(x) + ATν = 0 • minimization over nonnegative orthant minimize f0(x) subject to x � 0 x is optimal if and only if ∇f0(x)i ≥ 0 xi = 0 x ∈ dom f0, x � 0, ∇f0(x)i xi > 0= 0 Convex optimization problems 4–10Equivalent convex problems two problems are (informally) equivalent if the solution of one is readily obtained from the solution of the other, and vice-versa some common transformations that preserve convexity: • eliminating equality constraints minimize f0(x) subject to fi(x) ≤ 0, i = 1, . . . , m Ax = b is equivalent to minimize ( over z) f0(F z + x0) subject to fi(F z + x0) ≤ 0, i = 1, . . . , m where F and x0 are such that Ax = b x = F z + x0 for some z⇐⇒ Convex optimization problems 4–11• introducing equality constraints minimize f0(A0x + b0) subject to fi(Aix + bi) ≤ 0, i = 1, . . . , m is equivalent to minimize ( over x, yi) f0(y0) subject to fi(yi) ≤ 0, i = 1, . . . , m yi = Aix + bi, i = 0, 1, . . . , m • introducing slack variables for linear inequalities minimize f0(x) subject to aiTx ≤ bi, i = 1, . . . , m is equivalent to minimize ( over x, s) f0(x) subject to aTi x + si = bi, i = 1, . . . , m si ≥ 0, i = 1, . . . m Convex optimization problems 4–12• epigraph form: standard form convex problem is equivalent to minimize ( over x, t) t subject to f0(x) − t ≤ 0 fi(x) ≤ …