Titolo della tesi: Derivative-Free Optimization: worst-case complexity for Line- Search methods and a Mixed Penalty-Barrier approach.
This thesis investigates new advances in Derivative-Free Optimization (DFO), focusing on complexity
analysis for line-search methods and proposing a novel mixed penalty-barrier approach for handling
constraints in black-box optimization problems. Classical optimization approaches often rely on gra-
dient information; however, in practical applications, derivatives may be unavailable, unreliable, or
costly to compute. DFO addresses this gap by developing methods that depend solely on function
evaluations, which are crucial for applications with noisy, expensive, or simulation-based objective
functions.
Chapter 2 presents a theoretical analysis of line-search based DFO algorithms, concentrating on
their worst-case complexity bounds in both unconstrained and bound-constrained contexts. For
unconstrained problems, a worst-case complexity bound is established that matches the iteration
requirements of existing direct search methods, marking a significant theoretical contribution to the
field. Additionally, for the bound-constrained case, a criticality measure is introduced to evaluate
solution quality, with complexity bounds developed to ensure efficient progress. An active-set iden-
tification property is also demonstrated, showing that the method can recognize and exploit bounds
that are active at the solution, enhancing computational efficiency for bound-constrained problems.
Chapter 3 introduces a sequential mixed-penalty approach for solving general nonlinear constrained
black-box optimization problems, where traditional derivative-based constraint-handling techniques
are unsuitable. This approach combines two distinct penalty mechanisms: a logarithmic barrier for
handling inequality constraints and an exterior penalty for equality constraints. This dual strategy
leverages a line-search framework to enforce constraint satisfaction while accommodating variable
bounds, demonstrating improved feasibility attainment in constrained black-box settings. Further-
more, a direct search variant of the algorithm is developed, incorporating the mixed penalty strategy
to manage unrelaxable constraints effectively.
Together, these contributions advance the field of DFO by providing rigorous complexity bounds
for line-search methods and a robust mixed penalty-barrier framework for constrained optimiza-
tion. Empirical tests validate the efficacy of these algorithms across a diverse range of constrained
optimization problems, underscoring their applicability in real-world black-box settings.