共查询到20条相似文献,搜索用时 15 毫秒
1.
Frank Vallentin 《Linear algebra and its applications》2009,430(1):360-369
This paper is a tutorial in a general and explicit procedure to simplify semidefinite programs which are invariant under the action of a symmetry group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra of the binary Hamming scheme in this framework. Here its connection to the orthogonal Hahn and Krawtchouk polynomials becomes visible. 相似文献
2.
Roland W. Freund 《Operations Research Letters》2004,32(2):126-132
We study the sensitivity of solutions of linear semidefinite programs under small arbitrary perturbations of the data. We present an elementary and self-contained proof of the differentiability of the solutions as functions of the perturbations, and we characterize the derivative as the solution of a system of linear equations. 相似文献
3.
theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for
block diagonal semidefinite programs, of which linear programming is a special case.
Received November 26, 1995 / Revised version received November 1, 1998
Published online February 25, 1999 相似文献
4.
Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. Semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. Semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1] and [2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models. 相似文献
5.
A general decomposition framework for large convex optimization problems based on augmented Lagrangians is described. The approach is then applied to multistage stochastic programming problems in two different ways: by decomposing the problem into scenarios and by decomposing it into nodes corresponding to stages. Theoretical convergence properties of the two approaches are derived and a computational illustration is presented. 相似文献
6.
Madhu V. Nayakkankuppam 《Mathematical Programming》2007,109(2-3):477-504
We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using
the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos
method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects
related to parallelism) are combined in an implementation called LAMBDA, which delivers faster solution times than previously
possible, and acceptable parallel scalability on sufficiently large problems.
This work was supported in part by NSF grants DMS-0215373 and DMS-0238008. 相似文献
7.
Entropic proximal decomposition methods for convex programs and variational inequalities 总被引:2,自引:0,他引:2
We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition
method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a
decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to
produce for the first time provably convergent decomposition schemes based on C
∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty
solution sets, global convergence of the primal-dual sequences produced by the algorithm is established.
Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001 相似文献
8.
《European Journal of Operational Research》1998,108(3):653-670
Incorporating uncertainty in optimization models gives rise to large, structured mathematical programs. Decomposition procedures are well-suited for parallelization, thus providing a promising venue for solving large stochastic programs arising in diverse practical applications. This paper presents an adaptation of decomposition methods for execution on distributed computing systems. A regularized decomposition, as well as the linear decomposition algorithm, are implemented for execution on distributed multiprocessors. Computational results on an IBM SP2 multiprocessor system are reported to demonstrate the comparative performance of the methods on a number of test cases. 相似文献
9.
Mathematical Programming - We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies... 相似文献
10.
When using interior point methods for solving semidefinite programs (SDP), one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. In this paper, we propose a trust region algorithm for solving SDP problems. At each iteration we perform a number of conjugate gradient iterations, but do not need to solve a system of linear equations. Under mild assumptions, the convergence of this algorithm is established. Numerical examples are given to illustrate the convergence results obtained. 相似文献
11.
Mituhiro Fukuda Bastiaan J. Braams Maho Nakata Michael L. Overton Jerome K. Percus Makoto Yamashita Zhengji Zhao 《Mathematical Programming》2007,109(2-3):553-580
It has been a long-time dream in electronic structure theory in physical chemistry/chemical physics to compute ground state
energies of atomic and molecular systems by employing a variational approach in which the two-body reduced density matrix
(RDM) is the unknown variable. Realization of the RDM approach has benefited greatly from recent developments in semidefinite
programming (SDP). We present the actual state of this new application of SDP as well as the formulation of these SDPs, which
can be arbitrarily large. Numerical results using parallel computation on high performance computers are given. The RDM method
has several advantages including robustness and provision of high accuracy compared to traditional electronic structure methods,
although its computational time and memory consumption are still extremely large.
The work of Mituhiro Fukuda was primarily conducted at the Courant Institute of Mathematical Sciences, New York University. 相似文献
12.
A symmetric tensor, which has a symmetric nonnegative decomposition, is called a completely positive tensor. In this paper, we characterize the completely positive tensor as a truncated moment sequence, and transform the problem of checking whether a tensor is completely positive to checking whether its corresponding truncated moment sequence admits a representing measure, then present a semidefinite algorithm to solve it. If a tensor is not completely positive, a certificate for it can be obtained; if it is completely positive, a nonnegative decomposition can be obtained. 相似文献
13.
Jean B. Lasserre 《Advances in Computational Mathematics》2016,42(5):1129-1148
Given all (finite) moments of two measures μ and λ on \(\mathbb {R}^{n}\), we provide a numerical scheme to obtain the Lebesgue decomposition μ = ν + ψ with ν?λ and ψ ⊥ λ. When ν has a density in \(L_{\infty }(\lambda )\) then we obtain two sequences of finite moments vectors of increasing size (the number of moments) which converge to the moments of ν and ψ respectively, as the number of moments increases. Importantly, no à priori knowledge on the supports of μ,ν and ψ is required. 相似文献
14.
K. C. Kiwiel 《Journal of Optimization Theory and Applications》1995,84(3):529-548
A proximal bundle method is presented for minimizing a nonsmooth convex functionf. At each iteration, it requires only one approximate evaluation off and its -subgradient, and it finds a search direction via quadratic programming. When applied to the Lagrangian decomposition of convex programs, it allows for inexact solutions of decomposed subproblems; yet, increasing their required accuracy automatically, it asymptotically finds both the primal and dual solutions. It is an implementable approximate version of the proximal point algorithm. Some encouraging numerical experience is reported.The author thanks two anonymous referees for their valuable comments.Research supported by the State Committee for Scientific Research under Grant 8550502206. 相似文献
15.
《Applied Mathematical Modelling》2002,26(10):1003-1018
In this paper the inverse solution of the general (non-linear) diffusion problem or backward heat conduction problem. It is assumed that the direct solution can be satisfactorily modelled, for example by the finite difference method. The nature of the problem and typical approaches to its solution are briefly reviewed.An operator-splitting method is introduced as a means of solving the inverse diffusion problem. An error analysis of the method is given, particularly for the application of the method to the simple diffusion equation. The method is applied to a range of test problems to illustrate the points of the analysis and to demonstrate the properties and performance of the method. 相似文献
16.
17.
Renato. D. C. Monteiro 《Mathematical Programming》2003,97(1-2):209-244
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first
concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming,
putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed
for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following
IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion
of matrix completion to exploit data sparsity.
Received: December 16, 2002 / Accepted: May 5, 2003
Published online: May 28, 2003
Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods
– nonlinear programming – Newton method – first-order methods – bundle method – matrix completion
The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084,
CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401.
Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51 相似文献
18.
We consider iterative methods for semidefinite systems Ax = b based on splittings A = B ? C, where B is not necessarily nonsingular. Necessary and sufficient conditions for convergence are obtained. These are then used to obtain convergence results for block SOR, block SSOR, and block JOR methods for matrices with semidefinite block diagonal. 相似文献
19.
A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
Renato D. C. Monteiro Camilo Ortiz Benar F. Svaiter 《Mathematical Programming Computation》2014,6(2):103-150
In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks. We then specialize the method to the context of conic semidefinite programming (SDP) problems consisting of two easy blocks of constraints. Without putting them in standard form, we show that four important classes of graph-related conic SDP problems automatically possess the above two-easy-block structure, namely: SDPs for $\theta $ -functions and $\theta _{+}$ -functions of graph stable set problems, and SDP relaxations of binary integer quadratic and frequency assignment problems. Finally, we present computational results on the aforementioned classes of SDPs showing that our method outperforms the three most competitive codes for large-scale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a Newton-CG augmented Lagrangian method, called SDPNAL, by Zhao et al., and a variant of the BP method, called the SPDAD method, by Wen et al. 相似文献
20.
In this paper we design higher-order time integrators for systems of stiff ordinary differential equations. We combine implicit Runge–Kutta and BDF methods with iterative operator-splitting methods to obtain higher-order methods. The idea of decoupling each complicated operator in simpler operators with an adapted time scale allows to solve the problems more efficiently. We compare our new methods with the higher-order fractional-stepping Runge–Kutta methods, developed for stiff ordinary differential equations. The benefit is the individual handling of each operator with adapted standard higher-order time integrators. The methods are applied to equations for convection–diffusion reactions and we obtain higher-order results. Finally we discuss the applications of the iterative operator-splitting methods to multi-dimensional and multi-physical problems. 相似文献