Title | Convergence-order analysis of branch-and-bound algorithms for constrained problems |

Publication Type | Journal Article |

Year of Publication | 2018 |

Authors | Kannan R, Barton PI |

Journal | Journal of Global Optimization |

Volume | 71 |

Issue | 4 |

Pagination | 753–813 |

Abstract | The performance of branch-and-bound algorithms for deterministic global optimization is strongly dependent on the ability to construct tight and rapidly convergent schemes of lower bounds. One metric of the efficiency of a branch-and-bound algorithm is the convergence order of its bounding scheme. This article develops a notion of convergence order for lower bounding schemes for constrained problems, and defines the convergence order of convex relaxation-based and Lagrangian dual-based lower bounding schemes. It is shown that full-space convex relaxation-based lower bounding schemes can achieve first-order convergence under mild assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at Slater points, and at infeasible points when second-order pointwise convergent schemes of relaxations are used. Lagrangian dual-based full-space lower bounding schemes are shown to have at least as high a convergence order as convex relaxation-based full-space lower bounding schemes. Additionally, it is shown that Lagrangian dual-based full-space lower bounding schemes achieve first-order convergence even when the dual problem is not solved to optimality. The convergence order of some widely-applicable reduced-space lower bounding schemes is also analyzed, and it is shown that such schemes can achieve first-order convergence under suitable assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at unconstrained points in the reduced-space, and at infeasible points under suitable assumptions when the problem exhibits a specific separable structure. The importance of constraint propagation techniques in boosting the convergence order of reduced-space lower bounding schemes (and helping mitigate clustering in the process) for problems which do not possess such a structure is demonstrated. |

URL | http://rdcu.be/s99X |

DOI | 10.1007/s10898-017-0532-y |

# Convergence-order analysis of branch-and-bound algorithms for constrained problems

Submitted by suzane on