Continuous Optimisation HT26, Constrained optimisation problems
Flashcards
Suppose we have the constrained optimisation problem
\[\min _ {x \in \mathbb R^n} f(x) \quad \text{s.t.} \quad c _ E(x) = 0,\, c _ I(x) \ge 0\]
where $c _ E : \mathbb R^n \to \mathbb R^m$ and $c _ I : \mathbb R^n \to \mathbb R^p$. What is meant by $E$, $I$ and $\mathcal A(x)$?
- $E$ is the index set of equality constraints
- $I$ is the index set of inequality constraints
- $\mathcal A(x)$ is the index set of active constraints at $x$, i.e. $\mathcal A(x) := E \cup \{i \in I \mid c _ i(x) = 0\}$
Suppose we have the constrained optimisation problem
\[\min _ {x \in \mathbb R^n} f(x) \quad \text{s.t.} \quad c _ E(x) = 0,\, c _ I(x) \ge 0\]
where $c _ E : \mathbb R^n \to \mathbb R^m$ and $\mathbb c _ I : \mathbb R^n \to \mathbb R^p$. @Define the constraint Jacobians $J _ E(x), J _ I(x)$, and the unsubscripted $J(x)$ used when only one type of constraint is in play. @State also a useful identity in this notation.
$J _ E(x) \in \mathbb R^{m \times n}$ has $j$th row $\nabla c _ j(x)^\top$ for $j \in E$, and similarly $J _ I(x) \in \mathbb R^{p \times n}$ for $i \in I$. When only one constraint type is in play, $J(x)$ refers to the corresponding sub-block unambiguously.
Useful identity:
\[\sum _ {j \in E} y _ j \nabla c _ j(x) = J _ E(x)^\top y, \qquad \sum _ {i \in I} \lambda _ i \nabla c _ i(x) = J _ I(x)^\top \lambda.\]Bite-sized
The feasible set of the constrained problem $\min f(x)$ s.t. $c _ E(x) = 0$, $c _ I(x) \ge 0$ is $\Omega := \{x \in \mathbb R^n : c _ E(x) = 0, \, c _ I(x) \ge 0\}$.
At a feasible point $x \in \Omega$, an inequality constraint $i \in I$ is active if $c _ i(x) = 0$ (boundary) and inactive if $c _ i(x) > 0$ (strict interior). Equality constraints $i \in E$ are always considered active. The active set is $\mathcal A(x) = E \cup \{i \in I : c _ i(x) = 0\}$.
The Jacobian $J _ E(x) \in \mathbb R^{m \times n}$ of the equality constraints has $j$th row given by $\nabla c _ j(x)^\top$ for $j \in E$. The same convention applies to $J _ I(x) \in \mathbb R^{p \times n}$.