I am interesting in using eigenvectors of a quadratic form to perform iterative steps to get the function value to a certain point. While other methods may be more common, my quadratic form is not necessarily convex, and I need to find a guaranteed descent or ascent direction.
Let $f(x) = x^TPx + q^Tx + r$ be the quadratic function for x in $R^n$.
Now say I want to decrease the function value of $f(x) = f_0$ from this starting point to some value $f(x) = f_f$. From what I understand there are two basic iteration methods to decrease a function's value (using a step size $c > 0$:
- Gradient descent: let $x_{t+1} = x_t - c\nabla f(x)$
- Newton steps via Hessian inverse: $x_{t+1} = x_t - c\nabla^2 f(x)^{-1}\nabla f(x)$
These are typically used for convex quadratic functions. However, say for my quadratic form, P is not necessarily positive semidefinite; i.e. it could have both positive and negative eigenvalues.
Does it make sense then to take a step $x_{t+1} = x_t - cv_-$ where $v_-$ is the eigenvector corresponding to the largest negative eigenvalue (and reversed for ascent direction)? Basic numerical testing seems to confirm that this works on the function $f(x) = x^TPx$ for P with positive and negative eigenvalues.
What I'd like to know is whether or not, like gradient descent, this algorithm would converge to a value $f(x) = f_f$ in a finite number of iterations. Also, how would/should one modify these "eigenvector steps" since there is the $q^Tx$ term in the objective as well?
And lastly, please let me know if there are other preferable iterative methods for optimizing such nonconvex quadratics. Eigenvectors were just my random idea, definitely open to other approaches. Thanks.
EDIT - for clarity, here is what I am trying to do that led to my question:
minimize $y(x)$ (convex objective)
subject to $x^TP_ix + q_i^Tx + r_i \ge 0, i = 1,...,k$
and other convex constraints. And yes, I am doing a "trust region"-type iterative method, except my trust region defines where the quadratic models are "good enough" approximations of the original nonconvex (trigonometric, btw) inequality constraints. Am I better off just finding a quadratic convex approximation in the first place? My concern would be that the trust regions would be really small, I'd run into more local extrema points or saddles, have to solve more convex subproblems, etc.
The quadratic models are nonconvex: $P_i$ is not PSD or NSD in general. My question/idea came out of me wanting to be able to find a search direction that could make my inequalities closer to being true. E.g. if one of the quadratics is infeasible, step in a direction I know will increase its function value. The reason I opted for these nonconvex quadratics is that they describe the underlying functions very well over about a third of the volume of the domain, so you get a more "global" view of things. Again, this relates to wanting to solve less subproblems.