I am trying to find the maximum of a hermitian positive definite quadratic form x Q x H (where Q = Q H and all eigenvalues of Q are non-negative) over the complex unit cube | x i | ≤ 1, i = 1 , … , n where x = ( x 1 , x 2 , … , x n ) ∈ C n .This is the problem of minimizing a concave function over a convex domain. I have read that this problem is NP-hard but there exist some bounds on the optimum. What global optimization technique would your recommend to tackle this problem numerically? Since I am new to the field of optimization, I would appreciate every answer, thanks!

Question

I am trying to find the maximum of a hermitian positive definite quadratic form   x  Q      x    H   (where   Q  =      Q    H   and all eigenvalues of   Q are non-negative) over the complex unit cube       |        x    i        |    ≤  1,   i  =  1  ,  …  ,  n where   x  =  (      x    1    ,      x    2    ,  …  ,      x    n    )  ∈            C        n  .This is the problem of minimizing a concave function over a convex domain. I have read that this problem is NP-hard but there exist some bounds on the optimum. What global optimization technique would your recommend to tackle this problem numerically? Since I am new to the field of optimization, I would appreciate every answer, thanks!

1s1zubv · Accepted Answer

As the cube is convex and compact, it is the convex hull of its extreme points (by Krein-Milman theorem or in case of cube by its simple geometry). As the objective is convex and continuous, it has a global maximizer and one of them is an extreme point of the cube.