I have an inequality of the form:
$$\sum_{i=1}^n a_i\cdot x_i \ge a_0$$
where $a_i\gt 0$ for all $i$. Subject to this and $x_i\ge 0$ for all $i$, I have to minimize the expression:
$$\sum_{i=1}^n b_i\cdot x_i \;\;\text{ where } b_i\ge 0$$
What would be the most efficient way in terms of time complexity to solve this problem computationally? Please point towards relevant algorithms. Also I am open to Monte Carlo algorithms for the same if the deterministic version is hard.
EDIT: There has been a modification is my application design which calls for all involved quantities to be integers(non-negative). Now since this problem falls under the category of NP-Hard problems I am looking for good local search based approaches to the problem.
As stated the problem is solved by picking the index $i$ for which $b_i/a_i$ is smallest. Then setting $x_i = a_0/a_i$ and all other variables to zero, we get the objective function summing to:
$$ a_0 \cdot \frac{b_i}{a_i} $$
Time complexity is thus $O(n)$. Let me give an example to illustrate that restricting the variables (and perhaps coefficients) to integers makes the problem more difficult but still tractable.
The following "coin change" example is taken from the Wikipedia dynamic programming article, where it is used to motivate an alternative to the greedy algorithm.
Suppose coins are available in denominations $1,4,5,15,20$. We are asked how best to make up $23$ in change, where "best" means the fewest number of coins.
If we treat this as a linear programming problem, relaxing the integer constraint to allow real (rational) values of the $x_i$, then as outlined in the answer above a minimum value of $g(x)$ is achieved by taking $x_5 = 23/20 = 1.15$ (with other variables set to zero). Note that the "problem" constraint is satisfied as equality (a tight constraint) because the solution is a vertex of the polytope formed by the intersection of half-spaces defined by all constraints (the problem constraint as well as the non-negativity constraints).
One way to satisfy the integer constraint is by a greedy algorithm that selects the largest denomination coin as many times as possible without exceeding the amount of change to be made. Following this procedure we would choose $x_5=1$ to select a denomination $20$ coin, after which change still needs to be made for $23-20 = 3$ left over. Since only the denomination $1$ coin can be used without exceeding that remainder, this greedy algorithm uses four coins in all to give exact change (equality):
$$ 23 = 20 + 1 + 1 + 1 $$
But this doesn't actually minimize $g(x)$ since a solution with three coins is possible:
$$ 23 = 15 + 4 + 4 $$
Finding that solution, with the equality constraint, can be done using the dynamic programming approach outlined in the article. It essentially involves a search in order to overcome the limitations of the "follow your nose" greedy algorithm.
We want to use the example to illustrate that relaxing the equality constraint to an inequality allows integer solutions with even fewer coins! That is:
$$ 1x_1 + 4x_2 + 5x_3 + 15x_4 + 20x_5 \ge 23 $$
has non-negative integer solutions with as few as two coins.
The attentive Reader will notice that with this "relaxed" inequality (problem constraint) the earlier algorithm comes back into consideration. That is, by checking which index has the smallest $b_i/a_i$ (where in this coin change case all the $b_i=1$), we find the noninteger solution $g(x) = 1.15$ (i.e. $x_5 = 1.15$ and other $x_i$ zero).
Thus to obtain an integer solution we can "round-up" $x_5$ to two coins, and this is indeed an optimal solution since any integer-valued solutions must give us $g(x) \ge \lceil 1.15 \rceil = 2$.
However we cannot always achieve such a simple solution for the kinds of problems described here. Our easy success with the coin changing problem depended on the fact all $b_i = 1$ here, which meant:
$$ \left\lceil a_0 \cdot \frac{b_i}{a_i} \right\rceil = b_i \cdot \lceil a_0/a_i \rceil $$
whichever index $i$ gives the least $b_i/a_i$.
The general case of your problems will call for a search structured by dynamic programming, or one of the other approaches mentioned in the integer programming article.