Convex Optimization — Boyd & Vandenberghe 11. Equality constrained minimization • equality constrained minimization • eliminating equality constraints • Newton’s method with equality constraints • infeasible start Newton method • implementation 11–1Equality constrained minimization minimize f(x) subject to Ax = b • f convex, twice continuously differentiable • A ∈ Rp×n with rank A = p ⋆ • we assume p is finite and attained optimality conditions: x ⋆ is optimal iff there exists a ν⋆ such that ∇f(x ⋆ ) + ATν ⋆ = 0, Ax ⋆ = b Equality constrained minimization 11–2equality constrained quadratic minimization (with P ∈ Sn )+minimize (1/2)xTP x + qTx + r subject to Ax = b optimality condition: � P AT �� x ⋆ � � −q � = A 0 ν⋆ b • coefficient matrix is called KKT matrix • KKT matrix is nonsingular if and only if Ax = 0, x �= 0 =⇒ x TP x > 0 • equivalent condition for nonsingularity: P + ATA ≻ 0 Equality constrained minimization 11–3Eliminating equality constraints represent solution of {x | Ax = b} as {x | Ax = b} = {F z + ˆx | z ∈ Rn−p} • xˆ is (any) particular solution • range of F ∈ Rn×(n−p) is nullspace of A (rank F = n − p and AF = 0) reduced or eliminated problem minimize f(F z + ˆx) • an unconstrained problem with variable z ∈ Rn−p • from solution z ⋆, obtain x ⋆ and ν⋆ as x ⋆ = F z ⋆ + ˆx, ν ⋆ = −(AAT)−1A∇f(x ⋆ ) Equality constrained minimization 11–4example: optimal allocation with resource constraint minimize f1(x1) + f2(x2) + · · · + fn(xn) subject to x1 + x2 + · · · + xn = b eliminate xn = b − x1 − · · · − xn−1, i.e., choose � I � xˆ = ben, F = −1T ∈ Rn×(n−1) reduced problem: minimize f1(x1) + · · · + fn−1(xn−1) + fn(b − x1 − · · · − xn−1) (variables x1, . . . , xn−1) Equality constrained minimization 11–5Newton step Newton step Δxnt of f at feasible x is given by solution v of � ∇2f(x) AT �� v � � −∇f(x) � = A 0 w 0 interpretations • Δxnt solves second order approximation (with variable v) minimize f�(x + v) = f(x) + ∇f(x)Tv + (1/2)vT∇2f(x)v subject to A(x + v) = b • Δxnt equations follow from linearizing optimality conditions ∇f(x + v) + AT w ≈ ∇f(x) + ∇2f(x)v + AT w = 0, A(x + v) = b Equality constrained minimization 11–6Newton decrement Tλ(x) = �Δxnt∇2f(x)Δxnt�1/2 = �−∇f(x)TΔxnt�1/2 properties • gives an estimate of f(x) − p ⋆ using quadratic approximation f�: 1 λ(x)2 Ay=b 2 f(x) − inf f�(y) = • directional derivative in Newton direction: d f(x + tΔxnt)= −λ(x)2 dt ����t=0 • in general, λ(x) �= �∇f(x)T∇2f(x)−1∇f(x)�1/2 Equality constrained minimization 11–7Newton’s method with equality constraints given starting point x ∈ dom f with Ax = b, tolerance ǫ > 0. repeat 1. Compute the Newton step and decrement Δxnt, λ(x). 2. Stopping criterion. quit if λ2/2 ≤ ǫ. 3. Line search. Choose step size t by backtracking line search. 4. Update. x := x + tΔxnt. • a feasible descent method: x(k) feasible and f(x(k+1)) < f(x(k)) • affine invariant Equality constrained minimization 11–8Newton’s method and elimination Newton’s method for reduced problem minimize f˜(z) = f(F z + ˆx) • variables z ∈ Rn−p • xˆ satisfies Axˆ = b; rank F = n − p and AF = 0 • Newton’s method for f˜, started at z(0), generates iterates z(k) Newton’s method with equality constraints when started at x(0) = F z(0)+ ˆx, iterates are x(k+1) = F z(k)+ ˆx hence, don’t need separate convergence analysis Equality constrained minimization 11–9Newton step at infeasible points 2nd interpretation of page 11–6 extends to infeasible x (i.e., Ax � b)= linearizing optimality conditions at infeasible x (with x ∈ dom f) gives � ∇2f(x) AT �� Δxnt � = − � ∇f(x) � (1) A 0 w Ax − b primal-dual interpretation • write optimality condition as r(y) = 0, where y = (x, ν), r(y) = (∇f(x) + ATν, Ax − b) • linearizing r(y) = 0 gives r(y + Δy) ≈ r(y) + Dr(y)Δy = 0: � ∇2f(x) AT �� Δxnt � � ∇f(x) + ATν � = − A 0Δνnt Ax − b same as (1) with w = ν + Δνnt Equality constrained minimization 11–10Infeasible start Newton method given starting point x ∈ dom f, ν, tolerance ǫ > 0, α ∈ (0, 1/2), β ∈ (0, 1). repeat 1. Compute primal and dual Newton steps Δxnt, Δνnt. 2. Backtracking line search on �r�2. t := 1. while �r(x + tΔxnt, ν + tΔνnt)�2 > (1 − αt)�r(x, ν)�2, t := βt. 3. Update. x := x + tΔxnt, ν := ν + tΔνnt. until Ax = b and �r(x, ν)�2 ≤ ǫ. • not a descent method: f(x(k+1)) > f(x(k)) is possible • directional derivative of �r(y)�2 in direction Δy = (Δxnt, Δνnt) is d �r(y + tΔy)�2 = −�r(y)�2dt ����t=0 Equality constrained minimization 11–11Solving KKT systems � H AT �� v � � g � = − A 0 wh solution methods • LDLTfactorization • elimination (if H nonsingular) AH−1AT w = h − AH−1 g, Hv = −(g + AT w) • elimination with singular H: write as � H + ATQA AT �� v � � g + ATQh � = − A 0 wh with Q � 0 for which H + ATQA ≻ 0, and apply elimination Equality constrained minimization 11–12Equality constrained analytic centering primal problem: minimize −�ni=1 log xi subject to Ax = b dual problem: maximize −bTν + �ni=1 log(ATν)i + n three methods for an example with A ∈ R100×500, different starting points 1. Newton method with equality constraints (requires x(0) ≻ 0, Ax(0) = b) f(x (k) ) − p ⋆ 10−10 10−5 100 105 05 10 15 20 k Equality constrained minimization 11–132. Newton method applied to dual problem (requires ATν(0) ≻ 0) p ⋆ − g(ν (k) ) 10−10 10−5 100 105 0 2 4 6 8 10 k 3. infeasible start Newton method (requires x(0) ≻ 0)
View Full Document