Consider an optimization problem where you have $$ \min_x f(x)\\ \mbox{s.t} \, \; h(x) = 0 \\ g(x) \leq 0$$
I have understood that the active set consists of the equality constraints together with the part of the inequality constraints that belongs to g(x) = 0.
My question is what the active set tells us? Does the solution $x$ always lie in the active set? And I also wonder how it is used in practice in the numerical implementaion of algorithms.
Thank you!
I agree with DiegoNolan. Equality constraints are said to be active at any point. An inequality constraint $g_i(x)\geq0$ is said to be active at a point $x$ if $g_i(x)=0$. Then, the active set at $x$ refers to the set of inequality constraints that are active at $x$, more precisely, the set of indexes of the inequality constraints active at $x$:
$$I(x):= \{i:g_i(x)=0\}.$$
As far as I know the active set defined for convenience more than anything else. Which constraints are active at a point $x$ matter because they tell us whether or not $x$ is a regular point for the constraints, that is, $x$ is such that the set of gradients of the active constraints, that is,
$$\{\nabla h_i(x),\nabla g_j(x):j\in I(x)\}$$
is linearly independent. Loosely, a non-regular point is the analogue of a non-linearisable equilibrium in a system of ODEs in the sense that one cannot rely on first order approximations around the point. For this reason, regularity of a point is often required by the premise of results that allow you to test whether some point is a constrained local minimum. See for example, the KKT conditions (Theorem 14) and Theorem 15 of the lecture notes posted on here.
Additionally, a non-regular point is not "robust" to small perturbations on the constraints. For example, consider the feasibility problem with a single equality constraint: Find $x\in\mathbb{R}$ such that $x^2=0$. Clearly, it has a single solution $x=0$ (which is non-regular). However, suppose that the constraint is perturbed by a small $\delta$, $x^2+\delta=0$. If $\delta<0$ there are now two solutions $\pm\sqrt{x}$ and if $\delta>0$ there are no solutions.
With regards what's the importance of whether a point is regular or not in algorithms I can't tell you much apart from that the if it is not and the algorithm is stepping through point, it cannot apply first order approximation based tests to deduce information about the point.
In practice in active-set methods, you use an estimate of the active set to discard inactive inequality constraints and replace active inequality constraints with equality constraints. You're left with a fully equality-constrained problem that is "relatively" easy to solve: the corresponding optimality conditions are a system of nonlinear equations, which you can solve with your favorite method (such as Newton's method).
You then analyze the signs of the Lagrange multipliers (aka dual variables) and possibly update your estimate of the active set for the next iteration until you reach dual feasibility.
Consider a set of all constraints $C$ of an optimization problem $P$ on a feasible point $x \in \Omega$, where $\Omega$ is a feasible set:
Minimize $f(x)$
subject to $c_\epsilon (x) \leq 0 , c_\epsilon\in C, \epsilon \in E$
$c_\delta (x) = 0 , c_\delta \in C, \delta \in D$.
Then: $\mathcal{A}(x):= \{i\in E \cup D | c_i (x) = 0\}$.
Suppose there is such a constraint that $c_i (x) \in C < 0$, then the index $i$ for such constraint is inactive for solving $P$, otherwise $i$ would be active. So it is possible for an index $i$ not lie in the active set.
