| 21. |
- Brust, Johannes, et al.
(författare)
-
Shape-Changing L-SR1 Trust-Region Methods
- 2016
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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".
|
|
| 22. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 23. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
A generalised PAV algorithm for monotonic regression in several variables
- 2004
-
Ingår i: COMPSTAT. Proceedings in Computational Statistics. - Heidelberg, NY : PhysicaVerlag/Springer. - 3790815543 ; , s. 761-767
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 24. |
- Burdakov, Oleg, 1953-
(författare)
-
A greedy algorithm for the optimal basis problem
- 1997
-
Ingår i: BIT Numerical Mathematics. - : Springer. - 0006-3835 .- 1572-9125. ; 37:3, s. 591-599
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 25. |
- Burdakov, Oleg, 1953-
(författare)
-
Conjugate direction methods for solving systems of equations and finding saddle points. Part 1
- 1982
-
Ingår i: Engineering Cybernetics. - 0013-788X. ; 20:3, s. 13-19
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 26. |
- Burdakov, Oleg, 1953-
(författare)
-
Conjugate direction methods for solving systems of equations and finding saddle points. Part 2
- 1982
-
Ingår i: Engineering Cybernetics. - 0013-788X. ; 20:4, s. 23-31
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 27. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Mathematical Programs with Cardinality Constraints : Reformulation by Complementarity-type Constraints and a Regularization Method
- 2014
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 28. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
- 2016
-
Ingår i: SIAM Journal on Optimization. - : Society for Industrial & Applied Mathematics (SIAM). - 1052-6234 .- 1095-7189. ; 26:1, s. 397-425
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 29. |
- Burdakov, Oleg, 1953-
(författare)
-
Methods of the secant type for systems of equations with symmetric Jacobian matrix
- 1983
-
Ingår i: Numerical Functional Analysis and Optimization. - : Taylor & Francis. - 0163-0563 .- 1532-2467. ; 6:2, s. 183-195
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 30. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions
- 2011
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
