1
$\begingroup$

I would like to solve the following optimization problem \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} $Q$ is a positive semidefinite matrix. $\lambda>0$ is a constant (a real number).

I want to solve this problem repeatedly, with the slight change of $p$ and $Q$ in each iteration. The length of the vector $x$ is at most 1000.

I need a method as fast as possible, which can use the result of previous solve of the problem. Is there any source code available for the method? And if there is please provide a reference to it.

$\endgroup$
  • $\begingroup$ I don't have a library or even a method for you to use. Things I would need to know include the following: Is $\lambda$ just a number? Do you mean that $Q$ is positive semidefinite? Is $Q$ dense or sparse or neither? Perhaps you could give me the source where you get this problem from then I could take a look. $\endgroup$ – fred Apr 4 '16 at 19:35
  • $\begingroup$ :). yes, $Q$ is positive semidefinite and dense. $\lambda$ is just a number. I have a problem which I solved. Now my bottleneck is this problem, which I have to solve it efficiently, $\endgroup$ – user85361 Apr 5 '16 at 23:50
  • 1
    $\begingroup$ You might do well using a hot start capable active set QP solver which uses not only the previous optimum x, but also the previous optimum active set. This could provide a big speedup, particularly if many of the variables are on the bounds at the optimum, and the set of variables on their bounds does not vary much as Q and p are changed. $\endgroup$ – Mark L. Stone Jul 21 '16 at 1:07
  • $\begingroup$ Thank you @MarkL.Stone. Do you know of any such method with a more detailed algorithm? or even a source code? Could you make this an answer. Does using previous optimum active set, makes an improvement. The bounds are not changing at all. $\endgroup$ – user85361 Jul 21 '16 at 6:13
2
$\begingroup$

You could try any iterative algorithm, such as gradient descent or L-BFGS. To speed up solving each instance after the first, use the solution to the prior instance as the initial value for solving the next instance. Here the heuristic is that if $p,Q$ has changed only slightly, then we hope the optimal solution will be affected by only a small amount.

$\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.