Assignment 2

Due date: TBA
Total: 30 points
Coverage: Chapter 2 (Computational Approaches) and Chapter 3 (Optimization).

Submission

Use R Markdown or Quarto. Submit both your source file (.Rmd or .qmd) and its rendered PDF.

Begin the PDF with an answer table for Questions 1-3, followed by Question 4. Use the supplied response template, or make your own table with the same part labels.

Questions 1-2: Select one best answer, A, B, C, or D.
Question 3: Write True or False.
Question 4: Explain your reasoning in your own words, using one or two sentences per numbered prompt.

Only Question 4 requires explanations. R code and figures are optional. If you use R to check your work, include the code in your source file.

Question	Format	Points
1	8 multiple-choice questions on Chapter 2	8
2	8 multiple-choice questions on Chapter 3	8
3	6 true/false questions	6
4	2 short explanations with four prompts each	8
Total		30

The questions use the main material in both chapters; the optional real-world applications at the end of Chapter 3 are not required.

Question 1: Computational Approaches [8]

Select the best answer. Each question is worth 1 point.

1a)

Two formulas are mathematically equivalent in exact arithmetic. Which statement about their computer implementations is most accurate?

A. They can produce different numerical results because computers use finite-precision arithmetic.
B. They must produce exactly the same result in every decimal place.
C. They must use the same amount of memory.
D. They must take the same amount of time.

1b)

Let \(A\) be a nonsingular square matrix and \(b\) a compatible vector. Which R expression solves \(Ax=b\) without explicitly forming \(A^{-1}\)?

A. solve(A) %*% b
B. solve(A, b)
C. crossprod(A, b)
D. A %*% b

1c)

For a numeric matrix X, which expression is mathematically equivalent to crossprod(X)?

A. X %*% t(X)
B. X * X
C. sum(X * X)
D. t(X) %*% X

1d)

A regression design matrix has one column that is almost a copy of another. What is the main numerical concern?

A. The number of observations must have changed.
B. The response variable must contain missing values.
C. The normal-equation system can be ill-conditioned, making coefficient estimates sensitive to small perturbations.
D. The residual sum of squares must be exactly zero.

1e)

Suppose a full-column-rank design matrix has the thin QR decomposition \(X=QR\), with \(Q^\top Q=I\). Which triangular system gives the least-squares coefficients?

A. \(R\hat\beta=Qy\)
B. \(R\hat\beta=Q^\top y\)
C. \(Q\hat\beta=R^\top y\)
D. \(R^\top\hat\beta=Q^\top y\)

1f)

Suppose \(\Sigma=R^\top R\) is positive definite, with \(R\) upper triangular, and \(z=x-\mu\). Which computation gives \(z^\top\Sigma^{-1}z\) without explicitly forming an inverse?

A. Solve \(R^\top v=z\), then compute \(v^\top v\).
B. Solve \(Rv=z\), then compute \(v^\top v\).
C. Compute \(v=Rz\), then compute \(v^\top v\).
D. Compute \(z^\top z\) without using \(R\).

1g)

Use the same Cholesky convention, with

\[ R=\begin{pmatrix}4&1\\0&2\end{pmatrix}, \qquad z=\begin{pmatrix}4\\5\end{pmatrix}, \qquad \Sigma=R^\top R. \]

What is \(z^\top\Sigma^{-1}z\)?

A. 29
B. 25
C. 5
D. 3

1h)

You evaluate multivariate normal log-densities at many different observations, using the same positive-definite covariance matrix \(\Sigma\). Which work can be reused?

A. The centered vector \(z=x-\mu\) for every observation.
B. The complete log-density value for every observation.
C. The quadratic form \(z^\top\Sigma^{-1}z\) for every observation.
D. The Cholesky factor of \(\Sigma\) and its log-determinant.

Question 2: Optimization [8]

Select the best answer. Each question is worth 1 point.

2a)

You want to maximize a log-likelihood \(\ell(\theta)\) using an optimizer that minimizes its objective. Which objective should you supply?

A. \(\ell(\theta)\)
B. \([\ell(\theta)]^2\)
C. \(-\ell(\theta)\)
D. \(|\ell(\theta)|\)

2b)

Which conditions give the usual root-bracketing guarantee for bisection on an interval \([a,b]\)?

A. \(f(a)\) and \(f(b)\) are both positive.
B. \(f\) is differentiable at \(a\), regardless of its behavior elsewhere.
C. The midpoint is smaller than both endpoints.
D. \(f\) is continuous on \([a,b]\) and \(f(a)f(b)<0\).

2c)

Apply one Newton root-finding update to \(f(x)=x^2-3\), starting at \(x_0=2\). What is \(x_1\)?

Use \(x_1=x_0-f(x_0)/f'(x_0)\).

A. 1.75
B. 1.50
C. 2.25
D. 3.00

2d)

Minimize \(Q(x)=(x-3)^2\) using gradient descent. Starting at \(x_0=0\) with step size \(\alpha=0.25\), what is the next iterate?

Use \(x_1=x_0-\alpha Q'(x_0)\).

A. -1.50
B. 1.50
C. 0.75
D. 3.00

2e)

What is the main computational idea behind BFGS?

A. Enumerate every feasible parameter value.
B. Use the exact Hessian inverse at every iteration.
C. Guarantee a global optimum by adding random noise.
D. Update an approximation to curvature information instead of repeatedly computing the exact Hessian.

2f)

Consider \(Q(\theta_1,\theta_2)=(\theta_1-1)^2+100(\theta_2-1)^2\). Why can a single fixed step size be difficult for gradient descent?

A. The much larger curvature in one direction can cause zig-zagging or force a small step size.
B. The function is not differentiable.
C. The function has infinitely many local minima.
D. The gradient is zero at every point.

2g)

In simulated annealing for a minimization problem, a proposed move increases the objective by \(\Delta Q=2\). At temperature \(T=1\), what is its acceptance probability?

Use \(P(\text{accept})=\exp(-\Delta Q/T)\).

A. 0
B. \(e^{-2}\approx0.1353\)
C. 0.5
D. 1

2h)

A smooth, nonconvex objective is minimized with BFGS from several starting values. The returned objective values differ. What is the most appropriate next step?

A. Always keep the run with the fewest iterations.
B. Average all parameter vectors without evaluating the objective there.
C. Compare feasible returned objective values, examine diagnostics, and consider additional starts.
D. Declare the first converged result globally optimal.

Question 3: True or False [6]

Write True or False for each statement. Each statement is worth 1 point. No explanation is required.

3a)

For a full-column-rank regression design matrix, a normal-equation implementation and a QR implementation must return coefficients that agree in every floating-point digit.

3b)

When optimizing a multivariate normal log-likelihood over \(\mu\) and \(\Sigma\) with fixed dimension \(d\) and sample size, dropping an additive term that is constant in these parameters does not change the maximizer.

3c)

Replacing an explicit matrix inverse with a direct linear-system solve guarantees accurate coefficients even when the matrix is arbitrarily ill-conditioned.

3d)

A solution of \(Q'(x)=0\) can be a local maximum rather than a local minimum.

3e)

Under suitable smoothness conditions and with a starting point sufficiently close to a simple root, Newton’s method has quadratic convergence.

3f)

A genetic algorithm uses one evolving candidate solution, whereas simulated annealing maintains a population of candidate solutions.

Question 4: Explain What the Results Mean [8]

Each part is worth 4 points: 1 point for each numbered prompt. Use one or two sentences per prompt. We grade the statistical and computational reasoning, not the exact wording of your response.

4a) Rank deficiency is not missing data [4]

Suppose a regression design matrix contains an intercept and two predictors, with \(x_2=2x_1\) exactly and \(x_1\) nonconstant. There are no missing values. You try

solve(crossprod(X), crossprod(X, y))

and receive a computationally singular system error. A QR-based fit instead reports the numerical rank and returns NA for one redundant coefficient.

Explain:

What feature of the design matrix causes the normal-equation solve to fail?
What does the NA coefficient mean in this situation?
Can a QR-based approach still provide ordinary least-squares fitted values? Explain how.
What is one sensible way to remove the redundancy while retaining the same ordinary least-squares fitted values?

4b) A converged result still needs interpretation [4]

You are minimizing

\[ Q(x)=(x^2-1)^2+0.2x+1, \qquad x\in\mathbb{R}. \]

Two BFGS runs give the following results, rounded to four decimal places:

Run	Starting value	Returned value	Objective value \(Q(x)\)	Convergence code
A	1	0.9740	1.1974	0
B	-1	-1.0241	0.7976	0

Here, code 0 means the optimizer reports successful completion according to its convergence criteria. You do not need to run the optimizer or prove global optimality.

Explain:

Which returned point would you retain as the best found so far, and why?
How can a deterministic method return different answers for the same objective?
Do these convergence codes alone establish that either point is a global minimum? Explain.
Describe one additional check or search you would perform, and explain what it would tell you.