The coefficient inverse problems of frequency sounding of inhomogeneous media are considered. Such problems arise in applied sciences, such as geophysical exploration of gas, oil and mineral deposits, reservoir monitoring, underwater acoustics and electromagnetics, optical sensing, etc. Applying the nonlinear least squares method to such problems often results in a multiextremal objective function. This is due to incompleteness of sounding data. Under this condition, the iterative methods of nonlinear optimisation, such as the gradient or Newton-like methods, may lead to false solutions related to local minima. Furthermore, due to ill-posedness of coefficient inverse problems, the convergence of iterates cannot be guaranteed. On the other hand, the effective use of global optimisation algorithms is severely affected by both the large dimension of the searching space and ill-posedness. To treat simultaneously both these issues, the convexification approach to coefficient inverse problems has been recently proposed and developed by the authors. This approach consists of transforming an original inverse problem to an auxiliary problem of the field prediction from the surface into an inhomogeneity. As a result, the differential operator associated with this problem does not depend explicitly on an unknown coefficient. Applying the weighted least squares method to this problem and choosing the Carleman weight functions as weights, a strictly convex objective function is constructed on a certain compact set. This set plays the role of a correctness set providing the existence of stable approximate solutions of the auxiliary problem. Once the predicted field is approximately determined, the inversion is done via an explicit formula. Because of the strictly convex objective function defined on a compact set, the nonlinear inequality-constrained optimisation problem arises after finite-dimensional approximations. Two algorithms are developed to solve this problem. Both these algorithms are iterative and they can be interpreted as some sort of interior point algorithms that possess the regularising properties. The first algorithm exploits the Generalised Reduced Gradient Method avoiding the use of penalty functions, whereas the second algorithm utilises the contraction property of the map generated by the Frechet derivative of the objective function. A key point in these algorithms is that unlike conventional layer-stripping techniques, they provide the stable approximate solutions. Another advantage of the proposed algorithms is that the starting vector is determined directly from sounding data. The 1-D inverse model of magnetotelluric frequency sounding is selected to exemplify the convexification approach. The results of computational experiments with several realistic and synthetic marine shallow water configurations are presented to demonstrate the computational feasibility of the proposed algorithms. ~