排序方式: 共有42条查询结果,搜索用时 0 毫秒
1.
To minimize a convex function, we combine Moreau-Yosida regularizations, quasi-Newton matrices and bundling mechanisms. First
we develop conceptual forms using “reversal” quasi-Newton formulae and we state their global and local convergence. Then,
to produce implementable versions, we incorporate a bundle strategy together with a “curve-search”. No convergence results
are given for the implementable versions; however some numerical illustrations show their good behaviour even for large-scale
problems. 相似文献
2.
Ilse Fischer Gerald Gruber Franz Rendl Renata Sotirov 《Mathematical Programming》2006,105(2-3):451-469
We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary
number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only
a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple
semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition
problem, which are not achievable by direct approaches based only on interior-point methods.
Received: April, 2004
The last author gratefully acknowledges the support from the Austrian Science Foundation FWF Project P12660-MAT. 相似文献
3.
Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs 总被引:3,自引:0,他引:3
Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give a posteriori error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining the approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig—Wolfe decomposition method. 相似文献
4.
Nicola Maria Pugno 《Journal of the mechanics and physics of solids》2010,58(9):1397-1410
The study reported in this paper suggests that the influence of the surrounding nanotubes in a bundle is nearly identical to that of a liquid having surface tension equal to the surface energy of the nanotubes. This surprising behaviour is supported by the calculation of the polygonization and especially of the self-collapse diameters, and related dog-bone configurations, of nanotubes in a bundle, in agreement with atomistic simulations and nanoscale experiments. Accordingly, we have evaluated the strength of the nanotube bundle, with or without collapsed nanotubes, assuming a sliding failure: the self-collapse can increase the strength up to a value of about ∼30%, suggesting the design of self-collapsed super-strong nanotube bundles.Other systems, such as peapods and fullerites, can be similarly treated, including the effect of the presence of a liquid, as reported in the appendices. 相似文献
5.
Andreas E. Schroth 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》1999,69(1):211-227
Every flat Laguerre plane that satisfies a certain variation of the Miquel Condition is ovoidal. Equivalently, in flat Laguerre
planes a certain special version of the Bundle Theorem already implies the Bundle Theorem. 相似文献
6.
O. Briant C. Lemaréchal Ph. Meurdesoif S. Michel N. Perrot F. Vanderbeck 《Mathematical Programming》2008,113(2):299-344
When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate
and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear
programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better
theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method;
our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques
used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for
five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot
sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.
This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”. 相似文献
7.
For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual
track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the
algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent.
The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough.
Dedicated to Terry Rockafellar who has had a great influence on our work via strong support for proximal points and for structural
definitions that involve tangential convergence.
On leave from INRIA Rocquencourt
Research of the first author supported by the National Science Foundation under Grant No. DMS-0071459 and by CNPq (Brazil)
under Grant No. 452966/2003-5. Research of the second author supported by FAPERJ (Brazil) under Grant No.E26/150.581/00 and
by CNPq (Brazil) under Grant No. 383066/2004-2. 相似文献
8.
Maria Chiara Brambilla 《Mathematische Nachrichten》2008,281(4):499-516
We are interested in those bundles C on ?N which admit a resolution of the form 0 → ?s ? E ?t ? F → C → 0. In this paper we prove that, under suitable conditions on (E, F), a generic bundle with this form is either simple or canonically decomposable. As applications we provide an easy criterion for the stability of such bundles on ?2 and we prove the stability when E = ??, F = ??(1) and C is an exceptional bundle on ?N for N ≥ 2. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
9.
Horst Martini 《Discrete Mathematics》2009,309(16):5158-5168
It is well known that the famous covering problem of Hadwiger is completely solved only in the planar case, i.e.: any planar convex body can be covered by four smaller homothetical copies of itself. Lassak derived the smallest possible ratio of four such homothets (having equal size), using the notion of regular 4-covering. We will continue these investigations, mainly (but not only) referring to centrally symmetric convex plates. This allows to interpret and derive our results in terms of Minkowski geometry (i.e., the geometry of finite dimensional real Banach spaces). As a tool we also use the notion of quasi-perfect and perfect parallelograms of normed planes, which do not differ in the Euclidean plane. Further on, we will use Minkowskian bisectors, different orthogonality types, and further notions from the geometry of normed planes, and we will construct lattice coverings of such planes and study related Voronoi regions and gray areas. Discussing relations to the known bundle theorem, we also extend Miquel’s six-circles theorem from the Euclidean plane to all strictly convex normed planes. 相似文献
10.
Christian Wolf Csaba I. Fábián Achim Koberstein Leena Suhl 《European Journal of Operational Research》2014
Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the aggregate and the disaggregate version. In this study we report our experiments with a special convex programming method applied to the aggregate master problem. The convex programming method is of the type that uses an oracle with on-demand accuracy. We use a special form which, when applied to two-stage stochastic programming problems, is shown to integrate the advantages of the traditional variants while avoiding their disadvantages. On a set of 105 test problems, we compare and analyze parallel implementations of regularized and unregularized versions of the algorithms. The results indicate that solution times are significantly shortened by applying the concept of on-demand accuracy. 相似文献