<p>This is a quadratic program (QP). If the matrix <span class="math-container">$C$</span> where <span class="math-container">$(C)_{i,j} = c_{i,j}$</span> 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.</p>
<p>If the problem is not convex then I am not sure what can be done.</p>

CC BY-SA 4.0
2023-10-15T21:48:27.747Z
2023-10-15T21:48:27.747Z
NaturalLogZ
<p>Let <span class="math-container">$n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$</span> and consider the following optimization problem:</p>
<p><span class="math-container">$$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$</span>
<span class="math-container">$$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$</span>
<span class="math-container">$$\forall q \in Q: ~~~~~\sum_{i \in S_q} x_i \leq 1$$</span>
<span class="math-container">$$\forall i \in [n]~~~~~~~~~~~~~x_i \geq 0$$</span>
where <span class="math-container">$S_q \subseteq [n]$</span> for every <span class="math-container">$q \in Q$</span> and <span class="math-container">$c_{i,j} \in \mathbb{N}$</span> for every <span class="math-container">$i,j \in [n]$</span>. Let <span class="math-container">$m = |Q|$</span>; assume that <span class="math-container">$m = \log(n)$</span>, that is, the number of variables is exponential in the number of nontrivial constraints. Further, assume that <span class="math-container">$|S_q| = m^{O(1)}$</span> for all <span class="math-container">$q \in Q$</span>.</p>
<p><strong>Question:</strong> Under what conditions can we get an <span class="math-container">$\alpha$</span>-approximation for this problem in time <span class="math-container">$m^{O(1)}$</span>?</p>
<p>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?</p>

CC BY-SA 4.0
2023-10-18T20:20:32.647Z
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.
Neal Young
CC BY-SA 4.0
2023-10-18T20:31:12.640Z
... 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.
Neal Young
<linear-programming><convex-optimization><semidefinite-programming>
Solving non-linear programming with large number of variables
John
# Solving non-linear programming with large number of variables

(Asked by: username_0 on 2023-10-15)

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?

**Tags:** linear-programming, convex-optimization, semidefinite-programming

> **Comments:**
> **username_1**: 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.  
> **username_1**: ... 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.  

---

## 1 answers

### Answer by username_2 on 2023-10-15. Score: 1

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.

If the problem is not convex then I am not sure what can be done.


---

