grupp: top02-39 namn1: Robert Olsson namn2: ************************************************************ Title: Laboration 2 Date: 2001-03-07, 23:36 Name: Robert Olsson, 800619-4610, md9olsro Group: top02-39 ======================================================================= Please note: My version of Matlab, 5.2.1, has not the latest Optimization Toolbox installed. Therefor I had to use the function constr instead of fmincon. Unfortunately there were no replacement for the fminunc so the exterior penalty could not be simulated. Notation: A matrix (a b) (c d) is represented by (a,b; c,d). PART I -------- 1) a) By using the Steepest-descent method and the startpoint (10,10) we have to make 9 iterations. The optimal value is -11.1562 at the point (-2.2491,-3.06255). If we have used Newtons method instead we would have got the same result in only one iteration. We achieve the very same result after 9 iterations if we choosed (-5,-5) as startpoint with the Steepest-descent method. If we use the Newton method we will still get the solution in one step. Finally if we choose another startpoint we would get the same optimal value and at the same point but the number of iterations with the Steepest-descent method might be different. b) x = (-2.2491,-3.06255) f(x1,x2) = 2*(x1^2+2x1+1) + 8*(x2^2+6x2+9) + 5x1 + x2 grad(f) = (4x1+9; 16x2+49) grad(f(x)) = (0.0036; 0.0008) grad^2(f) = (4,0; 0,16) grad^2(f(x)) = (4,0; 0,16) The eigenvalues of the matrix above are 4 and 16 so the matrix is positive definite. I guess that the software has used some kind of rounding function resulting in a approximated value for the point. The necessary condition for local minimality is therefor fulfilled. The function is strictly convex since grad^2(f(x)) was positive definite. So the local minimum is a global minimum. c) The function is quadratic which implies a one-step soloution with the Newton method. 2) a) The number of iteration with the Steepest-descent method seems to be very large. The software can handle 201 iterations before it fails, stopping at the optimal value 0.044985 at the point (0.788032,0.620257). The Newton methods solves the problem without any problems, except for rounding. the optimal value is 0 at (1,1). The number of iterations before finding the optimal solution for Newton step=1, modified Newton and Newton Marquardt was 5, 13 respective 13. b) x = (1,1) f(x1,x2) = 100*(x2^2-2x2x1^2+x1^4) + (1-2x1+x1^2) grad(f) = (-400x2+400x1^3-2+2x1; 200x2-200x1^2) grad(f(x)) = (0; 0) grad^2(f) = (1200x1^2-2,-400; -400x1,200) grad^2(f(x)) = (1198,-400; -400,200) The eigenvalues are all positive and therefor is the function positive definite which implies that the function is convex. Yes, the point (1,1) is an optimum. c) Startpoint: (0,0) As above the software can not solve the problem by using the Steepest-descent method. All the Newton methods solve the problem. The Newton step=1 method is best of them, it only takes the method 2 iterations to find the optimal value. Startpoint: (0.99,0.5) If we choose a point near the optimal point the Steepest-descent method manage to reach the requested optimal point after 25 iterations. This kind of approach requires that you know either x1 or x2 at the optimal point. Again the Newton mwthods have no problems finding the optimal point. 3) a) With the Steepest-descent method we find, after 4 iterations, that the optimal value is -58 at the point (3,1). The Newton step=1 method can not solve the problem since the Hessian of the function at (0,0) is the zero matrix and division (or correct: inverse on) with zero matrixes is not defined. If we use the Newton Marquardt method we reach the correct result, the same as if would have used the Steepest-descent method but after only 3 iterations. b) Newton Marquardt method Startpoint: (0,-1) Iterations: 1 Optimal point: (3,-1) Optimal value: -50 I could not find any more optimal points. Since we have found -58 before, -50 can not be a global minimum. Further -50 can not be a global maximum since f(0)=0. x = (3,-1) f(x1,x2) = x1^3+2x2^3-27x1-6x2 grad(f) = (3x1^2-27; 6x2^2-6) grad(f(x)) = (0; 0) grad^2(f) = (6x1,0; 0,12x2) grad^2(f(x)) = (18,0; 0,-12) The eigenvalues of the Hessian is 18 and -12 which implies that the Hessian is not positive semidefinite. So the point (3,-1) is not a local minimum, just a stationary point. PART II -------- 1) a) The optimal value is 1.5625 at the point (0.625, 1.250). b) f(x1,x2) = -x1 + 2*x1^2 - 2*x2 + x2^2 - x1*x2; g1 = -x1^2+x2 => 0 g2 = 2*x1-x2 => 0 grad(f) = (-1+4*x1-x2; -2+2*x2-x1) grad^2(f) = (4, -1; -1, 2) grad(g1) = (-2*x1; 1) grad(g2) = (2; -1) x^ local min implies, 1. x^=(x1^,x2^) is in X={ (x1,x2) is in R^2 | -x1^2+x2=>0 ; 2*x1-x2=>0 } There is L^=(L1^,L2^) in R^2, such that 2. L1^ * g1(x^) = 0, L2^ * g2(x^) = 0 3. grad(f(x^)) - L1^ * grad(g1(x^)) - L2^ * grad(g2(x^)) = 0^2 4. L1^, L2^ => 0 Let us check if x^=(0.625, 1.250) satisfies the KKT conditions above, 1. -x1^2+x2=0.8594 > 0, 2*x1-x2=0 => 0, ok! 2. Choose L1^=0 and choose L2^=>0, ok! 3. (0.2500; -0.1250) - L2^ * (2; -1) = 0^2, let L2^=0.1250, ok! 4. 0.1250 > 0 and 0 = 0, ok! So, the KKT conditions are all satisfied at x^. If we the problem is convex the local minimum is a global minimum. Since g1 and g2 are concave and grad^2(f) positive definite, since eigenvalues 4.4142, 1.5858 > 0, we're done. The given point in a) is a global minimum. 2) I ran the command constr('upg2',[x1 x2]) for different values of x1 and x2. Initial (x1,x2) = (0 0) No feasible solution found. Initial (x1,x2) = (1 1) x1 = 3.4000 x2 = 1.2000 Optimal value = 3.4000 Initial (x1,x2) = (-1 -1) x1 = -3.0000 x2 = -2.0000 Optimal value = -3.0000 Initial (x1,x2) = (3.7 0) x1 = 3.6056 x2 = 0.0000 Optimal value = 3.6056 Initial (x1,x2) = (2 2) x1 = 3.4000 x2 = 1.2000 Optimal value = 3.4000 It feels like choosing (x1,x2) = (3.7, 0) as an initial point is pretty good since the function seems to have a local minimum around (3.6, 0). f(x1,x2) = x1 g1 = -(x1-1)^2-(x2+2)^2+16 => 0 g2 = x1^2+x2^2-13 => 0 grad(f) = (1; 0) grad^2(f) = (0, 0; 0, 0) grad(g1) = (-2*x1+2; -2*x2-4) grad(g2) = (2*x1; 2*x2) Let us check if the KKT conditions are satisfied at x^=(3.6056, 0.0000) 1. Ok! 2. Choose L1^=0 and choose L2^=>0, ok! 3. (1; 0) - L2^ * (7.2112; 0) = 0, let L2^=1/7.2112, ok! 4. 1/7.2112 > 0 and 0 = 0, ok! But is the problem convex? Let us see, g1 is concave but g2 is convex since the eigenvalues for the Hessian are positive. So the point x^ is a not a global minimum, just local. PART III -------- Note: Isn't it supposed to be [0; -1/3] at the third entry for the gradient of the constraint in example2.m? Anyway, I did not change it. 1) The Interior penalty function was the only one I could get to work, see note at top of this document. Problem 2 x1 -> 3.22 x2 -> 0.75 Optimal value -> 0.2590 Problem 3 x1 -> -3.59 x2 -> 3.55 Optimal value -> -12.7445 2) Let us check the KKT conditions for problem 2 at x^ = (3.22, 0.75). f(x1,x2) = x1*sin(x1)+x2*sin(x2) g1 = -x1-1/3 => 0 g2 = -sin(x2)+x1 => 0 g3 = x2/3-1/4 g4 = -||(x1,x2)-(1,1)^T||^2/5+1 => 0 grad(f) = (sin(x1)+x1*cos(x1); sin(x2)+x2*cos(x2)) grad(g1) = (-1; 0) grad(g2) = (1; -cos(x2)) grad(g3) = (0; 1/3) grad(g4) = not important... 1. Well, x^ is not a feasible solution since -x1-1/3 => 0 does not hold. So x^ is not a local optimum. Then let us check the point x^ = (-3.59, 3.55) in problem 3. This time we easily see that x^ is not a feasible solution since -x1-x2 <= 0 does not hold. Perhaps this is some kind of rounding problem in Matlab since -x1-x2 is almost equal to zero. x^ is not a local optimum. 3) For problem 1 we look at the KKT conditions. f(x1,x2) = ||x||^2 g1 = x1-2 => 0 g2 = x2/3-1/3 => 0 grad(f) = 2*(x1,x2) grad(g1) = (1; 0) grad(g2) = (0; 1/3) 1. We'll test if our points are feasible after we have found our candidates for local minimum. 2. L1^ * (x1-2) = 0, case 1: let L1^=0 L2^ * (x2/3-1/3) = 0, case i: L2^=0 3. 2*(x1,x2) = 0^2, implies that x1=x2=0. 4. Ok! case ii: x2=1 3. 2*(x1,1) - L2^ * (0; 1/3) = 0^2, implies that x1=0 and L2^=6. 4. Ok! case 2: x1=2 L2^ * (x2/3-1/3) = 0, case i: L2^=0 3. 2*(2,x2) - L1^ * (1; 0) = 0, implies that x2=0 and L1^=4. 4. Ok! case ii: x2=1 3. 2*(2,1) - L1^ * (1; 0) - L2^ * (0; 1/3) = 0, implies that L1^=4 and L2^=6 4. Ok! All KKT conditions, except the first one, are okey for (x1,x2) = (0,0) and (1,0) and (2,0) and (2,1). But (0,0) and (1,0) do not satisfy the first constraint and (2,0) does not satisfies the second constraint. The value for the objective function is 5 at (2,1). The global minimum is therefor 5 at (2,1) since it is the only local minimum. If we use the same idea in problem 2 we will get pretty many cases. Instead let x1=-1/3, x2=3/4 and choose L1^=0.6422, L2^=0, L3^=3.6912 and L4^=0 and the KKT conditions are satisfied. But then (x1,x2) is not a feasible point. In order to determine if the KKT conditions are fullfilled for any point we have to some more work but it seems as if no feasible x1 and x2 satisfies all KKT conditions. If so, there are no local optimal points. In problem 3, I found that either i) -x1=x2=+-root(12.5), ii) x1=x2=0 or iii) x1=0, x2=5 if the KKT conditions are satisfied. They are all feasible points. The optimal value, -12.5, of f is found when one of x1 and x2 is equal to -root(12.5) and the other one is equal to root(12.5).