Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards a multigrid method for the minimum-cost flow problem
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a first step towards a multigrid method for solving the min-cost flow problem. Specifically, we present a strategy that takes advantage of existing black-box fast iterative linear solvers, i.e. algebraic multigrid methods. We show with standard benchmarks that, while less competitive than combinatorial techniques on small problems that run on a single core, our approach scales well with problem size, complexity, and number of processors, allowing for tackling large-scale problems on modern parallel architectures. Our approach is based on combining interior-point with multigrid methods for solving the nonlinear KKT equations via Newtons method. However, the Jacobian matrix arising in the Newton iteration is indefinite and its condition number cannot be expected to be bounded. In fact, the eigenvalues of the Jacobian can both vanish and blow up near the solution, leading to a significant slow-down of the convergence speed of iterative solvers - or to the loss of convergence at all. In order to allow for the application of multigrid methods, which have been originally designed for elliptic problems, we furthermore show that the occurring Jacobian can be interpreted as the stiffness matrix of a mixed formulation of the weighted graph Laplacian of the network, whose metric depends on the slack variables and the multipliers of the inequality constraints. Together with our regularization, this allows for the application of a black-box algebraic multigrid method on the Schur-complement of the system.
rate research
Read More
This paper gives a localized method for the multi-commodity flow problem. We relax both the capacity constraints and flow conservation constraints, and introduce a congestion function $psi$ for each arc and $height$ function $h$ for each vertex and commodity. If the flow exceeds the capacity on arc $a$, arc $a$ would have a congestion cost. If the flow into the vertex $i$ is not equal to that out of the vertex for commodity $k$, vertex $i$ would have a height, which is positively related to the difference between the amount of the commodity $k$ into the vertex $i$ and that out of the vertex. Based on the height function $h$ and the congestion function $psi$, a new conception, stable pseudo-flow, is introduced, which satisfies the following conditions: ($mathrm{i}$) for any used arc of commodity $k$, the height difference between vertex $i$ and vertex $j$ is equal to the congestion of arc $(i,j)$; ($mathrm{ii}$) for any unused arc of commodity $k$, the height difference between vertex $i$ and vertex $j$ is less than or equal to the congestion of arc $(i,j)$. If the stable pseudo-flow is a nonzero-stable pseudo-flow, there exists no feasible solution for the multi-commodity flow problem; if the stable pseudo-flow is a zero-stable pseudo-flow, there exists feasible solution for the multi-commodity flow problem and the zero-stable pseudo-flow is the feasible solution. Besides, a non-linear description of the multi-commodity flow problem is given, whose solution is stable pseudo-flow. And the non-linear description could be rewritten as convex quadratic programming with box constraints. Rather than examine the entire network to find path, the conclusion in this paper shows that the multi-commodity flow problem could be solved in a localized manner by looking only at the vertex and its neighbors.
The key element of the approach to the theory of necessary conditions in optimal control discussed in the paper is reduction of the original constrained problem to unconstrained minimization with subsequent application of a suitable mechanism of local analysis to characterize minima of (necessarily nonsmooth) functionals that appear after reduction. Using unconstrained minimization at the crucial step of obtaining necessary conditions definitely facilitates studies of new phenomena and allows to get more transparent and technically simple proofs of known results. In the paper we offer a new proof of the maximum principle for a nonsmooth optimal control problem (in the standard Pontryagin form) with state constraints and then prove a new second order condition for a strong minimum in the same problem but with data differentiable with respect to the state and control variables. The role of variational analysis is twofold. Conceptually, the main considerations behind the reduction are connected with metric regularity and Ekelands principle. On the other hand, technically, calculation of subdifferentials of components of the functionals that appear after the reduction is an essential part of the proofs.
The subgradient extragradient method for solving the variational inequality (VI) problem, which is introduced by Censor et al. cite{CGR}, replaces the second projection onto the feasible set of the VI, in the extragradient method, with a subgradient projection onto some constructible half-space. Since the method has been introduced, many authors proposed extensions and modifications with applications to various problems. In this paper, we introduce a modified subgradient extragradient method by improving the stepsize of its second step. Convergence of the proposed method is proved under standard and mild conditions and primary numerical experiments illustrate the performance and advantage of this new subgradient extragradient variant.
In this paper, we show that for a minimal pose-graph problem, even in the ideal case of perfect measurements and spherical covariance, using the so-called wrap function when comparing angles results in multiple suboptimal local minima. We numerically estimate regions of attraction to these local minima for some numerical examples, and give evidence to show that they are of nonzero measure. In contrast, under the same assumptions, we show that the textit{chordal distance} representation of angle error has a unique minimum up to periodicity. For chordal cost, we also search for initial conditions that fail to converge to the global minimum, and find that this occurs with far fewer points than with geodesic cost.
This paper is concerned with a class of zero-norm regularized piecewise linear-quadratic (PLQ) composite minimization problems, which covers the zero-norm regularized $ell_1$-loss minimization problem as a special case. For this class of nonconvex nonsmooth problems, we show that its equivalent MPEC reformulation is partially calm on the set of global optima and make use of this property to derive a family of equivalent DC surrogates. Then, we propose a proximal majorization-minimization (MM) method, a convex relaxation approach not in the DC algorithm framework, for solving one of the DC surrogates which is a semiconvex PLQ minimization problem involving three nonsmooth terms. For this method, we establish its global convergence and linear rate of convergence, and under suitable conditions show that the limit of the generated sequence is not only a local optimum but also a good critical point in a statistical sense. Numerical experiments are conducted with synthetic and real data for the proximal MM method with the subproblems solved by a dual semismooth Newton method to confirm our theoretical findings, and numerical comparisons with a convergent indefinite-proximal ADMM for the partially smoothed DC surrogate verify its superiority in the quality of solutions and computing time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
