English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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