Math 565 Fritz Keinert due Thursday, Apr 30, 2015 Homework 5 For each problem that uses Matlab or some other tool, you should hand in a printout of the relevant script or function file(s), or a transcript of your interactive session, plus whatever outputs or plots are requested. Put the problems in the proper order, and label all printouts clearly. The final output should have full accuracy (format long); intermediate results can be shorter, if you want. 1. (Similar to Nocedal 13.2) I showed in class that the dual of the linear program maximize cT x subject to Ax ≤ b x≥0 is minimize bT λ subject to AT λ ≥ c λ ≥ 0. Show that the dual of the dual is the original primal problem again. (5) 2. (Similar to Nocedal 13.9) Solve the linear program maximize 5x1 + x2 subject to x1 + x2 ≤ 5, 2x1 + (1/2)x2 ≤ 8, x ≥ 0. by the simplex method as explained in class. That is, write out the initial tableau for the problem, and manipulate it until you have the answer. Start at x = (0, 0). Make sure to state the answer, not just give the final tableau. (5) 3. (Nocedal 14.1) Consider the following linear program minimize x1 subject to x1 + x2 = 1, x ≥ 0. Show that the solution is 0 x = , 1 ∗ ∗ λ = 0, 1 s = . 0 ∗ Verify that the system F (x, λ, s) = 0 also has the solution 1 0 x= , λ = 1, s = . 0 −1 (5) 2 Math 565 — Homework 5 — due Thursday, Apr 30, 2015 4. (Nocedal 15.2) Consider the problem 1 minimize sin(x1 + x2 ) + x23 + (x4 + x45 + x6 /2) 3 subject to 8x1 − 6x2 + x3 + 9x4 + 4x5 = 6, 3x1 + 2x2 − x4 + 6x5 + 4x6 = −4. In example 15.3 in Nocedal, the variables x3 and x6 are eliminated. Instead, eliminate x2 and x5 to obtain an unconstrained problem in the remaining variables x1 , x3 , x4 , x6 . (5) 5. Do optimization project 3: Design of a four-bar linkage (see pages appended at the end). In detail: (a) For general p, q, r, s, derive and program formulas that will calculate φ as a function of θ. (b) Derive and program formulas for computing φmax , φmin , θ+ , θ− , α, A, β0 , φmodel , and d2rms . Compute the values of all these things for p = 0.5, q = r = s = 1. The values should come out as shown in the picture. You don’t have to produce a picture. before beta optimization 2 1.8 1.6 φ max 1.4 1.2 1 α 0.8 0.6 0.4 φmin 0.2 0 β0 0 θ+ 1 2 θ− 3 4 5 6 (c) For fixed p, q, r, s as above, find the value β which minimizes d2rms . Use starting guess β0 . The optimal β will be quite close to β0 . (d) In addition to the constraints listed in the project 3 handout, derive the constraints that come from | cos γ| ≤ 1. Hint: They involve h, which depends on θ, but you can compute and use the maximum and minimum values of h to get constraints that do not depend on θ. (e) Keep s = 1 fixed, and minimize d2rms as a function of p, q, r. You can use the starting guesses from part (b). Other ones will probably also work. Hint: Inside the routine that computes d2rms (p, q, r), you need to optimize with respect to β. (30) Math 565 — Homework 5 — due Thursday, Apr 30, 2015 3 6. (Extra Credit) Solve the problem of the week #14 (see the end). 2 points extra credit for solving it numerically. Another 2 points if you can prove it analytically. Programming is quite easy. I found an analytic proof, but it was pretty hard. Hint: what do you know about the relationships between eigenvalues, determinant and trace, in particular for the case of 2 × 2 matrices? (2+2) Problem 14. Let a11 a12 A= a21 a22 and B = b11 b12 , b21 b22 with −1 ≤ aij , bij ≤ 1. Find the maximum possible value of det(A · B − B · A), and provide examples of matrices A and B for which the maximum is acheived. Disclaimer! This problem was submitted by Prof. Irvin Hentzel. I think we know the answer to this problem but we do not have a proof. I will list scores according to the following rule: “If M is the maximum answer submitted, with evidence, then all students who submit an answer, with evidence, in the interval [0.95M, M ] will be listed as successful solvers.” Solutions due by 10:00am Monday, April 27, 2015. 1

© Copyright 2018