liu.seSearch for publications in DiVA
Endre søk
Begrens søket
12 1 - 50 of 72
Referera
Referensformat
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Annet format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annet språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
Treff pr side
• 5
• 10
• 20
• 50
• 100
• 250
Sortering
• Standard (Relevans)
• Forfatter A-Ø
• Forfatter Ø-A
• Tittel A-Ø
• Tittel Ø-A
• Type publikasjon A-Ø
• Type publikasjon Ø-A
• Eldste først
• Nyeste først
• Disputationsdatum (tidligste først)
• Disputationsdatum (siste først)
• Standard (Relevans)
• Forfatter A-Ø
• Forfatter Ø-A
• Tittel A-Ø
• Tittel Ø-A
• Type publikasjon A-Ø
• Type publikasjon Ø-A
• Eldste først
• Nyeste først
• Disputationsdatum (tidligste først)
• Disputationsdatum (siste først)
Merk
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
• 1.
Linköpings universitet, Institutionen för medicinsk teknik, Medicinsk informatik. Linköpings universitet, Tekniska högskolan.
Global search strategies for solving multilinear least-squares problems2012Inngår i: Sultan Qaboos University Journal for Science, ISSN 1027-524X, Vol. 17, nr 1, s. 12-21Artikkel i tidsskrift (Fagfellevurdert)

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.
Linköpings universitet, Institutionen för medicinsk teknik, Medicinsk informatik. Linköpings universitet, Tekniska högskolan.
Global Search Strategies for Solving Multilinear Least-squares Problems2011Rapport (Annet vitenskapelig)

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.
Sparsity Optimization in Design of Multidimensional Filter Networks2013Rapport (Annet vitenskapelig)

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.
Linköpings universitet, Institutionen för medicinsk teknik, Medicinsk informatik. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Centrum för medicinsk bildvetenskap och visualisering, CMIV.
Sparsity Optimization in Design of Multidimensional Filter Networks2015Inngår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 16, nr 2, s. 259-277Artikkel i tidsskrift (Fagfellevurdert)

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.
University of California, Merced, CA, USA.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Wake Forest University, Winston-Salem, NC, USA. University of California, Merced, CA, USA.
A dense initialization for limited-memory quasi-Newton methods2019Inngår i: Computational Optimization and Applications, ISSN 0926-6003, Vol. 74, nr 1, s. 121-142Artikkel i tidsskrift (Annet vitenskapelig)

We consider a family of dense initializations for limited-memory quasi-Newton methods. The proposed initialization exploits an eigendecomposition-based separation of the full space into two complementary subspaces, assigning a different initialization parameter to each subspace. 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.

Fulltekst tilgjengelig fra 2020-05-29 08:00
• 6.
Applied Mathematics, University of California, Merced, USA.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Department of Mathematics, Wake Forest University, USA. Applied Mathematics, University of California, Merced, USA. 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 Methods2016Rapport (Annet vitenskapelig)

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.
Parallel Algorithms Team, CERFACS, Toulouse Cedex, France.
A greedy algorithm for the optimal basis problem1997Inngår i: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 37, nr 3, s. 591-599Artikkel i tidsskrift (Fagfellevurdert)

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.
Component-wise quasi-Newton methods1991Inngår i: Numerical methods of nonlinear programming and their implementations / [ed] C. Richter, H. Hollatz and D. Pallaschke, Berlin: Akademie Verlag, 1991, s. 17-27Kapittel i bok, del av antologi (Annet vitenskapelig)
• 9.
Computing Center, USSR Academy of Sciences, Moscow.
Conjugate direction methods for solving systems of equations and finding saddle points. Part 11982Inngår i: Engineering Cybernetics, ISSN 0013-788X, Vol. 20, nr 3, s. 13-19Artikkel i tidsskrift (Fagfellevurdert)

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.
Computing Center, USSR Academy of Sciences, Moscow.
Conjugate direction methods for solving systems of equations and finding saddle points. Part 21982Inngår i: Engineering Cybernetics, ISSN 0013-788X, Vol. 20, nr 4, s. 23-31Artikkel i tidsskrift (Fagfellevurdert)

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.
Computing Center, USSR Academy of Sciences, Moscow.
Methods of the secant type for systems of equations with symmetric Jacobian matrix1983Inngår i: Numerical Functional Analysis and Optimization, ISSN 0163-0563, E-ISSN 1532-2467, Vol. 6, nr 2, s. 183-195Artikkel i tidsskrift (Fagfellevurdert)

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.
On Limited Memory Methods with Shape Changing Trust Region2003Inngår i: The 18th International Symposium on Mathematical Programming,2003, 2003Konferansepaper (Annet vitenskapelig)
• 13.
Parallel Algorithms Group, CERFACS, Toulouse, France.
On properties of Newton's method for smooth and nonsmooth equations1995Inngår i: Recent Trends in Optimization Theory and Applications / [ed] R.P. Agarwal, World Scientific, 1995, s. 17-24Kapittel i bok, del av antologi (Annet vitenskapelig)

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.
On solving saddle point problems and monotone equations2018Inngår i: 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, s. 47-50Konferansepaper (Fagfellevurdert)
• 15.
Computing Center of the USSR Academy of Sciences, Moscow.
On Superlinear Convergence of Some Stable Variants of the Secant Method1986Inngår i: Zeitschrift für angewandte Mathematik und Mechanik, ISSN 0044-2267, E-ISSN 1521-4001, Vol. 66, nr 2, s. 615-622Artikkel i tidsskrift (Fagfellevurdert)

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.
CERFACS, Parallel Algorithms Team, Toulouse, France.
On using the minimum spanning tree algorithm for optimal secant approximation of derivatives1996Inngår i: Zeitschrift für angewandte Mathematik und Mechanik, ISSN 0044-2267, E-ISSN 1521-4001, Vol. 76, nr S3, s. 389-390Artikkel i tidsskrift (Fagfellevurdert)

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.
Computing Center, USSR Academy of Sciences, Moscow.
Some globally convergent modifications of Newton's method for solving systems of nonlinear equations1980Inngår i: Soviet mathematics - Doklady, ISSN 0197-6788, Vol. 22, nr 2, s. 376-378Artikkel i tidsskrift (Fagfellevurdert)
• 18.
Computing Center of the USSR Academy of Sciences, Moscow .
Stable symmetric secant methods with restart1991Inngår i: Cybernetics and Systems Analysis, ISSN 1060-0396, E-ISSN 1573-8337, Vol. 27, nr 3, s. 390-396Artikkel i tidsskrift (Fagfellevurdert)

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.
Computing Center, USSR Academy of Sciences, Moscow.
Stable versions of the secants method for solving systems of equations1983Inngår i: Computational Mathematics and Mathematical Physics, ISSN 0965-5425, E-ISSN 1555-6662, Vol. 23, nr 5, s. 1-10Artikkel i tidsskrift (Fagfellevurdert)

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.
Stabilized Barzilai-Borwein methodManuskript (preprint) (Annet vitenskapelig)

The Barzilai-Borwein (BB) method is a popular and efficient tool for solving large-scale unconstrained optimization problems. Its search direction is the same as for the steepest descent (Cauchy) method, but its stepsize rule is different. Owing to this, it converges much faster than the Cauchy method. A feature of the BB method is that it may generate too long steps, which throw the iterates too far away from the solution. Moreover, it may not converge, even when the objective function is strongly convex. In this paper, a stabilization technique is introduced. It consists in bounding the distance between each pair of successive iterates, which often allows for decreasing the number of BB iterations. When the BB method does not converge, our simple modification of this method makes it convergent. Under suitable assumptions, we prove its global convergence, despite the fact that no line search is involved, and only gradient values are used. Since the number of stabilization steps is proved to be finite, the stabilized version inherits the fast local convergence of the BB method. The presented results of extensive numerical experiments show that our stabilization technique often allows the BB method to solve problems in a fewer iterations, or even to solve problems where the latter fails.

• 21.
Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
Positioning Unmanned Aerial Vehicles As Communication Relays for Surveillance Tasks2010Inngår i: Robotics: Science and Systems V / [ed] Jeff Trinkle, Yoky Matsuoka, Jose Castellanos, MIT Press, 2010, s. 257-264Konferansepaper (Fagfellevurdert)

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.

• 22.
Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
Relay Positioning for Unmanned Aerial Vehicle Surveillance2010Inngår i: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 29, nr 8, s. 1069-1087Artikkel i tidsskrift (Fagfellevurdert)

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.

• 23.
Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
Optimal placement of UV-based communications relay nodes2010Inngår i: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 48, nr 4, s. 511-531Artikkel i tidsskrift (Fagfellevurdert)

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.

• 24.
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Rapport (Annet vitenskapelig)

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.

• 25.
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Inngår i: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, s. 26-50Konferansepaper (Fagfellevurdert)

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.

• 26.
Optimal Scheduling for Replacing Perimeter Guarding Unmanned Aerial Vehicles2014Rapport (Annet vitenskapelig)

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.

• 27.
Brandenburg University of Technology, Germany.
Stable multi-point secant methods with released requirements to point's position1994Inngår i: 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, s. 225-236Kapittel i bok, del av antologi (Annet vitenskapelig)
• 28.
Samsung Advanced Institute of Technology, China Lab, Beijing, China. State Key Laboratory of Scientic and Engineering Computing, Institute of Computational. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
On Efficiently Combining Limited Memory and Trust-Region Techniques2013Rapport (Annet vitenskapelig)

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.

• 29.
Tencent, Beijing, China. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. 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 Techniques2017Inngår i: Mathematical Programming Computation, ISSN 1867-2949, E-ISSN 1867-2957, Vol. 9, nr 1, s. 101-134Artikkel i tidsskrift (Fagfellevurdert)

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.

• 30.
Humboldt University, Germany . Dorodnicyn Computing Centre of Russian Academy of Sciences.
Yury G. Evtushenko - A tribute2014Inngår i: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 29, nr 5, s. 899-899Artikkel i tidsskrift (Annet vitenskapelig)

n/a

• 31.
Humboldt University, Department of Mathematics, Berlin, Germany. Dorodnicyn Computing Center, Russian Academy of Sciences, Moscow, Russia.
Yury G. Evtushenko---a tribute2005Inngår i: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 20, nr 1, s. 1-7Artikkel i tidsskrift (Annet vitenskapelig)
• 32.
A generalised PAV algorithm for monotonic regression in several variables2004Inngår i: COMPSTAT. Proceedings in Computational Statistics / [ed] J. Antoch, Heidelberg, NY: PhysicaVerlag/Springer , 2004, s. 761-767Konferansepaper (Fagfellevurdert)

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.

• 33.
Hasse diagrams and the generalized PAV-algorithm for monotonic regression in several explanatory variables2005Inngår i: Computational Statistics and Data Analysis, ISSN 0167-9473Artikkel i tidsskrift (Fagfellevurdert)

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.

• 34.
Data preordering in generalized pav algorithm for monotonic regression2006Rapport (Annet vitenskapelig)
• 35.
Data preordering in generalized PAV algorithm for monotonic regression2006Inngår i: Journal of Computational Mathematics, ISSN 0254-9409, E-ISSN 1991-7139, Vol. 24, nr 6, s. 771-790Artikkel i tidsskrift (Fagfellevurdert)

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.

• 36.
Generalized PAV algorithm with block refinement for partially ordered monotonic regression2009Inngår i: Proceedings of the Workshop on Learning Monotone Models from Data / [ed] A. Feelders and R. Potharst, 2009, s. 23-37Konferansepaper (Annet vitenskapelig)

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.

• 37.
New optimization algorithms for large-scale isotonic regression in L2-norm2007Inngår i: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, s. 44-44Konferansepaper (Annet vitenskapelig)

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.

• 38.
Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik. Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik. Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia. Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
Monotonic data fitting and interpolation with application to postprocessing of FE solutions2007Inngår i: CERFACS 20th Anniversary Conference on High-performance Computing,2007, 2007, s. 11-12Konferansepaper (Annet vitenskapelig)

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: $$\label{ir2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0. \end{array}$$ 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 $$\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}$$ 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.

• 39.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
Optimal placement of communications relay nodes2009Rapport (Annet (populærvitenskap, debatt, mm))

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.

• 40.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles2008Rapport (Annet vitenskapelig)

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.

• 41.
University of Science and Technology of Mazandaran, Behshar, Iran.
Multipoint secant and interpolation methods with nonmonotone line search for solving systems of nonlinear equations2018Inngår i: Applied Mathematics and Computation, ISSN 0096-3003, E-ISSN 1873-5649, Vol. 338, nr 1, s. 421-431Artikkel i tidsskrift (Fagfellevurdert)

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.

Fulltekst tilgjengelig fra 2020-07-11 00:01
• 42.
University of Würzburg, Germany. Technical University of Darmstadt, Germany.
Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method2016Inngår i: SIAM Journal on Optimization, ISSN 1052-6234, E-ISSN 1095-7189, Vol. 26, nr 1, s. 397-425Artikkel i tidsskrift (Fagfellevurdert)

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.

• 43.
University of Würzburg. Technical University of Darmstadt.
Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method2014Rapport (Annet vitenskapelig)

Optimization problems with cardinality constraints are very diﬃcult 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 thatﬁeld 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.

• 44.
University of Würzburg, Germany. Technical University of Darmstadt, Germany.
On a Reformulation of Mathematical Programs with Cardinality Constraints2015Inngår i: Advances in Global Optimization / [ed] David Gao, Ning Ruan and Wenxun Xing, Switzerland: Springer International Publishing , 2015, s. 3-14Kapittel i bok, del av antologi (Fagfellevurdert)

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.

• 45.
Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, Russia. Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, Russia.
Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions2011Rapport (Annet vitenskapelig)

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.

• 46.
Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions2012Inngår i: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 231, nr 8, s. 3126-3142Artikkel i tidsskrift (Fagfellevurdert)

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.

• 47.
Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia. Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia.
Optimization methods for postprocessing finite element solutions2007Inngår i: International Conference on Numerical Optimization and Numerical Linear Algebra,2007, 2007Konferansepaper (Annet vitenskapelig)

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. $$\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}$$ 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.

• 48.
Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles2017Inngår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 249, nr 1, s. 163-174Artikkel i tidsskrift (Fagfellevurdert)

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.

• 49.
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. 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 optimization2002Inngår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 117, nr 1-4, s. 51-70Artikkel i tidsskrift (Fagfellevurdert)

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.

• 50.
A Dual Active-Set Algorithm for Regularized Monotonic Regression2017Inngår i: Journal of Optimization Theory and Applications, ISSN 0022-3239, E-ISSN 1573-2878, Vol. 172, nr 3, s. 929-949Artikkel i tidsskrift (Fagfellevurdert)

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.

12 1 - 50 of 72
Referera
Referensformat
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Annet format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annet språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf