Nonlinear constrained optimization - how?

[maistral]

Perhaps the title says it all, but I should expand it more, I guess.

So I am trying to explore more about constrained optimization. I noticed that there are very little to no formal (with examples) discussions on algorithms on nonlinear constrained optimization in the internet. They would either run Excel Solver or some other numerical program to solve them.

Can someone point me to some resources, preferably with worked examples? I would appreciate any form of help about this. Thanks a lot guys!

 

[Dr. Courtney]

https://en.wikipedia.org/wiki/Lagrange_multiplier

 

[maistral]

Are there no other methods available, other than Lagrange multipliers? Something iterative similar to Gauss-Seidel would be awesome.

 

[lavinia]

Perhaps the title says it all, but I should expand it more, I guess.

So I am trying to explore more about constrained optimization. I noticed that there are very little to no formal (with examples) discussions on algorithms on nonlinear constrained optimization in the internet. They would either run Excel Solver or some other numerical program to solve them.

Can someone point me to some resources, preferably with worked examples? I would appreciate any form of help about this. Thanks a lot guys!

Are you interested in quadratic programs? These solve a quadratic optimization using a sequence of modified linear programs. Their solution is an efficient frontier.

 

[Dr. Courtney]

Are there no other methods available, other than Lagrange multipliers? Something iterative similar to Gauss-Seidel would be awesome.

Let me google that for you:

https://en.wikipedia.org/wiki/Constrained_optimization

https://www.youtube.com/results?search_query=lagrange+multipliers

https://www.youtube.com/results?search_query=constrained+optimization

When my colleagues and I taught this, we preferred teaching it with Lagrange multipliers, because this route makes it simple to set up and solve the equations with MMa, Octave, Maxima, Matlab, etc. There is a relatively simple recipe with only a few minor variations.

 

[maistral]

I have this problem that I want to solve:

Maximize Z = 3x + 2y
subject to: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0 , y ≥ 0

Assuming a, b, and c are my multipliers;

3 = 2a + 2b + 3c
2 = a + 3b + c
2x + y = 18
2x + 3y = 42
3x + y = 24

Obviously, the system is unsolvable.

I'm aware of the existence of the simplex method, but I'm trying to evade as much as possible the use of that method. In this problem; did the Lagrange multiplier method break down?

Or is it inevitable that I will have to use the Simplex method? Also; I want to read more on that quadratic programming. If possible, can you give me some resources where I can read basic information and at least, some worked examples about it? Thanks.

 

[lavinia]

Here is a link to Wolfe's method. I tried to find his original paper but ran into demand for money.

http://cowles.econ.yale.edu/P/cp/p02a/p0231.pdf

My recollection is that the simplex method is far from the only way to solve a linear program. It just happens to be remarkably fast.

I will see i f I can find worked quadratic programs. In financial problems, the solution is an "efficient frontier" that is, an optimum for each level of risk. Each point on the frontier is the solution of a separate linear program.

 

[maistral]

Here is a link to Wolfe's method. I tried to find his original paper but ran into demand for money.

http://cowles.econ.yale.edu/P/cp/p02a/p0231.pdf

My recollection is that the simplex method is far from the only way to solve a linear program. It just happens to be remarkably fast.

I will see i f I can find worked quadratic programs. In financial problems, the solution is an "efficient frontier" that is, an optimum for each level of risk. Each point on the frontier is the solution of a separate linear program.

Thanks for replying.

Just a side question. Is my assumption correct that the Lagrange Multiplier method broke down in that example?

Or I did it wrong?

 

[maistral]

I read more stuff about Lagrange multipliers and apparently I did something wrong. I saw sample problems about it and I noticed that all of them had no inequalities ("all with equals-sign", at least).

I'm having a really hard time understanding this. I think I managed to figure out how the Simplex method works (I think it's forcing all the slack variables with a negative/highly positive value to be zero, then solving the resulting system of equations).

I hope someone would help me though; this is totally unfamiliar territory to me. I couldn't even connect those unconstrained optimization methods to this type of optimization.

 

[FactChecker]

Most methods for nonlinear constrained optimization are done by applying a series of unconstrained nonlinear optimizations to modified objective functions. A "penalty function" is added to the objective function so that approaching a constraint adds a penalty. This modified objective function is minimized using unconstrained techniques to get a first estimate of the optimal point, x₁. The penalty function is large enough to keep x₁ safely away from any constraint. Then the penalty is reduced by a factor and the estimated optimum point is improved to x₂ using another unconstrained optimization starting at x₁. This is the subject of "nonlinear programming". There has been a lot of research in that area comparing different optimization techniques.

 

[maistral]

Most methods for nonlinear constrained optimization are done by applying a series of unconstrained nonlinear optimizations to modified objective functions. A "penalty function" is added to the objective function so that approaching a constraint adds a penalty. This modified objective function is minimized using unconstrained techniques to get a first estimate of the optimal point, x₁. The penalty function is large enough to keep x₁ safely away from any constraint. Then the penalty is reduced by a factor and the estimated optimum point is improved to x₂ using another unconstrained optimization starting at x₁. This is the subject of "nonlinear programming". There has been a lot of research in that area comparing different optimization techniques.

Thanks a lot for replying.

Are these penalty functions similar to the programming problem itself or are they dependent on the numerical technique/solution method used? I will try to read up more about this method, thanks a lot :)

 

[FactChecker]

Are these penalty functions similar to the programming problem itself or are they dependent on the numerical technique/solution method used?

In special cases, the penalty functions might be in the same family as the objective function, I don't know. In general, the process of calculating a penalty is automated in the tool that is used. There might be options that allow you to try different techniques.

 

[FactChecker]

I have this problem that I want to solve:

Maximize Z = 3x + 2y
subject to: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0 , y ≥ 0

You can certainly use nonlinear techniques on this but it is linear. No linear problem gives a hint of the significant issues in nonlinear programming. Linear problems are always convex, never have local minimums that are not global minimums, always have derivatives, etc, etc, etc.

 

[Jimster41]

Thanks a lot for replying.

Are these penalty functions similar to the programming problem itself or are they dependent on the numerical technique/solution method used? I will try to read up more about this method, thanks a lot :)

For real world optimization problems there is some trickiness to normalizing and calibrating a multi-dimensional objective/penalty function so that the optimizer "sees" the response surface the way you want. We are usually optimizing combustion to improve efficiency and reduce emissions, subject to equipment and CO (carbon monoxide) constraints. Problem is the engineering units are not the same. Nor are they specifically commensurate in any obvious tractable way. Dollars should do it, some might say, but that turns out to be impractical. Dollars are pretty abstract in reality. Plus, the whole thing really is non-linear. If you go just one more hair's length toward fuel-rich stoichiometry, after a point, CO will explode, sort of literally.

The tool I use is automated in the sense you look at the system in action (transparency is key) and turn some dials to change the tolerance of constraints, and the priority of objectives, tweak the curvature of the penalty and objective function components until it does what makes you happy (or not anxious). But for the problem you describe, where all dimensions are just the Reals, and the system is linear, none of that should be a problem. I find the direct search algorithm below to be instructive and practical. We use it for Design Of Experiments.

https://en.m.wikipedia.org/wiki/Pattern_search_(optimization)

 

[maistral]

Most methods for nonlinear constrained optimization are done by applying a series of unconstrained nonlinear optimizations to modified objective functions. A "penalty function" is added to the objective function so that approaching a constraint adds a penalty. This modified objective function is minimized using unconstrained techniques to get a first estimate of the optimal point, x₁. The penalty function is large enough to keep x₁ safely away from any constraint. Then the penalty is reduced by a factor and the estimated optimum point is improved to x₂ using another unconstrained optimization starting at x₁. This is the subject of "nonlinear programming". There has been a lot of research in that area comparing different optimization techniques.

After one week of brawling with these penalty and barrier methods (and around ~80 pdf and PowerPoint files downloaded about this for my self-studying), I finally understood and got it. Yay!

I noticed however the following:
- The logarithmic barrier forces the optimum to the 'edge' of the solution space. The moment it exceeds the solution space, the solution would blow up. While the 'blowing up' is common sense (logarithm of zero is... :v), I find the 'putting the optimum to the edge' part rather fascinating. Can you direct me on something that would elaborate more on this?

- The quadratic penalty method converges rather fast, considering the growth of my penalty multipliers, but I noticed the Hessian is... :\ According to what I've read, one way to reduce the ill-conditioning is to use an 'absolute penalty' method. I seem to be unable to make this absolute penalty method converge though. Are there any other methods that use penalties other than these two?

- The inverse barrier is freaking useless, lol. I seem to be unable to make it converge no matter what my initial assumptions are -_-

Thanks for your time! :D

 

[FactChecker]

It's hard to draw conclusions about different penalty function methods because of the wide variety of techniques that can be tried. The search methods, the rules for reducing penalties, the rules for restarting a search, etc., etc,. etc., are usually based on heuristics. It can be more of an art and a trial and error process. Because many nonlinear problems have local minimums that fool the algorithms, it is often necessary to try several times with different random starting points and record the best solution of all the starting points.

 

[Jimster41]

Your issues with edges seem familiar. If I'm following correctly one thing we did was put tunable dead-bands at limits (edges of inequalities, etc) to stop the optimizer just before it ran into problems related to the challenge of using math to draw surfaces at locations in what may be an ill-conditioned space, (equations that blow up).

Heuristics is a good word to capture the idea I think. At the end of the day you need something that keeps the wild optimizer in the corral, and reminds it where to find food, deals with idiosyncrasies of the space etc. catches unacceptable behavior. This is why the environment used is important IMHO. You really need to be able to build a cross between a pure response surface optimizater, something that sniffs the gradients using whatever algorithm might be best for that depending on characteristics of the surface, and something you can see, talk to, put ropes on, sand edges for, provide guidance to, etc. Hybridization, and "ensemble approaches" are my favorite concepts right now.

We recently upgraded our optimizer so that it can switch from a (neural) model based optimization, to a direct search, when it's sensitivity-confidence measure (apparently a nightmare to calculate) for a specific DOF falls below a threshold. This is something I've wished it would be smart enough to do for a long time, or at least be smart enough to know, when it doesn't really know, what some lever does.

You sound more like the guy who wrote the new objects and tells me how the knobs work. I'm more the guy who can't wait for new toys. It's a team effort.

 

[Jimster41]

It's hard to draw conclusions about different penalty function methods because of the wide variety of techniques that can be tried. The search methods, the rules for reducing penalties, the rules for restarting a search, etc., etc,. etc., are usually based on heuristics. It can be more of an art and a trial and error process. Because many nonlinear problems have local minimums that fool the algorithms, it is often necessary to try several times with different random starting points and record the best solution of all the starting points.

One trick we got from observing how the operators used the closed-loop optimizer was to keep track of a very simple or naive "best vector" . If the objectives were going south badly we would just "send it home" to that vector, which some of the attentive operators had been writing down. Sort of a case-based hybridization. It turned out to be a good idea, and clued us into the fact the optimizer was "getting lost", due to some local minima, or a just a poorly mapped response surface. We could also send it to a benchmark or control (off) vector to automate collection of performance measurement data.

 

[maistral]

Thanks for the replies guys. I guess I still have to run that old Monte Carlo thing.

Eitherway, I think I'll be trying that vector thing Jim's talking about. Thanks a lot guys!

 

[FactChecker]

There is a technique called "convexification" that attempts to solve the problem of local minimums in nonlinear programming. I have tried it and it seemed to work, but I don't have much experience with it.