2021/07/18 by Costandin, Marius
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2107.08482
In this paper we present two frameworks in which global maximization of a bounded hessian function over a strongly convex set can be reduced to convex optimization. The first presented framework is a continuation of one of our previous papers [11]. We improve the results and give an explicit algorithm for the computation in polynomial time of the farthest point in a finite intersection of n-disks to C ∈ ℝn × 1 under the requirement that C does not belong to the convex hull of the centers of the n-disks. Finally, in order to overcome this limitation we present a second framework which characterizes the furthest in the finite intersection of n-disks with C in the convex hull. Unfortunately this second framework requires the ability to decide if a polytope that we define is included in the intersection, which is hard in general. However, as a particular application of our second framework we are able solve in P time some instances of the subset sum problem with real entries: given a set of real numbers decide if there is a subset which adds up to zero.