0
$\begingroup$

The problem I am trying to tackle is:

$$\underset{\vec{x}}{\mathrm{argmin}}(\frac{1}{2}||\vec{x}-\vec{\mu}||^2)$$ Subject to: $$\vec{x}\cdot({\textbf{C}\vec{x}}) = K$$

Where $\vec{x}$ is an $n$ dimensional real vector, $\vec{\mu}$ is an $n$ dimensional vector, $\textbf{C}$ is an $n\times{n}$ real matrix and $K$ is a scalar. The first operation in the constraint is matrix multiplication, which yields a vector of dimension $n$. Then the dot product of the resultant vector is taken with $x$ to product a scalar.

As far as I got is fully writing out the Lagrange multiplier as so:

$$L(\vec x, \lambda) = \frac{1}{2}||\vec{x}-\vec{\mu}||^2 - \lambda(\vec{x}\cdot({\textbf{C}\vec{x}})-K)$$

Differentiating with respect to $x$ and setting the Lagrange to zero:

$$||\vec{x}-\vec{\mu}|| = \lambda\dfrac{d}{d\vec{x}}(\vec{x}\cdot({\textbf{C}\vec{x}}))$$

This yields us $n$ equations with $n+1$ unknowns. In this part even though it's fairly easy for me to see how I would differentiate any given element in the RHS, I am not totally sure how to fully represent it as a matrix and I think this is where I am getting stuck.

To solve for $n+1$ we need an extra equation, which is a differential of the Lagrange with respect to $\mu$:

$$\vec{x}\cdot({\textbf{C}\vec{x}})=K$$

The only real assumption I am making here is that there only one real distinct solution for $x$, but I think that is right. Can someone point me in the right direction and/ or let me know what I am doing wrong?

$\endgroup$
5
  • $\begingroup$ You should not be using dot for both dot product and matrix-vector product. This would be rather usual if you wrote it as $\vec x\cdot (C\vec x) = K$ or $\vec x^\top C\vec x = K$, and even more usual if $C$ were a symmetric matrix. If $x$ is a vector, you cannot multiply $\vec x C$. $\endgroup$ Aug 8 '19 at 0:24
  • $\begingroup$ Yep, you are absolutely right, my bad. Edited. $\endgroup$ Aug 8 '19 at 0:30
  • $\begingroup$ By any chance now is $C$ symmetric? You're not differentiating correctly. You need to take the gradient and get a vector in both sides. $\endgroup$ Aug 8 '19 at 0:32
  • $\begingroup$ $C$ is actually a covariance matrix from another operation(which does not depend on $x$), so it is symmetric! Thank you for the tip, I’ll look into it. $\endgroup$ Aug 8 '19 at 0:35
  • $\begingroup$ W.r. your assumption of a unique solution: think about the geometric interpretation of this problem: you’re trying to find the point on a quadric (hypersurface) that’s closest to $\mu$. Since $C$ is a covariance matrix, you’re dealing with an ellipsoid. The Lagrange multiplier method will find you constrained extrema: some of the solutions will correspond to maxima (and, depending on symmetries present, if $\mu$ is in the interior there might be an infinite number of solutions). $\endgroup$
    – amd
    Aug 8 '19 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.