共查询到20条相似文献,搜索用时 0 毫秒
1.
M. S. Babynin V. G. Zhadan 《Computational Mathematics and Mathematical Physics》2008,48(10):1746-1767
The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved. 相似文献
2.
Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming 总被引:3,自引:0,他引:3
In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an -approximate solution of an SDP in O(n2ln(1/)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.Research supported in part by the Singapore-MIT alliance, and NUS Academic Research Grant R-146-000-032-112.Mathematics Subject Classification (1991): 90C05, 90C30, 65K05 相似文献
3.
4.
5.
In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially effcient. 相似文献
6.
In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective. 相似文献
7.
8.
1.IntroductionSemidefiniteprogrammingunifiesquiteanumberofstandardmathematicalprogrammingproblems,suchaslinearprogrammingproblems,quadraticminimizationproblemswithconvexquadraticconstraints.Italsofindsmanyapplicationsinengineering,control,andcombinatorialoptimization[l,2].Inthepastfewyears,aquitenumberofresearchworkbasedoninteriorpointmethodsgaveattentiontoparametricsemidefiniteprogrammingproblems[3,4]fwherediscussionsaremostlyrelatedtopostoptimalandparametricanalysis.Inthispapergwefocusoureff… 相似文献
9.
Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases .
10.
In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can
be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We
derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite
completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch
of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite
problems into smooth convex–concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency
. Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.
相似文献
11.
《Optimization》2012,61(3):413-427
The hypergraph minimum bisection (HMB) problem is the problem of partitioning the vertices of a hypergraph into two sets of equal size so that the total weight of hyperedges crossing the sets is minimized. HMB is an NP-hard problem that arises in numerous applications – for example, in digital circuit design. Although many heuristics have been proposed for HMB, there has been no known mathematical program that is equivalent to HMB. As a means of shedding light on HMB, we study the equivalent, complement problem of HMB (called CHMB), which attempts to maximize the total weight of non-crossing hyperedges. We formulate CHMB as a quadratically constrained quadratic program, considering its semidefinite programming relaxation and providing computational results on digital circuit partitioning benchmark problems. We also provide results towards an approximation guarantee for CHMB. 相似文献
12.
We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence
of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices,
an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric
matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the
strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold .
The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The
research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the
National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation
of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars,
State Education Ministry, China. 相似文献
13.
《Operations Research Letters》2021,49(2):164-170
Stochastic semidefinite programming (SSDP) is a new class of optimization problems with a wide variety of applications. In this article, asymptotic analysis results of sample average approximation estimator for SSDP are established. Asymptotic analysis result already existing for stochastic nonlinear programming is extended to SSDP, that is, the conditions ensuring the convergence in distribution of sample average approximation estimator for SSDP to a multivariate normal are obtained and the corresponding covariance matrix is described in a closed form. 相似文献
14.
对于集值映射多目标半定规划问题, 在近似锥-次类凸的框架下, 建立了含矩阵和向量的择一性定理, 给出了问题的epsilon-弱有效解的epsilon-Lagrange乘子定理及标量化定理和epsilon-弱鞍点定理. 相似文献
15.
16.
Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming
(SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal
solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds
obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present
explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and
NT directions.
Received: December 1999 / Accepted: January 2001?Published online March 22, 2001 相似文献
17.
18.
In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation
of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic
center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity
condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function
of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming
case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain
a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the
constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due
to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based
on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right
hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since
a similar set for which the primal-dual Slater condition holds is always open.
Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001 相似文献
19.
In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization
problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems,
as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive
semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis
of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation
result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain
the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM
J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating
those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and
that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain
an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite.
This research was supported in part by NSF grant DMS-0306611. 相似文献
20.
This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method. 相似文献