Arbitrarily tight BB underestimators of general non-linear functions over sub-optimal domains

Area of Science:

• Optimization Theory
• Non-linear Programming
• Convex Analysis

Background:

• Global optimization of non-linear, non-convex functions is challenging.
• Existing methods like BB relaxations face limitations in tightness and bounding capabilities.

Purpose of the Study:

• To develop arbitrarily tight BB relaxations for general non-linear non-convex functions.
• To address the theoretical challenges in constructing effective BB underestimators.
• To propose a novel methodology for creating tighter underestimators in sub-optimal domains.

Main Methods:

• Transformation of the original function into an $\epsilon$-subenergy function.
• Derivation of BB underestimators for the transformed function.
• Validation through computational test cases comparing $\epsilon$-subenergy and classical BB underestimators.

Main Results:

• The proposed $\epsilon$-subenergy underestimators achieve arbitrarily tight bounds.
• These underestimators demonstrate superior performance in sub-optimal domains compared to classical BB methods.
• Computational tests confirm significantly tighter bounds and improved node fathoming capabilities.

Conclusions:

• The $\epsilon$-subenergy transformation provides a powerful tool for enhancing BB relaxations.
• This approach offers a significant improvement for global optimization problems involving non-linear non-convex functions.
• The method shows promise for tackling complex optimization problems where classical methods falter.