Notes for Class: Analytic Center, Newton’s Method, and Web-Based ACA 1 1 The Analytic Center of a Polyhedral System Given a polyhedral system of the form: Ax ≤ b , Mx = g , the analytic center is the solution of the following optimization problem: (ACP:) m maximizex,s s.t. i=1 si Ax + s = b s≥0 Mx = g . This is easily seen to be the same as: minimizex,s − (ACP:) s.t. m i=1 ln(si ) Ax + s = b s≥0 Mx = g . The analytic center possesses a very nice “centrality” property. Suppose that (ˆ x, s) ˆ is the analytic center. Deﬁne the following matrix:  Ŝ −2 (ŝ1 )−2   0 :=  ..  . 0 0 (ŝ2 )−2 ... 0 2 ... ... .. . 0 0 ... . . . (ŝm )−2    .  ^ x P Ein Eout Figure 1: Illustration of the Ellipsoid construction at the analytic center. Next deﬁne the following sets: P := {x | M x = g, Ax ≤ b} EIN := x | M x = g, EOUT := x | M x = g, ˆ ≤1 (x − x) ˆ T AT Ŝ −2 A(x − x) (x − x) ˆ T AT Ŝ −2 A(x − x) ˆ ≤m Theorem 1.1 If (ˆ x, s) ˆ is the analytic center, then: EIN ⊂ P ⊂ EOUT . This theorem is illustrated in Figure 1. The theorem is actually pretty easy to prove. 3 Proof: Suppose that x ∈ EIN , and let s = b − Ax. Since M x = g, we need only prove that s ≥ 0 to show that x ∈ P . By construction of EIN , s satisﬁes (s − ŝ)T Ŝ −2 (s − ŝ) ≤ 1, where sˆ = b − Aˆ x. This in turn can be written as: m i=1 (si − ŝi )2 ≤1, ŝ2i whereby we see that each si must satisfy si ≥ 0. Therefore Ax ≤ b and so x ∈ P. We can write the optimality conditions (KKT conditions) for problem ACP as: −Ŝ −1 e + λ = 0 0 + AT λ + M T u = 0 Aˆ x + sˆ = b M x̂ = g, where e = (1, . . . , 1)T , i.e., the e is the vector of ones. From this we can derive the following fact: if (x, s) is feasible for problem ACP, then eT Ŝ −1 s = eT Sˆ−1 (b − Ax) = λT b + uT M x = λT b + uT g . Since this is true for any (x, s) feasible for ACP, it will also be true for (ˆ x, s) ˆ x), and so (where sˆ = b − Aˆ eT Ŝ −1 s = λT b + uT g = eT Ŝ −1 ŝ = m . This means that s must lie in the set T := s | s ≥ 0, eT Sˆ−1 s = m Now the extreme points of T are simply the vectors: 4 . v 1 := mŝ1 e1 , . . . , v m := mŝm em , where ei is the ith unit vector. Notice that each of these extreme points v i satisﬁes: (v i − ŝ)T Ŝ −2 (v i − ŝ) = (mei − e)T (mei − e) = m2 − m ≤ m2 , and so any s ∈ T will satisfy (s − ŝ)T Ŝ −2 (s − ŝ) ≤ m2 . Therefore for x ∈ P , s = b − Ax will satisfy which is equivalent to that x ∈ EOUT . q.e.d. 2 (s − ŝ)T Ŝ −2 (s − ŝ) ≤ m, ˆ ≤ m. This in turn implies (x − x) ˆ T AT Ŝ −2 A(x − x) Newton’s Method Suppose we want to solve: (P:) min f (x) x ∈ n . At x = x̄, f (x) can be approximated by: 1 f (x) ≈ h(x) := f (¯ x) + ∇f (¯ x)T (x − x) ¯ t H(¯ ¯ + (x − x) x)(x − x), ¯ 2 which is the quadratic Taylor expansion of f (x) at x = x̄. Here ∇f (x) is the gradient of f (x) and H(x) is the Hessian of f (x). Notice that h(x) is a quadratic function, which is minimized by solving ∇h(x) = 0. Since the gradient of h(x) is: ∇h(x) = ∇f (¯ x) + H(¯ x)(x − x) ¯ , 5 we therefore are motivated to solve: ∇f (¯ x) + H(¯ x)(x − x) ¯ =0, which yields x). x−x ¯ = −H(¯ x)−1 ∇f (¯ x)−1 ∇f (¯ The direction −H(¯ x) is called the Newton direction, or the Newton step at x = x̄. This leads to the following algorithm for solving (P): Newton’s Method: Step 0 Given x0 , set k ← 0 Step 1 dk = −H(xk )−1 ∇f (xk ). If dk = 0, then stop. Step 2 Choose stepsize αk = 1. Step 3 Set xk+1 ← xk + αk dk , k ← k + 1. Go to Step 1. Note the following: • The method assumes H(xk ) is nonsingular at each iteration. • There is no guarantee that f (xk+1 ) ≤ f (xk ). • Step 2 could be augmented by a linesearch of f (xk + αdk ) to ﬁnd an optimal value of the stepsize parameter α. Proposition 2.1 If H(x) is SPD, then d = −H(x)−1 ∇f (x) is a descent direction, i.e. f (x + αd) < f (x) for all suﬃciently small values of α. Proof: It is suﬃcient to show that ∇f (x)t d = −∇f (x)t H(x)−1 ∇f (x) < 0. This will clearly be the case if H(x)−1 is SPD. Since H(x) is SPD, if v = 0, 0 < (H(x)−1 v)t H(x)(H(x)−1 v) = v t H(x)−1 v, thereby showing that H(x)−1 is SPD. 6 2.1 Rates of convergence A sequence of numbers {si } exhibits linear convergence if limi→∞ si = s̄ and |si+1 − s̄| = δ < 1. lim i→∞ |si − s̄| If δ = 0 in the above expression, the sequence exhibits superlinear convergence. A sequence of numbers {si } exhibits quadratic convergence if limi→∞ si = s̄ and |si+1 − s̄| = δ < ∞. lim i→∞ |si − s̄|2 Examples: Linear convergence: si = 1 10 i : 0.1, 0.01, 0.001, etc. s̄ = 0. |si+1 − s̄| = 0.1. |si − s̄| Superlinear convergence: si = i!1 : 1, 12 , 16 , 1 1 24 , 125 , etc. s̄ = 0. i! 1 |si+1 − s̄| = = → 0 as i → ∞. |si − s̄| (i + 1)! i+1 (2i ) 1 Quadratic convergence: si = 10 : 0.1, 0.01, 0.0001, 0.00000001, etc. s̄ = 0. i |si+1 − s̄| (102 )2 = = 1. |si − s̄|2 102i+1 Theorem 2.1 (Quadratic Convergence Theorem) Suppose f (x) ∈ C 3 on n (i.e., f (x) is three times continuously diﬀerentiable) and x∗ is a point that satisﬁes: ∇f (x∗ ) = 0 and H(x∗ ) is nonsingular. If Newton’s method is started suﬃciently close to x∗ , the sequence of iterates converges quadratically to x∗ . 7 Example 1: Let f (x) = 7x − ln(x). Then ∇f (x) = f (x) = 7 − x1 and H(x) = f (x) = x12 . It is not hard to check that x∗ = 17 = 0.142857143 is the unique global minimum. The Newton direction at x is −1 d = −H (x) f (x) 1 = −x2 7 − ∇f (x) = − f (x) x = x − 7x2 . Newton’s method will generate the sequence of iterates {xk } satisfying: xk+1 = xk + (xk − 7(xk )2 ) = 2xk − 7(xk )2 . Below are some examples of the sequences generated by this method for diﬀerent starting points. k 0 1 2 3 4 5 6 7 8 9 10 xk 1.0 −5.0 −185.0 −239, 945.0 −4.0 × 1011 xk 0 0 0 0 0 xk 0.1 0.13 0.1417 0.14284777 0.142857142 0.142857143 xk 0.01 0.0193 0.03599257 0.062916884 0.098124028 0.128849782 0.1414837 0.142843938 0.142857142 0.142857143 0.142857143 By the way, the “range of convergence” for Newton’s method for this function happens to be x ∈ (0.0 , 0.2857143) . Example 2: f (x) = − ln(1 − x1 − x2 ) − ln x1 − ln x2 .   ∇f (x) =  1 1−x1 −x2 1 1−x1 −x2 8 − 1 x1 − 1 x2   ,    H (x) =   x∗ = k 0 1 2 3 4 5 6 7 1 1 3, 3 1 1−x1 −x2 2 + 1 1−x1 −x2 1 x1 2 2 1 1−x1 −x2 1 1−x1 −x2 2  2 + 1 x2   . 2  , f (x∗ ) = 3.295836866. xk1 0.85 0.717006802721088 0.512975199133209 0.352478577567272 0.338449016006352 0.333337722134802 0.333333343617612 0.333333333333333 xk2 0.05 0.0965986394557823 0.176479706723556 0.273248784105084 0.32623807005996 0.333259330511655 0.33333332724128 0.333333333333333 xk − x∗ 0.58925565098879 0.450831061926011 0.238483249157462 0.0630610294297446 0.00874716926379655 7.41328482837195e−5 1.19532211855443e−8 1.57009245868378e−16 Some remarks: • Note from the statement of the convergence theorem that the iterates of Newton’s method are equally attracted to local minima and local maxima. Indeed, the method is just trying to solve ∇f (x) = 0. • What if H(xk ) becomes increasingly singular (or not positive deﬁnite)? In this case, one way to “ﬁx” this is to use H (xk ) + I. • The work per iteration of Newton’s method is O(n3 ) • So-called “quasi-Newton methods” use approximations of H(xk ) at each iteration in an attempt to do less work per iteration. 3 Modiﬁcation of Newton’s Method with Linear Equality Constraints Here we consider the following problem: 9 (P:) minimizex f (x) s.t. Ax = b. Just as in the regular version of Newton’s method, we approximate the objective with the quadratic expansion of f (x) at x = x̄: ˜ :) (P x) + ∇f (¯ x)T (x − x) ¯ + 12 (x − x) ¯ t H(¯ x)(x − x) ¯ minimizex h(x) := f (¯ s.t. Ax = b. Now we solve this problem by applying the KKT conditions, and so we solve the following system for (x, u): Ax = b ∇h(x) +AT u = 0 . Now let us substitute the fact that: ∇h(x) = ∇f (¯ x) + H(¯ x)(x − x) ¯ and A¯ x = b. Substituting this and replacing d = x − x̄, we have the system: Ad = 0 x) . x)d +AT u = −∇f (¯ H (¯ The solution (d, u) to this system yields the Newton direction d at x̄. 10 Notice that there is actually a closed form solution to this system, if we want to pursue this route. It is: d = −H(¯ x)−1 AT AH (¯ x)−1 ∇f (¯ x) + H (¯ x)−1 AT u = − AH (¯ x)−1 AT 4 −1 −1 AH(¯ x)−1 ∇f (¯ x) x)−1 ∇f (¯ AH(¯ x) . Web-Based ACA (Adaptive Conjoint Analysis) 11