| 31. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Multipoint secant and interpolation methods with nonmonotone line search for solving systems of nonlinear equations
- 2018
-
Ingår i: Applied Mathematics and Computation. - : Elsevier. - 0096-3003 .- 1873-5649. ; 338:1, s. 421-431
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 32. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
On a Reformulation of Mathematical Programs with Cardinality Constraints
- 2015
-
Ingår i: Advances in Global Optimization. - Switzerland : Springer International Publishing. - 9783319083766 - 9783319083773 ; , s. 3-14
-
Bokkapitel (refereegranskat)abstract
- 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.
|
|
| 33. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
On Efficiently Combining Limited-Memory and Trust-Region Techniques
- 2017
-
Ingår i: Mathematical Programming Computation. - : Springer. - 1867-2949 .- 1867-2957. ; 9:1, s. 101-134
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 34. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
On Efficiently Combining Limited Memory and Trust-Region Techniques
- 2013
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 35. |
|
|
| 36. |
- Burdakov, Oleg, 1953-
(författare)
-
On properties of Newton's method for smooth and nonsmooth equations
- 1995
-
Ingår i: Recent Trends in Optimization Theory and Applications. - : World Scientific. - 9789810223823 - 9789812798862 ; , s. 17-24
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 37. |
- Burdakov, Oleg, 1953-
(författare)
-
On solving saddle point problems and monotone equations
- 2018
-
Ingår i: IX Moscow International Conference on Operations Research (ORM2018). Moscow, October 22-27, 2018. Proceedings, Volume 1. - Moscow. - 9785317059248 - 9785317059231 ; , s. 47-50
-
Konferensbidrag (refereegranskat)
|
|
| 38. |
- Burdakov, Oleg, 1953-
(författare)
-
On Superlinear Convergence of Some Stable Variants of the Secant Method
- 1986
-
Ingår i: Zeitschrift für angewandte Mathematik und Mechanik. - : Wiley. - 0044-2267 .- 1521-4001. ; 66:2, s. 615-622
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 39. |
- Burdakov, Oleg, 1953-
(författare)
-
On using the minimum spanning tree algorithm for optimal secant approximation of derivatives
- 1996
-
Ingår i: Zeitschrift für angewandte Mathematik und Mechanik. - : Wiley. - 0044-2267 .- 1521-4001. ; 76:S3, s. 389-390
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 40. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles
- 2017
-
Ingår i: Annals of Operations Research. - : Springer. - 0254-5330 .- 1572-9338. ; 249:1, s. 163-174
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
