# Solving non-linear programming with large number of variables

Let $$n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$$ and consider the following optimization problem:

$$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$ $$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$ $$\forall q \in Q: ~~~~~\sum_{i \in S_q} x_i \leq 1$$ $$\forall i \in [n]~~~~~~~~~~~~~x_i \geq 0$$ where $$S_q \subseteq [n]$$ for every $$q \in Q$$ and $$c_{i,j} \in \mathbb{N}$$ for every $$i,j \in [n]$$. Let $$m = |Q|$$; assume that $$m = \log(n)$$, that is, the number of variables is exponential in the number of nontrivial constraints. Further, assume that $$|S_q| = m^{O(1)}$$ for all $$q \in Q$$.

Question: Under what conditions can we get an $$\alpha$$-approximation for this problem in time $$m^{O(1)}$$?

If this was a linear program (LP), I would find the dual problem and try to solve it using the ellipsoid method by constructing a separation oracle. Is there a similar analog for such a (non-linear) program with a large number of variables?

• How could you possibly do time $m^{O(1)} = \log^{O(1)} n$, when just representing the input (or the output) takes space polynomial in $n$? Maybe you are imagining the input is given in some implicit representation? If so you need to say explicitly what it is. Likewise for the output. Also, something else funny: with your assumptions, at most polylog$(n)$ variables occur in constraints, and any variable that doesn't can be set to an arbitrarily large value. So (unless the number of positive $c_{ij}$ is at most polylog $n$), the optimization problem must be unbounded. Commented Oct 18, 2023 at 20:20
• ... For it not to be unbounded, it must be that, for every positive $c_{ij}$, both $x_i$ and $x_j$ are one of the polylog$(n)$ variables that occur in a constraint. For that to happen, there must be only polylog$(n)$ positive $c_{ij}$'s. So why not assume that is the case, and that the input encoding explicitly lists only the positive $c_{ij}$'s. Then the input encoding has size polylog$(n) =$ poly$(m)$. So the instance is equivalent to a poly$(m)$-size instance of the same problem without your stated restrictions, and you are asking for a poly-time algorithm for such an instance. Commented Oct 18, 2023 at 20:31

This is a quadratic program (QP). If the matrix $$C$$ where $$(C)_{i,j} = c_{i,j}$$ is positive semi definite, then the problem is convex. It seems that your problem should have non-empty interior, so if it is convex, strong duality holds. Thus you could solve the dual problem using the Ellipsoid method, assuming you have a separation oracle for the dual constraints.