This paper studies the reduction of computation time of the global optimization for bilinear matrix inequality. For the purpose, we investigate the branch and bound algorithm and improve its lower bound calculation algorithm. With this improvement, the elapsed time for one iteration becomes shorter and the iteration number is decreased. Other amendments are added to the branch and bound algorithm with this improvement. We show that this improvement is effective through some computer experiments. In the computer experiment, the static output feedback gain synthesis that is known to be a BMI problem is considered.