Hacker News Reader

Comment by rwilson4 | Hacker News Reader

Yes, all constrained optimization problems can be converted to unconstrained problems. For example, consider:

minimize f(x) subject to x \in C

Let g(x)=f(x) if x \in C and infinity otherwise. Then

minimize g(x)

has the same solution as the original constrained problem. However, this conversion often conceals some of the structure of the original problem which can be exploited to solve the problem more efficiently.

Solving point problems as you have called them typically involves solving a sequence of least squares problems, which are simple to reason about and computationally efficient to solve. Solving a calculus of variations problem typically involves solving an integral or partial differential equation. Although there are theoretical similarities in practice they are pretty different.

View on HN

> this conversion often conceals some of the structure of the original problem which can be exploited to solve the problem more efficiently

I had thought about this. My Q then is: Why do we study generalized versions of problems where the objective function is arbitrary f(x) instead of the specific function that we care about? Aren't we losing some potential efficiency here as well?

We definitely do study specific instances. For example, the other day an article was posted here on Support Vector Machines, which are a convex optimization problem having a special structure that is exploitable for fast solutions. For more examples, see Convex Optimization by Boyd and Vandenberghe, and the course notes for EE364a/b at Stanford. Modern Convex Optimization by Bertsekas is also good. I had the privelege of taking the convex optimization sequence at Stanford from Prof. Boyd, and one of the major take aways is that many practical problems can be solved in quadratic or even linear time. A general purpose solver typically runs in cubic time. For large problems (lots of variables), a special purpose solver can solve problems in seconds that would take a general purpose solver hours!

The book posted here is very much an introduction; even the EE364 sequence was merely a jumping off point for being able to explore the literature. Mathematical optimization, and especially convex optimization, is a deep and beautiful field!

Thank you for all those references!

That is indeed how the subject has been developed historically and often introduced in optimisation courses. First one studies Linear Programs (minimize a linear function with affine equality and affine inequality constraints), then Quadratic Programs (quadratic functions with affine constraints), Quadratically Constrained Quadratic Programs, etc. So we often assume very specific properties of not just the objective but also the constraints, and we get some extra juice in these cases. Through this process of seeing what results we can prove in more generality, we finally arrived at getting a good body of theory and algorithms for minimizing convex functions with convex constraints. In some courses they start with the general theory, as the top down approach can save some time and brain space.

Reply on news.ycombinator.com