3

I have an optimization problem of the form

Max $x_1+x_2+x_3+\cdots+x_n$

subject to $x_0^2+x_1^2+x_2^2+\cdots+x_n^2+x_{12}^2+x_{13}^2+x_{14}^2+ \cdots+x_{1n}^2+x_{23}^2 + \cdots +x_{2n}^2+ \cdots +x_{n n-1}^2+x_{123}^2+\cdots+x_{12..n}^2=1$,

$x_0+x_1+x_2+\cdots+x_n+x_{12}+x_{13}$+$x_{14}+ \cdots +x_{1n}+x_{23}+ \cdots +x_{2n}+ \cdots +x_{n n-1}+x_{123}+ \cdots +x_{12..n}=1$,

where $x_0,x_1,x_2,\ldots,x_{123\ldots n}$ are unrestricted.

What is the upper bound for the cost function ..? Thank you.

user7530
  • 49,280
Kumar
  • 2,259

2 Answers2

2

It's unclear exactly how many total variables you have; call it $m$. Let $\textbf{1}_n$ be the vector with the first $n$ components 1, the rest 0; and $\mathbf1$ the vector with all components $1$.

Then the KKT conditions of your maximization problem are $$\mathbf{1}_n + 2\lambda x + \mu \mathbf{1} = 0,$$ where $\lambda$ and $\mu$ are the Lagrange multipliers. Call $v$ the value of the objective at the critical point. Then, dotting the above by $x$ gives $$v + 2\lambda + \mu = 0.$$ Dotting by $\mathbf{1}$ gives $$n + 2\lambda + m\mu = 0,$$ and lastly, dotting by $\mathbf{1}_n$ gives $$n + 2\lambda v + n\mu = 0.$$ Now we are left with a system of equations; they have only one nonlinear term so we can proceed by eliminating variables. Combining the first two equations gives $$ 2\lambda(m-1) = n - mv,$$ and the first and second, $$ 2\lambda (n - v) = n - nv.$$ We can now eliminate $\lambda$: $$(n-mv)(n-v) = (n-nv)(m-1)$$ $$n^2 -nv -nmv + mv^2 = n(m-1) - n(m-1)v$$ $$mv^2 -2nv + n(n-m+1) = 0.$$ So $$v = \frac{n \pm \sqrt{n(m-1)(m-n)}}{m}.$$ I'll leave it to you to check that the positive sign choice indeed gives a maximum.

user7530
  • 49,280
  • I have $2^n$ variables. If we observe the indices of the variables they are precisely subsets of the set {1,2,..n} where $x_0$ represents the variable corresponding the empty set. – Kumar Feb 18 '13 at 18:02
  • Ok, then plugging in $m=2^n$ into the formula above will give you the maximum value you're looking for. – user7530 Feb 18 '13 at 18:05
  • Can we say that maximum is bounded by $Max_{S \subseteq[n]} \big { \sqrt{|S|}, x_S \neq 0 \big } $,

    where $S \subseteq$ {1,2..n} is the index of the variable, and $[n]={1,2..n}$.

     – Kumar Feb 19 '13 at 12:40
  • I don't understand what $S$ is. In any case notice that the problem is symmetric in the first $n$ variables, so looking at subsets of them won't help.

    If you want an approximate bound, then it's true that $v \leq \sqrt{n}$, the optimum of the problem without the second constraint. But the above formula gives the exact answer, and is not too complicated...

     – user7530 Feb 19 '13 at 15:36
  • I had checked that $v \leq O(\sqrt{n})$

    I will explain what $S$ is with an example

    Let us take one possible feasible solution to the above problem is is $x_{12}= -\frac{1}{2}$ ,$x_{13}= \frac{1}{2}$,$x_{15}= \frac{1}{2}$,$x_{13457}= \frac{1}{2}$ and remaining all the variables are assigned to zero.

    $|S|$ is the largest index of the nonzero variable. For this example $|S|$=5 since $x_{13457}$ is the largest index variable with non zero value.

     – Kumar Feb 19 '13 at 18:04
  • I looking to bound the objective function with $O( \sqrt{|S|})$.

    The bound so far we had achieved is a special case of the above when $|S|=n$ , i.e.,the variable $x_{12..n}$ is nonzero,. Thank you so much.

     – Kumar Feb 19 '13 at 18:05
0

A thought: If you stack all variables inside a vector, say $x$, it should be straight forward to re-write the above problem as \begin{align} &\min_x b^Tx \\ \text{subject to}&x^Tx=1 \\ &c^Tx=1; \end{align} This is not a convex problem. I am not sure about a closed form solution though. KKT conditions should be able to do something.

dineshdileep
  • 8,887
  • @user7530 Oh yes, my mistake. I forgot it was an equality, I took into consideration the interior of the sphere also, which is not the case here. – dineshdileep Feb 18 '13 at 15:59