排序方式: 共有51条查询结果,搜索用时 15 毫秒
21.
The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with Semidefinite Programming, SDP. 相似文献
22.
LetG=(N,E) be an undirected graph. We present several new techniques for partitioning the node setN intok disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful. 相似文献
23.
W. R. S. Sutherland H. Wolkowicz V. Zeidan 《Journal of Optimization Theory and Applications》1988,58(2):319-330
For a given vectorx
0, the sequence {x
t} which optimizes the sum of discounted rewardsr(x
t, xt+1), wherer is a quadratic function, is shown to be generated by a linear decision rulex
t+1=Sx
t
+R. Moreover, the coefficientsR,S are given by explicit formulas in terms of the coefficients of the reward functionr. A unique steady-state is shown to exist (except for a degenerate case), and its stability is discussed. 相似文献
24.
Maziar Salahi Akram Taati Henry Wolkowicz 《Computational Optimization and Applications》2017,66(2):223-244
We study large-scale extended trust-region subproblems (eTRS) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust-region subproblem (TRS) but with an additional linear inequality constraint. It is well known that strong duality holds for the TRS and that there are efficient algorithms for solving large-scale TRS problems. It is also known that there can exist at most one local non-global minimizer (LNGM) for TRS. We combine this with known characterizations for strong duality for eTRS and, in particular, connect this with the so-called hard case for TRS. We begin with a recent characterization of the minimum for the TRS via a generalized eigenvalue problem and extend this result to the LNGM. We then use this to derive an efficient algorithm that finds the global minimum for eTRS by solving at most three generalized eigenvalue problems. 相似文献
25.
Abdo Y. Alfakih Amir Khandani Henry Wolkowicz 《Computational Optimization and Applications》1999,12(1-3):13-30
Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed. 相似文献
26.
Bob Grone Charles Johnson E. Marques De Sa Henry Wolkowicz 《Linear and Multilinear Algebra》2013,61(1-4):305-322
We study several bounds for the determinant of an n × n positive definite Hermitian matrix A. These bounds are the best possible given certain data about A. We find the best bounds in the cases that we are given: (i) the diagonal elements of A: (ii) the traces trA,tr A 2 and n and (iii)n, tr A tr A 2 and the diagonal elements of A. In case (i) we get the well known Hadamard inequality. The other bounds are Hadamard type bounds. The bounds are found using optimization techniques. 相似文献
27.
We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the coneswhere
is the elliptope (set of correlation matrices) and
is the (closed convex) cone of EDMs.we havefor some scalar independent of i. 相似文献
The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ1,λ2,…,λn such that
∑j=1nλjpj=0, ∑j=1nλj=0,
∑j=1nλjpi−pj2= forall i=1,…,n,
28.
The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective, q 0(x)→min, subject to an upper and lower bounded general quadratic constraint, ?≤q 1(x)≤u. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this implicitly convex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in Fortin and Wolkowicz (Optim. Methods Softw. 19(1):41–67, 2004) and Rendl and Wolkowicz (Math. Program. 77(2, Ser. B):273–299, 1997) can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper. 相似文献
29.
Semidefinite programming 总被引:5,自引:0,他引:5
30.