No label defined (Q4352202)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1054662
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1054662

      Statements

      0 references
      0 references
      11 November 1997
      0 references
      underestimating linear program
      0 references
      branch and bound
      0 references
      rectangular domain regions
      0 references
      We present here a new method for bounding nonlinear programs which forms the foundation for a branch and bound algorithm presented in the first chapter. The bounding method is a generalization of the method proposed by \textit{R. E. Swaney} (to appear) and is applicable to NLPs in factorable form, which include problems with quadratic objective functions and quadratic constraints as well as problems with twice differentiable transcendental functions. Branch and bound algorithms typically get an upper bound on the solution from the best known feasible point, so some branch and bound algorithms use a local NLP method to find good feasible points. The algorithm presented here incorporates global bounding information into the search for local minima and feasible points. The bounding method here is developed for branch and bound algorithms using rectangular domain regions. An underestimating LP based on McCormick's convex envelopes and additional constraints formed from positive definite combinations of quadratic terms is used to provide a lower bound for the original problem over a rectangular region. Two different approaches are used in the search for feasible points, one using MINOS 5.4 and a second one using the underestimating LP in an iterative scheme. These aspects are first treated in the chapter. The key features of the bounding method are its ease of evaluation, its wide applicability, and its ability to provide the exact lower bound over a region of finite size. Because the bounding method uses an LP, it can be reliably and efficiently solved using existing algorithms. It can be applied to a large class of problems because it only requires them to be in factorable form. Lastly, the underestimating LP is designed to provide the exact lower bound when built around the global minimum of a region of finite size, enabling finite termination of the branch and bound algorithm. The development of the underestimating LP will be presented as follows: in Section 1, an LP underestimator for a particular orthant (one of \(2^n\) sub-rectangles of the current rectangular region) is developed using McCormick's convex envelopes. The difficulty with unconstrained minima is demonstrated, and a variable transformation and new constraints based on positive definite combinations of quadratic terms are presented to solve the problem. In Section 2, a method to combine the \(2^n\) orthants into a single underestimating LP is presented. The combination of the orthant programs can be viewed as an LP with interval coefficients, so a method for transforming an LP with interval coefficients into an LP with real coefficients is developed. The interval form of the orthant program is simplified and tightened by eliminating some of the variables, and then it is transformed into a conventional LP with fixed (noninterval) coefficients. This transformation avoids the solution of \(2^n\) subproblems while retaining finite termination characteristics for nonconvex NLPs. For the entire collection see [Zbl 0869.00021].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references