Development and analysis of direct-search methods for feedback control and time-varying optimization

Details

Supervisors

Bianchin, Gianluca ; Nunes Grapiglia, Geovani

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

enThis thesis develops and analyses direct-search accept/reject methods — one-, two-, and three-point variants — for steering a dynamical system toward an optimal operating point when its dynamics are unknown, the cost is observed through imperfect measurements, and may itself evolve over time. These methods rely solely on the sign of the difference between noisy function evaluations, never on its magnitude, and operate in a strictly output-feedback setting: the algorithm interacts with the plant only through the measured output, without access to the internal state. We build a unified proof template and apply it progressively to three regimes of increasing difficulty: a feedback-control setting with constant disturbance, a time-varying setting with exact measurements, and their combination. In each case, we derive non-asymptotic bounds directly controlling a best-iterate stationarity measure, which we adopt as the natural criterion for nonconvex time-varying problems. The two-point method reaches a complexity comparable to the descent-based baseline in the feedback-control setting, up to logarithmic factors, while removing the need to tune a learning rate. We also show that temporal drift and oracle error aggregate additively in the combined setting, and identify an explicit regime in which a non-trivial stationarity guarantee is achievable. A multi-rate extension further quantifies the trade-off between holding the plant input longer and reducing the oracle inaccuracy. Numerical experiments on a linear-quadratic benchmark confirm the predicted rates and decompose the theoretical bound term by term. A practical application — the cascade tracking of a damped-spiral reference by a two-dimensional vehicle subject to unmodelled drag and a stationary wind disturbance — compares the direct-search method against PID, MPC, and a descent-based zeroth-order method. Model-based methods dominate under ideal conditions; as soon as the plant model is misspecified or the disturbance estimator is absent, the direct-search method becomes competitive while requiring essentially no hyperparameter tuning. The main message is that the accept/reject principle, despite its simplicity, is a remarkably universal mechanism: it admits a unified convergence analysis across the three settings considered, achieves complexity rates comparable to descent-based alternatives, and retains its practical advantages in realistic conditions that go beyond the strict scope of the theory.