Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity

The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (T_m), have drawn much attention recently. The question as to whether Problem ( T_m) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T_1) has an exact SOCP/SDP reformulation and thus is polynomially solvable. By adopting an early result of Martinez on local non-global minimum of the trust region subproblem, we can inductively reduce any instance in (T_m) to a sequence of trust region subproblems (T_0). Although the total number of (T_0) to be solved takes an exponential order of m, the reduction scheme still provides an argument that the class (T_m) has polynomial complexity for each fixed m. In contrast, we show by a simple example that, solving the class of extended trust region subproblems which contains more linear inequality constraints than the problem dimension; or the class of instances consisting of an arbitrarily number of linear constraints is NP-hard. When m is small such as m=1,2, our inductive algorithm should be more efficient than the SOCP/SDP reformulation since at most 2 or 5 subproblems of (T_0), respectively, are to be handled. In the end of the paper, we improve a very recent dimension condition by Jeyakumar and Li under which (T_m) admits an exact SDP relaxation. Examples show that such an improvement can be strict indeed.

Article

Download

View Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity