Page 52 - Sustainability in the process industry

Pro c ess O p timization 29

to be convex. For linear problems (e.g., MILP), the locally optimal
solution is guaranteed to be global—in other words, the best possible.
Another advantage of the linear model is that linear solvers, unlike
with nonlinear ones, do not require initialization with a feasible
solution. Nonlinear problems are much more difficult to solve, and
attaining feasibility of the solutions is a significant issue. Any result
obtained guarantees global optimality only if the optimization
problem is shown to be convex (Williams, 1999).

3.6 Deterministic Algorithms for Solving Continuous
Linear Optimization Problems

The best-known algorithm for LPR problems is the simplex algorithm
(Dantzig, 1951; Dantzig, Orden, and Wolfe, 1954). It solves LPR
maximization problems by constructing a feasible solution at a vertex
of the search polyhedron and then walking along the edges of the
polyhedron to other vertices with successively higher objective
function values. Although this algorithm is efficient in general, in
some cases it may require exponential time to find the optimum.
Khachiyan (1979) proposed a method that, in the worst case, finds a
solution in polynomial time for the worst case. Today, the LPR
problems are usually solved using one of two methods:
1. Revisions of the simplex algorithm: This algorithm has been
developed almost continuously over the years since its initial
formulation, starting with the revised Simplex Method of
Dantzig and Orchard-Hays (1953). A thorough consideration
of the simplex algorithm and its computational techniques is
given in Maros (2003b). Modern LPR solvers use algorithms
that flexibly solve both continuous and integer linear
problems.
2. Interior point methods: In contrast to the simplex algorithm,
which finds the optimal solution by traversing points on the
boundary of the feasible region, interior point methods move
through the interior of the feasible region. One such method
(see Mehrotra, 1992) is used by MATLAB.

3.7 Deterministic Algorithms for Solving Continuous
Nonlinear Optimization Problems

Nonlinear programming is used to solve continuous nonlinear
problems. A common feature of all deterministic search methods is
that, starting from a current solution point, they perform an iterative
search for a better feasible solution within the vicinity of the current