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!

Improve this question
$\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, 2016 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$
    – f10w
    Jan 22, 2016 at 15:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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