Exercices
1. Apply some steps of the Hooke-Jeeves method with the initial approxima-
tion x = 0 and y = 0 and an initial step size of h = 1 to find the minimum
of the function.
f (x, y) = 3x2 + 5y 2 + 4xy + 17x − 13y + 4
2. Apply three steps of the Hooke-Jeeves method with the initial approxima-
tion x = 1, y = 1 and z = 1 and an initial step size of h = 1 to find the
minimum of the function
f (x, y, z) = 4cos(0.3xy) + 3cos(0.2yz) + 3cos(0.1xz).
3. Practice problem
1 Write a program that given a function and an initial point tests the
function in all four directions with step size 0.1. Your program should
print the original point, the improved point and the vector between
them. Test your function using f (x, y) = (x − 3)2 + (y + 1)2 .
2 Write a program that, given a function, a starting point, and a vector,
moves the point in the direction of the vector until the function value
stops decreasing. Choose a starting point and run it through your
code from problem 1 to find a vector. Run the starting point and
vector through your code for problem 2. and repeat until the vector
is (0, 0).
3 Write a program that, given a function and a starting point, will run
the first two steps of the Hooke-Jeeves procedure and return the next
starting point. Repeat until the vector returns 0.
4 Insert your code from Problem 3 into a loop that will run as long as
the vector is nonzero. Use
f (x, y) = (x + y)2 + sin((x + 2))2 + y 2 + 10
Run your new code with an interval of 1 to get a new point; from that
starting point repeat with a new interval of 0.1; continue to repeat,
reducing intervals, until you reach an interval of 0.0001.
• Insert your code from Problem 4 into a loop that will run Hooke-
Jeeves with successive interval widths from 1 to 0.000001.
[ ]
1 0
4. Consider the function f (x) = 12 xT Sx, x ∈ R2 with S = . How
0 b
quickly does the algorithm go to (0, 0) based on the values of b when
the initial point is (b, 1)? How is b related to the condition number of
S? Sketch the level curves of f and some iterates given by the steepest
descent algorith.
hint: With a big condition number the iterates oscillate all over the
place, with a small condition number the steps will be very small and the
convergence will be extremely slow.
1
5. • Let f : Rn → R be twice differentiable. Show that f is striclty convex
with constant m > 0 f and only if
Hf (x) − mIn
is positive.
• Let f : Rn → R be twice differentiable and convex. Show that
g(x) = f (x) + ϵ||x||2 is strictly convex with ϵ > 0.
• Justify that for f (x) a strictly convex function x ∈ Rn and d a
descent direction of f at x the optimal step is well defined (that is
f (x+td) has a unique global minimum at t∗ ∈ (0, +∞)). Under these
hypothesis, show that t = t∗ if and only if < ∇f (x + td), d >= 0.
6. Let f : Rn → R be twice differentiable. We assume that there is a constant
M > 0 such that for all x, h ∈ Rn
hT Hf (x)h ≤ M ||h||2 .
• Show that for all x, y ∈ Rn
M
f (y) ≤ f (x)+ < ∇f (x), y − x > + ||y − x||2 .
2
• Fix an x ∈ Rn and set g(y) = f (x)+ < ∇f (x), y − x > + M
2 ||y − x|| .
2
Show that g has a unique minimum and find the minimum value.
• Assume that f has a global minimum at x∗ whose value is p∗ . Show
that for all x ∈ Rn
1
p∗ ≤ f (x) − ||∇f (x)||2 .
2M
7. Consider the minimization problem
minx∈R2 (x1 − 1)2 + (x2 + 1)2
under the constraint (x1 − 1)2 − x2 ≤ 0.
• Solve the problem using Lagrange multipliers.
• Solve the problem with the penalty method with µk = k for k = 1, 2, ..