1

$x$ is a known matrix, $y$ is a known vector, solve for $w$ (weights vector) given the following constraints.

  • $w_1 x_{1,1} + w_2 x_{2,1} + \dots + w_n x_{n,1} = y_1$
  • $w_1 x_{1,2} + w_2 x_{2,2} + \dots + w_n x_{n,2} \geq y_2$
  • $w_1 x_{1,3} + w_2 x_{2,3} + \dots + w_n x_{n,3} \leq y_3$
  • ${}\quad\vdots$
  • $w_1 x_{1,m} + w_2 x_{2,m} + \dots + w_n x_{n,m} \gt y_m$
  • all weights must be positive, upper bounded (e.g. $0 \leq w_i \leq 5)$
  • number of non-zero weights should be small relative to $m$ (e.g. 10 non-zero weights when $m$ is 10,000)

I am new to linear programming. How should I go about solving this problem? If applicable, what software packages and functions in those packages should I use?

Michael Hardy
  • 1
Amir Sadoughi
  • 11
  • What do you want to maximize or minimize ? – Claude Leibovici Jan 26 '14 at 15:59
  • @ClaudeLeibovici I don't have anything to maximize or minimize at the moment. I could add a price to each $x_i$, minimizing the sum cost ($\sum w_i x_{i,price}$), if that helps. – Amir Sadoughi Jan 26 '14 at 16:06
  • So, with the price as objective, it looks like my problem is the classic diet problem with the added constraint on the number of non-zero weights (cardinality constraint). Any ideas on solution methods? – Amir Sadoughi Jan 26 '14 at 17:18

0 Answers0