共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone
operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to
a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly
in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem
has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion
introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto
intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible
since it amounts, at most, to solving a linear system of two equations in two unknowns.
Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999 相似文献
2.
Hans Detlef Mittelmann 《Numerische Mathematik》1981,36(4):375-387
Summary We consider nonlinear variational inequalities corresponding to a locally convex minimization problem with linear constraints of obstacle type. An efficient method for the solution of the discretized problem is obtained by combining a slightly modified projected SOR-Newton method with the projected version of thec g-accelerated relaxation method presented in a preceding paper. The first algorithm is used to approximately reach in relatively few steps the proper subspace of active constraints. In the second phase a Kuhn-Tucker point is found to prescribed accuracy. Global convergence is proved and some numerical results are presented. 相似文献
3.
Arian Novruzi 《Numerische Mathematik》2001,88(1):185-201
Summary. In this paper we establish a error estimation on the boundary for the solution of an exterior Neumann problem in . To solve this problem we consider an integral representation which depends from the solution of a boundary integral equation.
We use a full piecewise linear discretisation which on one hand leads to a simple numerical algorithm but on the other hand
the error analysis becomes more difficult due to the singularity of the integral kernel. We construct a particular approximation
for the solution of the boundary integral equation, for the solution of the Neumann problem and its gradient on the boundary
and estimate their error.
Received May 11, 1998 / Revised version received July 7, 1999 / Published online August 24, 2000 相似文献
4.
Summary. We propose an algorithm for the numerical solution of
large-scale symmetric positive-definite linear complementarity problems.
Each step of the algorithm combines an application of the successive
overrelaxation
method with projection (to determine an approximation of the optimal active
set) with the preconditioned conjugate gradient method (to solve the reduced
residual systems of linear equations). Convergence of the iterates to the
solution is proved. In the experimental part we compare the efficiency of the
algorithm with several other methods. As test example we consider the
obstacle problem with different obstacles.
For problems of dimension up to 24\,000 variables, the algorithm finds the
solution in less then 7 iterations, where each iteration
requires about 10
matrix-vector multiplications.
Received July 14, 1993 / Revised version received February 1994 相似文献
5.
Dariusz R. Kowalski Eyal Nussbaum Michael Segal Vitaly Milyeykovsky 《Optimization Letters》2014,8(2):777-799
In this paper we consider online scheduling problems for linear topology under various objective functions: minimizing the maximum completion time, minimizing the largest delay, and minimizing the sum of completion times. We give optimal solutions for uni-directional version of the problem for each of the objectives and show that for the two-directional versions of each problem, no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions. We also propose 2-approximation on-line algorithms for the MinMakespan and the MinSum minimization objectives. We also prove that no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions for the weighted case of uni-directional scenarios. 相似文献
6.
Hongyuan Zha 《Numerische Mathematik》1996,72(3):391-417
Summary.
We present a numerical algorithm for computing a few
extreme generalized
singular values and corresponding vectors of a sparse
or structured matrix
pair .
The algorithm is based on the CS decomposition and
the Lanczos
bidiagonalization process.
At each iteration step of the
Lanczos process, the solution to
a linear least squares problem with
as
the coefficient matrix is approximately computed, and
this consists the only interface
of the algorithm with
the matrix pair .
Numerical results are also
given to demonstrate
the feasibility and efficiency of the algorithm.
Received
April 1, 1994 / Revised version received December 15, 1994 相似文献
7.
Kamal Jain 《Combinatorica》2001,21(1):39-60
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges
in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as
the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively
rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge
gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem.
Received March 6, 1998 相似文献
8.
We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem. 相似文献
9.
L. Pasquini 《Numerische Mathematik》2000,86(3):507-538
Summary. A general method for approximating polynomial solutions of second-order linear homogeneous differential equations with polynomial
coefficients is applied to the case of the families of differential equations defining the generalized Bessel polynomials,
and an algorithm is derived for simultaneously finding their zeros. Then a comparison with several alternative algorithms
is carried out. It shows that the computational problem of approximating the zeros of the generalized Bessel polynomials is
not an easy matter at all and that the only algorithm able to give an accurate solution seems to be the one presented in this
paper.
Received July 25, 1997 / Revised version received May 19, 1999 / Published online June 8, 2000 相似文献
10.
Convergent adaptive finite elements for the nonlinear Laplacian 总被引:3,自引:3,他引:0
Andreas Veeser 《Numerische Mathematik》2002,92(4):743-770
Summary. The numerical solution of the homogeneous Dirichlet problem for the p-Laplacian, , is considered. We propose an adaptive algorithm with continuous piecewise affine finite elements and prove that the approximate
solutions converge to the exact one. While the algorithm is a rather straight-forward generalization of those for the linear
case p=2, the proof of its convergence is different. In particular, it does not rely on a strict error reduction.
Received December 29, 2000 / Revised version received August 30, 2001 / Published online December 18, 2001
RID="*"
ID="*" Current address: Dipartimento di Matematica, Università degli Studi di Milano, Via C. Saldini 50, 20133 Milano, Italy; e-mail: veeser@mat.unimi.it 相似文献
11.
A cascadic multigrid algorithm for semilinear elliptic problems 总被引:12,自引:0,他引:12
Gisela Timmermann 《Numerische Mathematik》2000,86(4):717-731
Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear
finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer
grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton
systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution
within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that
the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity.
Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000 相似文献
12.
13.
We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively. 相似文献
14.
We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems. 相似文献
15.
Thomas Huckle 《Numerische Mathematik》1998,79(2):213-229
The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show
a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix
is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The
basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform
a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include
some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show
that this new algorithm is fast and reliable.
Received March 24, 1995 / Revised version received December 13, 1995 相似文献
16.
G. Saviozzi 《Discrete Applied Mathematics》1985,11(3):311-314
A method for handling degeneracy in linear complementarity problems is presented. It uses a sequential version of Lemke's algorithm [1] which, in the absence of degeneracy and in the case of copositive-plus matrices, finds an optimal solution or shows that none exists. The degeneracy phenomenon is overcome by modifying some constraining equations, without altering the feasible region of the problem. 相似文献
17.
Christian Kanzow 《Numerische Mathematik》2001,89(1):135-160
Summary. We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than
most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively
complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems
(like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines
the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension)
at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global
and local convergence properties. Some preliminary numerical results will also be given.
Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001 相似文献
18.
In this paper we study a class of cooperative games with non-transferable utility (NTU) derived from multiple objective linear
programs (MOLP's). This is done in order to introduce the NTU-Shapley value as a solution to multiple objective linear programming.
We present an algorithm for the computation of the set of all NTU-Shapley values for the bicriterion cases, which is based
on the simplex algorithm. Furthermore, we give a new optimal recursive procedure for the computation of the Shapley value
of TU-games.
Received: September 1997/Final version: May 1999 相似文献
19.
《European Journal of Operational Research》2005,161(3):663-672
We define a version of the Inverse Linear Programming problem that we call Linear Programming System Identification. This version of the problem seeks to identify both the objective function coefficient vector and the constraint matrix of a linear programming problem that best fits a set of observed vector pairs. One vector is that of actual decisions that we call outputs. These are regarded as approximations of optimal decision vectors. The other vector consists of the inputs or resources actually used to produce the corresponding outputs. We propose an algorithm for approximating the maximum likelihood solution. The major limitation of the method is the computation of exact volumes of convex polytopes. A numerical illustration is given for simulated data. 相似文献
20.
A multicriteria competitive Markov decision process 总被引:1,自引:0,他引:1
A. M. Rodrı´guez-Chı´a J. Puerto F. R. Fernández 《Mathematical Methods of Operations Research》2002,55(3):359-369