I have an optimisation problem that can be described as a simple set of linear equations in dot product form as $\mathbf{b}=\mathbf{x} \cdot A$, where vector $\mathbf{b}$ and matrix $A$ are known and vector $\mathbf{x}$ has to be estimated. Normally, this can be easily solved with linear least squares. However, both $\mathbf{b}$ and $A$ contain only non-negative integer values, and the estimated vector $\mathbf{x}$ also needs to consist only of non-negative integers.

The dimensions are $\mathbf{b} \in \Bbb{N}^{352}$, $\mathbf{x} \in \Bbb{N}^{24010}$, and $A \in \Bbb{N}^{24010 \times 352}$, where $\Bbb{N}$ also includes $0$.

The search space is rather large, which means I would rather not opt for gradient or stochastic search algorithms to find a global optimum. Is there an algebraic or statistic method to solve such optimisation problems, or am I looking for a free lunch?

  • 1
    $\begingroup$ How many unknowns do you have, that is , dimension of $x$? This can be formulated as as (mixed) integer linear programming problem, or, since you mention least squares, a mixed integer quadratic programming problem. See cran.r-project.org/web/views/Optimization.html $\endgroup$ – kjetil b halvorsen Aug 8 '17 at 14:50
  • 1
    $\begingroup$ The dimension of x is rather large, i.e. 24010, and may in future applications even be larger. I've tried to get an impression of (pure) integer programming, however, I am completely new to the subject. I've found some articles mentioning branch-and-cut or combinations with tabu search, any idea whether there feasible algorithms (preferably already available as python library) for a problem this size (the dimension of $b$ is 352)? A nod in the right direction would be wonderful. $\endgroup$ – Gijs Peters Aug 10 '17 at 9:59
  • $\begingroup$ can you give all the dimensions? will come back $\endgroup$ – kjetil b halvorsen Aug 10 '17 at 10:24
  • $\begingroup$ $\mathbf{b} \in \Bbb{N}^{352}$, $\mathbf{x} \in \Bbb{N}^{24010}$, and $A \in \Bbb{N}^{24010 \times 352}$, where $\Bbb{N}$ also includes $0$. $\endgroup$ – Gijs Peters Aug 10 '17 at 14:34
  • $\begingroup$ To ask the obvious: Can you please tell us what have you tried so far? :) For example have you tried the "obvious heuristic" approach of simply solving the OLS with non-negative constraints and then discretising the solution? (BTW, the dimensions mentioned are not something mortifying - a $24K \times 352$ design matrix is nothing to write home about for a standard LS task - granted there might be some subtleties we do not know) $\endgroup$ – usεr11852 Aug 10 '17 at 21:19

I think (tell me if I'm wrong) that the aim of transforming your optimisation problem into solving a linear system equation is precisely simplifying the problem. One can solve a linear system, this is pure algebra whereas solving an optimization problem is quite more difficult in the sense that this is less obvious to check if a solution works.

Thus why don't you just consider linear system equation algorithms solvers such as :

Gauss, Cholesky, Jacobi, gradient methods or even probabilistic methods ?

PS : I know this is not a suitable answer for the policy of the website, this is a real question, not a suggestion, and I would have put it as a comment but I can't.

  • $\begingroup$ Thanks. In essence, the problem can be described as a linear without simplifications or concessions. The only problem is that the parameter estimations should be non-negative integers, and I would like to know if there is a least squares variation that can solve this; calculating gradients or jacobians would be very expensive. $\endgroup$ – Gijs Peters Aug 8 '17 at 14:15
  • $\begingroup$ Oh I see now, my mistake, the algorithms I mentionned would certainly not give you non-negative integers. That's my fault, even if I read carefuly, this was still not enough carefuly. $\endgroup$ – ThanhKim Aug 11 '17 at 7:40

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.