The trust region subproblem with non-intersecting linear constraints.

*(English)*Zbl 1308.90121The authors consider an extended trust region subproblem (eTRS) in which the trust region is formed by the intersection of the unit ball and the solution set of \(m\) linear inequality constraints, and they study the relation of the optimal value of the eTRS to that of a particular convex relaxation of this problem which is solvable in polynomial time. As was shown earlier, both optimal values are identical for \(m\leq 2\) when the linear constraints are parallel and the optimal value of the relaxation problem is strictly smaller than that of the eTRS for \(m\geq 2\) when at least two of the linear constraints intersect within the unit ball, i.e., are satisfied with equality for some feasible point of the eTRS. In this paper it is proved that in fact for each \(m\) there is no gap between both optimal values as long as the \(m\) linear constraints do not intersect or, more generally, as long as they do not intersect in the interior of the unit ball.

Reviewer: Rembert Reemtsen (Cottbus)

##### MSC:

90C20 | Quadratic programming |

90C22 | Semidefinite programming |

90C25 | Convex programming |

90C26 | Nonconvex programming, global optimization |

90C30 | Nonlinear programming |

##### Keywords:

trust-region subproblem; second-order cone programming; semidefinite programming; nonconvex quadratic programming
PDF
BibTeX
Cite

\textit{S. Burer} and \textit{B. Yang}, Math. Program. 149, No. 1--2 (A), 253--264 (2015; Zbl 1308.90121)

Full Text:
DOI

##### References:

[1] | Barvinok, A, Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13, 189-202, (1995) · Zbl 0829.05025 |

[2] | Burer, S., Anstreicher, K.: Second-order cone constraints for extended trust-region subproblems. University of Iowa (March 2011). Revised July 2012 and Nov 2012. To appear in SIAM J. Optim. · Zbl 1298.90062 |

[3] | Celis, M.R., Dennis, J.E., Tapia, R.A.: A trust region strategy for nonlinear equality constrained optimization. In: Numerical Optimization, vol. 1984, pp. 71-82 (Boulder, Colo., 1984). SIAM, Philadelphia, PA (1985) · Zbl 0566.65048 |

[4] | Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA (2000) · Zbl 0958.65071 |

[5] | Fu, M; Luo, Z-Q; Ye, Y, Approximation algorithms for quadratic programming, J. Comb. Optim., 2, 29-50, (1998) · Zbl 0896.90154 |

[6] | Gould, NIM; Lucidi, S; Roma, M; Toint, PL, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510 |

[7] | MorĂ©, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042 |

[8] | Pataki, G, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23, 339-358, (1998) · Zbl 0977.90051 |

[9] | Pong, T., Wolkowicz, H.: The generalized trust region subproblem. University of Waterloo, Waterloo, Ontario (2012) · Zbl 1329.90100 |

[10] | Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2, Ser. B):273-299 (1997). · Zbl 0888.90137 |

[11] | Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1997) · Zbl 0926.90078 |

[12] | Sturm, JF; Zhang, S, On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 246-267, (2003) · Zbl 1082.90086 |

[13] | Ye, Y; Floudas, C (ed.); Pardalos, P (ed.), A new complexity result on minimization of a quadratic function with a sphere constraint, (1992), Princeton, NJ |

[14] | Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.