First, look up the Frank-Wolfe algorithm. It is based precisely on a first-order approximation of the objective function, resulting in a linear function that is then minimized. (Because of the linearity of the approximation, the subproblem solution is one of the extreme points of the feasible set, which is found through the simplex method, for example.) A line search in the original objective function over the line segment between the current iterate and the extreme point just found yields the next iteration, and so on. A more detailed description is here:

https://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm

It's definitely NOT an efficient method, but for small examples it is ok, and it's a very good illustration how an iterative method converges. It is in fact one of the best illustrations of the connection between an algorithm and the optimality conditions for the problem: the Frank-Wolfe algorithm is in fact immediately derived from the variational inequality, representing the optimality conditions for the problem: the subproblem is a test whether the current vector is stationary; if it is not then the subproblem provides a feasible descent direction, in which one then performs a line search wrt. the objective function.

It is in general not an efficient method - the step lengths typically shrink fast - but it is a very good illustration on the connection between optimality conditions and search directions.

Dear Temitayo

Yes, in my opinion using the first order Taylor is sufficient

However I don't really know at what point you have to linearize

Dear Tamitayo

I was thinking about your problem and I would like to suggest a procedure to determine points.

I would use second, or third or even fourth Taylor expansion

For each one of them you will get a lineal tangent, and then you can get the corresponding coordinates.

Then you can compute the value of the objective function at each point

Most probably you will get a different value for each point, consequently, you can select the best considering maximization or minimization.

I don't know if this can work, it is only an idea

It depends on the character of the objective (convex or not) and on the rest of the problem the problem. From your question I suppose that there are integer variables present, but what kind of constraints - nonlinear, too? If the constraints are nonlinear, is the relaxation of the feasible set convex?

If the constraints are non-convex solving the first step in the Frank-Wolfe algorithm wouldn't be easy.

If the objective is nonconvex you could also do a piecewise linearization introducing additional binaries (a typical example for SOS2).

Dear Tamitayo

One way in which you can determine the 'best' point in the Pareto front is to look for knee points. There is one very clearly seen in your Pareto front. The reason is that at that point you have the maximum slope which equals to the largest substitution rate

Tamitayo,

What Dr. Nolberto just said is the right answer for you to look for in a pareto front!

Another relatively easy case is when the objective function is separable, ie, can be written as the sum of functions of a single variable. Check out John Beasley's web page on separable programming.

http://people.brunel.ac.uk/~mastjjb/jeb/or/sep.html

What is the aim of your task?

To investigate an algorithm based on sequential linearization of the objective for a NLP with linear constraints, thus solving the NLP by solving sequences of LPs? The problem with this approach is when solving with the Simplex method you'll always iterate over vertices of the constraint polyhedron. And even with an interior point method you'll always get a boundary point as the next iterate - as long as the linearization is not constant, since by chance you tried the NLP solution yielding a zero gradient. THis is due to the fact that the solution set of an LP is always a face of the polyhedron.

But the solution of the NLP need not be in any vertex - it can be an interior point of the constraint polyhedron, e.g, with the objective ||x-x_0||^2. So in that case the iteration will never converge to the solution.

What is a well-established method: sequential quadratic approximation of the objective - look up SQP.

Best regards

Ralf Gollmer

Dear Ralf

Very interesting your technical answer.

There is however two aspects of it that I don't understand, I am not saying that they are wrong, but simply stating that I don't understand them. Could you please explain?

First, you express that a problem is that when you always iterate over vertices of the constraint polyhedron, and I wonder what is wrong with that?

Is it not the very essence of the Simplex algorithm, where in each iteration it is following the vertices until it finds the optimum, that is, where one of them tangents the objective function?

What do you mean that the linearization is not constant?

Dear Nolberto,

I suggested the aim of linearizing the nonlinear objective was to do a sequential search for the optimal point of the ORIGINAL, i.e. nonlinear, problem. While a linear problem always has its optima in faces of the polyhedron and that's why it is sufficient to iterate over the vertices in the Simplex algorithm, the original problem may have its optimum in an inner point.

Regard e.g. the simple (convex) problem

min {x^2+y^2 | -100

.

Dear Ralf

Thank you for your fast and documented answer. It clarified my doubts, and I understand that you are right.

For me it is very important an illustrative your last paragraph, because it rebuts the belief that you always can apply linearization in a problem with linear constraints and non-linear objective function.

However, pls explain me what you mean by a non-constant linearization.

Now, I need your advice. I got a more complicated problem, which I believe I have the answer, but I am not sure of its correctness, and I would like to have your opinion.

Suppose that you have two products A and B and need to purchase one of them subject to a set of constraints such as Unit cost, Unit Benefit and Labor.

Both products are only available in certain bulk quantities (100, 200 and 400 units for product A), and (100, 150 and 350 units for product B). Of course, the unit cost of each one will depend on the quantities purchased, that is, there is a non-lineal relationship between quantities and costs, benefits and labor in the three cases, consequently the three inequalities are quadratic.

Actions are:

Minimize Cost

Maximize Benefits

Equal available Labor

The objective is to select the product and quantities to buy.

If you want, I can send you all data.

What do you think is the procedure to solve this problem?

Thank you

There are smarter ways also than Frank-Wolfe; one is the Partan (Parallel tangents) version. Look it up.

Dear Nolberto,

first just the simple anwer to one of your questions: If in the example one (by accident) guesses the solution (0,0), the gradient would be zero, thus objective of the linearization would become

min {0| x feasible}

The objective would be constant.

The the real solution of the nonlienar problem would also be an optimal point of the linearization (as all feasible points are) - but the Simplex algorithm would not yield it.

Regarding the problem you described I'll have to think a bit - hope to reach an advice.

Best regards

Ralf

Thank you Ralf, I am looking forward, as well as very interested, for your answer to my problem

Regarding your problem I agree, however I wonder why the Simplex would not yield it

While most the reserrchers have suggested different methods. You can use that has features of using picecewise linear function to linearizing a non linear function. Thanks

Dear Sir, use separable programming problem method.

Dear Goutam

Just as a teaching tool, years ago I solved a problem where the relationship between prices and quantities were non-lineal

I built the function between these two aspects and divided each curve in three parts, replacing the curve segment by a lineal function. Of course, you can divide the curve in how many lineal segments as you wish, and it also depends in the concavity or convexity of the curve.

Further, I built a matrix considering each part of each variable as an alternative. Since the example was very simple, only two variables, there were three alternatives for prices and three for quantities, and the applied SIMUS, which is based on Linear Programming.

This is a very simple approach, however, if there are many variables and many criteria, the problem may become big, which is not a problem for solving, but for preparing the decision matrix.

https://pdfs.semanticscholar.org/.../61570650a081b1972ad9f803bd5...

Dear T.H.

The link does not work

Dear Ralf Gollmer :

I am working with a similar problem that requires an SOS2 condition (my nonlinear element is in some of the constraints). Via separable programming I managed to get one of the constraints linearised, and my question here lies on the breaking points used for the piecewise lineariation.

Is there a way to optimally/efficiently select how many breaking points are present in the piecewise linearisation? How is the process of solving the problem affected by increasing the number of breaking points?

In the constraint that I linearised, I only used four breaking points and three slopes between them, for a quadratic function; but for the other two I'm afraid I need more than that.

Thank you very much in advance,

Carlos

Dear Carlos,

sorry, I can't help - I do not know a means of a priori selecting an 'optimal' piecewise linearization. Many breakpoints make the problem bigger and probably harder to solve with MILP software, while taking only very few introduces bigger differences to the original function. Of course a good representation will be needed only near the solution, further away the linearization can be rough. But at least the principal shape of the function has to be represented.

I tried once to make the piecewise linearization adaptive to the location of the solution by introducing additional breakpoints in the interval active at the current solution, but did this 'by hand', not automated - and I did not even sketch a script for doing so - because in the end we decided to keep the problem nonlinear and to handle it by NLP solvers.

Best regards

Ralf

Check out "Benders decomposition".

This may be stating the obvious, but it all depends on the properties of the objective function. If you are minimising a convex function, then you can use Kelley's cutting-plane method, the penalty-barrier method, the bundle method, and so on. If your function is non-convex but separable, then you can use separable programming (as I mentioned above). If none of those hold, things get more difficult, and you will probably need global optimisation tools.

Thank you everyone for your responses, I really appreciate them all. I'll try some initial number of breaking points as a benchmark and see what comes from it.

Best wishes,

Carlos

In converting an optimization problem with nonlinear objective function with linear constraints into a Linear Problem or a MIP, after you have observed the various suggestions of Adams N. Letchford, you might need to re-scale the problem. Scaling will afford you the opportunity to use the Kelley's cutting plane method, the penalty barrier method and the Conjugate Gradient Method.