A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF MAX-BISECTION

A successive quadratic programming algorithm for solving SDP relaxation of Max- Bisection is provided and its convergence result is given.The step-size in the algorithm is obtained by solving n easy quadratic equations without using the linear search technique.The numerical experiments show that this algorithm is rather faster than the interior-point method.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

边界约束二次规划问题的分解方法

１．引言本文考虑如下边界约束的二次规划问题：其中ＱＥ＊"""是对称的,Ｃ,人。Ｅ＊"是给定的常数向量,且Ｚ＜。这类问题经常出现在偏微分方程,离散化的连续时间最优控制问题、线性约束的最小二乘问题、工程设计、或作为非线性规划方法中的序列子问题．因此具有特殊的重要性．本文提出求解问题（１．１）的分解方法．它类似求解线性代数方程组的选代法,它是对Ｑ进行正则分裂【对即把Ｑ分裂为两个矩阵之和,Ｑ＝Ｎ十片而这两个矩阵之差（Ｎ一则是对称正定的．在每次迭代中用一个易于求解的矩阵Ｎ替代Ｑ进行计算一新的二次规划问题．在适…     

A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints

The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported. Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore.     

A SUBSPACE PROJECTED CONJUGATE GRADIENT ALGORITHM FOR LARGE BOUND CONSTRAINED QUADRATIC PROGRAMMING

A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At every iterative level, the search direction consists of two parts, one of which is a subspace trumcated Newton direction, another is a modified gradient direction. With the projected search the algorithm is suitable to large problems. The convergence of the method is proved and same numerical tests with dimensions ranging from 5000 to 20000 are given.     

Solving Nonlinear Programming Problems with Noisy Function Values and Noisy Gradients

An efficient algorithm for solving nonlinear programs with noisy equality constraints is introduced and analyzed. The unknown exact constraints are replaced by surrogates based on the bundle idea, a well-known strategy from nonsmooth optimization. This concept allows us to perform a fast computation of the surrogates by solving simple quadratic optimization problems, control the memory needed by the algorithm, and prove the differentiability properties of the surrogate functions. The latter aspect allows us to invoke a sequential quadratic programming method. The overall algorithm is of the quasi-Newton type. Besides convergence theorems, qualification results are given and numerical test runs are discussed.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

On Regularization Methods for Inverse Problems of Dynamic Type

In this paper, we consider new regularization methods for linear inverse problems of dynamic type. These methods are based on dynamic programming techniques for linear quadratic optimal control problems. Two different approaches are followed: a continuous and a discrete one. We prove regularization properties and also obtain rates of convergence for the methods derived from both approaches. A numerical example concerning the dynamic EIT problem is used to illustrate the theoretical results.     

A ROBUST TRUST REGION ALGORITHM FOR SOLVING GENERAL NONLINEAR PROGRAMMING

1. Introductioncrust region methods are iterative. As a strategy of globalization, the trust region approach was introduced into solving unconstrained optimization and proved to be efficient androbust. An excellent survey was given by Mor6(1983). The associated research with trustregion methods for unconstrained optimization can be found in Fletcher(1980), Powell(1975),Sorensen(1981), Shultz, Schnabel and Byrd(1985), Yuan(1985). The solution of the trust region subproblem is still an activ…     

二次规划逆问题的牛顿方法

针对二次规划逆问题,将其表达为带有互补约束的锥约束优化问题.借助于对偶理论,将问题转化为变量更少的线性互补约束非光滑优化问题.通过扰动的方法求解转化后的问题并证明了收敛性.采用非精确牛顿法求解扰动问题,给出了算法的全局收敛性与局部二阶收敛速度.最后通过数值实验验证了该算法的可行性.     

Parallel orthogonal factorization null-space method for dynamic quadratic programming

An algorithm has been developed to solve quadratic programs that have a dynamic programming structure. It has been developed for use as part of a parallel trajectory optimization algorithm and aims to achieve significant speed without sacrificing numerical stability. the algorithm makes use of the dynamic programming problem structure and the domain decomposition approach. It parallelizes the orthogonal factorization null-space method of quadratic programming by developing a parallel orthogonal factorization and a parallel Cholesky factorization. Tests of the algorithm on a 32-node INTEL iPSC/2 hypercube demonstrate speedup factors as large as 10 in comparison to the fastest known equivalent serial algorithm.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

A novel recurrent nonlinear neural network for solving quadratic programming problems

This paper presents a new neural network for solving quadratic programming problems. The new model has a simple form, furthermore it has a good convergence rate with a less number calculation operation than the old models. It converges very fast to exact solution of the dual problem and by substituting in a formulation, the optimal solution of the original problem is obtained. Neural network model with one of numerical method is solved. Finally, simple numerical examples are provided for more illustration.     

求解带二次约束的非凸二次规划的一种分支定界算法

本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.     

A novel method for robust minimisation of univariate functions with quadratic convergence

We describe a novel method for minimisation of univariate functions which exhibits an essentially quadratic convergence and whose convergence interval is only limited by the existence of near maxima. Minimisation is achieved through a fixed-point iterative algorithm, involving only the first and second-order derivatives, that eliminates the effects of near inflexion points on convergence, as usually observed in other minimisation methods based on the quadratic approximation. Comparative numerical studies against the standard quadratic and Brent's methods demonstrate clearly the high robustness, high precision and convergence rate of the new method, even when a finite difference approximation is used in the evaluation of the second-order derivative.