<p>Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1. </p>

<p>\begin{align}
  \text{maximize } &amp;\sum_{i,j=1}^{m,n} c_{ij} \gamma_{ij} \notag\\
  \text{subject to: }&amp; \notag\\
  &amp;  \gamma_{ij} = \min\{1, \sum_{k = 1}^{K}{x_{ik}y_{jk} }\}  &amp;&amp; 
\forall i,j\\
  &amp; 0 \le x_{ik}, y_{jk} \le 1 &amp;&amp; \forall i,j,k 
\end{align}</p>

CC BY-SA 3.0
2016-04-29T05:56:34.077Z
Seems unlikely.  Even for $K=1$, deciding whether a given instance has  value at least $\ell$ is equivalent to the following problem: given a bipartite graph $G=(V,W,E)$, decide whether it has an induced subgraph $G'=(V',W',E')$ with at least $\ell$ more edges than non-edges (that is, $2|E'| - |V'|\,|W'| \ge \ell$).  I'd guess that is NP-hard.
Neal Young
CC BY-SA 3.0
2016-05-06T09:28:26.900Z
Thanks. Do you think, there might exist a randomized algorithm/FPT to solve this optimization problem.
Vadapalli Adithya
<ds.algorithms><optimization><convex-optimization>
Non-Linear Programming with \min operator in the constraint
Vadapalli Adithya
# Non-Linear Programming with \min operator in the constraint

(Asked by: username_0 on 2016-04-28)

Can the following non-linear program be solved in polynomial time? $c\_{ij}$'s are constants and known. Each $c\_{ij}$ is either -1 or 1.

\begin{align}
\text{maximize } &\sum\_{i,j=1}^{m,n} c\_{ij} \gamma\_{ij} \notag\\
\text{subject to: }& \notag\\
& \gamma\_{ij} = \min\{1, \sum\_{k = 1}^{K}{x\_{ik}y\_{jk} }\} &&
\forall i,j\\
& 0 \le x\_{ik}, y\_{jk} \le 1 && \forall i,j,k
\end{align}

**Tags:** ds.algorithms, optimization, convex-optimization
> **Comments:**
> **username_1**: Seems unlikely.  Even for $K=1$, deciding whether a given instance has  value at least $\ell$ is equivalent to the following problem: given a bipartite graph $G=(V,W,E)$, decide whether it has an induced subgraph $G'=(V',W',E')$ with at least $\ell$ more edges than non-edges (that is, $2|E'| - |V'|\,|W'| \ge \ell$).  I'd guess that is NP-hard.  
> **username_0**: Thanks. Do you think, there might exist a randomized algorithm/FPT to solve this optimization problem.  

---

## 0 answers

