In this paper, we present novel multi-variable Newton-based extremum seeking systems, based on Lie bracket approximation methods. More precisely, we consider cost functions with an unknown mathematical description, but whose value can be measured on-line. We propose extremum seeking systems that approximate the Newton-based optimization law, by combining the on-line measurement of the cost with time-periodic excitation signals. The inversion of the Hessian matrix is avoided by introducing a first order dynamical system, whose output approximates the Newton step. This provides practical robustness with respect to ill-conditioned Hessian matrices. Semi-global stability properties of the proposed schemes are demonstrated both for static cost functions and for cost functions associated with a general non-linear dynamical system. The effectiveness of the approach is shown in simulations. (C) 2019 Elsevier Ltd. All rights reserved.