2
$\begingroup$

I'm given a $M\times N$ ($M$ rows, $N$ cols) matrix $X$ and a $1\times M$ column vector $y$ ($M>N$). I need to find such a vector $x$ that minimizes the value of s, where

$s= \sum_{i=1}^{M}\left [(y_i - \hat{y}_i)^2 \right] $

and where $\hat{y} = X \times x$

Basicaly, this is a set of linear constraints. There is also a constraint that for every $x_{i, j} \in X$ , the following is true: $0 \le x_{i,j} \lt 1$

It is known that $X$ is sparse (most of the elements are 0's). The typical number of rows in $X$ is 200 and the typical number of columns is 150

Is Simplex algorithm or gradient-based optimization methods well-suited to perform this job or should I try using global heuristic methods such as Genetic algorithm, taboo search etc? What Python tools would you suggest to attack this problem?

Last, but not least: is there any other SE forum that is better suited for this questoin?

Improve this question
$\endgroup$
2
  • $\begingroup$ As for now it is ok here; proper site is in commitment on Area now. $\endgroup$
    – user88
    Jul 26, 2011 at 8:00
  • $\begingroup$ @David, what you describe is least squares and the solution $x$ is given by $x=(X'X)^{-1}X'y$, so it does not matter whether $X$ is restricted or not. Could you please clarify whether the constraints are on $x$ or on $X$? If there are linear inequality constraints on $x$ then user603 answer applies. $\endgroup$
    – mpiktas
    Jul 26, 2011 at 11:14

1 Answer 1

Reset to default
1
$\begingroup$

This is a classical problem (quadratic approximation subject ot linear constraints).

Check function $\verb+lsei+$ in $\verb+R+$ package $\verb+lsei+$ or the matlab package cvx or the python package cvxopt.

Improve this answer
$\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.