```markdown
### Feasibility and Phase I Methods

#### Feasibility Problem
Find \( x \) such that:
\[ 
f_i(x) \leq 0, \quad i = 1, \ldots, m, \quad Ax = b \tag{2} 
\]

#### Phase I
Computes a strictly feasible starting point for the barrier method.

#### Basic Phase I Method
Minimize (over \( x, s \)) \( s \) subject to:
\[ 
f_i(x) \leq s, \quad i = 1, \ldots, m 
\]
\[ 
Ax = b \tag{3} 
\]

#### Conditions
- If \( x, s \) feasible, with \( s < 0 \), then \( x \) is strictly feasible for (2).
- If the optimal value \( p^\star \) of (3) is positive, then problem (2) is infeasible.
- If \( p^\star = 0 \) and attained, then problem (2) is feasible (but not strictly); if \( p^\star = 0 \) and not attained, then problem (2) is infeasible.

*Slide by A. d’Aspremont, Convex Optimization M2.*
```
