1
$\begingroup$

I want to solve a problem of form $$\min_x x'Ax + b'x \;\;\mbox{ s.t. } l\leq x \leq u$$ where $A$ is a positive semidefinite matrix, thus the function I'm optimizing should be convex.

However the eigenvalues of $A$ are all close to zero or zero, and on my computer due to numerical errors they might be negative zero.

I'm looking for a way to easily solve this problem numerically, right now I'm using gradient descent and repair solutions outside the box constraint by forcing them back onto the border. However I'm not sure whether that is a valid approach or not.

Which method of Numerical Optimization would one use for this kind of problem? Keeping in mind my problems with the machine precision.

Cheers,

Lukas

$\endgroup$
0
$\begingroup$

Hint: let $A_k = A+\frac{1}{k}I_n$. Solve the problem for this and in each iteration increase $k$.

$\endgroup$
  • $\begingroup$ you mean in each iteration of gradient descent? $\endgroup$ – Whadupapp Jul 7 '14 at 11:48
  • $\begingroup$ Set $k=1$, use steepest descent until stopping condition at ${\rm x}_1^*$, the restart then algorithm with $k=2$ and initial point ${\rm x}_1^*$. Again use a steepest descent until stopping condition at ${\rm x}_2^*$, then restart the algorithm with $k=3$ and initial point ${\rm x}_2^*$... $\endgroup$ – Mohammad Khosravi Jul 7 '14 at 11:51
  • $\begingroup$ seems to do the trick =) Not very fast though...I guess I'll have to adapt the stopping criteria, using a less strict one for early iterations. Thanks! $\endgroup$ – Whadupapp Jul 7 '14 at 13:11
0
$\begingroup$

One way to deal with the zero eigenvalues is to perform a 'eigenvalue clipping'. The matrix $A$ can be written as its eigenvalue decomposition $$A = Q\Lambda Q^{-1}$$ where $\Lambda$ is a diagonal matrix with the eigenvalues of $A$. Replace the zero and near-zero eigenvalues in $\Lambda$ with a positive number $\epsilon$ and call the resulting matrix $\Lambda'$. Construct a new matrix $$A' = Q\Lambda'Q^{-1}$$ $A'$ now is fully positive definite. You should be able to perform the optimization with $A'$ without problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.