Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization

Jens Clausen, A, Zilinskas

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are based on the sampling of function values.

    We propose a branch and bound algorithm based on regular simplexes. Initially, the domain in question is covered with regular simplexes, and our subdivision scheme maintains this property. The bound calculation becomes both simple and efficient, and we describe two schemes for sampling points of the function: midpoint sampling and vertex sampling.

    The convergence of the algorithm is proved, and numerical results are presented for the two dimensional case, for which also a special initial covering is presented. (C) 2002 Elsevier Science Ltd. All rights reserved.
    Original languageEnglish
    JournalComputers & Mathematics with Applications
    Volume44
    Issue number7
    Pages (from-to)943-955
    ISSN0898-1221
    DOIs
    Publication statusPublished - 2002

    Cite this

    @article{fc8f155d99874cf5953f6e1fc3db8e8f,
    title = "Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization",
    abstract = "We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are based on the sampling of function values.We propose a branch and bound algorithm based on regular simplexes. Initially, the domain in question is covered with regular simplexes, and our subdivision scheme maintains this property. The bound calculation becomes both simple and efficient, and we describe two schemes for sampling points of the function: midpoint sampling and vertex sampling.The convergence of the algorithm is proved, and numerical results are presented for the two dimensional case, for which also a special initial covering is presented. (C) 2002 Elsevier Science Ltd. All rights reserved.",
    keywords = "Branch and Bound, Global Optimization",
    author = "Jens Clausen and A, Zilinskas",
    year = "2002",
    doi = "10.1016/S0898-1221(02)00205-5",
    language = "English",
    volume = "44",
    pages = "943--955",
    journal = "Computers & Mathematics with Applications",
    issn = "0898-1221",
    publisher = "Pergamon Press",
    number = "7",

    }

    Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization. / Clausen, Jens; Zilinskas, A,.

    In: Computers & Mathematics with Applications, Vol. 44, No. 7, 2002, p. 943-955.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization

    AU - Clausen, Jens

    AU - Zilinskas, A,

    PY - 2002

    Y1 - 2002

    N2 - We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are based on the sampling of function values.We propose a branch and bound algorithm based on regular simplexes. Initially, the domain in question is covered with regular simplexes, and our subdivision scheme maintains this property. The bound calculation becomes both simple and efficient, and we describe two schemes for sampling points of the function: midpoint sampling and vertex sampling.The convergence of the algorithm is proved, and numerical results are presented for the two dimensional case, for which also a special initial covering is presented. (C) 2002 Elsevier Science Ltd. All rights reserved.

    AB - We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are based on the sampling of function values.We propose a branch and bound algorithm based on regular simplexes. Initially, the domain in question is covered with regular simplexes, and our subdivision scheme maintains this property. The bound calculation becomes both simple and efficient, and we describe two schemes for sampling points of the function: midpoint sampling and vertex sampling.The convergence of the algorithm is proved, and numerical results are presented for the two dimensional case, for which also a special initial covering is presented. (C) 2002 Elsevier Science Ltd. All rights reserved.

    KW - Branch and Bound

    KW - Global Optimization

    U2 - 10.1016/S0898-1221(02)00205-5

    DO - 10.1016/S0898-1221(02)00205-5

    M3 - Journal article

    VL - 44

    SP - 943

    EP - 955

    JO - Computers & Mathematics with Applications

    JF - Computers & Mathematics with Applications

    SN - 0898-1221

    IS - 7

    ER -