Simple bound constrained optimization problem

Question

My problem is $$\text{minimize}: \phantom{2} f(x) \\ \text{subject to }: \phantom{2} x_4 \ge 0$$ where $x=(x_1,x_2,x_3,x_4)$.

I know that the fourth component $x_4$ of the desired local minimizer is greater than zero, so the inequality constraint at the solution is inactive. However, there are other local minimizers that are infeasible. So, if one simply drops the bound constraint during the Newton iteration it might converge to an infeasible point.

My question is: What algorithm is the most effective one to solve this bound constraint problem?

I tried log-barrier method $$\text{minimize}: \phantom{2} g(x)=f(x) - u \log(x_4)$$ with $u \rightarrow 0$. For example, $u_1=1, u_2=1\times 10^{-1},\cdots,u_7=1\times 10^{-6}$

But at some $u_k$, say $u_3=1\times 10^{-3}$ the unconstrained minimization cannot converge, even though it converges at $u_1=1$ and $u_2=1 \times 10^{-1}$. I used line-search. I see that during the Newton iteration $g(x)$ is decreasing but the norm of the gradient $||\nabla g||$ doesn't. I cannot figure out the possible reason. Maybe ill-conditioning?

Answer 1

There is really no particularly good answer that is generically true for any $f(x)$. My recommendation is to read the book by Nocedal & Wright on Numerical Optimization (one of my all-time favorite books) which covers the log-barrier method you use and many others. For example, you could consider active set methods, or the quadratic penalty method, etc.

Answer 2

An important special case of constrained optimization is constituted by optimization problems with simple bounds:

$$\min_{x \in \mathbb R^n} \quad f(x) \quad \text{s.t.} \quad x \geq 0$$

Assume that $f$ is continuously differentiable. Show that the first order necessary conditions for this problem are equivalent to $\min \{x, \nabla f(x)\}=0$, where the minimum is component-wise?? Please answer it.