Active Elements in Projected Newton's Method?

Question

To those who are familiar with the projected Newton's method or projected gradient method...

We consider a constrained optimization problem with simple bounds. Particularly, minimize f(x) subject to L <= x <= U, where f maps R^n to R. x, L, and U are vectors in R^n. In the projected Newton's method that is used to solve this problem, the search direction is obtained by solving the linear system (reduced Hessian)*(search direction) = - gradient. Based on this, the active elements of an iterate are moved in the direction of the negative gradients at those elements. By definition of active sets, the gradients at the active elements have to be negative (for upper bound) and positive (for lower bound). Hence, after projection, the active elements are moved back to the boundary.

My first question is if x_i is an active element in iteration 1, will it be an active element until convergence? In other words, does the active set only get bigger, not smaller, and members of the active set are only added, not removed?

My second question is what if we use epsilon active set instead of just active set? Will it change anything?

If you need the definition of active set or any other clarification/background, please feel free to let me know. Thank you so much for your ideas and discussions. This is very important to me.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

EDIT: We consider the problem: \begin{equation} \min f(x) \quad \text{subject to} \quad a \leq x \leq b \end{equation} where $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is continuously differentiable.

An active set is defined as \begin{equation} \mathcal{A}:= \{ i | (x_i = a_i \quad \text{and} \quad (\nabla f(x))_i > 0) \quad \text{or} \quad (x_i = b_i \quad \text{and} \quad (\nabla f(x))_i < 0) \} \end{equation}

Suppose our initial iterate $x_0$ is on the boundary, e.g. $x_0 = a$, then it is possible to have some inactive elements where $(\nabla f(x))_i < 0$, right?

In the projected Newton's method, first with step length $\alpha = 1$, the active elements move in the directions of the negative gradients, which will point outside of the feasible region. Then, those elements are projected back to the boundaries. The inactive elements move in the Newton directions. Then we test for sufficient decrease...but even when we decrease $\alpha$, the active elements still move back to the boundaries and those elements still meet the "active" criteria in the next Newton iteration?

I know the active set can shrink...there must be something wrong in my thoughts...

Answer 1

The answer to your first question is no -- the active set does not only grow, it can also shrink, even if your objective function is convex. An example is if you start at some point on the boundary, then the first step moves along one active constraint to find the minimum of the objective function along this segment; but then, the second step will likely move away from the boundary because at the previous point the gradient will have pointed (in general, unless you are at the solution) into the domain.

The answer to your second question is not clear to me. I would say that it depends on the size of epsilon. If epsilon is small enough, my best guess is that it doesn't matter, but small enough will be relatively to the curvature of the objective function.

If you want to learn more about the active set method, my favorite book on optimization is "Numerical optimization" by Nocedal and Wright -- which has an extensive discussion of active set methods.