Active Elements in Projected Newton's Method?
To those who are familiar with the projected <PERSON>'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 <PERSON>'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). 768
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 <PERSON>'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 <PERSON> 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 <PERSON> iteration?
I know the active set can shrink...there must be something wrong in my thoughts... 474