4
$\begingroup$

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...

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry for not responding sooner. I was wondering if the projected gradient/Newton methods are active set methods or a different kind of methods? $\endgroup$ – Linh Huynh Jan 3 '15 at 0:04
  • $\begingroup$ They are different methods. These methods are also discussed in Nocedal/Wright, if I recall correctly. $\endgroup$ – Wolfgang Bangerth Jan 3 '15 at 1:53
  • $\begingroup$ Yes, they are :D...I am going to edit my question in response to your comment... $\endgroup$ – Linh Huynh Jan 3 '15 at 2:07
  • $\begingroup$ Projected gradient methods are active set methods, according to Nocedal & Wright, Chapter 16.7. $\endgroup$ – Geoff Oxberry Jan 6 '15 at 1:01
  • $\begingroup$ @GeoffOxberry: Ah, thanks for pointing it out. I suppose I wouldn't have put them in that category, but if they do it in the book, I'm not going to object either. $\endgroup$ – Wolfgang Bangerth Jan 7 '15 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.