# Methods for Constrained Optimization Problems with Box Constraints

Consider this problem:

$$\begin{array}{ll} \text{minimize } & f(x) \\ \text{subject to } & a \leq x \leq b \end{array}$$

where $a,b,x \in \mathbb{R}^n$ and $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ is continuously differentiable. By this definition, the feasible set is closed and convex.

I would greatly appreciate it if you could give me a big picture of the classes of methods that solve this problem. I know there are some methods such as projected gradient/Newton methods or primal-dual active set/semismooth Newton methods and some variations of these methods. However, these are specific. The book by Nocedal and Wright seems to discuss the following types of methods:

• active set
• interior-point
• penalty and augmented Lagrangian

The book "Optimization with PDE Constraints" by Hinze, Pinnau, and Ulbrich discusses:

• Newton's methods
• Semismooth Newton's methods (which Google Scholar says is equivalent to the primal-dual active set methods)

I am doing a literature review of the methods for this problem and hope that through my literature review I can discover something that needs improving. I have only 2 months (January and February) to do this. I am very new to this field and do not consider myself mathematically mature. I have very little experiences. Hence, it would be great if some of you could kindly share your experiences/visions. It would help me a lot if I could have a big picture of the methods. I would forever be grateful.

• Your definition actually describes an open (not closed*) domain. You'd need $a\le x\le b$. – Wolfgang Bangerth Jan 3 '15 at 1:56
• yes. you were right. typo :D – Linh Huynh Jan 3 '15 at 2:01

The book by Nocedal and Wright spends a lot of time developing your intuition. It is an excellent resource to get an overview. It is also not very mathematical, so I would suggest reading through the relevant chapters.

• The thing I am worried about is that if I do a thesis that is a literature review of the methods...and just do the same thing as the book...then...I am not sure if it is a good thesis... – Linh Huynh Jan 3 '15 at 2:03
• Also, there are a lot of methods in the book...I want to pick some methods and investigate them...the question is which methods to pick so that a comparison among them would make sense... – Linh Huynh Jan 3 '15 at 2:04
• The problem you consider is a simple one. You're not going to discover a new method that others haven't thought of so far. If that's the problem you're working with, then all you can hope for is to go through existing methods and compare them. If I had to choose a set of methods for the problem you describe, I'd compare the active set method against the augmented Lagrangian method -- both are considered state of the art. – Wolfgang Bangerth Jan 3 '15 at 3:52
• Thank you! For comparison, which criteria would you use: fast, accurate, easy to understand,....? – Linh Huynh Jan 3 '15 at 4:09
• I disagree with WolfgangBangerth. The problem you are considering is quite broad. Without additional information, large problem sizes, nonconvex problems, and effective preconditioning of KKT systems are still ongoing topics of research. If you aim to do a master's or PhD thesis, narrowing the problem class would make it more interesting and useful. – Geoff Oxberry Jan 3 '15 at 7:20