| 1. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
A Dual Active-Set Algorithm for Regularized Monotonic Regression
- 2017
-
Ingår i: Journal of Optimization Theory and Applications. - : Springer. - 0022-3239 .- 1573-2878. ; 172:3, s. 929-949
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 2. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
A Dual Active-Set Algorithm for Regularized Slope-Constrained Monotonic Regression
- 2017
-
Ingår i: Iranian Journal of Operations Research. - Tehran : CMV Verlag. - 2008-1189. ; 8:2, s. 40-47
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- Sysoev, Oleg, et al.
(författare)
-
Bootstrap confidence intervals for large-scale multivariate monotonic regression problems
- 2016
-
Ingår i: Communications in statistics. Simulation and computation. - : Taylor & Francis. - 0361-0918 .- 1532-4141. ; 45:3, s. 1025-1040
-
Tidskriftsartikel (refereegranskat)abstract
- Recently, the methods used to estimate monotonic regression (MR) models have been substantially improved, and some algorithms can now produce high-accuracy monotonic fits to multivariate datasets containing over a million observations. Nevertheless, the computational burden can be prohibitively large for resampling techniques in which numerous datasets are processed independently of each other. Here, we present efficient algorithms for estimation of confidence limits in large-scale settings that take into account the similarity of the bootstrap or jackknifed datasets to which MR models are fitted. In addition, we introduce modifications that substantially improve the accuracy of MR solutions for binary response variables. The performance of our algorithms isillustrated using data on death in coronary heart disease for a large population. This example also illustrates that MR can be a valuable complement to logistic regression.
|
|
| 4. |
- Andersson, Mats, et al.
(författare)
-
Sparsity Optimization in Design of Multidimensional Filter Networks
- 2015
-
Ingår i: Optimization and Engineering. - : Springer. - 1389-4420 .- 1573-2924. ; 16:2, s. 259-277
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
(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".
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
