| 1. |
- Daneva (Mitradjieva), Maria, et al.
(författare)
-
A Comparison of Feasible Direction Methods for the Stochastic Transportation Problem
- 2010
-
Ingår i: Computational optimization and applications. - : Springer Science and Business Media LLC. - 0926-6003 .- 1573-2894. ; 46:3, s. 451-466
-
Tidskriftsartikel (refereegranskat)abstract
- The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.
|
|
| 2. |
- Larsson, Torbjörn, et al.
(författare)
-
A generic column generation principle: derivation and convergence analysis
- 2015
-
Ingår i: Operational Research. - : Springer Science and Business Media LLC. - 1109-2858 .- 1866-1505. ; 15:2, s. 163-198
-
Tidskriftsartikel (refereegranskat)abstract
- Given a non-empty, compact and convex set, and an a priori definedcondition which each element either satisfies or not, we want to find an elementbelonging to the former category. This is a fundamental problem of mathematicalprogramming which encompasses nonlinear programs, variational inequalities,saddle-point problems. We present a conceptual column generation scheme, whichalternates between solving a restriction of the original problem and a columngeneration phase which is used to augment the restricted problems. We establishgeneral applicability of the conceptual method, as well as to the three problemclasses mentioned. We also establish a version of the conceptual method in whichthe restricted and column generation problems are allowed to be solvedproximately, and of a version allowing for the dropping of columns. We showsome solution methods (e.g., Dantzig–Wolfe decomposition and simplicialcomposition) are special instances, and present new convergent column generationmethods in nonlinear programming, such as a sequential linear programming typemethod. Along the way, we also relate our quite general scheme in nonlinearprogramming presented in this paper with several other classic, and more recent,iterative methods in nonlinear optimization.
|
|
| 3. |
- Larsson, Torbjörn, et al.
(författare)
-
Convergent Lagrangian heuristics for nonlinear minimum cost network flows
- 2008
-
Ingår i: European Journal of Operational Research. - : Elsevier BV. - 0377-2217 .- 1872-6860. ; 189:2, s. 324-346
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector, this is referred to as "early primal recovery". It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme, such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable, in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes. © 2007 Elsevier B.V. All rights reserved.
|
|
| 4. |
- Larsson, Torbjörn, et al.
(författare)
-
Ergodic convergence in subgradient optimization - with application to simplicial decomposition of convex programs
- 2012
-
Ingår i: Contemporary Mathematics. - Providence, Rhode Island : American Mathematical Society. - 0271-4132 .- 1098-3627. ; 568, s. 159-186
-
Tidskriftsartikel (refereegranskat)abstract
- When non-smooth, convex minimization problems are solved by subgradient optimization methods, the subgradients used will in general not accumulate to subgradients that verify the optimality of a solution obtained in the limit. It is therefore not a straightforward task to monitor the progress of subgradient methods in terms of the approximate fulfilment of optimality conditions. Further, certain supplementary information, such as convergent estimates of Lagrange multipliers and convergent lower bounds on the optimal objective value, is not directly available in subgradient schemes. As a means of overcoming these weaknesses in subgradient methods, we introduced in LPS96b, LPS96c, and LPS98 the computation of an ergodic (averaged) sequence of subgradients. Specifically, we considered a non-smooth, convex program solved by a conditional subgradient optimization scheme with divergent series step lengths, and showed that the elements of the ergodic sequence of subgradients in the limit fulfil the optimality conditions at the optimal solution, to which the sequence of iterates converges. This result has three important implications. The first is the finite identification of active constraints at the solution obtained in the limit. The second is the establishment of the convergence of ergodic sequences of Lagrange multipliers; this result enables sensitivity analyses for solutions obtained by subgradient methods. The third is the convergence of a lower bounding procedure based on an ergodic sequence of affine underestimates of the objective function; this procedure also provides a proper termination criterion for subgradient optimization methods. This article contributes first an overview of results and applications found in LPS96b, LPS96c, and LPS98 pertaining to the generation of ergodic sequences of subgradients generated within a subgradient scheme. It then presents an application of these results to that of the first instance of a simplicial decomposition algorithm for convex and non-smooth optimization problems.
|
|
| 5. |
- Larsson, Torbjörn, et al.
(författare)
-
Subben's checklist and the quality of articles in OR
- 2014
-
Ingår i: ORbit. ; :23, s. 6-7
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- This short article presents two itemed lists that may be a helping hand during the assessment of a scientific article in the field of mathematical optimization/operations research, be it your own, a Master's or PhD student's, or even a paper that you are refereeing for a journal or a conference. The first list (“Subben’s checklist”) describes necessary ingredients of a complete article, while the second list provides criteria for assessing the quality/scientific value of an article.
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
|
|
| 9. |
|
|
| 10. |
|
|
