16.4 Inequality-constrained problems

Algorithms for solving convex quadratic programs that contains both inequality and equality constraints

• Active-set methods
  • are effective for small- and medium-sized problems
• Interior-point methods
• gradient projection methods
  • a special type of active-set methods
  • the most effective when the only constraints in the problem are bounds on the variables

Optimality conditions for inequality-constrained problems

\[\begin{eqnarray} \mathcal{L}(x, \lambda) := \frac{1}{2} x^{\mathrm{T}}Gx + x^{\mathrm{T}}c - \sum_{i \in \mathcal{I} \cup \mathcal{E}} \lambda_{i}(a_{i}^{\mathrm{T}}x - b_{i}) . \label{equation_16_35} \end{eqnarray}\]

Active set is defiend as

\[\begin{eqnarray} \mathcal{A}(x^{*}) & = & \{ i \in \mathcal{E} \cup \mathcal{I} \mid a_{i}^{\mathrm{T}} x^{*} = b_{i} \} . \label{equation_16_36} \end{eqnarray}\] \[\begin{eqnarray} G x^{*} + c - \sum_{i \in \mathcal{A}(x^{*})} \lambda_{i}^{*} a_{i} & = & 0 \label{equation_16_37_a} \\ a_{i}^{\mathrm{T}}x^{*} & = & b_{i} \quad i \in \mathcal{A}(x^{*}) \label{equation_16_37_b} \\ a_{i}^{\mathrm{T}}x^{*} & \ge & b_{i} \quad i \in \mathcal{I} \setminus \mathcal{A}(x^{*}) \label{equation_16_37_c} \\ \lambda_{i}^{*} & \ge & 0 \quad i \in \mathcal{I} \cap \mathcal{A}(x^{*}) \label{equation_16_37_d} \end{eqnarray}\]

Theorem 16.4

• $x^{*}$,
  • satisfies the conditoins \(\eqref{equation_16_37}\) for some \(\lambda_{i}^{*}, i \in \mathcal{A}(x^{*}\)
• $G$
  • positive semidefinite

Then $x^{*}$ is a global solution of (16.1).

proof

$\Box$