Homework Assignment #5
MATH 309: Continuous Optimization
Due date: Friday November 8, 2019
1. (Least squares data fitting) Recall Example #1 from Lecture 18 where we performed a least-squares
fit to the following five data points
(tj , yj) = (1.5, 2.3), (3, 2.9), (4, 5), (5.6, 3.3), (6.2, 2.2)
using a nonlinear fitting function. I also explained how the data-fitting problem simplifies drasti-
cally when the fitting function is a first-degree polynomial (linear).
(a) Extend this linear least squares approach to perform a quadratic fit of the form φ(t;x) = x1 +
x2t + x3t2 using a general set of points (tj , yj) with j = 1, 2, . . .m. Derive the corresponding
3× 3 linear system for the coefficients x.
(b) Solve the linear system from (a) for the data points above and hence derive the quadratic
function that best fits the data in a least-squares sense. Use Matlab to generate an accurate
plot of the data along with the fitting function.
(c) Modify the code lec18ex1.m to use lsqcurvefit to determine the quadratic fit numeri-
cally. Show that the resulting quadratic function is identical to the one you derived analyt-
ically in part (b). Compare the resnorm value with that we found in Example #1 for the
combined exponential–cosine fit, and use this (along with graphical evidence) to judge which
is the better fit to the given data.
FOR FUN: Use lsqcurvefit to determine a cubic (or even higher degree polynomial) fit and see whether
it’s better or worse!
2. (Facility location problem) A company plans to build a number of new service centers that serve 6
major clients at the following known locations:
(cj , dj) = (3, 3), (4, 4), (1, 5), (5, 2), (1, 1), (5, 1),
for j = 1, 2, . . . , 6. A decisionmust bemade about the optimal location of the service centers, where
the aim here is to minimize the travel distance for these clients. The optimizing criterion chosen is
that the sum of the squares of the distance from each service point to each client should be a global
minimum.
(a) As a first step, state this problem as a nonlinear optimization problem for a single service
center with location (a, b) and determine the exact minimizer. Discuss your result, and include
a plot showing your optimal service point along with the client locations.
(b) Generalize your results from part (a) to the case when you have 3 service centers denoted by
(ai, bi) for i = 1, 2, 3, and hence 6 unknowns. Again find the solution analytically. Discuss the
result and explain why it is not really that useful.
(c) There are several ways to “fix” the problem from part (b) in order to obtain a more practical
solution. For example, you might try to use an objective function that minimizes the maxi-
mum squared-distance to any of the three service centers individually, which can be expressed
mathematically as
min
j=1,...,6
[
max
i=1,2,3
(
cj − ai)2 + (dj − bi
)2]
.
1
Thisminimax problem is actually just one member of a really fascinating family of optimization
problems but unfortunately, we are unable to solve it using the techniques we’ve learned so
far in Math 309.
Instead, consider a modified version of the problem in which the client coordinates given
above are located on the corners of a rectangular grid of numbered streets (vertical, labelled
by cj) and avenues (horizontal, labelled by dj). Suppose that the company knows already that
it wants to build its new service centers somewhere along First, Third and Fifth Streets, which
means that the locations of these three buildings are given by
(1, b1), (3, b2), (5, b3),
where the bi are to be determined. State the corresponding optimization problem, using the
original objective function based on sum of squared distance. Find the global minimizer, plot
the results, and comment on the reasonableness of your solution.
Note: This sort of facility location problem comes up in many other applications such as optimal placement of
microprocessor circuitry components, robotic control, design of microfluidic experiments, genome sequencing
arrays, etc.
3. (Shape optimization) This question continues with the tank design problems (TD1 and TD2) consid-
ered in lectures.
(a) Fill in the missing details for the derivation of the analytical solution to the “dual” tank design
problem TD2 that maximizes the volume V (x1, x2) of a rectangular tank for a given surface
area S.
(b) Write a Matlab code that solves the unconstrained problems TD1 and TD2 numerically by
doing one of the following:
• determining the gradient and Hessian for each analytically, and then using these within
a Newton line-search algorithm (just use one of the mynewton∗ codes from class), OR
• approximating the gradient and Hessian using finite differences, and then using these
within a quasi-Newton algorithm. Here, you can use either the mybfgs or bfgswopt
solvers, along with the fdgrad and fdhess functions from Homework #3.
Use your code to solve the following two problems in order:
À For the given volume V = 100, solve problem TD1 for the minimum surface area S∗.
Á Use this value of S∗ as the surface area for problem TD2, and determine the corresponding
tank dimensions that maximize the volume.
Hence, verify that the two problems are duals of each other.
2