Improvement algorithm and its time complexity

[malamenm]

Hi, I have a problem with the following problem:

Assume f^j is concave and strictly increasing for all j, j=1,..,n. Show that the optimal solution x* satisfies the condition (from j=1 to n) ∑x*_j=B.

Now consider the following improvement algorithm:

start with x⁰=0 for k=1:B

select s∈argmax_j{f_j(x_j^k-1+1)-f_j(x_j^k-1}
update x^k s.t. x_j^k=x_j^k-1 for j≠s, and x_s^k=x_s^k-1+1
end
x bar = x^B

I am trying to find the time complexity of the algorithm and to show that x bar is an optimal solution (i.e. the algorithm above is an exact algorithm if fj is concave and strictly increasing for all j, j=1,..,n)

Does anybody have any suggestions on how to start on this?

Any help will be much appreciated

 

[jvicens]

Thank you for sharing your problem and seeking help. I would be happy to offer some suggestions on how to approach this problem.

Firstly, let's define some terms and assumptions to make the problem clearer. We can assume that fj represents a function that maps from a set of inputs (x) to a set of outputs (fj(x)). Concave means that the function is curving downwards, and strictly increasing means that the function is always increasing as the input increases. The notation ∑x*j represents the sum of all x values for j=1 to n. B is a constant value.

Now, to solve this problem, we can start by understanding the steps of the improvement algorithm and their purpose. The algorithm starts with an initial value of x0=0 and then iteratively updates the x values until it reaches xB, which is the final solution. The algorithm selects the index (s) for which the function fj(xjk-1+1)-fj(xjk-1) is maximum, and then updates the x values accordingly. This process continues until k reaches the constant value B.

Next, we need to consider the time complexity of this algorithm. Time complexity refers to the amount of time taken by an algorithm to solve a problem. In this case, we can see that the algorithm has a loop that runs for k=1 to B, and inside this loop, it performs a computation to find the maximum value of the function fj(xjk-1+1)-fj(xjk-1). This computation will take a constant amount of time for each iteration of the loop, and hence the time complexity of this algorithm is O(B).

To show that x bar is an optimal solution, we can use proof by contradiction. Assume that x bar is not an optimal solution, which means that there exists another solution (let's call it x*) that satisfies the condition ∑x*j=B and gives a higher value of the objective function fj(x*). However, since the algorithm updates the x values to maximize the objective function at each iteration, it will eventually reach x bar, which contradicts our assumption. Therefore, x bar must be an optimal solution.

In conclusion, the improvement algorithm has a time complexity of O(B) and produces an optimal solution x bar, making it an exact algorithm. I hope this helps you in understanding the problem and finding a solution.