# Quadratic Optimization Problem with Box Constraints

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

Hint: let $A_k = A+\frac{1}{k}I_n$. Solve the problem for this and in each iteration increase $k$.
• 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^*$... – Mohammad Khosravi Jul 7 '14 at 11:51
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.