DOC PREVIEW
MIT 6 079 - Equality constrained minimization

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 079 - Equality constrained minimization

Download Equality constrained minimization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Equality constrained minimization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Equality constrained minimization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?