A Survey of Optimization Methods from a Machine Learning Perspective <s> C. Derivative-Free Optimization <s> There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> C. Derivative-Free Optimization <s> Independence from the coordinate system is one source of efficiency and robustness for the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). The recently proposed Adaptive Encoding (AE) procedure generalizes CMA-ES adaptive mechanism, and can be used together with any optimization algorithm. Adaptive Encoding gradually builds a transformation of the coordinate system such that the new coordinates are as decorrelated as possible with respect to the objective function. But any optimization algorithm can then be used together with Adaptive Encoding, and this paper proposes to use one of the simplest of all, that uses a dichotomy procedure on each coordinate in turn. The resulting algorithm, termed Adaptive Coordinate Descent (ACiD), is analyzed on the Sphere function, and experimentally validated on BBOB testbench where it is shown to outperform the standard (1+1)-CMA-ES, and is found comparable to other state-of-the-art CMA-ES variants. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> C. Derivative-Free Optimization <s> In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $\epsilon$-accurate solution with probability at least $1-\rho$ in at most $O(\tfrac{n}{\epsilon} \log \tfrac{1}{\rho})$ iterations, where $n$ is the number of blocks. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper #2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\epsilon$ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving true iteration complexity bounds. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $\ell_1$-regularized least squares and support vector machine problems with a billion variables. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> C. Derivative-Free Optimization <s> This paper addresses the solution of bound-constrained optimization problems using algorithms that require only the availability of objective function values but no derivative information. We refer to these algorithms as derivative-free algorithms. Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied, and it has found renewed interest in recent time. Along with many derivative-free algorithms, many software implementations have also appeared. The paper presents a review of derivative-free algorithms, followed by a systematic comparison of 22 related implementations using a test set of 502 problems. The test bed includes convex and nonconvex problems, smooth as well as nonsmooth problems. The algorithms were tested under the same conditions and ranked under several criteria, including their ability to find near-global solutions for nonconvex problems, improve a given starting point, and refine a near-optimal solution. A total of 112,448 problem instances were solved. We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size. For the problems used in this study, TOMLAB/MULTIMIN, TOMLAB/GLCCLUSTER, MCS and TOMLAB/LGO are better, on average, than other derivative-free solvers in terms of solution quality within 2,500 function evaluations. These global solvers outperform local solvers even for convex problems. Finally, TOMLAB/OQNLP, NEWUOA, and TOMLAB/MULTIMIN show superior performance in terms of refining a near-optimal solution. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> C. Derivative-Free Optimization <s> Blackbox optimization refers to problems where the structure of the objective and constraint functions cannot be exploited. This is often the case when their evaluation requires the execution of a (usually time-consuming) simulation using computational models that are typically inaccessible by the user. The term Derivative-Free Optimization refers to the use of algorithms that utilize only function values because their partial derivatives are either not defined or not available; gradient approximations may sometimes be obtained, but the amount of work required to ensure they are dependable may not be worth the effort. Both blackbox and derivative-free optimization have attracted significant, and still increasing, interest from researchers over the last decade. Thus, we felt that it was time to dedicate a special issue of OPTE to this topic. Blackbox and derivative-free optimization methods are often the only realistic and practical tools available to engineers working on simulation-based design. It is obvious that if the design optimization problem at hand allows an evaluation or reliable approximation of the gradients, then efficient gradient-based methods should be used. Blackbox and derivative-free algorithms are not competitors of gradient-based methods; they are a fallback when gradient-based algorithms cannot be used. The design engineering community is increasingly becoming aware that <s> BIB005
For some optimization problems in practical applications, the derivative of the objective function may not exist or is not easy to calculate. The solution of finding the optimal point, in this case, is called derivative-free optimization, which is a discipline of mathematical optimization  , BIB005 , BIB004 . It can find the optimal solution without the gradient information. There are mainly two types of ideas for derivative-free optimization. One is to use heuristic algorithms. It is characterized by empirical rules and chooses methods that have already worked well, rather than derives solutions systematically. There are many types of heuristic optimization methods, including classical simulated annealing arithmetic, genetic algorithms, ant colony algorithms, and particle swarm optimization BIB001 ,  ,  . These heuristic methods usually yield approximate global optimal values, and the theoretical support is weak. We do not focus on such techniques in this section. The other is to fit an appropriate function according to the samples of the objective function. This type of methods usually attaches some constraints to the search space to derive the samples. Coordinate descent method is a typical derivativefree algorithm  , and it can be extended and applied to optimization algorithms for machine learning problems easily. In this section, we mainly introduce the coordinate descent method. The coordinate descent method is a derivative-free optimization algorithm for multi-variable functions. Its idea is that one-dimensional search can be performed sequentially along each axis direction to obtain updated values for each dimension. This method is suitable for some problems in which the loss function is non-differentiable. The vanilla approach is to select a set of bases e 1 , e 2 , ..., e N in the linear space as the search directions and minimizes the value of the objective function in each direction. For the target function J(Θ), when Θ k is already obtained, the jth dimension of Θ k+1 is solved by   Thus, The convergence of this method is similar to the gradient descent method. The order of update can be an arbitrary arrangement from e 1 to e N in each iteration. The descent direction can be generalized from the coordinate axis to the coordinate block BIB003 . The main difference between the coordinate descent and the gradient descent is that each update direction in the gradient descent method is determined by the gradient of the current position, which may not be parallel to any coordinate axis. In the coordinate descent method, the optimization direction is fixed from beginning to end. It does not need to calculate the gradient of the objective function. In each iteration, the update is only executed along the direction of one axis, and thus the calculation of the coordinate descent method is simple even for some complicated problems. For indivisible functions, the algorithm may not be able to find the optimal solution in a small number of iteration steps. An appropriate coordinate system can be used to accelerate the convergence. For example, the adaptive coordinate descent method takes principal component analysis to obtain a new coordinate system with as little correlation as possible between the coordinates BIB002 . The coordinate descent method still has limitations when performing on the non-smooth objective function, which may fall into a non-stationary point.