Nonlinear problems, optimization

Miettinen, K., Lotov, A. V., Kamenev, G. K. and Berezkin, V. E. (2003a). Integration of two multiobjective optimization methods for nonlinear problems. Optimization Methods and Software 18, 1, pp. 63-80. 

Sargent, R.W.H. "A Review of Optimization Methods for Nonlinear Problems", in Computer Applications in Chemical Engineering, R.G. Squires and G.V. Reklaitis, Eds., ACS Symposium Series 124, 37-52, 1980. 

From the discussion in this chapter, it is clear that the difficulties associated with optimizing nonlinear problems are far greater than those for optimizing linear problems. For linear problems, finding the global optimum can, in principle, be guaranteed. 

One of the approaches that can be used in design is to carry out structural and parameter optimization of a superstructure. The structural optimization required can be carried out using mixed integer linear programming in the case of a linear problem or mixed integer nonlinear programming in the case of a nonlinear problem. Stochastic optimization can also be very effective for structural optimization problems. 

In numerical studies it turned out that the MILP problem can not only be solved much faster than the MINLP problem, but for most of the model instances it provides solutions of significantly higher solution quality. Certainly, the engineered linearization of the nonlinear problem causes a loss in model precision, but on the other hand it enables a globally optimal solution. Since the MILP solutions are feasible for the MINLP problem, it is clear that the inferior quality of the MINLP solutions originates from the fact that only local minima were found. 

As optimization methods as well as computer hardware and software have improved over the past two decades, the degree of difficulty of the problems that can be solved has expanded significantly. Continued improvements in optimization algorithms and computer technology should enable optimization of large-scale nonlinear problems involving thousands of variables, both continuous and integer, some of which may be stochastic in nature. 

In nonlinear programming problems, optimal solutions need not occur at vertices and can occur at points with positive degrees of freedom. It is possible to have no active constraints at a solution, for example in unconstrained problems. We consider nonlinear problems with constraints in Chapter 8. 

In addition to providing optimal x values, both simplex and barrier solvers provide values of dual variables or Lagrange multipliers for each constraint. We discuss Lagrange multipliers at some length in Chapter 8, and the conclusions reached there, valid for nonlinear problems, must hold for linear programs as well. In Chapter 8 we show that the dual variable for a constraint is equal to the derivative of the optimal objective value with respect to the constraint limit or right-hand side. We illustrate this with examples in Section 7.8. 

The Excel Solver. Microsoft Excel, beginning with version 3.0 in 1991, incorporates an NLP solver that operates on the values and formulas of a spreadsheet model. Versions 4.0 and later include an LP solver and mixed-integer programming (MIP) capability for both linear and nonlinear problems. The user specifies a set of cell addresses to be independently adjusted (the decision variables), a set of formula cells whose values are to be constrained (the constraints), and a formula cell designated as the optimization objective. The solver uses the spreadsheet interpreter to evaluate the constraint and objective functions, and approximates derivatives, using finite differences. The NLP solution engine for the Excel Solver is GRG2 (see Section 8.7). 

In this chapter, we discuss solution approaches for MILP and MINLP that are capable of finding an optimal solution and verify that they have done so. Specifically, we consider branch-and-bound (BB) and outer linearization (OL) methods. BB can be applied to both linear and nonlinear problems, but OL is used for nonlinear problems by solving a sequence of MILPs. Chapter 10 further considers branch-and-bound methods, and also describes heuristic methods, which often find very good solutions but are unable to verify optimality. 

Branch and bound (BB) is a class of methods for linear and nonlinear mixed-integer programming. If carried to completion, it is guaranteed to find an optimal solution to linear and convex nonlinear problems. It is the most popular approach and is currently used in virtually all commercial MILP software (see Chapter 7). 

The operation of a plant under steady-state conditions is commonly represented by a non-linear system of algebraic equations. It is made up of energy and mass balances and may include thermodynamic relationships and some physical behavior of the system. In this case, data reconciliation is based on the solution of a nonlinear constrained optimization problem. 

Das, I., Dennis, J. E. (1998) Normalboundary intersection a new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8, 631-657. 

A key idea in developing necessary and sufficient optimality conditions for nonlinear constrained optimization problems is to transform them into unconstrained problems and apply the optimality conditions discussed in Section 3.1 for the determination of the stationary points of the unconstrained function. One such transformation involves the introduction of an auxiliary function, called the Lagrange function L(x,A, p), defined as... 

The optimality conditions discussed in the previous sections formed the theoretical basis for the development of several algorithms for unconstrained and constrained nonlinear optimization problems. In this section, we will provide a brief outline of the different classes of nonlinear multivariable optimization algorithms. 

V. Visweswaran. Global optimization of nonconvex, nonlinear problems. PhD thesis, Princeton University, 1995. 

When the nonlinear discrete optimization problem is formulated as the generalized disjunctive program in (DPI), one can develop a corresponding logic-based branch-and-bound method. The basic difference is that the branching is performed... 

This operation is referred to as majorization and allows simpler constraints to be used, facilitating solution at the expense of reducing the feasible space for p. This method is not readily applicable to nonlinear dynamic optimization, where there is no formula for the constraints but trading conservatism in design for ease of solution can be achieved for the problems of interest by a different strategy discussed in Section II.A.2. 

In putting everything together, we have to face these algorithmic problems (1) determine the optimal parameters 0 by maximizing the probability p(O,j 0) -this is a nonlinear global optimization problem-, (2) determine the optimal sequence of hidden metastable states j = jt) for given optimal parameters, and (3) determine the number of important metastable states which we, up to now, simply assumed to be identical with the number of hidden states. 

Zhou, J., Tits, A., Lawrence, C. Users s Guide for FFSQP Version 3.7 A FORTRAN code for solving constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality and linear constraints, University of Maryland, 1997. 

If we decide to treat the estimation problem using the nonlinear model, the problem becomes more challenging. As we will see, the parameter estimation becomes a nonlinear optimization that must be solved numerically instead of a linear matrix inversion that can be solved analytically as in Equation 9.8. Moreover, the confidence intervals become more difficult to compute, and they lose their strict probabilistic interpretation as a-level confidence regions. As we will see, however, the approximate confidence intervals remain very useful in nonlinear problems. The numerical challenges for nonlinear models... 

---