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

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

一类二次半定规划内点算法的搜索方向

利用牛顿法求解一类二次半定规划的扰动KKT方程组,得出这类二次半定规划原始-对偶路径跟踪算法搜索方向求解的统一形式,以及HKM搜索方向和NT搜索方向存在唯一的充分条件,最后给出了计算搜索方向的表达式,和特殊情况下搜索方向的计算方法.     

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

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

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

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

半定规划的一个新的宽邻域非可行内点算法

基于一种新的宽邻域,提出一个求解半定规划的新的非可行内点算法．在适当的假设条件下,证明了该算法具有较好的迭代复杂界O（√nL）,优于目前此类算法的最好的复杂性O（n√nL）,等同于可行内点算法．     

半定规划的一种非精确不可行内点法

本文给出了求解半定规划的一种基于KM方向的非精确不可行内点法 ,分析了其收敛性 ,结果表明 ,该算法最多可以在O(n2 ln( 1 /ε) )步内求出半定规划的一个ε 近似解 ,与YZhang所提出的精确不可行内点法有相同的界 .     

二阶锥权互补问题的非精确非内点连续化算法

基于二阶锥权互补函数,将二阶锥权互补问题转化为一个方程组,运用非精确非内点连续化算法求解该方程组.该算法能以任意点作为初始点,且每次迭代时至多求解一个方程组.为节省算法求解方程组时的计算时间和内存,将非精确牛顿法引入到算法中.在适当假设下,证明了该算法是全局与局部二阶收敛的.最后数值实验表明了算法的良好性能.     

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

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

半定规划的近似中心投影法

1．引言半定规划问题标准形的数学形式是这里C，AIEIR”””及变量XEIRn“”为对称矩阵，Tr（·）表示矩阵的迹，用符号＞0和三0分别表示矩阵正定和半正定．由于半定规划在控制论，结构优化，组合优化方面有重要应用［1，3，16，17］以及线性规划内点法取得的巨大成就［7］，将线性规划的内点法推广到半定规划上，是数学规划领域内近年来受到重视的一个研究课题．线性规划内点法中的势函数下降法［10，16］原始对偶中心路径跟踪法［2，4，8，9，11。15］已经先后被推广到半定规划上．ROOS－Visl近似中心法则是求解线性规划的另一类内…     

P0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于P0函数非线性互补问题提出了一个基于Kanzow光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性.特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Jacobi阵是Lipschitz连续的.文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的.本文提出的方法在每一次迭代只须解一个线性方程式组.     

一个新的求解二阶锥规划的非内部连续化算法

基于光滑Fischer-Burmeister函数,本文给出一个新的求解二阶锥规划的非内部连续化算法.算法对初始点的选取没有任何限制,并且在每一步迭代只需求解一个线性方程组并进行一次线性搜索.在不需要满足严格互补条件下,证明了算法是全局收敛且是局部超线性收敛的.数值试验表明算法是有效的.     

Identification of the Optimal Active Set in a Noninterior Continuation Method for LCP

This paper concerns about the possibility of identifying the active set in a noninterior continuation method for solving the standard linear complementarity problem based on the algorithm and theory presented by Burke and Xu (J. Optim. Theory Appl. 112 (2002) 53). It is shown that under the assumptions of P-matrix and nondegeneracy, the algorithm requires at most Olog(₀₀/)) iterations to find the optimal active set, where ₀ is the width of the neighborhood which depends on the initial point, ₀> 0 is the initial smoothing parameter, is a positive number which depends on the problem and the initial point, and is a small positive number which depends only on the problem.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

求解一类非线性规划的连续同伦方法(英文)

In this paper we present a homotopy continuation method for finding the Karush-Kuhn-Tucker point of a class of nonlinear non-convex programming problems. Two numerical examples are given to show that this method is effective. It should be pointed out that we extend the results of Lin et al. （see Appl. Math. Comput., 80（1996）, 209-224） to a broader class of non-convex programming problems.     

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.     

连续化方法求解一般无界非凸规划的K-K-T点

给出了求解无界非凸规划的K-K-T系统的一种连续化方法,在适当的条件下,得到了连接可行域内部任意给定的点和非凸规划的K-K-T点的同伦路径存在性的构造性证明,从而构建了可数值实现的全局收敛性算法.数值算例进一步验证了本文结果的有效性.     

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).     

Superlinear Noninterior One-Step Continuation Method for Monotone LCP in the Absence of Strict Complementarity

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).