Do the ellipsoid methods belong to the trust region methods?
Reading their descriptions I tend to think the idea of the ellipsoid methods belong to the idea of the trust region methods, but am not sure if I am correct.
What are their relations and differences then?
Thanks and regards!
No.
In trust region methods you're using a local quadratic (or even linear model) of the objective function to find a minimum of an unconstrained problem. In each iteration of the algorithm you find the minimum of this quadratic model over a ball or ellipsoid that is the current trust region. You then move to that point and repeat the process. The size of the trust region is increased when the quadratic approximation is working well and decreased when it performs poorly.
In the ellipsoid method, you start with an ellipsoid containing an optimal solution to a convex minimization problem that can also include convex constraints. In each iteration you find a hyperplane such that the optimal solution is constrained to be within the intersection of the ellipsoid and a half space defined by the hyperplane. You construct a new smaller ellipsoid containing an optimal solution that surrounds the points that weren't cut off by your hyperplane.
Although both algorithms involve ellipsoids, the underlying ideas are very different. For example, the ellipsoidal trust region in the trust region method typically doesn't contain an optimal solution to the original problem until the very end of the iterations, while in the ellipsoid method, an optimal solution is contained within the ellipsoid at all times.
The best way for you to understand is to take the time to study both methods in some depth. There's a good introduction to the ellipsoid method in Chvatal's book on linear programming. Trust region methods are described in most textbooks on nonlinear programming.
