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

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

约束优化无罚函数非单调SQP算法

本文研究求解非线性约束优化问题.利用非单调无罚函数方法,提出了一个新的序列二次规划算法.该算法在每次迭代过程中只需求解一个QP子问题和一个线性方程组.在一般条件下,算法具有全局收敛性,数值结果表明,计算量小于单调且含罚函数的传统算法.     

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

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

一般约束优化基于识别函数的模松弛算法

借助于半罚函数和产生工作集的识别函数以及模松弛SQP算法思想, 本文建立了求解带等式及不等式约束优化的一个新算法. 每次迭代中, 算法的搜索方向由一个简化的二次规划子问题及一个简化的线性方程组产生. 算法在不包含严格互补性的温和条件下具有全局收敛性和超线性收敛性. 最后给出了算法初步的数值试验报告.     

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

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

一个求解广义圆锥互补问题的无导数光滑算法

本文研究了一个求解广义圆锥互补问题的无导数光滑算法.利用光滑函数将广义圆锥互补问题等价转化成一个光滑方程组,然后再利用牛顿法求解此方程组.该算法采用了一种新的非单调无导数线搜索技术,并且在适当条件下具有全局和局部二次收敛性质.数值实验结果表明算法是非常有效的.     

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

本文基于Nesterov-Todd方向,并引进中心路径测量函数以及原始对偶对数障碍函数,建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O(n|lnε|)次可得到一个ε最优解.论文最后报告了初步的数值试验结果.     

不可微合成函数的极小化方法

本文提出了一种极小化不可微合成函数的下降算法。该算法通过内部迭代寻找下降方向，每次内部迭代求解一个二次规划。外部迭代点不精确线搜索求得，算法在有限步内得到近似平稳点，经过适当修正后，算法全局收敛到平衡点。     

一个求解半正定规划问题的新原始-对偶内点算法

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n 10g n/ε)和O(√n log n/ε),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性.     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法,该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法,本文中的算法使用了不同的线性搜索和半空间,在计算本文所引的两个数值例子时,该算法比文献[10]中的算法所需迭代步更少.     

A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems

ABSTRACT

In this paper, we consider a class of sparse inverse semidefinite quadratic programming problems, in which a nonconvex alternating direction method of multiplier is investigated. Under mild conditions, we establish convergence results of our algorithm and the corresponding non-ergodic iteration-complexity is also considered under the assumption that the potential function satisfies the famous Kurdyka–?ojasiewicz property. Numerical results show that our algorithm is suitable to solve the given sparse inverse semidefinite quadratic programming problems.     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.     

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem

In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm. Finally, we test our code on an extended set of instances of the maxcut problem and we report comparisons with other existing codes.     

最大割问题的二次规划方法

本文给出了最大割问题的二次规划算法。这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界，然后用分支定界法得到了最大割问题的解。数值结果表明这种算法是非常有效的。     

A Dynamical Systems Analysis of Semidefinite Programming with Application to Quadratic Optimization with Pure Quadratic Equality Constraints

This paper considers the problem of minimizing a quadratic cost subject to purely quadratic equality constraints. This problem is tackled by first relating it to a standard semidefinite programming problem. The approach taken leads to a dynamical systems analysis of semidefinite programming and the formulation of a gradient descent flow which can be used to solve semidefinite programming problems. Though the reformulation of the initial problem as a semidefinite pro- gramming problem does not in general lead directly to a solution of the original problem, the initial problem is solved by using a modified flow incorporating a penalty function. Accepted 10 March 1998     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

A self-concordance property for nonconvex semidefinite programming

The paper considers nonconvex quadratic semidefinite problems. This class arises, for instance, as subproblems in the sequential semidefinite programming algorithm for solving general smooth nonlinear semidefinite problems. We extend locally the concept of self-concordance to problems that satisfy a weak version of the second order sufficient optimality conditions.     

Sequential Semidefinite Program for Maximum Robustness Design of Structures under Load Uncertainty

A robust structural optimization scheme as well as an optimization algorithm are presented based on the robustness function. Under the uncertainties of the external forces based on the info-gap model, the maximization of the robustness function is formulated as an optimization problem with infinitely many constraints. By using the quadratic embedding technique of uncertainty and the S-procedure, we reformulate the problem into a nonlinear semidefinite programming problem. A sequential semidefinite programming method is proposed which has a global convergent property. It is shown through numerical examples that optimum designs of various linear elastic structures can be found without difficulty.The authors are grateful to the Associate Editor and two anonymous referees for handling the paper efficiently as well as for helpful comments and suggestions.     

A parameterized hessian quadratic programming problem

We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.     

A parameterized hessian quadratic programming problem

We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem. This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.