Non Linear Programming  

Overview of non-linear programming

Many industrial optimisation applications involve modelling, which is to some extent akin to the realm of Physics. In optimising the design, for example, we optimise meta-models or non-linear response surfaces resulting from a non-statistical model. Likewise, topologic or shape optimisation makes extensive use of non-linear models - and often very large such models.

Formal notation for a non-linear mathematical programme:
Min f(x)
g_j(x) <=0 j = 1,…,m
where x is a vector of real numbers representing the decision variables.

The techniques used to resolve mathematical problems and the performance of optimisation algorithms depend on the type of objective function and constraint functions.

• Linear programming deals with cases where f(x) and g_j(x) are linear. The simplex algorithm or interior methods can solve very large problems (from hundreds of thousands to a few million variables, and tens of thousands of constraints).
• quadratic programming manages cases where the objective function f(x) is quadratic, and constraints g_j(x) are linear. Powerful algorithms are available for handling this special case, e.g. in optimisation problems for financial portfolios.
• stochastic programming and robust programming treat situations where the data is known only as a probability (i.e. expressed as random variables) or imprecisely (as in robust programming).
• dynamic programming is for cases where an optimal solution necessarily comprises both optimal sub-solutions (e.g. a property used to find the shortest path in graphs) and the shortest paths under constraints (algorithms used in column generation mechanisms for resolving the sub-problem in components such as LP-ShiftPlanner).
• non-linear programming studies the general case where the objective f(x) and/or the constraints g_j(x) are non-linear functions.

Most non-linear programming methods use the concept of the gradient of functions f(x) and g_j(x) in order to calculate the descent directions, i.e. an improvement of the objective function. With linear programming, the gradient is the c vector of the objective function and does not vary within the solution space. When the functions are convex (as for continuous linear programming, for example), descent algorithms converge upon a global optimum. In the general case, these algorithms and the corresponding software converge to a local optimum only. Whenever possible, it is important to run these algorithms from several different initial solutions in order to find the best, i.e. the global, solution.

A non-linear programme under constraints may also be transformed into a problem without constraints using the Lagrange multiplier: this method introduces slack variables into the objective function as constraints, and increasing penalties for these differences as we approach saturation levels for the corresponding constraints.

Solvers and IT implementation

Several solvers are available for resolving non-linear programmes.
Eurodecision has tested the following solvers:

• OPT++
• FSQP
• KNITRO
• FAIPA
• GLPK
• LPSOLVE
• Coin-OR: IPOpt, OBOE