Skip to main content
MathOverflow

Return to Question

typo in formula; deleted 2 characters in body
Source Link
JMS
JMS
  • 269
  • 2
  • 11

Let $A$ be $p\times p$ symmetric positive definite with distinct eigenvalues and $x_p\in \mathbb{R}^p$ and consider the problem

Minimize $x'Ax + b'x$

Subject to $x'x=1$

Most of the information I've found is is either very general/theoretical or specific to linear constraints, although I'm largely flitting around optimization texts and crossing my fingers since I don't know exactly what I'm looking for.

Anyway, my first pass was to use a Lagrange multiplier;

$f(x, \lambda) = x'(A+\lambda)x + b'x + \lambda(x'x-1)$$f(x, \lambda) = x'Ax + b'x + \lambda(x'x-1)$

Taking derivatives and setting to zero gives

$x = -\frac{1}{2} (A+\lambda I)^{-1}b$

$\frac{1}{4} b'(A+\lambda I)^{-2}b = 1$

I've got my system in $p+1$ equations and I can go about solving them. Analytically I haven't gotten anywhere, except simplifying things a little with the eigendecomposition of $A$. When $b=0$ the solution is trivially $x=e_1$, the first eigenvector of $A$, so let's ignore that case. So my first question: is there an analytical solution that I'm too mathematically challenged to see? If not, what is the best way to solve this problem?

(To help quantify "best", I have potentially many such problems to solve for smallish $p$, say 5-10, and $A$ is the same but $b$ changes. An approximate solution is OK, in fact an approximate solution near the correct global solution is better than an exact local one.)

Let $A$ be $p\times p$ symmetric positive definite with distinct eigenvalues and $x_p\in \mathbb{R}^p$ and consider the problem

Minimize $x'Ax + b'x$

Subject to $x'x=1$

Most of the information I've found is is either very general/theoretical or specific to linear constraints, although I'm largely flitting around optimization texts and crossing my fingers since I don't know exactly what I'm looking for.

Anyway, my first pass was to use a Lagrange multiplier;

$f(x, \lambda) = x'(A+\lambda)x + b'x + \lambda(x'x-1)$

Taking derivatives and setting to zero gives

$x = -\frac{1}{2} (A+\lambda I)^{-1}b$

$\frac{1}{4} b'(A+\lambda I)^{-2}b = 1$

I've got my system in $p+1$ equations and I can go about solving them. Analytically I haven't gotten anywhere, except simplifying things a little with the eigendecomposition of $A$. When $b=0$ the solution is trivially $x=e_1$, the first eigenvector of $A$, so let's ignore that case. So my first question: is there an analytical solution that I'm too mathematically challenged to see? If not, what is the best way to solve this problem?

(To help quantify "best", I have potentially many such problems to solve for smallish $p$, say 5-10, and $A$ is the same but $b$ changes. An approximate solution is OK, in fact an approximate solution near the correct global solution is better than an exact local one.)

Let $A$ be $p\times p$ symmetric positive definite with distinct eigenvalues and $x_p\in \mathbb{R}^p$ and consider the problem

Minimize $x'Ax + b'x$

Subject to $x'x=1$

Most of the information I've found is is either very general/theoretical or specific to linear constraints, although I'm largely flitting around optimization texts and crossing my fingers since I don't know exactly what I'm looking for.

Anyway, my first pass was to use a Lagrange multiplier;

$f(x, \lambda) = x'Ax + b'x + \lambda(x'x-1)$

Taking derivatives and setting to zero gives

$x = -\frac{1}{2} (A+\lambda I)^{-1}b$

$\frac{1}{4} b'(A+\lambda I)^{-2}b = 1$

I've got my system in $p+1$ equations and I can go about solving them. Analytically I haven't gotten anywhere, except simplifying things a little with the eigendecomposition of $A$. When $b=0$ the solution is trivially $x=e_1$, the first eigenvector of $A$, so let's ignore that case. So my first question: is there an analytical solution that I'm too mathematically challenged to see? If not, what is the best way to solve this problem?

(To help quantify "best", I have potentially many such problems to solve for smallish $p$, say 5-10, and $A$ is the same but $b$ changes. An approximate solution is OK, in fact an approximate solution near the correct global solution is better than an exact local one.)

Source Link
JMS
JMS
  • 269
  • 2
  • 11

Optimizing a quadratic restricted to the sphere

Let $A$ be $p\times p$ symmetric positive definite with distinct eigenvalues and $x_p\in \mathbb{R}^p$ and consider the problem

Minimize $x'Ax + b'x$

Subject to $x'x=1$

Most of the information I've found is is either very general/theoretical or specific to linear constraints, although I'm largely flitting around optimization texts and crossing my fingers since I don't know exactly what I'm looking for.

Anyway, my first pass was to use a Lagrange multiplier;

$f(x, \lambda) = x'(A+\lambda)x + b'x + \lambda(x'x-1)$

Taking derivatives and setting to zero gives

$x = -\frac{1}{2} (A+\lambda I)^{-1}b$

$\frac{1}{4} b'(A+\lambda I)^{-2}b = 1$

I've got my system in $p+1$ equations and I can go about solving them. Analytically I haven't gotten anywhere, except simplifying things a little with the eigendecomposition of $A$. When $b=0$ the solution is trivially $x=e_1$, the first eigenvector of $A$, so let's ignore that case. So my first question: is there an analytical solution that I'm too mathematically challenged to see? If not, what is the best way to solve this problem?

(To help quantify "best", I have potentially many such problems to solve for smallish $p$, say 5-10, and $A$ is the same but $b$ changes. An approximate solution is OK, in fact an approximate solution near the correct global solution is better than an exact local one.)