| 1. |
- Andersson, Mats, et al.
(författare)
-
Global Search Strategies for Solving Multilinear Least-squares Problems
- 2011
-
Rapport (övrigt vetenskapligt)abstract
- 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.
|
|
| 2. |
- 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)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.
|
|
| 3. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
An O(n2) algorithm for isotonic regression
- 2006
-
Ingår i: Large-Scale Nonlinear Optimization. - New York : Springer Science+Business Media B.V.. - 0-387-30063-5 ; s. 25-33
-
Konferensbidrag (övrigt vetenskapligt)abstract
- We consider the problem of minimizing the distance from a given n-dimensional vector to a set defined by constraints of the form xi ≤ xj. Such constraints induce a partial order of the components xi, which can be illustrated by an acyclic directed graph. This problem is also known as the isotonic regression (IR) problem. IR has important applications in statistics, operations research and signal processing, with most of them characterized by a very large value of n. For such large-scale problems, it is of great practical importance to develop algorithms whose complexity does not rise with n too rapidly. The existing optimization-based algorithms and statistical IR algorithms have either too high computational complexity or too low accuracy of the approximation to the optimal solution they generate. We introduce a new IR algorithm, which can be viewed as a generalization of the Pool-Adjacent-Violator (PAV) algorithm from completely to partially ordered data. Our algorithm combines both low computational complexity O(n2) and high accuracy. This allows us to obtain sufficiently accurate solutions to IR problems with thousands of observations.
|
|
| 4. |
|
|
| 5. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Monotonic data fitting and interpolation with application to postprocessing of FE solutions
- 2007
-
Ingår i: CERFACS 20th Anniversary Conference on High-performance Computing,2007. ; s. 11-12
-
Konferensbidrag (övrigt vetenskapligt)abstract
- In this talk we consider the isotonic regression (IR) problem which can beformulated as follows. Given a vector $\bar{x} \in R^n$, find $x_* \in R^n$ which solves the problem:\begin{equation}\label{ir2}\begin{array}{cl}\mbox{min} & \|x-\bar{x}\|^2 \\\mbox{s.t.} & Mx \ge 0.\end{array}\end{equation}The set of constraints $Mx \ge 0$ represents here the monotonicityrelations of the form $x_i \le x_j$ for a given set of pairs of thecomponents 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}) arecharacterized by very large values of $n$. We introduce new IRalgorithms. Our numerical experiments demonstrate the high efficiencyof our algorithms, especially for very large-scale problems, and theirrobustness. They are able to solve some problems which all existing IRalgorithms fail to solve. We outline also our new algorithms formonotonicity-preserving interpolation of scattered multivariate data.In this talk we focus on application of our IR algorithms inpostprocessing of FE solutions.Non-monotonicity ofthe numerical solution is a typical drawback of the conventionalmethods of approximation, such as finite elements (FE), finite volumes,and mixed finite elements. The problem of monotonicity isparticularly important in cases of highly anisotropic diffusion tensorsor distorted unstructured meshes. For instance, in the nuclear wastetransport simulation, the non-monotonicity results in the presence ofnegative concentrations which may lead to unacceptable concentrationand chemistry calculations failure. Another drawback of the conventionalmethods is a possible violation of the discrete maximum principle, whichestablishes 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 recoveringthe monotonicity and some other important properties that may not beexhibited by $\bar{x}$.The mathematical formulation of the postprocessing problemis reduced to the following convex quadratic programming problem\begin{equation}\label{ls2}\begin{array}{cl}\mbox{min} & \|x-\bar{x}\|^2 \\\mbox{s.t.} & Mx \ge 0, \quad l \le x \le u, \quad e^Tx = m,\end{array}\end{equation}where$e=(1,1, \ldots ,1)^T \in R^n$. The set of constraints $Mx \ge 0$ represents here the monotonicityrelations between some of the adjacent mesh cells.The constraints $l \le x \le u$ originate fromthe discrete maximum principle. The last constraint formulates the conservativity requirement.The postprocessing based on (\ref{ls2}) is typically a large scaleproblem. We introduce here algorithms for solving this problem. Theyare based on the observation that, in the presence of the monotonicityconstraints only, problem (\ref{ls2}) is the classical monotonicregression problem, which can be solved efficiently by some of theavailable monotonic regression algorithms. This solution is used thenfor producing the optimal solution to problem (\ref{ls2}) in thepresence of all the constraints. We present results of numericalexperiments to illustrate the efficiency of our algorithms.
|
|
| 6. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions
- 2011
-
Rapport (övrigt vetenskapligt)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.
|
|
| 7. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
New optimization algorithms for large-scale isotonic regression in L2-norm
- 2007
-
Ingår i: EUROPT-OMS Conference on Optimization,2007. - University of Hradec Kralove, Czech Republic : Guadeamus. ; s. 44-44
-
Konferensbidrag (övrigt vetenskapligt)abstract
- Isotonicregression problem (IR) has numerous important applications instatistics, operations research, biology, image and signalprocessingand other areas. IR in L2-norm is a minimization problem in whichtheobjective function is the squared Euclidean distance from a givenpointto a convex set defined by monotonicity constraints of the form:i-thcomponent of the decision vector is less or equal to its j-thcomponent. Unfortunately, the conventional optimization methods areunable to solve IR problems originating from large data sets.The existing IR algorithms, such as the minimum lower setsalgorithm byBrunk, the min-max algorithm by Lee, the network flow algorithm byMaxwell & Muchstadt and the IBCR algorithm by Block et al. areable tofind exact solution to IR problem for at most a few thousands ofvariables. The IBCR algorithm, which proved to be the mostefficient ofthem, is not robust enough. An alternative approach is related tosolving IR problem approximately. Following this approach, Burdakovetal. developed an algorithm, called GPAV, whose block refinementextension,GPAVR, is able to solve IR problems with a very high accuracy in afarshorter time than the exact algorithms. Apart from this, GPAVR is avery robust algorithm, and it allows us to solve IR problems withoverhundred thousands of variables.In this talk, we introduce new exact IR algorithms, which can beviewedas active set methods. They use the approximate solution producedbythe GPAVR algorithm as a starting point. We present results of ournumerical experiments demonstrating the high efficiency of the newalgorithms, especially for very large-scale problems, and theirrobustness. They are able to solve the problems which all existingexact IR algorithms fail to solve.
|
|
| 8. |
|
|
| 9. |
- 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. - 978-981-02-2382-3 - 978-981-279-886-2 ; s. 17-24
-
Bokkapitel (övrigt vetenskapligt)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.
|
|
| 10. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Optimization methods for postprocessing finite element solutions
- 2007
-
Ingår i: International Conference on Numerical Optimization and Numerical Linear Algebra,2007.
-
Konferensbidrag (övrigt vetenskapligt)abstract
- Simulation of transport phenomena based on advection-diffusion equationis very popular in many engineering applications. Non-monotonicity ofthe numerical solution is the typical drawback of the conventionalmethods of approximation, such as finite elements (FE), finite volumes,and mixed finite elements. The problem of monotonicity isparticularly important in cases of highly anisotropic diffusion tensorsor distorted unstructured meshes. For instance, in the nuclear wastetransport simulation, the non-monotonicity results in the presence ofnegative concentrations which may lead to unacceptable concentrationand chemistry calculations failure. Another drawback of the conventionalmethods is a possible violation of the discrete maximum principle, whichestablishes 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 recoveringthe monotonicity and some other important properties that may not beexhibited by $\bar{x}$.The mathematical formulation of the postprocessing problemis reduced to the following convex quadratic programming problem%Given the FE solution $\bar{x} \in R^n$, find $x_* \in R^n$ which%solves the list-distance problem.\begin{equation}\label{ls2}\begin{array}{cl}\mbox{min} & \|x-\bar{x}\|^2 \\\mbox{s.t.} & Mx \ge 0, \\ & l \le x \le u, \\ & e^Tx = m.\end{array}\end{equation}The set of constraints $Mx \ge 0$ represents here the monotonicityrequirements. It establishes relations between some of the adjacentmesh 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 fromthe discrete maximum principle. In the last constraint, $e=(1,1, \ldots ,1)^T \in R^n$. It formulates the conservativityrequirement.The postprocessing based on (\ref{ls2}) is typically a large scaleproblem. We introduce here algorithms for solving this problem. Theyare based on the observation that, in the presence of the monotonicityconstraints only, problem (\ref{ls2}) is the classical monotonicregression problem, which can be solved efficiently by some of theavailable monotonic regression algorithms. This solution is used thenfor producing the optimal solution to problem (\ref{ls2}) in thepresence of all the constraints. We present results of numericalexperiments to illustrate the efficiency of our algorithms.
|
|
