Journal articles: 'Frank-Wolfe Method'

1

Zahavy, Tom, Alon Cohen, Haim Kaplan, and Yishay Mansour. "Apprenticeship Learning via Frank-Wolfe." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 6720–28. http://dx.doi.org/10.1609/aaai.v34i04.6150.

Full text

Abstract:

We consider the applications of the Frank-Wolfe (FW) algorithm for Apprenticeship Learning (AL). In this setting, we are given a Markov Decision Process (MDP) without an explicit reward function. Instead, we observe an expert that acts according to some policy, and the goal is to find a policy whose feature expectations are closest to those of the expert policy. We formulate this problem as finding the projection of the feature expectations of the expert on the feature expectations polytope – the convex hull of the feature expectations of all the deterministic policies in the MDP. We show that this formulation is equivalent to the AL objective and that solving this problem using the FW algorithm is equivalent well-known Projection method of Abbeel and Ng (2004). This insight allows us to analyze AL with tools from convex optimization literature and derive tighter convergence bounds on AL. Specifically, we show that a variation of the FW method that is based on taking “away steps” achieves a linear rate of convergence when applied to AL and that a stochastic version of the FW algorithm can be used to avoid precise estimation of feature expectations. We also experimentally show that this version outperforms the FW baseline. To the best of our knowledge, this is the first work that shows linear convergence rates for AL.

APA, Harvard, Vancouver, ISO, and other styles

2

Freund, Robert M., and Paul Grigas. "New analysis and results for the Frank–Wolfe method." Mathematical Programming 155, no. 1-2 (November 28, 2014): 199–230. http://dx.doi.org/10.1007/s10107-014-0841-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

FRANDI, EMANUELE, RICARDO ÑANCULEF, MARIA GRAZIA GASPARO, STEFANO LODI, and CLAUDIO SARTORI. "TRAINING SUPPORT VECTOR MACHINES USING FRANK–WOLFE OPTIMIZATION METHODS." International Journal of Pattern Recognition and Artificial Intelligence 27, no. 03 (May 2013): 1360003. http://dx.doi.org/10.1142/s0218001413600033.

Full text

Abstract:

Training a support vector machine (SVM) requires the solution of a quadratic programming problem (QP) whose computational complexity becomes prohibitively expensive for large scale datasets. Traditional optimization methods cannot be directly applied in these cases, mainly due to memory restrictions. By adopting a slightly different objective function and under mild conditions on the kernel used within the model, efficient algorithms to train SVMs have been devised under the name of core vector machines (CVMs). This framework exploits the equivalence of the resulting learning problem with the task of building a minimal enclosing ball (MEB) problem in a feature space, where data is implicitly embedded by a kernel function. In this paper, we improve on the CVM approach by proposing two novel methods to build SVMs based on the Frank–Wolfe algorithm, recently revisited as a fast method to approximate the solution of a MEB problem. In contrast to CVMs, our algorithms do not require to compute the solutions of a sequence of increasingly complex QPs and are defined by using only analytic optimization steps. Experiments on a large collection of datasets show that our methods scale better than CVMs in most cases, sometimes at the price of a slightly lower accuracy. As CVMs, the proposed methods can be easily extended to machine learning problems other than binary classification. However, effective classifiers are also obtained using kernels which do not satisfy the condition required by CVMs, and thus our methods can be used for a wider set of problems.

APA, Harvard, Vancouver, ISO, and other styles

4

Migdalas, Athanasios. "A regularization of the Frank—Wolfe method and unification of certain nonlinear programming methods." Mathematical Programming 65, no. 1-3 (February 1994): 331–45. http://dx.doi.org/10.1007/bf01581701.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kherad, Mahdi, Hamed Vahdat-Nejad, and Morteza Araghi. "Trasfugen: Traffic assignment of urban network by an approximation fuzzy genetic algorithm." International Journal of Modeling, Simulation, and Scientific Computing 09, no. 04 (August 2018): 1850034. http://dx.doi.org/10.1142/s1793962318500344.

Full text

Abstract:

This paper proposes the Trasfugen method for traffic assignment aimed at solving the user equilibrium problem. To this end, the method makes use of a genetic algorithm. A fuzzy system is proposed for controlling the mutation and crossover rates of the genetic algorithm, and the corrective strategy is exploited for handling the equilibrium problem constraints. In the model, an approximation algorithm is proposed for obtaining the paths between the origin–destination pairs in the demand matrix. Unlike the traditional deterministic algorithm that has exponential time complexity, this approximation algorithm has polynomial time complexity and is executed much faster. Afterward, the Trasfugen method is applied to the urban network of Tehran metropolitan and the efficiency is investigated. Upon comparing the results obtained from the proposed model with those obtained from the conventional traffic assignment method, namely, the Frank–Wolfe method; it is shown that the proposed algorithm, while acting worse during the initial iterations, achieves better results in the subsequent iterations. Moreover, it prevents the occurrence of local optimal points as well as early/premature convergence, thus producing better results than the Frank–Wolfe algorithm.

APA, Harvard, Vancouver, ISO, and other styles

6

Chryssoverghi, I., A. Bacopoulos, B. Kokkinis, and J. Coletsos. "Mixed Frank–Wolfe Penalty Method with Applications to Nonconvex Optimal Control Problems." Journal of Optimization Theory and Applications 94, no. 2 (August 1997): 311–34. http://dx.doi.org/10.1023/a:1022631611812.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Xu, Jianhua, and Quan Ma. "Multi-label regularized quadratic programming feature selection algorithm with Frank–Wolfe method." Expert Systems with Applications 95 (April 2018): 14–31. http://dx.doi.org/10.1016/j.eswa.2017.11.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Tatineni, Maya, Henrik Edwards, and David Boyce. "Comparison of Disaggregate Simplicial Decomposition and Frank-Wolfe Algorithms for User-Optimal Route Choice." Transportation Research Record: Journal of the Transportation Research Board 1617, no. 1 (January 1998): 157–62. http://dx.doi.org/10.3141/1617-22.

Full text

Abstract:

The disaggregate simplicial decomposition (DSD) method has been posed as a better alternative to existing algorithms for solving the deterministic user-optimal route choice model. The application of the DSD algorithm is compared and evaluated with the commonly used Frank-Wolfe (FW) algorithm on a large network in the Chicago area. The results indicate that the DSD algorithm performs much better than the FW with respect to reaching the optimality conditions specified by the model.

APA, Harvard, Vancouver, ISO, and other styles

9

Nakamura, Kengo, Shinsaku Sakaue, and Norihito Yasuda. "Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 2200–2209. http://dx.doi.org/10.1609/aaai.v34i02.5596.

Full text

Abstract:

Computation of equilibria for congestion games has been an important research subject. In many realistic scenarios, each strategy of congestion games is given by a combination of elements that satisfies certain constraints; such games are called combinatorial congestion games. For example, given a road network with some toll roads, each strategy of routing games is a path (a combination of edges) whose total toll satisfies a certain budget constraint. Generally, given a ground set of n elements, the set of all such strategies, called the strategy set, can be large exponentially in n, and it often has complicated structures; these issues make equilibrium computation very hard. In this paper, we propose a practical algorithm for such hard equilibrium computation problems. We use data structures, called zero-suppressed binary decision diagrams (ZDDs), to compactly represent strategy sets, and we develop a Frank–Wolfe-style iterative equilibrium computation algorithm whose per-iteration complexity is linear in the size of the ZDD representation. We prove that an ϵ-approximate Wardrop equilibrium can be computed in O(poly(n)/ϵ) iterations, and we improve the result to O(poly(n) log ϵ−1) for some special cases. Experiments confirm the practical utility of our method.

APA, Harvard, Vancouver, ISO, and other styles

10

Kubentayeva, Meruza, and Alexander Gasnikov. "Finding Equilibria in the Traffic Assignment Problem with Primal-Dual Gradient Methods for Stable Dynamics Model and Beckmann Model." Mathematics 9, no. 11 (May 27, 2021): 1217. http://dx.doi.org/10.3390/math9111217.

Full text

Abstract:

In this paper, we consider the application of several gradient methods to the traffic assignment problem: we search equilibria in the stable dynamics model (Nesterov and De Palma, 2003) and the Beckmann model. Unlike the celebrated Frank–Wolfe algorithm widely used for the Beckmann model, these gradients methods solve the dual problem and then reconstruct a solution to the primal one. We deal with the universal gradient method, the universal method of similar triangles, and the method of weighted dual averages and estimate their complexity for the problem. Due to the primal-dual nature of these methods, we use a duality gap in a stopping criterion. In particular, we present a novel way to reconstruct admissible flows in the stable dynamics model, which provides us with a computable duality gap.

APA, Harvard, Vancouver, ISO, and other styles

11

Ali Al-Hawasy, Jamil A., and Eman H. Al-Rawdanee. "Numerical Solution for Classical Optimal Control Problem Governing by Hyperbolic Partial Differential Equation via Galerkin Finite Element-Implicit method with Gradient Projection Method." Ibn AL- Haitham Journal For Pure and Applied Science 32, no. 2 (May 20, 2019): 71. http://dx.doi.org/10.30526/32.2.2141.

Full text

Abstract:

This paper deals with the numerical solution of the discrete classical optimal control problem (DCOCP) governing by linear hyperbolic boundary value problem (LHBVP). The method which is used here consists of: the GFEIM " the Galerkin finite element method in space variable with the implicit finite difference method in time variable" to find the solution of the discrete state equation (DSE) and the solution of its corresponding discrete adjoint equation, where a discrete classical control (DCC) is given. The gradient projection method with either the Armijo method (GPARM) or with the optimal method (GPOSM) is used to solve the minimization problem which is obtained from the necessary condition for optimality of the DCOCP to find the DCC.An algorithm is given and a computer program is coded using the above methods to find the numerical solution of the DCOCP with step length of space variable , and step length of time variable . Illustration examples are given to explain the efficiency of these methods. The results show the methods which are used here are better than those obtained when we used the Gradient method (GM) or Frank Wolfe method (FWM) with Armijo step search method to solve the minimization problem.

APA, Harvard, Vancouver, ISO, and other styles

12

Freund, Robert M., Paul Grigas, and Rahul Mazumder. "An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion." SIAM Journal on Optimization 27, no. 1 (January 2017): 319–46. http://dx.doi.org/10.1137/15m104726x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Liuzzi, Giampaolo, and Francesco Rinaldi. "Solving $$\ell _0$$ ℓ 0 -penalized problems with simple constraints via the Frank–Wolfe reduced dimension method." Optimization Letters 9, no. 1 (June 6, 2014): 57–74. http://dx.doi.org/10.1007/s11590-014-0757-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Lin, Yu, Hongfei Jia, Bo Zou, Hongzhi Miao, Ruiyi Wu, Jingjing Tian, and Guanfeng Wang. "Multiobjective Environmentally Sustainable Optimal Design of Dedicated Connected Autonomous Vehicle Lanes." Sustainability 13, no. 6 (March 20, 2021): 3454. http://dx.doi.org/10.3390/su13063454.

Full text

Abstract:

The emergence of connected autonomous vehicles (CAVs) is not only improving the efficiency of transportation, but also providing new opportunities for the sustainable development of transportation. Taking advantage of the energy consumption of CAVs to promote the sustainable development of transportation has attracted extensive public attention in recent years. This paper develops a mathematical approach to investigating the problem of the optimal implementation of dedicated CAV lanes while simultaneously considering economic and environmental sustainability. Specifically, the problem is described as a multi-objective bi-level programming model, in which the upper level is to minimize the system-level costs including travel time costs, CAV lane construction cost, and emission cost, whereas the lower level characterizes the multi-class network equilibrium with a heterogeneous traffic stream consisting of both human-driven vehicle (HVs) and CAVs. To address the multi-objective dedicated CAV lane implement problem, we propose an integrated solution framework that integrates a non-dominated sorting genetic algorithm II (NSGA-II) algorithm, diagonalized algorithm, and Frank–Wolfe algorithm. The NSGA-II was adopted to solve the upper-level model, i.e., hunting for the optimal CAV lanes implementation schemes. The diagonalized Frank–Wolfe (DFW) algorithm is used to cope with multi-class network equilibrium. Finally, numerical experiments were conducted to demonstrate the effectiveness of the proposed model and solution method. The experimental results show that the total travel time cost, total emission cost, and total energy consumption were decreased by about 12.03%, 10.42%, and 9.4%, respectively, in the Nguyen–Dupuis network as a result of implementing the dedicated CAV lanes.

APA, Harvard, Vancouver, ISO, and other styles

15

Wu, Wen-Xiang, and Hai-Jun Huang. "A Path-Based Gradient Projection Algorithm for the Cost-Based System Optimum Problem in Networks with Continuously Distributed Value of Time." Journal of Applied Mathematics 2014 (2014): 1–9. http://dx.doi.org/10.1155/2014/271358.

Full text

Abstract:

The cost-based system optimum problem in networks with continuously distributed value of time is formulated as a path-based form, which cannot be solved by the Frank-Wolfe algorithm. In light of magnitude improvement in the availability of computer memory in recent years, path-based algorithms have been regarded as a viable approach for traffic assignment problems with reasonably large network sizes. We develop a path-based gradient projection algorithm for solving the cost-based system optimum model, based on Goldstein-Levitin-Polyak method which has been successfully applied to solve standard user equilibrium and system optimum problems. The Sioux Falls network tested is used to verify the effectiveness of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

16

Karakitsiou, A., and A. Migdalas. "Convex optimization problems in supply chain planning and their solution by a column generation method based on the Frank Wolfe method." Operational Research 16, no. 3 (October 13, 2015): 401–21. http://dx.doi.org/10.1007/s12351-015-0205-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Boland, Natashia, Jeffrey Christiansen, Brian Dandurand, Andrew Eberhard, Jeff Linderoth, James Luedtke, and Fabricio Oliveira. "Combining Progressive Hedging with a Frank--Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming." SIAM Journal on Optimization 28, no. 2 (January 2018): 1312–36. http://dx.doi.org/10.1137/16m1076290.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Macklin, Miles, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Zach Corse. "Local Optimization for Robust Signed Distance Field Collision." Proceedings of the ACM on Computer Graphics and Interactive Techniques 3, no. 1 (April 18, 2020): 1–17. http://dx.doi.org/10.1145/3384538.

Full text

Abstract:

Signed distance fields (SDFs) are a popular shape representation for collision detection. This is due to their query efficiency, and the ability to provide robust inside/outside information. Although it is straightforward to test points for interpenetration with an SDF, it is not clear how to extend this to continuous surfaces, such as triangle meshes. In this paper, we propose a per-element local optimization to find the closest points between the SDF isosurface and mesh elements. This allows us to generate accurate contact points between sharp point-face pairs, and handle smoothly varying edge-edge contact. We compare three numerical methods for solving the local optimization problem: projected gradient descent, Frank-Wolfe, and golden-section search. Finally, we demonstrate the applicability of our method to a wide range of scenarios including collision of simulated cloth, rigid bodies, and deformable solids.

APA, Harvard, Vancouver, ISO, and other styles

19

Rojo, Marta. "Evaluation of Traffic Assignment Models through Simulation." Sustainability 12, no. 14 (July 9, 2020): 5536. http://dx.doi.org/10.3390/su12145536.

Full text

Abstract:

Assignment methodologies attempt to determine the traffic flow over each network arc based on its characteristics and the total flow over the entire area. There are several methodologies—some fast and others that are more complex and require more time to complete the calculation. In this study, we evaluated different assignment methodologies using a computer simulation and tested the results in a specific case study. The results showed that the “all-or-nothing” methods and the incremental assignment methods generally yield results with an unacceptable level of error unless the traffic is divided into four or more equal parts. The method of successive averages (MSA) was valid starting from a relatively low number of iterations, while the user equilibrium methodologies (approximated using the Frank and Wolfe algorithm) were valid starting from an even lower number of iterations. These results may be useful to researchers in the field of computer simulation and planners who apply these methodologies in similar cases.

APA, Harvard, Vancouver, ISO, and other styles

20

Zhou, Yingliang, Qiwei Jiang, and Jin Qin. "Pre-Disaster Retrofit Decisions for Sustainable Transportation Systems in Urban Areas." Sustainability 11, no. 15 (July 26, 2019): 4044. http://dx.doi.org/10.3390/su11154044.

Full text

Abstract:

A transportation system is an important material base for implementing timely rescue and emergency evacuation after disasters in urban areas. In order to reduce disaster risks and develop sustainable transportation systems, it is important to improve their resilience and ensure their reliability. This paper mainly studies pre-disaster retrofit decisions for sustainable transportation systems in urban areas. As the optimization goal, pre-disaster retrofit costs and post-disaster restoration costs under constraints of post-disaster system connectivity, travel time reliability, and post-disaster link capacity are taken into account to construct a bi-level stochastic programming model. A method based on the simulated annealing algorithm and Frank–Wolfe algorithm is used to solve the problem. The case study shows that the calculation is quick, and the result is reasonable. The study result proves that the method proposed in this paper can provide an effective solution to such problems.

APA, Harvard, Vancouver, ISO, and other styles

21

Abohany, A. A., Rizk Masoud Rizk-Allah, Diana T. Mosa, and Aboul Ella Hassanien. "A Novel Approach for Solving a Fully Rough Multi-Level Quadratic Programming Problem and Its Application." International Journal of Service Science, Management, Engineering, and Technology 11, no. 4 (October 2020): 137–65. http://dx.doi.org/10.4018/ijssmet.2020100109.

Full text

Abstract:

The most widely used actions and decisions of the real-world tasks frequently appear as hierarchical systems. To deal with these systems, the multi-level programming problem presents the most flourished technique. However, practical situations involve some the impreciseness regarding some decisions and performances; RST provides a vital role by considering the lower and upper bounds of any aspect of uncertain decision. By preserving the advantages of it, in the present study, solving fully rough multi-level quadratic programming problems over the variables, parameters of the objective functions, and the constraints such as rough intervals are focused on. The proposed approach incorporates the interval method, slice-sum method, Frank and Wolfe algorithm, and the decomposition algorithm to reach optimal values as rough intervals. The proposed is validated by an illustrative example, and also environmental-economic power dispatch is investigated as a real application. Finally, the proposed approach is capable of handling the fully rough multi-level quadratic programming models.

APA, Harvard, Vancouver, ISO, and other styles

22

Futami, Futoshi, Zhenghang Cui, Issei Sato, and Masashi Sugiyama. "Bayesian Posterior Approximation via Greedy Particle Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 3606–13. http://dx.doi.org/10.1609/aaai.v33i01.33013606.

Full text

Abstract:

In Bayesian inference, the posterior distributions are difficult to obtain analytically for complex models such as neural networks. Variational inference usually uses a parametric distribution for approximation, from which we can easily draw samples. Recently discrete approximation by particles has attracted attention because of its high expression ability. An example is Stein variational gradient descent (SVGD), which iteratively optimizes particles. Although SVGD has been shown to be computationally efficient empirically, its theoretical properties have not been clarified yet and no finite sample bound of the convergence rate is known. Another example is the Stein points (SP) method, which minimizes kernelized Stein discrepancy directly. Althoughafinitesampleboundisassuredtheoretically, SP is computationally inefficient empirically, especially in high-dimensional problems. In this paper, we propose a novel method named maximum mean discrepancy minimization by the Frank-Wolfe algorithm (MMD-FW), which minimizes MMD in a greedy way by the FW algorithm. Our method is computationally efficient empirically and we show that its finite sample convergence bound is in a linear order in finite dimensions.

APA, Harvard, Vancouver, ISO, and other styles

23

Jovanovic, Uros, Elham Shayanfar, and Paul M. Schonfeld. "Selecting and Scheduling Link and Intersection Improvements in Urban Networks." Transportation Research Record: Journal of the Transportation Research Board 2672, no. 51 (May 22, 2018): 1–11. http://dx.doi.org/10.1177/0361198118758681.

Full text

Abstract:

Deciding which projects, alternatives or investments to implement is a complex and important problem not only in transportation engineering, but in management, operations research and economics. Projects are interrelated if their benefits or costs depend on which other projects are implemented. Furthermore, in the network development problem analyzed here, the timing of projects also affects the benefits and costs of other projects. This paper presents a method for optimizing the selection and scheduling of interrelated improvements in road networks that explicitly considers intersections. The Frank Wolfe algorithm, which is modified here to consider intersections, is used for evaluating network improvements as well as for traffic assignment. Intersections are modelled with pseudo-links whose delays are estimated with Akcelik’s generalized model. The objective is to minimize the present value of total costs (including user time) by determining which projects should be selected and when they should be completed. A genetic algorithm is used for optimizing the sequence and schedule of projects.

APA, Harvard, Vancouver, ISO, and other styles

24

Huang, Zhipeng, and Huimin Niu. "A Bilevel Programming Model to Optimize Train Operation Based on Satisfaction for an Intercity Rail Line." Discrete Dynamics in Nature and Society 2014 (2014): 1–7. http://dx.doi.org/10.1155/2014/432096.

Full text

Abstract:

The passenger travel demands for intercity rail lines fluctuate obviously during different time periods, which makes the rail departments unable to establish an even train operation scheme. This paper considers an optimization problem for train operations which respond to passenger travel demands of different periods in intercity rail lines. A satisfactory function of passenger travelling is proposed by means of analyzing the passengers’ travel choice behavior and correlative influencing factors. On this basis, the paper formulates a bilevel programming model which maximizes interests of railway enterprises and travelling satisfaction of each passenger. The trains operation in different periods can be optimized through upper layer planning of the model, while considering the passenger flow distribution problem based on the Wardrop user equilibrium principle in the lower layer planning. Then, a genetic algorithm is designed according to model features for solving the upper laying. The Frank-Wolfe algorithm is used for solving the lower layer planning. Finally, a numerical example is provided to demonstrate the application of the method proposed in this paper.

APA, Harvard, Vancouver, ISO, and other styles

25

Li, Mao-sheng, and He-lai Huang. "Road-safety recognition and network equilibrium with perceived route-choice sets." Transportation Safety and Environment 1, no. 2 (November 1, 2019): 126–34. http://dx.doi.org/10.1093/tse/tdz009.

Full text

Abstract:

Abstract Safety is regarded as the second basic need in Maslow’s hierarchy of needs (1943), and safety recognition and circumvention behaviour in the route-choice decision-making process should therefore be accommodated in network-traffic equilibrium analysis frameworks. This paper proposes a framework by which crash frequency, forecasted using the safety-analysis method or compiled from historical data for intersections, is used to measure the safety consciousness of drivers. Drivers are then classified into different groups according to their acceptable-risk thresholds, and each group has its own route-choice set. Decision behaviour whereby drivers are willing to bear additional costs in order to circumvent travel risk is incorporated into the variational inequality model based on the user equilibrium in the perceived route-choice set (UE-PRCS), which is an extension of Wardrop’s first principle. The Frank–Wolfe algorithm, based on the convex combination method, is employed to obtain the solution. A small road network is used as a case study to illustrate the proposed framework, incorporating risk recognition and circumvention behaviour under different combinations of traffic demand and risk-sensitivity group ratio. The results show that the standard user equilibrium is a special case of the UE-PRCS, but that the UE traffic state is more common than the UE-PRCS under different parameters.

APA, Harvard, Vancouver, ISO, and other styles

26

Sun, Carlos, R. Jayakrishnan, and Wei K. Tsai. "Computational Study of a Path-Based Algorithm and Its Variants for Static Traffic Assignment." Transportation Research Record: Journal of the Transportation Research Board 1537, no. 1 (January 1996): 106–15. http://dx.doi.org/10.1177/0361198196153700115.

Full text

Abstract:

Recent research has indicated that advances in computer memory have made the use of path-based algorithms in urban traffic networks a possibility. The path-based gradient projection (GP) offers significant benefits in computation times over the conventional Frank-Wolfe algorithm and may be especially suited for real-time applications. The computational results from applying GP to networks of up to 4,900 nodes, as well as the performance of different variants of GP, are discussed. Also discussed is the sensitivity of the results to parameters such as the number of destinations and the level of congestion. The variants of the basic GP algorithm examined are intended to further improve the per-iteration performance of the algorithm for larger networks. These variants include a GP version with a modified first derivative update and different versions that use line-search techniques, including a boundary stopping method. The results establish that GP indicates substantial benefits even for larger networks. The modifications, while they do improve the computation times per GP iteration, affect the convergence quality of the algorithm, indicating that the earlier GP algorithm is a better alternative for both large and small networks.

APA, Harvard, Vancouver, ISO, and other styles

27

Jagabathula, Srikanth, Lakshminarayanan Subramanian, and Ashwin Venkataraman. "A Conditional Gradient Approach for Nonparametric Estimation of Mixing Distributions." Management Science 66, no. 8 (August 2020): 3635–56. http://dx.doi.org/10.1287/mnsc.2019.3373.

Full text

Abstract:

Mixture models are versatile tools that are used extensively in many fields, including operations, marketing, and econometrics. The main challenge in estimating mixture models is that the mixing distribution is often unknown, and imposing a priori parametric assumptions can lead to model misspecification issues. In this paper, we propose a new methodology for nonparametric estimation of the mixing distribution of a mixture of logit models. We formulate the likelihood-based estimation problem as a constrained convex program and apply the conditional gradient (also known as Frank–Wolfe) algorithm to solve this convex program. We show that our method iteratively generates the support of the mixing distribution and the mixing proportions. Theoretically, we establish the sublinear convergence rate of our estimator and characterize the structure of the recovered mixing distribution. Empirically, we test our approach on real-world datasets. We show that it outperforms the standard expectation-maximization (EM) benchmark on speed (16 times faster), in-sample fit (up to 24% reduction in the log-likelihood loss), and predictive (average 28% reduction in standard error metrics) and decision accuracies (extracts around 23% more revenue). On synthetic data, we show that our estimator is robust to different ground-truth mixing distributions and can also account for endogeneity. This paper was accepted by Serguei Netessine, operations management.

APA, Harvard, Vancouver, ISO, and other styles

28

Huang, Zhipeng, Huimin Niu, Ruhu Gao, Haoyu Fan, and Chenglin Liu. "Optimizing Train Timetable Based on Departure Time Preference of Passengers for High-Speed Rails." Journal of Advanced Transportation 2021 (March 9, 2021): 1–20. http://dx.doi.org/10.1155/2021/6611289.

Full text

Abstract:

Passengers would like to choose the most suitable train based on their travel preferences, expenses, and train timetable in the high-speed railway corridor. Meanwhile, the railway department will constantly adjust the train timetable according to the distribution of passenger flows during a day to achieve the optimal operation cost and energy consumption saving plan. The question is how to meet the differential travel needs of passengers and achieve sustainable goals of service providers. Therefore, it is necessary to design a demand-oriented and environment-friendly high-speed railway timetable. This paper formulates the optimization of train timetable for a given high-speed railway corridor, which is based on the interests of both passengers and transportation department. In particular, a traveling time-space network with virtual departure arc is constructed to analyze generalized travel costs of passengers of each origin-destination (OD), and bilevel programming model is used to optimize the problem. The upper integer programming model regards the minimization of the operating cost, which is simplified to the minimum traveling time of total trains, as the goal. The lower level is a user equilibrium model which arranges each OD passenger flow to different trains. A general advanced metaheuristic algorithm embedded with the Frank–Wolfe method is designed to implement the bilevel programming model. Finally, a real-world numerical experiment is conducted to verify the effectiveness of both the model and the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

29

Almotahari, Amirmasoud, and Anil Yazici. "Practice Friendly Metric for Identification of Critical Links in Road Networks." Transportation Research Record: Journal of the Transportation Research Board 2674, no. 8 (June 23, 2020): 219–29. http://dx.doi.org/10.1177/0361198120925475.

Full text

Abstract:

Despite the important planning value of transportation link criticality, the existing methodologies are mostly in the academic domain, and require in-depth technical skills and extensive data. The most common approach to identify critical links in transportation networks is to remove each link iteratively, conduct traffic assignment, and assess the criticality of each link based on the consequences of its removal. Since conducting multiple traffic assignment is costly for large networks, the authors of this paper recently introduced the link criticality index (LCI). The LCI utilizes the iterations in the Frank–Wolfe solution of the user equilibrium (UE) problem to provide link criticality ranking within a single traffic assignment. The LCI was shown to provide balanced rankings with respect to alternative routes as well as the link flows. However, the LCI is not practice-friendly because of the technical knowledge and data needed to run traffic assignments. Accordingly, this paper introduces a practice friendly link criticality index (PF-LCI). PF-LCI relaxes some of the technical requirements and uses some expert knowledge input data to provide “top” link criticality rankings that are consistent with the LCI. PF-LCI utilizes the network flow instances at different times of day instead of iterations of UE assignment solution. Expert knowledge input is sought for the major origin–destination pairs (ODs) and the viable routes between the selected ODs. The method is implemented on a small sample network and the Sioux Falls network to test PF-LCI’s capabilities. Results show that PF-LCI produces accurate rankings for the top critical links that are most relevant to practitioners’ concerns.

APA, Harvard, Vancouver, ISO, and other styles

30

Mu, Cun, Yuqian Zhang, John Wright, and Donald Goldfarb. "Scalable Robust Matrix Recovery: Frank--Wolfe Meets Proximal Methods." SIAM Journal on Scientific Computing 38, no. 5 (January 2016): A3291—A3317. http://dx.doi.org/10.1137/15m101628x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Frandi, Emanuele, Ricardo Ñanculef, Stefano Lodi, Claudio Sartori, and Johan A. K. Suykens. "Fast and scalable Lasso via stochastic Frank–Wolfe methods with a convergence guarantee." Machine Learning 104, no. 2-3 (July 21, 2016): 195–221. http://dx.doi.org/10.1007/s10994-016-5578-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Mitradjieva, Maria, and Per Olov Lindberg. "The Stiff Is Moving—Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment*." Transportation Science 47, no. 2 (May 2013): 280–93. http://dx.doi.org/10.1287/trsc.1120.0409.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Bomze, Immanuel M., Francesco Rinaldi, and Samuel Rota Bulò. "First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants." SIAM Journal on Optimization 29, no. 3 (January 2019): 2211–26. http://dx.doi.org/10.1137/18m1206953.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Al-Hawasy, J. A., and E. H. Al-Rawdanee. "Mixed Penalty with Gradient, Gradient Projection and Frank Wolfe Methods for Solving Nonlinear Hyperbolic Optimal Control Sate Constraints." Journal of Physics: Conference Series 1804, no. 1 (February 1, 2021): 012033. http://dx.doi.org/10.1088/1742-6596/1804/1/012033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Bomze, Immanuel M., Francesco Rinaldi, and Damiano Zeffiro. "Frank–Wolfe and friends: a journey into projection-free first-order optimization methods." 4OR, September 6, 2021. http://dx.doi.org/10.1007/s10288-021-00493-y.

Full text

Abstract:

AbstractInvented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank–Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility and applicability in a wide range of contexts, combined with an account on recent progress in variants, improving on both the speed and efficiency of this surprisingly simple principle of first-order optimization.

APA, Harvard, Vancouver, ISO, and other styles

36

Al-Hawasy, Jamil A. Ali, and Eman H. Mukhalef Al-Rawdanee. "Numerical Solutions for the Optimal Control Governing by Variable Coefficients Nonlinear Hyperbolic Boundary Value Problem Using the Gradient Projection, Gradient and Frank Wolfe Methods." Iraqi Journal of Science, May 17, 2020, 161–69. http://dx.doi.org/10.24996/ijs.2020.si.1.21.

Full text

Abstract:

This paper is concerned with studying the numerical solution for the discrete classical optimal control problem (NSDCOCP) governed by a variable coefficients nonlinear hyperbolic boundary value problem (VCNLHBVP). The DSCOCP is solved by using the Galerkin finite element method (GFEM) for the space variable and implicit finite difference scheme (GFEM-IFDS) for the time variable to get the NS for the discrete weak form (DWF) and for the discrete adjoint weak form (DSAWF) While, the gradient projection method (GRPM), also called the gradient method (GRM), or the Frank Wolfe method (FRM) are used to minimize the discrete cost function (DCF) to find the DSCOC. Within these three methods, the Armijo step option (ARMSO) or the optimal step option (OPSO) are used to improve the discrete classical control (DSCC). Finally, some illustrative examples for the problem are given to show the accuracy and efficiency of the methods.

APA, Harvard, Vancouver, ISO, and other styles

37

Al-Rawdanee, Eman H. Mukhalef, and Jamil A. Ali Al-Hawasy Al-Hawasy. "Mixed Implicit Galerkin – Frank Wolf, Gradient and Gradient Projection Methods for Solving Classical Optimal Control Problem Governed by Variable Coefficients, Linear Hyperbolic, Boundary Value Problem." Iraqi Journal of Science, September 29, 2020, 2303–14. http://dx.doi.org/10.24996/ijs.2020.61.9.17.

Full text

Abstract:

This paper deals with testing a numerical solution for the discrete classical optimal control problem governed by a linear hyperbolic boundary value problem with variable coefficients. When the discrete classical control is fixed, the proof of the existence and uniqueness theorem for the discrete solution of the discrete weak form is achieved. The existence theorem for the discrete classical optimal control and the necessary conditions for optimality of the problem are proved under suitable assumptions. The discrete classical optimal control problem (DCOCP) is solved by using the mixed Galerkin finite element method to find the solution of the discrete weak form (discrete state). Also, it is used to find the solution for the discrete adjoint weak form (discrete adjoint) with the Gradient Projection method (GPM) , the Gradient method (GM), or the Frank Wolfe method (FWM) to the DCOCP. Within each of these three methods, the Armijo step option (ARSO) or the optimal step option (OPSO) is used to improve (to accelerate the step) the solution of the discrete classical control problem. Finally, some illustrative numerical examples for the considered discrete control problem are provided. The results show that the GPM with ARSO method is better than GM or FWM with ARSO methods. On the other hand, the results show that the GPM and GM with OPSO methods are better than the FWM with the OPSO method.

APA, Harvard, Vancouver, ISO, and other styles

38

Guo, Jiahong, Huiling Liu, and Xiantao Xiao. "A unified analysis of stochastic gradient‐free Frank–Wolfe methods." International Transactions in Operational Research, October 27, 2020. http://dx.doi.org/10.1111/itor.12889.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Frank-Wolfe Method'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles