liu.seSearch for publications in DiVA
Change search
Refine search result
12 1 - 50 of 71
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
    Global search strategies for solving multilinear least-squares problems2012In: Sultan Qaboos University Journal for Science, ISSN 1027-524X, Vol. 17, no 1, p. 12-21Article in journal (Refereed)
    Abstract [en]

    The multilinear least-squares (MLLS) problem is an extension of the linear leastsquares problem. The difference is that a multilinear operator is used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows for moving from one local minimizer to a better one. The efficiency of this strategy is illustrated by results of numerical experiments performed for some problems related to the design of filter networks.

  • 2.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Global Search Strategies for Solving Multilinear Least-squares Problems2011Report (Other academic)
    Abstract [en]

    The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinearoperator is used in place of a matrix-vector product. The MLLS istypically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows formoving from one local minimizer to a better one. The efficiencyof this strategy isillustrated by results of numerical experiments performed forsome problems related to the design of filter networks.

  • 3.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Sparsity Optimization in Design of Multidimensional Filter Networks2013Report (Other academic)
    Abstract [en]

    Filter networks is a powerful tool used for reducing the image processing time, while maintaining its reasonably high quality.They are composed of sparse sub-filters whose low sparsity ensures fast image processing.The filter network design is related to solvinga sparse optimization problem where a cardinality constraint bounds above the sparsity level.In the case of sequentially connected sub-filters, which is the simplest network structure of those considered in this paper, a cardinality-constrained multilinear least-squares (MLLS) problem is to be solved. If to disregard the cardinality constraint, the MLLS is typically a large-scale problem characterized by a large number of local minimizers. Each of the local minimizers is singular and non-isolated.The cardinality constraint makes the problem even more difficult to solve.An approach for approximately solving the cardinality-constrained MLLS problem is presented.It is then applied to solving a bi-criteria optimization problem in which both thetime and quality of image processing are optimized. The developed approach is extended to designing filter networks of a more general structure. Its efficiency is demonstrated by designing certain 2D and 3D filter networks. It is also compared with the existing approaches.

  • 4.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology. Linköping University, Center for Medical Image Science and Visualization (CMIV).
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Sparsity Optimization in Design of Multidimensional Filter Networks2015In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 16, no 2, p. 259-277Article in journal (Refereed)
    Abstract [en]

    Filter networks are used as a powerful tool used for reducing the image processing time and maintaining high image quality.They are composed of sparse sub-filters whose high sparsity ensures fast image processing.The filter network design is related to solvinga sparse optimization problem where a cardinality constraint bounds above the sparsity level.In the case of sequentially connected sub-filters, which is the simplest network structure of those considered in this paper, a cardinality-constrained multilinear least-squares (MLLS) problem is to be solved. Even when disregarding the cardinality constraint, the MLLS is typically a large-scale problem characterized by a large number of local minimizers, each of which is singular and non-isolated.The cardinality constraint makes the problem even more difficult to solve.

    An approach for approximately solving the cardinality-constrained MLLS problem is presented.It is then applied to solving a bi-criteria optimization problem in which both thetime and quality of image processing are optimized. The developed approach is extended to designing filter networks of a more general structure. Its efficiency is demonstrated by designing certain 2D and 3D filter networks. It is also compared with the existing approaches.

  • 5.
    Brust, Johannes
    et al.
    University of California, Merced, CA, USA.
    Burdakov, Oleg
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Erway, Jennifer B.
    Wake Forest University, Winston-Salem, NC, USA.
    Marcia, Roummel F.
    University of California, Merced, CA, USA.
    Dense Initializations for Limited-Memory Quasi-Newton MethodsManuscript (preprint) (Other academic)
    Abstract [en]

    We consider a family of dense initializations for  limited-memory quasi-Newton methods.  The proposed initialization  uses two parameters to approximate the curvature of the Hessian in  two complementary subspaces.  This family of dense  initializations is proposed in the context of   a limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS)   trust-region method that makes use of a shape-changing norm to  define each subproblem. As with L-BFGS methods that traditionally  use diagonal initialization, the dense initialization and the  sequence of generated quasi-Newton matrices are never explicitly  formed.  Numerical experiments on the CUTEst test set suggest that  this initialization together with the shape-changing trust-region  method outperforms other L-BFGS  methods for solving general nonconvex unconstrained optimization  problems.  While this dense initialization is proposed in the  context of a special trust-region method, it has broad applications  for more general quasi-Newton trust-region and line search methods.  In fact, this initialization is suitable for use with any  quasi-Newton update that admits a compact representation and, in  particular, any member of the Broyden class of updates.

  • 6.
    Brust, Johannes
    et al.
    Applied Mathematics, University of California, Merced, USA.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Erway, Jennifer B.
    Department of Mathematics, Wake Forest University, USA.
    Marcia, Roummel F.
    Applied Mathematics, University of California, Merced, USA.
    Yuan, Ya-xiang
    State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, AMSS, CAS, Beijing, China.
    Shape-Changing L-SR1 Trust-Region Methods2016Report (Other academic)
    Abstract [en]

    In this article, we propose a method for solving the trust-region subproblem when a limited-memory symmetric rank-one matrix is used in place of the true Hessian matrix. The method takes advantage of two shape-changing norms to decompose the trust-region subproblem into two separate problems, one of which has a closed-form solution and the other one is easy to solve. Sufficient conditions for global solutions to both subproblems are given. The proposed solver makes use of the structure of limited-memory symmetric rank-one matrices to find solutions that satisfy these optimality conditions. Solutions to the trust-region subproblem are computed to high-accuracy even in the so-called "hard case".

  • 7.
    Burdakov, Oleg
    Parallel Algorithms Team, CERFACS, Toulouse Cedex, France.
    A greedy algorithm for the optimal basis problem1997In: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 37, no 3, p. 591-599Article in journal (Refereed)
    Abstract [en]

    The following problem is considered. Given m+1 points {x i }0 m in R n which generate an m-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form x i x j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrix f′ of a nonlinear mappingf by using values off computed at m+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination of m pairs {x i ,x j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm in O(m 2) time. The complexity of this reduction is equivalent to one m×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is below O(n 2.376) for m=n. Applications of the algorithm to interpolation methods are discussed.

  • 8.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Component-wise quasi-Newton methods1991In: Numerical methods of nonlinear programming and their implementations / [ed] C. Richter, H. Hollatz and D. Pallaschke, Berlin: Akademie Verlag, 1991, p. 17-27Chapter in book (Other academic)
  • 9.
    Burdakov, Oleg
    Computing Center, USSR Academy of Sciences, Moscow.
    Conjugate direction methods for solving systems of equations and finding saddle points. Part 11982In: Engineering Cybernetics, ISSN 0013-788X, Vol. 20, no 3, p. 13-19Article in journal (Refereed)
    Abstract [en]

    This article is devoted to the development of methods of pseudo-orthogonal directions for solving systems of nonlinear equations in which the mapping is uniformly monotonic. Rapidly convergent methods that do not involve evaluation of derivatives are constructed. They constitute a generalization of such methods of unconditional minimization as the method of parallel displacements, Zangwill's method, and Powell's method. The methods developed can be applied, in particular, to finding saddle points of uniformly convex-concave functions.

  • 10.
    Burdakov, Oleg
    Computing Center, USSR Academy of Sciences, Moscow.
    Conjugate direction methods for solving systems of equations and finding saddle points. Part 21982In: Engineering Cybernetics, ISSN 0013-788X, Vol. 20, no 4, p. 23-31Article in journal (Refereed)
    Abstract [en]

    This article is the second part of a paper devoted to the development of methods of pseudo-orthogonal directions for solving systems of nonlinear equations (for part I see Eng. Cybern. 1982, Vol. 20, No. 3, p. 13-19). An approach is developed for studying the reate of convergence of such methods. Local quadratic convergence of the proposed methods to the solution of the system of equations is proven. This implies the quadratic convergence of some methods of unconstrained minimization: the method of parallel displacements, Zangull's method, and Powell's method.

  • 11.
    Burdakov, Oleg
    Computing Center, USSR Academy of Sciences, Moscow.
    Methods of the secant type for systems of equations with symmetric Jacobian matrix1983In: Numerical Functional Analysis and Optimization, ISSN 0163-0563, E-ISSN 1532-2467, Vol. 6, no 2, p. 183-195Article in journal (Refereed)
    Abstract [en]

    Symmetric methods (SS methods) of the secant type are proposed for systems of equations with symmetric Jacobian matrix. The SSI and SS2 methods generate sequences of symmetric matrices J and H which approximate the Jacobian matrix and inverse one, respectively. Rank-two quasi-Newton formulas for updating J and H are derived. The structure of the approximations J and H is better than the structure of the corresponding approximations in the traditional secant method because the SS methods take into account symmetry of the Jacobian matrix. Furthermore, the new methods retain the main properties of the traditional secant method, namely, J and H-1are consistent approximations to the Jacobian matrix; the SS methods converge superlinearly; the sequential (n + 1)-point SS methods have the R-order at least equal to the positive root of tn+1-tn-1=0.

  • 12.
    Burdakov, Oleg
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    On Limited Memory Methods with Shape Changing Trust Region2003In: The 18th International Symposium on Mathematical Programming,2003, 2003Conference paper (Other academic)
  • 13.
    Burdakov, Oleg
    Parallel Algorithms Group, CERFACS, Toulouse, France.
    On properties of Newton's method for smooth and nonsmooth equations1995In: Recent Trends in Optimization Theory and Applications / [ed] R.P. Agarwal, World Scientific, 1995, p. 17-24Chapter in book (Other academic)
    Abstract [en]

    Variational inequalities, nonlinear programming, complementarity problems and other problems can be reduced to nonsmooth equations, for which some generalizations of Newton's method are known. The Newton path, as a natural generalization of the Newton direction, was suggested by D.Ralph for enlarging the convergence region (globalization) of Newton-Robinson's method in the nonsmooth case. We investigate some properties of both the Newton direction and the Newton path, which seem to be basic for various globalization strategies. In particular, a simple formula for the derivative of an arbitrary norm of residuals along the Newton direction,derived earlier by the author for the smooth equations, is generalizedhere for the derivative along the Newton path.

  • 14.
    Burdakov, Oleg
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    On solving saddle point problems and monotone equations2018In: IX Moscow International Conference on Operations Research (ORM2018). Moscow, October 22-27, 2018. Proceedings, Volume 1 / [ed] A.A. Vasin and A.F. Izmailov, Moscow, 2018, Vol. 1, p. 47-50Conference paper (Refereed)
  • 15.
    Burdakov, Oleg
    Computing Center of the USSR Academy of Sciences, Moscow.
    On Superlinear Convergence of Some Stable Variants of the Secant Method1986In: Zeitschrift für angewandte Mathematik und Mechanik, ISSN 0044-2267, E-ISSN 1521-4001, Vol. 66, no 2, p. 615-622Article in journal (Refereed)
    Abstract [en]

    In a recent author's paper four classes of methods of the secant type for solving systems of nonlinear equations were proposed. They are stable with respect to linear dependence of the search directions. If the Jacobian matrix is symmetric, then two of them take into account this property. It is proved here that some four special methods from the classes converge superlinearly.

  • 16.
    Burdakov, Oleg
    CERFACS, Parallel Algorithms Team, Toulouse, France.
    On using the minimum spanning tree algorithm for optimal secant approximation of derivatives1996In: Zeitschrift für angewandte Mathematik und Mechanik, ISSN 0044-2267, E-ISSN 1521-4001, Vol. 76, no S3, p. 389-390Article in journal (Refereed)
    Abstract [en]

    The following problem is considered. Given m + 1 points {xi}0m in Rn which generate an m-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form xi - xj. This problem is present in, e.g., stable variants of the secant method, where it is required to approximate the Jacobian matrix f' of a nonlinear mapping f by using values off computed at m + 1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider a functional which is maximized to find an optimal combination of m pairs {xi, xj}. We show that the problem is not of combinatorial complexity but can be reduced to the minimum spanning tree (MST) problem, which is solved by an MST-type algorithm in O(m2n) time.

  • 17.
    Burdakov, Oleg
    Computing Center, USSR Academy of Sciences, Moscow.
    Some globally convergent modifications of Newton's method for solving systems of nonlinear equations1980In: Soviet mathematics - Doklady, ISSN 0197-6788, Vol. 22, no 2, p. 376-378Article in journal (Refereed)
  • 18.
    Burdakov, Oleg
    Computing Center of the USSR Academy of Sciences, Moscow .
    Stable symmetric secant methods with restart1991In: Cybernetics and Systems Analysis, ISSN 1060-0396, E-ISSN 1573-8337, Vol. 27, no 3, p. 390-396Article in journal (Refereed)
    Abstract [en]

    Two secant type methods are proposed for solving systems of nonlinear equations with a symmetrical Jacobi matrix. Quasi-Newton rank-two updating formulas are used. Stability and superlinear convergence are proved.

  • 19.
    Burdakov, Oleg
    Computing Center, USSR Academy of Sciences, Moscow.
    Stable versions of the secants method for solving systems of equations1983In: Computational Mathematics and Mathematical Physics, ISSN 0965-5425, E-ISSN 1555-6662, Vol. 23, no 5, p. 1-10Article in journal (Refereed)
    Abstract [en]

    An interpretation of quasi-Newton methods of solving sets of equations is given, and provides the basis of four versions of the secantsmethod, stable with respect to a linear dependence of the directions of motion. The first version involves an approximation of the matrix of first derivatives (the Jacobi matrix), and the second an approximation of the inverse Jacobi matrix. The other two versions are aimed at solving sets of equations with symmetric Jacobi matrix. The stability of the versions is proved.

  • 20.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Positioning Unmanned Aerial Vehicles As Communication Relays for Surveillance Tasks2010In: Robotics: Science and Systems V / [ed] Jeff Trinkle, Yoky Matsuoka, Jose Castellanos, MIT Press, 2010, p. 257-264Conference paper (Refereed)
    Abstract [en]

    When unmanned aerial vehicles (UAVs) are used to survey distant targets, it is important to transmit sensor information back to a base station. As this communication often requires high uninterrupted bandwidth, the surveying UAV often needs afree line-of-sight to the base station, which can be problematic in urban or mountainous areas. Communication ranges may also belimited, especially for smaller UAVs. Though both problems can be solved through the use of relay chains consisting of one or more intermediate relay UAVs, this leads to a new problem: Where should relays be placed for optimum performance? We present two new algorithms capable of generating such relay chains, one being a dual ascent algorithm and the other a modification of the Bellman-Ford algorithm. As the priorities between the numberof hops in the relay chain and the cost of the chain may vary, wecalculate chains of different lengths and costs and let the ground operator choose between them. Several different formulations for edge costs are presented. In our test cases, both algorithms are substantially faster than an optimized version of the original Bellman-Ford algorithm, which is used for comparison.

  • 21.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Relay Positioning for Unmanned Aerial Vehicle Surveillance2010In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 29, no 8, p. 1069-1087Article in journal (Refereed)
    Abstract [en]

    When unmanned aerial vehicles (UAVs) are used for surveillance, information must often be transmitted to a base station in real time. However, limited communication ranges and the common requirement of free line of sight may make direct transmissions from distant targets impossible. This problem can be solved using relay chains consisting of one or more intermediate relay UAVs. This leads to the problem of positioning such relays given known obstacles, while taking into account a possibly mission-specific quality measure. The maximum quality of a chain may depend strongly on the number of UAVs allocated. Therefore, it is desirable to either generate a chain of maximum quality given the available UAVs or allow a choice from a spectrum of Pareto-optimal chains corresponding to different trade-offs between the number of UAVs used and the resulting quality. In this article, we define several problem variations in a continuous three-dimensional setting. We show how sets of Pareto-optimal chains can be generated using graph search and present a new label-correcting algorithm generating such chains significantly more efficiently than the best-known algorithms in the literature. Finally, we present a new dual ascent algorithm with better performance for certain tasks and situations.

  • 22.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Optimal placement of UV-based communications relay nodes2010In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 48, no 4, p. 511-531Article in journal (Refereed)
    Abstract [en]

    We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.

  • 23.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Report (Other academic)
    Abstract [en]

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.   For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed ecient label correcting algorithms.   The presented approach is applied to nding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The eciency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

  • 24.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014In: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, p. 26-50Conference paper (Refereed)
    Abstract [en]

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed efficient label correcting algorithms.The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

  • 25.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Optimal Scheduling for Replacing Perimeter Guarding Unmanned Aerial Vehicles2014Report (Other academic)
    Abstract [en]

    Guarding the perimeter of an area in order to detect potential intruders is an important task in a variety of security-related applications. This task can in many circumstances be performed by a set of camera-equipped unmanned aerial vehicles (UAVs). Such UAVs will occasionally require refueling or recharging, in which case they must temporarily be replaced by other UAVs in order to maintain complete surveillance of the perimeter. In this paper we consider the problem of scheduling such replacements. We present optimal replacement strategies and justify their optimality.

  • 26.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Felgenhauer, Ursula
    Brandenburg University of Technology, Germany.
    Stable multi-point secant methods with released requirements to point's position1994In: System Modelling and Optimization: proceedings of the 16th IFIP-TC7 conference, Compiègne, France-July 5-9, 1993 / [ed] J. Henry and J.-P. Yvon, London/Berlin: Springer, 1994, p. 225-236Chapter in book (Other academic)
  • 27.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Gong, Lujin
    Samsung Advanced Institute of Technology, China Lab, Beijing, China.
    Yuan, Ya-Xiang
    State Key Laboratory of Scientic and Engineering Computing, Institute of Computational.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    On Efficiently Combining Limited Memory and Trust-Region Techniques2013Report (Other academic)
    Abstract [en]

    Limited memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We show how to efficiently combine limited memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead compared with the cost of computing the quasi-Newton direction in line-search limited memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

  • 28.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Gong, Lujin
    Tencent, Beijing, China.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Yuan, Ya-xiang
    State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, AMSS, CAS, Beijing, China.
    On Efficiently Combining Limited-Memory and Trust-Region Techniques2017In: Mathematical Programming Computation, ISSN 1867-2949, E-ISSN 1867-2957, Vol. 9, no 1, p. 101-134Article in journal (Refereed)
    Abstract [en]

    Limited-memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

  • 29.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Griewank, Andreas
    Humboldt University, Germany .
    Lotov, Alexander
    Dorodnicyn Computing Centre of Russian Academy of Sciences.
    Yury G. Evtushenko - A tribute2014In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 29, no 5, p. 899-899Article in journal (Other academic)
    Abstract [en]

    n/a

  • 30.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Griewank, Andreas
    Humboldt University, Department of Mathematics, Berlin, Germany.
    Lotov, Alexander V
    Dorodnicyn Computing Center, Russian Academy of Sciences, Moscow, Russia.
    Yury G. Evtushenko---a tribute2005In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 20, no 1, p. 1-7Article in journal (Other academic)
  • 31.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Grimvall, Anders
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
    Hussian, Mohamed
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
    A generalised PAV algorithm for monotonic regression in several variables2004In: COMPSTAT. Proceedings in Computational Statistics / [ed] J. Antoch, Heidelberg, NY: PhysicaVerlag/Springer , 2004, p. 761-767Conference paper (Refereed)
    Abstract [en]

    We present a new algorithm for monotonic regression in one or more explanatory variables. Formally, our method generalises the well-known PAV (pool-adjacent-violators) algorithm from fully to partially ordered data. The computational complexity of our algorithm is O(n2). The goodness-of-fit to observed data is much closer to optimal than for simple averaging techniques.

  • 32.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Grimvall, Anders
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    Hussian, Mohamed
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    Sysoev, Oleg
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    Hasse diagrams and the generalized PAV-algorithm for monotonic regression in several explanatory variables2005In: Computational Statistics and Data Analysis, ISSN 0167-9473Article in journal (Refereed)
    Abstract [en]

    Monotonic regression is a nonparametric method for estimation ofmodels in which the expected value of a response variable y increases ordecreases in all coordinates of a vector of explanatory variables x = (x1, …, xp).Here, we examine statistical and computational aspects of our recentlyproposed generalization of the pool-adjacent-violators (PAV) algorithm fromone to several explanatory variables. In particular, we show how the goodnessof-fit and accuracy of obtained solutions can be enhanced by presortingobserved data with respect to their level in a Hasse diagram of the partial orderof the observed x-vectors, and we also demonstrate how these calculations canbe carried out to save computer memory and computational time. Monte Carlosimulations illustrate how rapidly the mean square difference between fittedand expected response values tends to zero, and how quickly the mean squareresidual approaches the true variance of the random error, as the number of observations increases up to 104.

  • 33.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Grimvall, Anders
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
    Sysoev, Oleg
    Linköping University, Department of Mathematics.
    Data preordering in generalized pav algorithm for monotonic regression2006Report (Other academic)
  • 34.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Grimvall, Anders
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Sysoev, Oleg
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Data preordering in generalized PAV algorithm for monotonic regression2006In: Journal of Computational Mathematics, ISSN 0254-9409, E-ISSN 1991-7139, Vol. 24, no 6, p. 771-790Article in journal (Refereed)
    Abstract [en]

    Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. {\sl Nonconvex Optimization and Its Applications}, Springer-Verlag, (2006) {\bf 83}, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.

  • 35.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Grimvall, Anders
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    Sysoev, Oleg
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    Generalized PAV algorithm with block refinement for partially ordered monotonic regression2009In: Proceedings of the Workshop on Learning Monotone Models from Data / [ed] A. Feelders and R. Potharst, 2009, p. 23-37Conference paper (Other academic)
    Abstract [en]

    In this paper, the monotonic regression problem (MR) is considered. We have recentlygeneralized for MR the well-known Pool-Adjacent-Voilators algorithm(PAV) from the case of completely to partially ordered data sets. Thenew algorithm, called GPAV, combines both high accuracy and lowcomputational complexity which grows quadratically with the problemsize. The actual growth observed in practice is typically far lowerthan quadratic. The fitted values of the exact MR solution composeblocks of equal values. Its GPAV approximation has also a blockstructure. We present here a technique for refining blocks produced bythe GPAV algorithm to make the new blocks more close to those in theexact solution. This substantially improves the accuracy of the GPAVsolution and does not deteriorate its computational complexity. Thecomputational time for the new technique is approximately triple thetime of running the GPAV algorithm. Its efficiency is demonstrated byresults of our numerical experiments.

  • 36.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Grimvall, Anders
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Computer and Information Science, Statistics.
    Sysoev, Oleg
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Computer and Information Science, Statistics.
    New optimization algorithms for large-scale isotonic regression in L2-norm2007In: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, p. 44-44Conference paper (Other academic)
    Abstract [en]

    Isotonic regression problem (IR) has numerous important applications in statistics, operations research, biology, image and signal processing and other areas. IR in L2-norm is a minimization problem in which the objective function is the squared Euclidean distance from a given point to a convex set defined by monotonicity constraints of the form: i-th component of the decision vector is less or equal to its j-th component. Unfortunately, the conventional optimization methods are unable to solve IR problems originating from large data sets. The existing IR algorithms, such as the minimum lower sets algorithm by Brunk, the min-max algorithm by Lee, the network flow algorithm by Maxwell & Muchstadt and the IBCR algorithm by Block et al. are able to find exact solution to IR problem for at most a few thousands of variables. The IBCR algorithm, which proved to be the most efficient of them, is not robust enough. An alternative approach is related to solving IR problem approximately. Following this approach, Burdakov et al. developed an algorithm, called GPAV, whose block refinement extension, GPAVR, is able to solve IR problems with a very high accuracy in a far shorter time than the exact algorithms. Apart from this, GPAVR is a very robust algorithm, and it allows us to solve IR problems with over hundred thousands of variables. In this talk, we introduce new exact IR algorithms, which can be viewed as active set methods. They use the approximate solution produced by the GPAVR algorithm as a starting point. We present results of our numerical experiments demonstrating the high efficiency of the new algorithms, especially for very large-scale problems, and their robustness. They are able to solve the problems which all existing exact IR algorithms fail to solve.

  • 37.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Grimvall, Anders
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Computer and Information Science, Statistics.
    Sysoev, Oleg
    Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Computer and Information Science, Statistics.
    Kapyrin, Ivan
    Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
    Vassilevski, Yuri
    Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
    Monotonic data fitting and interpolation with application to postprocessing of FE solutions2007In: CERFACS 20th Anniversary Conference on High-performance Computing,2007, 2007, p. 11-12Conference paper (Other academic)
    Abstract [en]

    In this talk we consider the isotonic regression (IR) problem which can be formulated as follows. Given a vector $\bar{x} \in R^n$, find $x_* \in R^n$ which solves the problem: \begin{equation}\label{ir2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0. \end{array} \end{equation} The set of constraints $Mx \ge 0$ represents here the monotonicity relations of the form $x_i \le x_j$ for a given set of pairs of the components of $x$. The corresponding row of the matrix $M$ is composed mainly of zeros, but its $i$th and $j$th elements, which are equal to $-1$ and $+1$, respectively. The most challenging applications of (\ref{ir2}) are characterized by very large values of $n$. We introduce new IR algorithms. Our numerical experiments demonstrate the high efficiency of our algorithms, especially for very large-scale problems, and their robustness. They are able to solve some problems which all existing IR algorithms fail to solve. We outline also our new algorithms for monotonicity-preserving interpolation of scattered multivariate data. In this talk we focus on application of our IR algorithms in postprocessing of FE solutions. Non-monotonicity of the numerical solution is a typical drawback of the conventional methods of approximation, such as finite elements (FE), finite volumes, and mixed finite elements. The problem of monotonicity is particularly important in cases of highly anisotropic diffusion tensors or distorted unstructured meshes. For instance, in the nuclear waste transport simulation, the non-monotonicity results in the presence of negative concentrations which may lead to unacceptable concentration and chemistry calculations failure. Another drawback of the conventional methods is a possible violation of the discrete maximum principle, which establishes lower and upper bounds for the solution. We suggest here a least-change correction to the available FE solution $\bar{x} \in R^n$. This postprocessing procedure is aimed on recovering the monotonicity and some other important properties that may not be exhibited by $\bar{x}$. The mathematical formulation of the postprocessing problem is reduced to the following convex quadratic programming problem \begin{equation}\label{ls2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0, \quad l \le x \le u, \quad e^Tx = m, \end{array} \end{equation} where$e=(1,1, \ldots ,1)^T \in R^n$. The set of constraints $Mx \ge 0$ represents here the monotonicity relations between some of the adjacent mesh cells. The constraints $l \le x \le u$ originate from the discrete maximum principle. The last constraint formulates the conservativity requirement. The postprocessing based on (\ref{ls2}) is typically a large scale problem. We introduce here algorithms for solving this problem. They are based on the observation that, in the presence of the monotonicity constraints only, problem (\ref{ls2}) is the classical monotonic regression problem, which can be solved efficiently by some of the available monotonic regression algorithms. This solution is used then for producing the optimal solution to problem (\ref{ls2}) in the presence of all the constraints. We present results of numerical experiments to illustrate the efficiency of our algorithms.

  • 38.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Optimal placement of communications relay nodes2009Report (Other (popular science, discussion, etc.))
    Abstract [en]

    We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.

  • 39.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles2008Report (Other academic)
    Abstract [en]

    We study the problem of positioning unmanned aerial vehicles (UAVs) to maintain an unobstructed flow of communication from a surveying UAV to some base station through the use of multiple relay UAVs. This problem can be modeled as a hopconstrained shortest path problem in a large visibility graph. We propose a dual ascent method for solving this problem, optionally within a branch-and-bound framework. Computational tests show that realistic problems can be solved in a reasonably short time, and that the proposed method is faster than the classical dynamic programming approach.

  • 40.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Kamandi, Ahmad
    University of Science and Technology of Mazandaran, Behshar, Iran.
    Multipoint secant and interpolation methods with nonmonotone line search for solving systems of nonlinear equations2018In: Applied Mathematics and Computation, ISSN 0096-3003, E-ISSN 1873-5649, Vol. 338, no 1, p. 421-431Article in journal (Refereed)
    Abstract [en]

    Multipoint secant and interpolation methods are effective tools for solving systems of nonlinear equations. They use quasi-Newton updates for approximating the Jacobian matrix. Owing to their ability to more completely utilize the information about the Jacobian matrix gathered at the previous iterations, these methods are especially efficient in the case of expensive functions. They are known to be local and superlinearly convergent. We combine these methods with the nonmonotone line search proposed by Li and Fukushima (2000), and study global and superlinear convergence of this combination. Results of numerical experiments are presented. They indicate that the multipoint secant and interpolation methods tend to be more robust and efficient than Broyden’s method globalized in the same way.

    The full text will be freely available from 2020-07-11 00:01
  • 41.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Kanzow, Christian
    University of Würzburg, Germany.
    Schwartz, Alexandra
    Technical University of Darmstadt, Germany.
    Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method2016In: SIAM Journal on Optimization, ISSN 1052-6234, E-ISSN 1095-7189, Vol. 26, no 1, p. 397-425Article in journal (Refereed)
    Abstract [en]

    Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in detail. Since our reformulation is a minimization problem in continuous variables, it allows to apply ideas from that field to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinality constraints. This regularization method is shown to be globally convergent to a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.

  • 42.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kanzow, Christian
    University of Würzburg.
    Schwartz, Alexandra
    Technical University of Darmstadt.
    Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method2014Report (Other academic)
    Abstract [en]

    Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discreteoptimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between thelocal minima is also discussed in detail. Since our reformulation is a mini-mization problem in continuous variables, it allows to apply ideas from thatfield to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinalityconstraints. This regularization method is shown to be globally convergentto a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.

  • 43.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kanzow, Christian
    University of Würzburg, Germany.
    Schwartz, Alexandra
    Technical University of Darmstadt, Germany.
    On a Reformulation of Mathematical Programs with Cardinality Constraints2015In: Advances in Global Optimization / [ed] David Gao, Ning Ruan and Wenxun Xing, Switzerland: Springer International Publishing , 2015, p. 3-14Chapter in book (Refereed)
    Abstract [en]

    Mathematical programs with cardinality constraints are optimization problems with an additional constraint which requires the solution to be sparse in the sense that the number of nonzero elements, i.e. the cardinality, is bounded by a given constant. Such programs can be reformulated as a mixed-integer ones in which the sparsity is modeled with the use of complementarity-type constraints. It is shown that the standard relaxation of the integrality leads to a nonlinear optimization program of the striking property that its solutions (global minimizers) are the same as the solutions of the original program with cardinality constraints. Since the number of local minimizers of the relaxed program is typically larger than the number of local minimizers of the cardinality-constrained problem, the relationship between the local minimizers is also discussed in detail. Furthermore, we show under which assumptions the standard KKT conditions are necessary optimality conditions for the relaxed program. The main result obtained for such conditions is significantly different from the existing optimality conditions that are known for the somewhat related class of mathematical programs with complementarity constraints.

  • 44.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kapyrin, Ivan
    Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, Russia.
    Vassilevski, Yuri
    Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, Russia.
    Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions2011Report (Other academic)
    Abstract [en]

    We suggest here a least-change correction to available finite element (FE) solution.This postprocessing procedure is aimed at recoveringthe monotonicity and some other important properties that may not beexhibited by the FE solution. It is based on solvinga monotonic regression problem with some extra constraints.One of them is a linear equality-type constraint which models the conservativityrequirement. The other ones are box-type constraints, andthey originate from the discrete maximum principle.The resulting postprocessing problem is a large scale quadratic optimization problem. It is proved that the postprocessedFE solution preserves the accuracy of the discrete FE approximation.We introduce an algorithm for solving the postprocessingproblem. It can be viewed as a dual ascent method basedon the Lagrangian relaxation of the equality constraint.We justify theoretically its correctness.Its efficiency is demonstrated by the presented results of numerical experiments.

  • 45.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kapyrin, Ivan
    Russian Academy of Science.
    Vassilevski, Yuri
    Russian Academy of Science.
    Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions2012In: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 231, no 8, p. 3126-3142Article in journal (Refereed)
    Abstract [en]

    We suggest here a least-change correction to available finite element (FE) solution. This postprocessing procedure is aimed at recovering the monotonicity and some other important properties that may not be exhibited by the FE solution. Although our approach is presented for FEs, it admits natural extension to other numerical schemes, such as finite differences and finite volumes. For the postprocessing, a priori information about the monotonicity is assumed to be available, either for the whole domain or for a subdomain where the lost monotonicity is to be recovered. The obvious requirement is that such information is to be obtained without involving the exact solution, e.g. from expected symmetries of this solution. less thanbrgreater than less thanbrgreater thanThe postprocessing is based on solving a monotonic regression problem with some extra constraints. One of them is a linear equality-type constraint that models the conservativity requirement. The other ones are box-type constraints, and they originate from the discrete maximum principle. The resulting postprocessing problem is a large scale quadratic optimization problem. It is proved that the postprocessed FE solution preserves the accuracy of the discrete FE approximation. less thanbrgreater than less thanbrgreater thanWe introduce an algorithm for solving the postprocessing problem. It can be viewed as a dual ascent method based on the Lagrangian relaxation of the equality constraint. We justify theoretically its correctness. Its efficiency is demonstrated by the presented results of numerical experiments.

  • 46.
    Burdakov, Oleg
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Kapyrin, Ivan
    Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
    Vassilevski, Yuri
    Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
    Optimization methods for postprocessing finite element solutions2007In: International Conference on Numerical Optimization and Numerical Linear Algebra,2007, 2007Conference paper (Other academic)
    Abstract [en]

    Simulation of transport phenomena based on advection-diffusion equation is very popular in many engineering applications. Non-monotonicity of the numerical solution is the typical drawback of the conventional methods of approximation, such as finite elements (FE), finite volumes, and mixed finite elements. The problem of monotonicity is particularly important in cases of highly anisotropic diffusion tensors or distorted unstructured meshes. For instance, in the nuclear waste transport simulation, the non-monotonicity results in the presence of negative concentrations which may lead to unacceptable concentration and chemistry calculations failure. Another drawback of the conventional methods is a possible violation of the discrete maximum principle, which establishes lower and upper bounds for solution. We suggest here a least-change correction to the available FE solution $\bar{x} \in R^n$. This postprocessing procedure is aimed on recovering the monotonicity and some other important properties that may not be exhibited by $\bar{x}$. The mathematical formulation of the postprocessing problem is reduced to the following convex quadratic programming problem %Given the FE solution $\bar{x} \in R^n$, find $x_* \in R^n$ which %solves the list-distance problem. \begin{equation}\label{ls2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0, \\ & l \le x \le u, \\ & e^Tx = m. \end{array} \end{equation} The set of constraints $Mx \ge 0$ represents here the monotonicity requirements. It establishes relations between some of the adjacent mesh cells in the form $x_i \le x_j$, which relates cells $i$ and $j$. The corresponding row of the matrix $M$ is composed mainly of zeros, but its $i$th and $j$th elements, which are equal to $-1$ and $+1$, respectively. The set of constraints $l \le x \le u$ originates from the discrete maximum principle. In the last constraint, $e=(1,1, \ldots ,1)^T \in R^n$. It formulates the conservativity requirement. The postprocessing based on (\ref{ls2}) is typically a large scale problem. We introduce here algorithms for solving this problem. They are based on the observation that, in the presence of the monotonicity constraints only, problem (\ref{ls2}) is the classical monotonic regression problem, which can be solved efficiently by some of the available monotonic regression algorithms. This solution is used then for producing the optimal solution to problem (\ref{ls2}) in the presence of all the constraints. We present results of numerical experiments to illustrate the efficiency of our algorithms.

  • 47.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles2017In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 249, no 1, p. 163-174Article in journal (Refereed)
    Abstract [en]

    Guarding the perimeter of an area in order to detect potential intruders is an important task in a variety of security-related applications. This task can in many circumstances be performed by a set of camera-equipped unmanned aerial vehicles (UAVs). Such UAVs will occasionally require refueling or recharging, in which case they must temporarily be replaced by other UAVs in order to maintain complete surveillance of the perimeter. In this paper we consider the problem of scheduling such replacements. We present optimal replacement strategies and justify their optimality.

  • 48.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Martinez, JM
    Linkoping Univ, Dept Math, Div Optimizat, S-58183 Linkoping, Sweden Univ Campinas, UNICAMP, IMECC, Dept Appl Math, BR-13081970 Campinas, SP, Brazil Univ Nacl Cordoba, CIEM, Fac Matemat Astron & Fis, RA-5000 Cordoba, Argentina.
    Pilotta, EA
    Linkoping Univ, Dept Math, Div Optimizat, S-58183 Linkoping, Sweden Univ Campinas, UNICAMP, IMECC, Dept Appl Math, BR-13081970 Campinas, SP, Brazil Univ Nacl Cordoba, CIEM, Fac Matemat Astron & Fis, RA-5000 Cordoba, Argentina.
    A limited-memory multipoint symmetric secant method for bound constrained optimization2002In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 117, no 1-4, p. 51-70Article in journal (Refereed)
    Abstract [en]

    A new algorithm for solving smooth large-scale minimization problems with bound constraints is introduced. The way of dealing with active constraints is similar to the one used in some recently introduced quadratic solvers. A limited-memory multipoint symmetric secant method for approximating the Hessian is presented. Positive-definiteness of the Hessian approximation is not enforced. A combination of trust-region and conjugate-gradient approaches is used to explore a useful negative curvature information. Global convergence is proved for a general model algorithm. Results of numerical experiments are presented.

  • 49.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Sysoev, Oleg
    Linköping University, Department of Computer and Information Science, Statistics. Linköping University, Faculty of Arts and Sciences.
    A Dual Active-Set Algorithm for Regularized Monotonic Regression2017In: Journal of Optimization Theory and Applications, ISSN 0022-3239, E-ISSN 1573-2878, Vol. 172, no 3, p. 929-949Article in journal (Refereed)
    Abstract [en]

    Monotonic (isotonic) regression is a powerful tool used for solving a wide range of important applied problems. One of its features, which poses a limitation on its use in some areas, is that it produces a piecewise constant fitted response. For smoothing the fitted response, we introduce a regularization term in the monotonic regression, formulated as a least distance problem with monotonicity constraints. The resulting smoothed monotonic regression is a convex quadratic optimization problem. We focus on the case, where the set of observations is completely (linearly) ordered. Our smoothed pool-adjacent-violators algorithm is designed for solving the regularized problem. It belongs to the class of dual active-set algorithms. We prove that it converges to the optimal solution in a finite number of iterations that does not exceed the problem size. One of its advantages is that the active set is progressively enlarging by including one or, typically, more constraints per iteration. This resulted in solving large-scale test problems in a few iterations, whereas the size of that problems was prohibitively too large for the conventional quadratic optimization solvers. Although the complexity of our algorithm grows quadratically with the problem size, we found its running time to grow almost linearly in our computational experiments.

  • 50.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Sysoev, Oleg
    Linköping University, Department of Computer and Information Science, The Division of Statistics and Machine Learning. Linköping University, Faculty of Arts and Sciences.
    A Dual Active-Set Algorithm for Regularized Slope-Constrained Monotonic Regression2017In: Iranian Journal of Operations Research, ISSN 2008-1189, Vol. 8, no 2, p. 40-47Article in journal (Refereed)
    Abstract [en]

    In many problems, it is necessary to take into account monotonic relations. Monotonic (isotonic) Regression (MR) is often involved in solving such problems. The MR solutions are of a step-shaped form with a typical sharp change of values between adjacent steps. This, in some applications, is regarded as a disadvantage. We recently introduced a Smoothed MR (SMR) problem which is obtained from the MR by adding a regularization penalty term. The SMR is aimed at smoothing the aforementioned sharp change. Moreover, its solution has a far less pronounced step-structure, if at all available. The purpose of this paper is to further improve the SMR solution by getting rid of such a structure. This is achieved by introducing a lowed bound on the slope in the SMR. We call it Smoothed Slope-Constrained MR (SSCMR) problem. It is shown here how to reduce it to the SMR which is a convex quadratic optimization problem. The Smoothed Pool Adjacent Violators (SPAV) algorithm developed in our recent publications for solving the SMR problem is adapted here to solving the SSCMR problem. This algorithm belongs to the class of dual active-set algorithms. Although the complexity of the SPAV algorithm is o(n2) its running time is growing in our computational experiments almost linearly with n. We present numerical results which illustrate the predictive performance quality of our approach. They also show that the SSCMR solution is free of the undesirable features of the MR and SMR solutions.

12 1 - 50 of 71
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf