0
$\begingroup$

I have two quadratic functions $$W(x_1,x_2,\ldots,x_n)=\sum_{i}^{n} a_{ii} x_i^2+ \sum_{i\neq j}^{n} a_{ij}x_ix_j+\sum_{i}^{n} b_{i} x_i, $$ and $$V(x_1,x_2,\ldots,x_n)=\sum_{i}^{n} c_{ii} x_i^2+ \sum_{i\neq j}^{n} c_{ij}x_ix_j+\sum_{i}^{n} d_{i} x_i,$$with $x_i\in[0,1)$. Both functions are subject to constraint $\sum_{i}x_i \leq M$ where $M<n$. All parameters $a_{ii}, a_{ij}$, $b_{ii}$, $b_{ij}$ and $d_i$, $b_{i}$ to be non-negative. Note I split the second order terms, they can be written into one term like $\sum_{i}^{n}\sum_{j}^{n} a_{ij}x_ix_j$.

My question is, when will the two functions have the same maximizer? A sufficient condition is when the parameters are all same: $a_{ij}=c_{ij}$, $b_i=d_i$, for all $i,j$. Or parameters of $V$ is proportional to parameters of $W$. See Why coefficients have to be proportional for two quadratic functions to have the same roots. But is this necessary? Other than special cases where they are multiples of each other, can I have a simple necessary and sufficient condition? Thanks in advance.

$\endgroup$
  • $\begingroup$ Well, if $a_{i,i}<0$, $c_{i,i}<0$, and $b_i=d_i=0$ for all $i$, as well as $a_{i,j}=c_{i,j}=0$ for all $i,j$ with $i\neq j$, then the maximizer of $W$ and $V$ is the same: $x_1=x_2=\ldots=x_n=0$. You will see that $W$ and $V$ are not proportional in most choices of $a_{i,i}$'s and $c_{i,i}$'s. $\endgroup$ – Batominovski Aug 18 '16 at 1:37
  • $\begingroup$ @Batominovski, thanks for commenting. I already restricted all parameters to be non-negative. $\endgroup$ – Bob Aug 18 '16 at 1:39
  • $\begingroup$ If the parameters are nonnegative, there shouldn't be a maximizer. $W$ and $V$ are increasing in each $x_i$. If the domain were to be $0\leq x_i\leq 1$ for all $i$, then in most cases, there will be a unique maximizer $x_1=x_2=\ldots=x_n=1$. If you want to discuss the minimizer, then in most cases, the minimizer will be unique: $x_1=x_2=\ldots=x_n=0$. $\endgroup$ – Batominovski Aug 18 '16 at 1:47
  • $\begingroup$ @Batominovski, you are right, I over-simplified the set-up. $x_i$'s should have a constraint. $\endgroup$ – Bob Aug 18 '16 at 1:52
  • $\begingroup$ Anyhow, the maximizer must lie on the $(n-1)$-dimensional hyperplane $\sum_{i=1}^n\,x_i=M$. In most cases, there are no maximizing points, unless you allow the $x_i$'s to be $1$. In that case, in most cases, there exists a unique maximizing point at which $\lfloor M\rfloor$ of the $x_i$'s must be $1$, whereas at least $n-1-\lfloor M\rfloor$ of them are $0$. $\endgroup$ – Batominovski Aug 18 '16 at 15:32

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.