For each of the following statements, please indicate whether the statement is true or false and justify your answer.

(a) (4 pts) If I solve an optimization problem, then add a new constraint and solve it again, the optimal solution must change.

(b) (4 pts) An optimization problem with a discontinuous objective function and a closed and bounded feasible region can never admit an optimal solution.

(c) (4 pts) Consider the optimization problem

(P) = min f(x) s.t. g(x) ≤ 0.

Assume (P) admits an optimal solution and the optimal objective value is v. Now consider the optimization problem (P′ ) = min f(x) s.t. g(x) ≤ 1 and assume (P′ ) also admits an optimal solution, with objective value v′ . Then we know that v′ ≤ v.

(d) (4 pts) Consider an optimization problem:

(P) : min f(x) s.t. x ∈ X , where X is a non-empty closed convex set. Suppose that the problem (P) has the property that every local optimal solution is also globally optimal. Then f(x) must be a convex function.

(e) (4 pts) Let f(x) = max(min(x, −x + 1), min(x − 1, −x + 2)) defined for x ∈ R. Then f is convex.

(f) (4 pts) Let g(x) = ( 0 if x < 0x2ifx ≥ 0.

Then g is convex.

Problem 2: Convex composition rules (20 pts)

In Lecture 4, we explained that composing convex functions preserved convexity under certain conditions (linear inner function or nondecreasing outer function). The goal of this problem is to prove this result. (As a result, in this problem you may not use the composition rules discussed in lecture.)

(a) (3 pts) Consider the function f(x) = ex2 . Notice that it can be decomposed as f(x) = h(g(x)), where g(x) = x2 and h(y) = ey . Both g and h are convex functions. Prove f(x) = ex2 is a convex function for x ∈ R. Plot f over the interval x ∈ [−2, 2].(b) (3 pts) Now let g(x) = x2 and h(y) = e−y . Both g and h are convex functions. Is f(x) = h(g(x)) a convex function for x ∈ R? Plot f over the interval [−2, 2].

(c) (8 pts) Prove the following general result: If h(y) is a convex and nondecreasing function in y ∈ R and g(x) is convex for x ∈ Rn, then f(x) = h(g(x)) is convex. You cannot assume the functions are differentiable. Note that the example in (a) satisfies the condition, but the example in (b) does not.

(d) (6 pts) Show f(x, y) = ln(ex + ey ) for (x, y) ∈ R2 is a convex function. Note that h(y) = log(y) is concave, but composing with the inner exponential functions makes the overall function convex.

Problem 3: Ellipsoids and quasi-convexity (25 pts)

(a) (4 pts) One of the most useful convex sets in optimization is the ellipsoid, which is a higher-dimensional generalization of the two-dimensional ellipse. A particular ellipse in R2 is given below:

E =  x = (x1, x2) :  x1 x2  5/8 3/83/8 5/8   x1x2 ≤ 1Prove that E is a convex set.

(b) (4 pts) More generally, an ellipsoid in Rn is defined as E = {x : (x − ¯x)⊺Q(x − ¯x) ≤ 1} , which is centered at¯x with a positive-definite matrix Q. Prove that E is a convex set by generalizing your result from part (a).

(c) (7 pts) A function f : Rn is called quasiconvex if

f(λx + (1 − λ)y) ≤ max {f(x), f(y)} ∀x, y ∈ Rn , λ ∈ [0, 1]

Prove that if f is a quasiconvex function, then the sub-level set Sα = {x ∈ Rn : f(x) ≤ α} is a convex set for every α.

(d) (5 pts) It turns out that the reciprocal of part (c) is also true, namely, if all the sub-level sets of a function are convex, then the function is quasiconvex. Similarly, if all the super-level sets of a function are convex, then the function is quasiconcave. Use this fact to show that the probability density function of a standard normal random variable is quasiconcave. Recall that the probability density function of a standard normal random variable in one dimension is given by f(x) =1√2π e− x22, defined for x ∈ R.

(e) (5 pts) More generally, a multi-variate (n-dimensional) normal random variable with mean ¯x ∈ Rn and covariance matrix Q ∈ Rn×n has the following probability density function:

f(x) =1(2π) n/2p det(Q)e− 12(x−¯x)⊺Q(x−¯x), where the covariance matrix is symmetric and positive-definite. Show that f is quasi-concave, using results from part (b) and (d).

Problem 4: Mortgage financing (31 pts)

After receiving several performance-based raises at work and saving up for several years, you finally have enough income and savings to purchase your dream condo in Atlanta. Congratulations!

The property you are purchasing has a closing price of $500,000, for which you put down a 20% down payment ($100,000). You plan to take out a mortgage to finance the remaining $400,000. At the bank, your mortgage officer offers you three fixed-rate mortgage choices, described in Table 1.

(a) (2 pts) For a fixed-rate mortgage, the (constant) monthly payment p is given by the following expression:

p =Lr(1 + r)n (1 + r)n − 1, where

(i) Using this formula, compute the monthly payment (rounded to the nearest cent) for each of the three mortgage options provided by the bank.

(ii) Which loan has the highest monthly payment?

(iii) Which loan has the highest total payment over its lifetime?

Because your first priority is keeping the monthly payment down, and you’re planning to stay in Atlanta for a long time, you’re feeling good about the 30-year mortgage. However, you feel like you could be getting a better deal. What if instead of picking one of the three mortgages, you combined all three to reduce the monthly payment even further?

You decide to build an optimization model to solve this problem. Formally, you are trying to find the optimal allocation of the loan principal L between n = 3 mortgage products over a time horizon of T months.

Each product i has a fixed monthly interest rate ri and a number of payment months Ti.

You define the decision variables as follows:

(b) (2 pts) What are the upper and lower bounds (if any) on the decision variables?

(c) (1 pt) What is the interpretation of y1,0/(P 3i=1 yi,0)?

(d) (3 pts) In a given month t, what is the relationship between yi,t and xi,t?

(e) (6 pts) Given your answers to part (b), (c) and (d), formulate an optimization problem to minimize the total monthly payment across all loans, with constraints ensuring that the loans initially total L = $400, 000 and loan i is fully paid off in month Ti.

(f) (2 pts) Our optimization formulation allows different amounts to be paid towards each loan each month,as long as the loan is fully paid off in the allotted timeframe. The bank doesn’t like this unpredictable payment schedule and imposes a minimum monthly payment mi = $100 on each loan i. Modify the formulation from part (e) to incorporate this new constraint.

(g) (10 pts) Implement the optimization model in JuMP and solve it using Gurobi. Make sure to submit your code as a Jupyter notebook.

(i) Report the optimal objective value (optimal monthly payment).

(ii) What are the monthly savings compared to the lowest monthly payment from part (a)?

(iii) What are the total savings over the 30-year horizon?

(iv) What fraction of the total loan amount L is allocated to each mortgage product?

(v) Plot the monthly payments for each loan as a function of time. You can use the areaplot function from the Plots package in Julia to produce a stacked area plot. In a separate figure, create a second stacked areaplot showing the remaining balance on each loan as a function of time.

Some things to watch out for when implementing:

(h) (3 pts) How would the optimal monthly payment change if the total loan amount L increased from $400,000 to $450,000?

(i) (2 pts) How would the optimal monthly payment change if the minimum payment m1 on the 15-year mortgage increased from $100 to $150?

Note that the JuMP documentation described the shadow price function as reporting “a value that can be interpreted as the improvement in the objective in response to an infinitesimal relaxation (on the scale of one unit) in the right-hand side of the constraint”.