Convexification and Global Optimization of Problems Involving the Euclidean Norm

The field of deterministic global optimization has advanced significantly over the last several decades, enabled by the development of new algorithmic techniques and improved computer hardware, and is experiencing a surge of interest. However, global optimization methods for general nonlinear problems are less mature than those for other NP-hard classes of optimization problems, such as mixed-integer linear or quadratic optimization. In this thesis, we study a particularly challenging class of nonconvex optimization problems, characterized by the presence of the Euclidean norm. These problems arise naturally in the context of chemical and statistical physics, but also appear in applications including discrete geometry and operations research, and the question of certifying global optimality remains open even for small instances. We identify the simultaneous elimination of Euclidean and permutational symmetry groups, as well as the convexification of reverse convex sets defined by the Euclidean norm, as two key challenges for global optimization methods, and introduce a benchmark library of instances of this type. Furthermore, we advance the state of the art by developing symmetry elimination and convexification techniques in the context of two problems arising in chemistry and physics and one from location theory. Numerical experiments with the general-purpose global optimization solver BARON indicate that our algorithms accelerate the solution of these problems by up to two orders of magnitude.

Level thesis:degree_level

Doctoral

Department dc:contributor.department

Chemical and Biomolecular Engineering

Grantor dc:publisher

Georgia Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Kuznetsov, Anatoliy

Advisor dc:contributor.advisor

• Sahinidis, Nikolaos

Committee members dc:contributor.committeemember

• Scott, Joseph K.
• Wilson, Corey J.
• Boukouvala, Fani
• Skolnick, Jeffrey

• Global optimization
• Simultaneous convexification
• Symmetry elimination

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/1853/78549

OAI identifier oai:identifier

oai:repository.gatech.edu:1853/78549