0
$\begingroup$

I have a quadratic program $$ \underset{V\mathbf{x}=\mathbf{d}, \mathbf{x} \geq \mathbf{0} }{\min} f_{\mu}(\mathbf x)= \sum_{i=1}^{n} \text{Var}\left(R_{i}\right)-\sum_{i=1}^{n}\mu\text{E}(R_i), $$ where $\mu$ is a constant, and $\text{Var}(R_i) = \sum_{i=1}^{n}\sum_{j\neq{}i}\alpha_{ij}(1-q_j)q_j,$ and $\text{E}(R_i) = \sum_{i=1}^{n}\sum_{j\neq{}i}\alpha_{ij}q_j,$ with the matrix $V$ being, for case $n = 3:$ $$ V = \begin{bmatrix} {q_1} & {q_2} & {q_3} & {0} & {0} & {0} & {0} & {0} & {0}\\ {0} & {0} & {0} & {q_1} & {q_2} & {q_3} & {0} & {0} & {0}\\ {1} & {0} & {0} & {1} & {0} & {0} & {1} & {0} & {0}\\ {0} & {1} & {0} & {0} & {1} & {0} & {0} & {1} & {0}\\ {0} & {0} & {1} & {0} & {0} & {1} & {0} & {0} & {1}\\ \end{bmatrix} $$ and the column-vector $d$ being $\mathbf d = \begin{bmatrix} q_1\\q_2\\\vdots\\q_{n-1}\\1 \\\vdots\\ 1 \end{bmatrix}$ in the general case. Here, we enumerate the variables $\alpha_{ij}$ in row-major order and bind them to variables $x_1,\ldots,x_{n^2}.$ Since the non-negativity conditions $x \geq 0$ are involved, I know we should be going for KKT conditions. I can throw this into a QP solver (cvxpy in my case), and get back the numerical solutions allright. How one would, however, go about showing that "numerical solution is the only way to go"? That is, how one would "prove" that analytic solution is somehow "unattainable"? I can see that even if one were to go from KKT conditions and try all the $2^n$ cases, then the algorithm would be exponential, and thus computationally prohibitive for any large $n.$

EDIT: How to prove that this problem does not admit a closed-form solution?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.