Math/CS 661: Optimization --- Fall 2006

To contact the instructor: j.rhodes@uaf.edu

Course syllabus: M661syl.pdf

Homework Assignments:

Problems are from Nocedal & Wright, unless otherwise stated.

• 9/6 Show the following, from the definition:
  1. f(x)=x^2 is convex on R.
  2. f(x)=x is convex on R.
  3. f(x,y)=x^2+y^2 is convex on R^2.
  4. f(x,y)=x^2-y^2 is not convex on R^2, nor is -f.
  Also, p.30, problems 2.1, 2.2, 2.3, 2.7
• 9/8 p. 30, problems 2.8, 2.12, 2.13, 2.14
• 9/11 p. 62, problems 3.1,3.2
• 9/13 p. 62, problem 3,3
• 9/15 none
• 9/18 p. 62, problems 3.5,3.6,3.7
• 9/20 none
• 9/22 p. 133, problems 5.2,5.3, and
  1. Develop a Gram-schmidt-like process that for any given symmetric, positive definite A and vectors v_1,v_2,...v_k will produce a set of vectors with the same span that are conjugate with respect to A.
  2. 2. Demonstrate your process on the matrix A=[1 1 0; 1 2 0; 0 1 2] and vectors (1,0,0), (0,1,0), (0,0,1).
• 9/25 p.132, problem 5.1
• 9/27 p.132, problems 5.4, 5.5, 5.6
• 9/29 p. 132, problem 5.8, and
  1. If A is positive definite symmetric, under what conditions on C will C'AC (where C' denotes the transpose of C) be positive definite symmetric? Prove your claim.
• 10/2, p. 162, problems 6.1,6.2
• 10/4, p. 274, problem 10.1, and
  1. For the data points (1,3.5), (2,5.5), (3,7), (4,8.5) determine the least-squares best fit line, showing all work.
  2. For the same data determine the least-squares best fit quadratic.
• 10/6,
  1. In class it was shown that the Gauss-Newton method will terminate in one step if used to find a linear least-squares fit with x0=(0,...,0). If x0 is a non-zero vector will it still terminate in one step? Either show it does not (by example), or prove that it does.
  2. Complete the maximum likelihood estimate of p for the genetic example in class. ( Recall f(p)=(p^2)^4 *(2p(1-p) )^36*((1-p)^2)^60 )
• 10/9, p. 358, problems 12.4, 12.6, 12.16
• 10/11, p. 358, problems 2.1, 12.3, 12.18, 12.20, 12.21
• 10/13, p. 358, problem 12.15; Also,attempt to prove:
  1. (Let * denote the dot product) Suppose a,b,c are vectors such that for all vectors d the following holds: a*d>=0, b*d>=0 implies c*d>=0. Then c=ra+sb for some scalars r,s that are non-negative. (We showed c=ra+sb in class; you must show the non-negativity of r,s.)
  Warning: This can be suprisingly complicated to prove. Partial proofs, geometrically plausible `explanations' and other less-than-complete solutions can be turned in.
• 10/16, no assignment
• 10/18:
  1. Consider the LP problem: Minimize f(x,y,z)=y subject to 2x+3y <= 9, |x-2|<= 1, x>=0,y>=0. Put this in canonical and stadard forms. (Do not solve.)
  2. Consider the LP problem: Minimize f(x,y,z)=-4x-2y-2z subject to 3x+y+z=12, x-y+z=-8, x>=0. Find all vertices of the polytope/polyhedron defined by the constraints, and use these to determine a minimizing point.

• 10/20: p.63, problem 3
  1. In problem 1 from 10/18, draw the feasible polytope in x-y space, find all vertices, and decide which one minimizes f.
  2. In problem 1 from 10/18 in standard form, give 5 basic solutions, at least 4 of which are basic feasible solutions. (The bfs's are most easily found by working from the vertices you found in the previous problem. The fifth basic solution you should find by picking some basis.)

Data for midterm exam:

Problem 4:

t, y =

1, 9.25
2, 28.87
3, 93.16
4, 288.32
5, 886.32
6, 2744.78
7, 8499.80
8, 26314.18
9, 81456.16
10, 252162.05

• 10/30, p. 63, problems 1,9,11 (Note: Think about 9 and 11 geometrically), and
  1. Use the Simplex algorithm to maximize x+y+3z, subject to x+y=1, y+z=2, x,y,z ≥0 (An initial BFS can be found easily for this.)
  2. Use Simplex to minimize 2x+3y, subject to 4x+2y ≥12, x+4y≥6, x,y≥0. Find an initial BFS for this by introducing additional variables and minimizing an appropriate objective function.
• 11/1, no new problems
• 11/3, no new problems, choose project
• 11/6, For problems 1,2 from 10/30, write dual problems and solve them; p. 85, problem 5
• 11/8, Prove Gale's Theorem: Let A,b, be given. Then the following are equivalent: a) There exists an x such that Ax<=b, and b) if y satisfies y' A=0 and y>=0, then y' b>=0. (Note: y' means "y transpose" .)
• 11/10, p. 85, problems 14,15
• 11/13, no problems
• 11/15, p. 102, problem 2
• 11/17, p. 102, problem1
• 11/20, no new problems
• 11/22, no new problems
• 11/27, no new problems
• 11/29, p. 115, problems 3,7 (Last assigned problems)
• Project Presentations: Friday 12/8 Jake, Kent; Monday 12/11 Russell, James, Jim