Is the NLP formalism sub-optimal for real-world problems

Question

My home-brew optimization studies have raised yet another fundamental question. The Nonlinear Programming formalism, "minimize f(x) subject to inequality and equality constraints, and x membership" appears to be the main game in town, but seems (to me) to be more theoretical than practical. I can see that it is a useful vehicle for mathematical proofs & theorems regarding optmization, but is it really the best approach for real-world problems?

My question really comes down to implementation of constraints. In my understanding of NLP, the constraints for a problem are implemented using Lagrange multipliers (or some other technique) that turns constraints into additional variables to for a new, unconstrained, and higher dimensional problem.

My hands-on experience is diametrically opposed to this; I found that adding constraints in the algorithm itself worked poorly, if at all, and eventually I gave up on the attempt. I have been much more successful applying constraints within the model, not the algorithm. Linked to this, when I apply constraints my problems can even (for equality constraints) become lower-dimensional.

For example, when implementing a simple "box" optimization (find dimensions x, y, z to maximize enclosed volume given fixed area A, or minimize area to enclose a fixed volume V) elsewhere. Applying either equality constraint directly to the model (eliminating z in terms of x, y, and either A or V) each 3D problem is reduced to 2D. According to my understanding of NLP (hence the question) that method would add another equation to specify the constraint, giving a 4D problem, which is less computationally efficient, and probably less numerically stable. This leads to a "deficit" of two dimensions per equality constraint.

As far as inequality constraints are concerned, there is no dimension reduction, so the corresponding "deficit" is just one dimension per constraint. Here is a small sample of model code, which is I hope clear enough to at least illustrate what I mean by applying constraints to the model:

void cost (int n, point *p, const model *m) {
    for (int i = 0; i < n; i++) {
        if (p->x[i] <= m->min || p->x[i] >= m->max) {
            p->f = INFINITY;  // "variable range limit" constraint; cost is infinite
            return;
        }
    }
    p->f = 0.0L;
    for (int i = 0; i <= 50; i++) {  // passband
        real t = tx(n, p, powl(10.0L, 0.02L * i - 1.0L));
        p->f += t >= m->pb ? 0.0L : SQR(m->pb - t);  // satisfied spec constraint; cost is zero
    }
    for (int i = 0; i <= 50; i++) {  // stopband
        real t = tx(n, p, powl(10.0L, 0.02L * i) + m->ksi - 1.0L);
        p->f += t <= m->sb ? 0.0L : SQR(m->sb - t);  // ditto
    }
}

The "tx()" function evaluates the power transmission through an electrical filter over a logarithmic frequency range. If anyone is interested, the full source for this is in a tiny project here. This approach works very well for the Nelder-Mead optimizer, as well as the alternative particle-based ones.

Is my experience common, or is the approach (apply constraints in the model, and not the algorithm) controversial because it "defies" NLP?

Answer 1

You question the orthodoxy when you say that the traditional NLP "seems (to me) to be more theoretical than practical". In most cases, if people have been advocating for a particular approach for 50 years (as they have been — all of the relevant books on nonlinear optimization spend many chapters on Lagrange multipliers and dealing with constraints), then a reasonable guess is that they are probably right and claiming that it is not practical without substantial empirical evidence is probably wrong.

Of course, this does not mean that for specific cases you may get lucky with a simpler approach. In your particular case, you can easily eliminate a variable via a constraint. But this will generally not be possible. For example, if you have the constraint $xe^x=1$, then you can't just solve for $x$ — you can't eliminate that constraint, and that's a typical case in all practical applications. Separately, I don't think that your assertion that larger problems are less numerically stable is true. In fact, the introduction of Lagrange multipliers oftentimes makes the problem more stable because the resulting is less nonlinear than the one where you eliminate variables. To give an example, consider the problem

\begin{align} \min_{x, y} f(x,y)=x+y^3\\ \text{subject to}\quad y=x^2\, . \end{align}

You can eliminate $y$ if you want, to obtain a very nonlinear reduced objective function

$$f_\text{red}(x)=x+x^6\, ,$$

or you can form a less nonlinear Lagrangian

$$L(x,y,\lambda)=x + y^3 + \lambda(y-x^2)\, .$$

You may have increased the dimension by two, but you get a problem that is less nonlinear for which the Newton method will consequently likely converge in fewer iterations.