1
$\begingroup$

I am trying to solve the following problem, where $a_{ij} \ge 0 \ \forall i,j$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject to}\quad &\sum_{i=1}^m x_{ij} \le 1 \quad \forall j,\\ &\sum_{j=1}^n x_{ij} \le 1\quad \forall i,\\ &x_{ij} \ge 0 \quad \forall i,j.\end{align} Could you please suggest me with some methods? (The faster the better.)

Thank you in advance for your answers!

$\endgroup$
2
  • 1
    $\begingroup$ you put the label "convex-optimization" in, are you sure it is convex? If it's convex, any standard quadratic programming solver shouldn't have a problem. They'll use most likely some sort of interior point method $\endgroup$
    – jf328
    Jan 22 '16 at 15:34
  • $\begingroup$ @jf328: Yes the problem is convex. It is a quadratic program with the quadratic term matrix is diagonal and non-negative. Since the problem has a special structure, I hope I can find a method that can solve it as fast as possible (I'm trying interior point methods too). $\endgroup$
    – Khue
    Jan 22 '16 at 15:44
2
$\begingroup$

This is a regular positive definite quadratic minimization problem with linear constraints. It should be trivial to solve using one the usual methods for this approach. A simple approach would be, for example, to take the active set method explained in great detail in Nocedal and Wright, "Numerical Optimization".

You could of course also take one of the interior point, penalty, or augmented Lagrange methods -- all of these should be able to quickly solve this problem.

$\endgroup$
0

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.