0
$\begingroup$

Giving a vector of length $m$: $a=[a_1,...,a_m]^T$, where $a_i\neq a_j, \forall 1\leq i<j\leq m$. I am considering an optimization problem as follows: $$ \max_x \sum_{1\leq i < j \leq m}x_i x_j (a_i-a_j)^2=\frac12 x^TAx, s.t. 1^Tx=1, x\geq 0 $$ where the matrix $A\in R^{m\times m}$ and $[A]_{ij}=(a_i−a_j)^2$, and $1$ is a $m$-length vector of ones.

I can verify that the rank of $A$ is at most 3 (referring to https://math.stackexchange.com/questions/1586178/rank-of-a-matrix-in-specific-form).

Since this is a non-convex optimization, I wonder whether there is a way to solve it (I tried Lagrangian method but didn't get a solution) and whether there is an analytic result for the optimization problem.

$\endgroup$
  • $\begingroup$ Are you aware of en.wikipedia.org/wiki/Quadratic_programming? $\endgroup$ – flawr Dec 27 '15 at 10:52
  • $\begingroup$ @flawr Does that mean any QP is solvable? And another problem is that $A$ is not invertible and in duality I see the form of inverse. Thanks! $\endgroup$ – SoftSail Dec 27 '15 at 11:04
0
$\begingroup$

Non-convex QPs are very difficult to solve. You may need some kind of global solver to handle this. Here are some solvers that can handle these type of problems: GloMIQO, Baron, Cplex.

$\endgroup$

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.