A Survey of Optimization Methods from a Machine Learning Perspective <s> 7) Frank-Wolfe Method: <s> This paper presents a very simple modification of the Frank-Wolfe algorithm for the solution of the traffic assignment problem. It is shown that the modified algorithm can be implemented without much increase in computational effort over the original one. Convergence of the algorithm is proved and computational results are reported to demonstrate the validity of the modification. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 7) Frank-Wolfe Method: <s> The problem of maximizing a concave function f(x) in a simplex S can be solved approximately by a simple greedy algorithm. For given k, the algorithm can find a point x(k) on a k-dimensional face of S, such that f(x(k)) ≥ f(x*) - O(1/k). Here f(x*) is the maximum value of f in S. This algorithm and analysis were known before, and related to problems of statistics and machine learning, such as boosting, regression, and density mixture estimation. In other work, coming from computational geometry, the existence of e-coresets was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm. Similar greedy algorithms, that are special cases of the Frank-Wolfe algorithm, were described for other enclosure problems. Here these results are tied together, stronger convergence results are reviewed, and several coreset bounds are generalized or strengthened. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 7) Frank-Wolfe Method: <s> We provide stronger and more general primal-dual convergence results for Frank-Wolfe-type algorithms (a.k.a. conditional gradient) for constrained convex optimization, enabled by a simple framework of duality gap certificates. Our analysis also holds if the linear subproblems are only solved approximately (as well as if the gradients are inexact), and is proven to be worst-case optimal in the sparsity of the obtained solutions. ::: ::: On the application side, this allows us to unify a large variety of existing sparse greedy methods, in particular for optimization over convex hulls of an atomic set, even if those sets can only be approximated, including sparse (or structured sparse) vectors or matrices, low-rank matrices, permutation matrices, or max-norm bounded matrices. ::: ::: We present a new general framework for convex optimization over matrix factorizations, where every Frank-Wolfe iteration will consist of a low-rank update, and discuss the broad application areas of this approach. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 7) Frank-Wolfe Method: <s> The theory of reinforcement learning provides a normative account, deeply rooted in psychological and neuroscientific perspectives on animal behaviour, of how agents may optimize their control of an environment. To use reinforcement learning successfully in situations approaching real-world complexity, however, agents are confronted with a difficult task: they must derive efficient representations of the environment from high-dimensional sensory inputs, and use these to generalize past experience to new situations. Remarkably, humans and other animals seem to solve this problem through a harmonious combination of reinforcement learning and hierarchical sensory processing systems, the former evidenced by a wealth of neural data revealing notable parallels between the phasic signals emitted by dopaminergic neurons and temporal difference reinforcement learning algorithms. While reinforcement learning agents have achieved some successes in a variety of domains, their applicability has previously been limited to domains in which useful features can be handcrafted, or to domains with fully observed, low-dimensional state spaces. Here we use recent advances in training deep neural networks to develop a novel artificial agent, termed a deep Q-network, that can learn successful policies directly from high-dimensional sensory inputs using end-to-end reinforcement learning. We tested this agent on the challenging domain of classic Atari 2600 games. We demonstrate that the deep Q-network agent, receiving only the pixels and the game score as inputs, was able to surpass the performance of all previous algorithms and achieve a level comparable to that of a professional human games tester across a set of 49 games, using the same algorithm, network architecture and hyperparameters. This work bridges the divide between high-dimensional sensory inputs and actions, resulting in the first artificial agent that is capable of learning to excel at a diverse array of challenging tasks. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 7) Frank-Wolfe Method: <s> Part 1 Models: urban traffic planning - the transportation planning process, organization and goal definition, base-year inventory, model analysis, travel forecast, network evaluation, discussion the basic equilibrium model and extensions - the Wardrop conditions, the mathematical program for user equilibrium, properties of equilibrium solutions, user equilibrium versus system optimum, non-separable costs and multiclass-user transportation networks, related network problems, discussion, some extentions general traffic equilibrium models - traffic equilibrium models, properties of equilibrium solutions. Part 2 Methods: algorithms for the basic model and its extensions - the Frank-Wolfe algorithm and its extensions, algorithm concepts, algorithms for the basic model, algorithms for elastic demand problems, algorithms for stochastic assignment models, algorithms for side-constrained assignment models, discussion algorithms for general traffic equilibria - algorithm concepts, algorithms for general traffic equilibria, discussion. <s> BIB005
In 1956, Frank and Wolfe proposed an algorithm for solving linear constraint problems  . The basic idea is to approximate the objective function with a linear function, then solve the linear programming to find the feasible descending direction, and finally make a one-dimensional search along the direction in the feasible domain. This method is also called the approximate linearization method. Here, we give a simple example of Frank-Wolfe method. Consider the optimization problem, where A is an m × n full row rank matrix, and the feasible region is , and substitute it into equation BIB004 . Then we have which is equivalent to Suppose there exist an optimal solution y k , and then there must be So y k − x k is the decreasing direction of f (x) at x k . A fetch step of λ k updates the search point in a feasible direction. The detailed operation is shown in Algorithm 1. Algorithm 1 Frank-Wolfe Method  , BIB003 Input: The algorithm satisfies the following convergence theorem  : c (1) x k is the Kuhn-Tucker point of (31) when The Frank-Wolfe algorithm is a first-order iterative method for solving convex optimization problems with constrained conditions. It consists of determining the feasible descent direction and calculating the search step size. The algorithm is characterized by fast convergence in early iterations and slower in later phases. When the iterative point is close to the optimal solution, the search direction and the gradient of the objective function tend to be orthogonal. Such a direction is not the best downward direction so that the FrankWolfe algorithm can be improved and extended in terms of the selection of the descending directions BIB001 , BIB005 , BIB002 .