AbstractWe first construct a "tight" parallelepiped R, containing 0 by using an arbitrary set of Q-conjugate directions and by solving 2n linear programs. We show that the convex envelope of x with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each sub problem we obtain the linear convex envelope of x over a smaller parallelepiped, R. Then, we obtain a lower bound by minimizing this convex envelope over R ' n 0 We show that the branch and bound algorithm converges to a feasible solution z e. Preliminary computational results are also presented.
SubjectsConcave minimization, Global optimization, Quadratic functions, Convex envelope
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).