Algorithm Conceptual Question (Decay Rate Example)

[drw5ff]

Hey Johan,

I had a conceptual question about the bisection algorithm you used for your decay rate example: How do you know that the t_works that you converge on is the minimum solution and continuous everywhere above it? Is it assumed since the problem is continuous quasiconvex with some local optimal solution?

For instance, the t_upper value you converge on depends on t_upper = t_upper*2. These are discrete values with several points inbetween that we assume feasible since the larger values are feasible. I believe the same thing happens near the midpoint t_test = (t_upper+t_lower)/2.

I'm not looking for an elaborate proof. I'm just looking for a confirmation that bisection algorithm does what it's supposed to. Thanks in advance for any feedback you're willing to give.

- Dan

[Johan Löfberg]

A basic bisection (where we maximize t, and the feasible set is monotonically decreasing in t) relies on

1. If it is infeasible for t=A, then it is infeasible for any t>A, and the optimal value must be less than A

2. If it is feasible for t=B, then any optimal solution must have t>=B

Hence, use any method you want to get some A and some B. Then check C=(A+B)/2 which either is infeasible or feasible, and iterate

[drw5ff]

Thanks Johan!

That answer helps a lot.