一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

半定规划的逆问题

本文提出了半定规划的逆问题,利用半定规划的最优性条件,分别给出了其在ｌ∞,ｌ１,ｌ２ 模意义下的数学模型,它们仍为半定规划问题．     

非线性半定规划若干进展

讨论非线性半定规划的四个专题,包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法．     

非线性半定规划若干进展

讨论非线性半定规划的四个专题, 包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法.     

半定规划的一种修正原对偶内点算法研究

提出了半定规划(SDP)的一种修正的原对偶内点算法,对初始点的选取进行了改进,提高了算法的计算效率,并证明了新算法的迭代复杂性是O(n).     

关于半定规划的一种宽邻域不可行内点算法的注记

针对半定规划的宽邻域不可行内点算法, 将牛顿法和预估校正法进行结合, 构造出适当的迭代方向, 提出一个修正的半定规划宽邻域不可行内点算法, 并在适当的假设条件下, 证明了该算法具有O(\sqrt{n}L)的迭代复杂界．最后利用Matlab编程, 给出了基于KM方向和NT方向的数值实验结果．     

解半定规划的二次摄动方法

半定规划在系统论,控制论,组合优化,和特征值优化等领域有着广泛的应用。本文将半定规划摄动成二次半定规划,它的唯一解恰为原问题的解,并且对其偶问题等价于一个线性对称的投影方程,可方便地用投影收缩方法求解,从而获得原半定规划问题的解。文章给出了算法及其收敛性分析,数值试验结果表明摄动方法是解半定规划的一种有效的方法。     

二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性

主要是将半定规划(Semidefinite Programming,简称SDP)的内点算法推广到二次半定规划(Quadratic Semidefinite Programming,简称QSDP),重点讨论了其中搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的H..K..M搜索方向,接着证明了该搜索方向的存在唯一性,最后给出了搜索方向的具体计算方法.     

凸二次半定规划一个新的原始对偶路径跟踪算法

本文提出求解凸二次半定规划的一个新的原始对偶路径跟踪算法.在每次迭代中,通过求解一个线性方程组产生搜索方向.在一定条件下证明算法产生的迭代点列落在中心路径的邻域内,且算法至多经■次迭代可得到一个ε-最优解.     

二次半定规划的增广拉格朗日算法

基于变换X=VV~T,本文将半定规划问题转换为非线性规划问题,提出了解决此问题的增广拉格朗日算法,并证明了算法的线性收敛性.在此算法中,每一次迭代计算的子问题利用最速下降搜索方向和满足wolf条件的线性搜索法求最优解.数值实验表明,此算法是行之有效的,且优于内点算法.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

图的最大二等分问题的非线性规划算法

基于图的最大二等分问题的半定规划松驰模型 ,本文提出一个非线性规划算法求解该模型 ,得到该半定规划松驰模型的一个次优解 ,并且给出算法的收敛性证明 .数值试验表明该方法可以有效地求解图的最大二等分问题的松驰模型     

APPOXIMATION ALGORITHM FOR MAX—BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

Using outward rotations,we obtain an approximation algorithm for Max-Bisection problem,i.e.,Partitioning the vertices of an unirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges.In many interesting cases,the algorithm performs better than the algorithms of Ye and of Halperin and Zwick .The main tool used to obtain this result is semidefinite programming.     

Semidefinite Programming Relaxation for Nonconvex Quadratic Programs

This paper applies the SDP (semidefinite programming)relaxation originally developed for a 0-1 integer program to ageneral nonconvex QP (quadratic program) having a linear objective functionand quadratic inequality constraints, and presents some fundamental characterizations of the SDP relaxation including its equivalence to arelaxation using convex-quadratic valid inequalities for the feasible regionof the QP.     

半定规划的PRP~+共轭梯度法(英文)

本文对半定规划(SDP)的最优性条件提出一价值函数并研究其性质.基此,提出半定规划的PRP+共轭梯度法.为得到PRP+共轭梯度法的收敛性,提出一Armijo-型线搜索.无需水平集有界及迭代点列聚点的存在,算法全局收敛.     

半定规划的非内点连续化方法

基于Fischer-Burmeister函数,本文将半定规划(SDP)的中心路径条件转化为非线性方程组,进而用SDCP的非内点连续化方法求解之.证明了牛顿方向的存在性,迭代点列的有界性.在适当的假设条件下,得到算法的全局收敛性及局部二次收敛率.数值结果表明算法的有效性.     

Optimality Conditions in Semidefinite Programming

Semidefinite positiveness of operators on Euclidean spaces is characterized. Using this characterization, we compute in a direct way the first-order and second-order tangent sets to the cone of semidefinite positive operators on such a space. These characterizations are useful for optimality conditions in semidefinite programming.     

Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming

We prove the superlinear convergence of the primal-dual infeasible interior-point path-following algorithm proposed recently by Kojima, Shida, and Shindoh and by the present authors, under two conditions: (i) the semidefinite programming problem has a strictly complementary solution; (ii) the size of the central path neighborhood approaches zero. The nondegeneracy condition suggested by Kojima, Shida, and Shindoh is not used in our analysis. Our result implies that the modified algorithm of Kojima, Shida, and Shindoh, which enforces condition (ii) by using additional corrector steps, has superlinear convergence under the standard assumption of strict complementarity. Finally, we point out that condition (ii) can be made weaker and show the superlinear convergence under the strict complementarity assumption and a weaker condition than (ii).     

Approximate Toeplitz Matrix Problem Using Semidefinite Programming

Given a data matrix, we find its nearest symmetric positive-semidefinite Toeplitz matrix. In this paper, we formulate the problem as an optimization problem with a quadratic objective function and semidefinite constraints. In particular, instead of solving the so-called normal equations, our algorithm eliminates the linear feasibility equations from the start to maintain exact primal and dual feasibility during the course of the algorithm. Subsequently, the search direction is found using an inexact Gauss-Newton method rather than a Newton method on a symmetrized system and is computed using a diagonal preconditioned conjugate-gradient-type method. Computational results illustrate the robustness of the algorithm.     

Penalty and Barrier Methods for Convex Semidefinite Programming

In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.