0
$\begingroup$

I am trying to find the maximum of a hermitian positive definite quadratic form $xQx^H$ (where $Q=Q^H$ and all eigenvalues of $Q$ are non-negative) over the complex unit cube $|x_i|\leq 1$, $i=1,\dots,n$ where $x=(x_1,x_2,\dots,x_n)\in\mathbb{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 (see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.6954&rep=rep1&type=pdf ) . 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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As far as I have read, the standard form of convex optimization problems is to minimize an objective function. In this case, maximization of $xQx^H$ would mean minimization of $-xQx^H$, which is not convex. Do I miss something? Even if the maximum lies on an extreme point of the cube, how do you define a "vertex" on complex cube? If it is the set $|x_i|=1$ $\forall i$, then one still has an optimization problem over the Cartesian product of the phases of $x_i$, i.e. over $[0,2\pi]^n$. $\endgroup$ – Bryson of Heraclea Jun 29 '15 at 11:49
  • $\begingroup$ you are right. it seems, you still have to optimize over the phases. it is manageable but surely not beautiful. $\endgroup$ – user251257 Jun 29 '15 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.