DSC 140B
Problems tagged with optimization

Problems tagged with "optimization"

Problem #047

Tags: optimization, linear algebra, quiz-03, eigenvalues, eigenvectors, lecture-04

Let \(A\) be a symmetric matrix with eigenvalues \(6\) and \(-9\).

True or False: The maximum value of \(\|A\vec{x}\|\) over all unit vectors \(\vec{x}\) is \(6\).

Solution

False. The maximum is \(9\).

The maximum of \(\|A\vec{x}\|\) over unit vectors is achieved when \(\vec{x}\) is an eigenvector corresponding to the eigenvalue with the largest absolute value.

Here, \(|-9| = 9 > 6 = |6|\), so the maximum is achieved at the eigenvector with eigenvalue \(-9\).

If \(\vec{u}\) is a unit eigenvector with eigenvalue \(-9\), then:

\[\|A\vec{u}\| = \|(-9)\vec{u}\| = |-9| \cdot\|\vec{u}\| = 9 \cdot 1 = 9 \]

Problem #048

Tags: optimization, linear algebra, quiz-03, eigenvalues, eigenvectors, quadratic forms, lecture-04

Let \(A\) be a \(3 \times 3\) symmetric matrix with the following eigenvectors and corresponding eigenvalues: \(\vec{u}^{(1)} = \frac{1}{3}(1, 2, 2)^T\) has eigenvalue \(4\), \(\vec{u}^{(2)} = \frac{1}{3}(2, 1, -2)^T\) has eigenvalue \(1\), and \(\vec{u}^{(3)} = \frac{1}{3}(2, -2, 1)^T\) has eigenvalue \(-10\).

Consider the quadratic form \(\vec{x}\cdot A\vec{x}\).

Part 1)

What unit vector \(\vec{x}\) maximizes \(\vec{x}\cdot A\vec{x}\)?

Solution

\(\vec{u}^{(1)} = \frac{1}{3}(1, 2, 2)^T\) The quadratic form \(\vec{x}\cdot A\vec{x}\) is maximized by the eigenvector with the largest eigenvalue. Among \(4\), \(1\), and \(-10\), the largest is \(4\), so the maximizer is \(\vec{u}^{(1)}\).

Part 2)

What is the maximum value of \(\vec{x}\cdot A\vec{x}\) over all unit vectors?

Solution

\(4\) The maximum value equals the largest eigenvalue. We can verify:

\[\vec{u}^{(1)}\cdot A\vec{u}^{(1)} = \vec{u}^{(1)}\cdot(4\vec{u}^{(1)}) = 4(\vec{u}^{(1)}\cdot\vec{u}^{(1)}) = 4 \cdot 1 = 4 \]

Part 3)

What unit vector \(\vec{x}\) minimizes \(\vec{x}\cdot A\vec{x}\)?

Solution

\(\vec{u}^{(3)} = \frac{1}{3}(2, -2, 1)^T\) The quadratic form is minimized by the eigenvector with the smallest eigenvalue. Among \(4\), \(1\), and \(-10\), the smallest is \(-10\), so the minimizer is \(\vec{u}^{(3)}\).

Part 4)

What is the minimum value of \(\vec{x}\cdot A\vec{x}\) over all unit vectors?

Solution

\(-10\) The minimum value equals the smallest eigenvalue. We can verify:

\[\vec{u}^{(3)}\cdot A\vec{u}^{(3)} = \vec{u}^{(3)}\cdot(-10\vec{u}^{(3)}) = -10(\vec{u}^{(3)}\cdot\vec{u}^{(3)}) = -10 \cdot 1 = -10 \]

Problem #094

Tags: laplacian eigenmaps, quiz-05, optimization, lecture-08

Define the cost function to be:

\[\text{Cost}(\vec f) = \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n w_{ij}(f_i - f_j)^2 \]

Consider the similarity matrix with \(n = 3\):

\[ W = \begin{pmatrix} 1 & 0.5 & 0\\ 0.5 & 1 & 0.9\\ 0 & 0.9 & 1 \end{pmatrix}\]

Which of the following embedding vectors \(\vec f\) leads to the minimum cost?

Solution

\((1, 1, 1)^T\).

When \(f_i = f_j\) for all \(i, j\), the term inside the summation is always \(0\), leading the value of the cost function to be \(0\). This is the minimum possible value of the cost function, since all terms in the sum are non-negative.