We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball $r \le \|x\| \le R$ intersected with a full-dimensional second order cone (SOC) constraint of the form $\|x – c\| \le b^T x – a$. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) … Read more
The use of convex relaxations has lately gained considerable interest in Power Systems. These relaxations play a major role in providing quality guarantees for non-convex optimization problems. For the Optimal Power Flow (OPF) prob- lem, the semidefinite programming (SDP) relaxation is known to produce tight lower bounds. Unfortunately, SDP solvers still suffer from a lack … Read more
We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP), which is known to be NP-hard, with $p$ suppliers and $q$ demanders. In particular, we study cases in which the cost function is quadratic or square-root concave. The key idea of our relaxation methods is in the change … Read more
In this paper, we study a class of biquadratic optimization problems. We first relax the original problem to its semidefinite programming (SDP) problem and discuss the approximation ratio between them. Under some conditions, we show that the relaxed problem is tight. Then we consider how to approximately solve the problems in polynomial time. Under several … Read more
In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several … Read more