```markdown
### Two-way Partitioning

**Objective:**
- Minimize \( x^T W x \)
- Subject to \( x_i^2 = 1 \), for \( i = 1, \ldots, n \)

**Problem Characteristics:**
- Nonconvex problem
- Feasible set contains \( 2^n \) discrete points

**Interpretation:**
- Partition the set \(\{1, \ldots, n\}\) into two sets.
- \( W_{ij} \) represents the cost of assigning \( i, j \) to the same set.
- \(-W_{ij}\) is the cost of assigning \( i, j \) to different sets.

**Dual Function:**
\[ 
g(\nu) = \inf_x \left( x^T W x + \sum_i \nu_i (x_i^2 - 1) \right) 
= \inf_x \left( x^T (W + \text{diag}(\nu)) x - 1^T \nu \right)
\]
- Resulting in:
  - \(-1^T \nu\) if \( W + \text{diag}(\nu) \succeq 0 \)
  - \(-\infty\) otherwise

**Lower Bound Property:**
- \( p^\star \geq -1^T \nu \) if \( W + \text{diag}(\nu) \succeq 0 \)

**Example:**
- Setting \(\nu = -\lambda_{\min}(W)1\) gives the bound \( p^\star \geq n \lambda_{\min}(W) \)

*Source: A. d’Aspremont. Convex Optimization M2.*
```
