<p>This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there are a bunch of 'optimization' problems (find the minimal/maximal of ... such that ...) that can be solved by Binary Search, sometimes very easily. Is there any theory that tell us what kind of optimization problems can be solved by that algorithm?, or maybe, are all optimization problems solvable by Binary Search (theoretically)?.</p>

<p>Thanks,
Mario.</p>

CC BY-SA 3.0
2015-12-01T16:28:05.137Z
A general recipe for reducing optimization (say minimization) to feasibility is to add the constraint "objective value is at most $t$" and do binary search to find the smallest $t$ for which the resulting problem is feasible. This is how you usually solve convex programs with the ellipsoid method for example. But I would not call this "solving by binary search" because all the actual heavy lifting happens in solving the feasibility problem.
Sasho Nikolov
CC BY-SA 3.0
2015-12-01T17:40:47.307Z
Binary search wouldn't be applicable for _combinatorial_ optimization problems (such as the Travelling Salesman Problem), since the input to the function you're searching over is not a vector in $\mathbb{R}^n$.
NietzscheanAI
CC BY-SA 3.0
2015-12-02T06:57:22.373Z
By the definition of binary search, it must be that the objective function is weakly monotone. I believe it is almost trivial to see this.
chazisop
<optimization><binary-trees>
Binary Search for optimisation problems
Mario
# Binary Search for optimisation problems

(Asked by: username_0 on 2015-12-01)

This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there are a bunch of 'optimization' problems (find the minimal/maximal of ... such that ...) that can be solved by Binary Search, sometimes very easily. Is there any theory that tell us what kind of optimization problems can be solved by that algorithm?, or maybe, are all optimization problems solvable by Binary Search (theoretically)?.

Thanks,
Mario.

**Tags:** optimization, binary-trees
> **Comments:**
> **username_1**: A general recipe for reducing optimization (say minimization) to feasibility is to add the constraint "objective value is at most $t$" and do binary search to find the smallest $t$ for which the resulting problem is feasible. This is how you usually solve convex programs with the ellipsoid method for example. But I would not call this "solving by binary search" because all the actual heavy lifting happens in solving the feasibility problem.  
> **username_2**: Binary search wouldn't be applicable for _combinatorial_ optimization problems (such as the Travelling Salesman Problem), since the input to the function you're searching over is not a vector in $\mathbb{R}^n$.  
> **username_3**: By the definition of binary search, it must be that the objective function is weakly monotone. I believe it is almost trivial to see this.  

---

## 0 answers

