grupp: 42 namn1: Johan Larsson namn2: Joan Gatari ************************************************************ PART I ------ Task 1 ------ a) Below the number of iterations and the solution point found with the respective methods are stated for different starting points. SD = Steepest Descent. Starting point (10,10) (-5,-5) (5,-5) Method SD (9,(-2.2491,-3.06255)) (9,(-2.25225,-3.06234)) (17,(-2.2488,-3.06218)) Newton (1,(-2.25,-3.06249)) (1,(-2.24994,-3.06246)) (1,(-2.25001,-3.0625)) b) It is a global minimum. c) The function is quadratic and Newton's method has quadratic convergence for such functions. Task 2 ------ a) We choose starting point (-1.5,-1.0), which is in the specified region. With termination criterion 'gradient length' set to 0.0001, 0.001, 0.01, respectively, SD used all 200 iterations without being terminated. The found point in all three cases was appr. (0.96,0.92) with function value 0.0016. Modified Newton was significantly more efficient and needed 14 iterations to find the solution 5.0518e-12 in the point (0.99,0.99), which indicates that the exact solution has the objective function value 0 in the point (1,1). This was confirmed by the ordinary Newton method which found the point (1,1) with function value 0 in just 5 iterations. As for Levenberg-Marquardt, it achieved the same point and value as modified Newton, also in 14 iterations. b) No, the function is not convex (concave e.g. in the point (0,3)). The obtained point is a local minimum but not certain to be a global one due to the function's nonconvexity. c) The closer you start to the optimal point with SD, the faster it achieves a low function value. However, it does not converge with gradient length 0.0001 as a termination criterion. Instead, in order to make the method converge (when starting close to the optimum), one needs to choose 'iteration distance' as the termination criterion, also set to 0.0001. Newton's method works just as quickly from any starting point (empirical claim based on about ten different points). With 'Gradient length' set to 0.0001, it occurs that the method does not converge wholly, but the obtained function value is of the order of 10^-10 in these cases, i.e. at a negligible distance from the optimum. Task 3 ------ a) Steepest descent terminated at the point (3,1) with function value -58 in 6 iterations. The Newton method doesn't work because it can only find a descent direction if the Hessian is positive definite, which it is not in the point (0,0). With Levenberg-Marquardt we found the same point as with SD above, in only 3 iterations. It works even in the starting point (0,0) due to the added perturbation matrix. b) After starting in some arbitrarily chosen points e.g {(2,-1),(1,3)} we found two stationary points (3,1) and (3,-1). They are inflexion points. PART II ------- Task 1 ------ a) We obtained the solution x = (0.625,1.25). b) KKT conditions: (l = lambda*, i signifies index) i) Primal feasibility gi(x*) >= 0 ii) Complementarity li*gi(x*) = 0 iii) Dual feasibility Solve grad(L(x*,l)) = 0 => => if li >= 0, x* is a regualar and local minimum For minimization we have the following problem: min f(x1,x2) = -x1 + 2*x1^2 - 2*x2 + x2^2 - x1*x2 s.t. -x1^2 + x2 >= 0 2*x1 - x2 >= 0 This gives g1 = -x1^2 + x2 and g2 = 2*x1 - x2, which in turn yields L(x,l) = -x1 + 2*x1^2 - 2*x2 + x2^2 - x1*x2 + l1*(x1^2 - x1) - l2*(2*x1 - x2) i) g1(x*) = 0.86 approximately, which is > 0 g2(x*) = 0 ii) l1 * g1(x*) = 0 implies l1 = 0 iii) After calculating derivatives, we arrive at the condition l2 * [2,-1]T = [0.25,-0.125]T, where T signifies transpose. This condition yields l2 = 0.125 > 0, so dual feasibility is fulfilled. Conclusion: KKT conditions are fulfilled. To examine if the problem is convex, we check whether grad2(L(x,l)) is positive definite. Grad2(L) (i.e. the Hessian of L) is [4 -1; -1 2] in matlab notation. We get the eigenvalues l1,2 = 3 +- sqrt(3), which are both positive, ie. the Hessian is positive definite and the problem is convex. Thus the found point is indeed a global maximizer. Task 2 ------ Starting Point x* ______________ __ (1,1) (3.4,1.2) (0,0) No feasible solution (3.7,0) (3.6056,0) (-1,-1) (-3,-2) (2,2) (3.4,1.2) The best point is (-3,-2) since the problem is min x1 and -3 is the least value for x1.Also the point satisfies the KKT conditions. To check convexity, we check if the Hessian of the Lagrangian function is pos. definite. The Hessian was found to be [1/6 0; 0 1/6], i.e. its eigenvalues are the diagonal elements, which are positive, thus confirming the found point to be a global minimum. PART III -------- Task 1 ------ 1. The found points were (approximately, eyesight limitations): Problem 2 Problem 3 IPA (3.2,0.75) (3.2,0.75) EPA (3.7,-3.7) (3.7,-3.7) 2. For problem 2, the point found is a local optimum. For problem 3, the point found with both methods is a local optimum, since the point (-3.7,3.7) yields the same function value. 3. For problem 2, there are three optima. The one we found seems to be a local one and the one at ~(0.3,3.1) seems to have a slightly lower function value, indicating that it's the global optimum. The third optimum is in the lower right corner of the feasible region at ~(0.75,0.75), and it is local. For problem three two optima exist as already pointed out in the answer to the second question, and their function values are equal, so they are both local optima. Johan Larsson d96johla@dtek.chalmers.se Joan Gatari md0gatwa@mdstud.chalmers.se