A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM

This paper represents an inexact sequential quadratic programming (SQP) algorithm which can solve nonlinear programming (NLP) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.     

A potential reduction algorithm for an extended SDP problem

An extended semi-definite programming, the SDP with an additional quadratic term in the objective function, is studied. Our generalization is similar to the generalization from linear programming to quadratic programming. Optimal conditions for this new class of problems are discussed and a potential reduction algorithm for solving QSDP problems is presented. The convergence properties of this algorithm are also given.     

A hybrid method for multidimensional scaling using city-block distances

The problem of multidimensional scaling with city-block distances in the embedding space is reduced to a two level optimization problem consisting of a combinatorial problem at the upper level and a quadratic programming problem at the lower level. A hybrid method is proposed combining randomized search for the upper level problem with a standard quadratic programming algorithm for the lower level problem. Several algorithms for the combinatorial problem have been tested and an evolutionary global search algorithm has been proved most suitable. An experimental code of the proposed hybrid multidimensional scaling algorithm is developed and tested using several test problems of two- and three-dimensional scaling.     

Augmented lagrangian nonlinear programming algorithm that uses SQP and trust region techniques

An augmented Lagrangian nonlinear programming algorithm has been developed. Its goals are to achieve robust global convergence and fast local convergence. Several unique strategies help the algorithm achieve these dual goals. The algorithm consists of three nested loops. The outer loop estimates the Kuhn-Tucker multipliers at a rapid linear rate of convergence. The middle loop minimizes the augmented Lagrangian functions for fixed multipliers. This loop uses the sequential quadratic programming technique with a box trust region stepsize restriction. The inner loop solves a single quadratic program. Slack variables and a constrained form of the fixed-multiplier middleloop problem work together with curved line searches in the inner-loop problem to allow large penalty wieghts for rapid outer-loop convergence. The inner-loop quadratic programs include quadratic onstraint terms, which complicate the inner loop, but speed the middle-loop progress when the constraint curvature is large.The new algorithm compares favorably with a commercial sequential quadratic programming algorithm on five low-order test problems. Its convergence is more robust, and its speed is not much slower.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

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.     

Model for estimating power shortage in electric power systems with quadratic losses of power in transmission lines

A model for estimating power shortage in electric power systems with quadratic losses of power in transmission lines is studied. This model is designed to analyze problems of reliability of electric power systems. A method of presentation of this model in the form of a convex programming problem is given. An interior point algorithm is proposed for model implementation. This algorithm takes into account quadratic approximations of constraints functions. Results of the experimental study of the algorithm are presented.     

A projected lagrangian algorithm for semi-infinite programming

A globally convergent algorithm is presented for the solution of a wide class of semi-infinite programming problems. The method is based on the solution of a sequence of equality constrained quadratic programming problems, and usually has a second order convergence rate. Numerical results illustrating the method are given.     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

Branch and bound algorithm for multidimensional scaling with city-block metric

A two level global optimization algorithm for multidimensional scaling (MDS) with city-block metric is proposed. The piecewise quadratic structure of the objective function is employed. At the upper level a combinatorial global optimization problem is solved by means of branch and bound method, where an objective function is defined as the minimum of a quadratic programming problem. The later is solved at the lower level by a standard quadratic programming algorithm. The proposed algorithm has been applied for auxiliary and practical problems whose global optimization counterpart was of dimensionality up to 24.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming

This paper is concerned with nonlinear, semidefinite, and second-order cone programs. A general algorithm, which includes sequential quadratic programming and sequential quadratically constrained quadratic programming methods, is presented for solving these problems. In the particular case of standard nonlinear programs, the algorithm can be interpreted as a prox-regularization of the Solodov sequential quadratically constrained quadratic programming method presented in Mathematics of Operations Research (2004). For such type of methods, the main cost of computation amounts to solve a linear cone program for which efficient solvers are available. Usually, “global convergence results” for these methods require, as for the Solodov method, the boundedness of the primal sequence generated by the algorithm. The other purpose of this paper is to establish global convergence results without boundedness assumptions on any of the iterative sequences built by the algorithm.     

关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

A trust region method based on interior point techniques for nonlinear programming

An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is presented. Received: May 1996 / Accepted: August 18, 2000?Published online October 18, 2000     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

A quadratic programming algorithm

By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582.     

An interior point method for general large-scale quadratic programming problems

In this paper, we present an interior point algorithm for solving both convex and nonconvex quadratic programs. The method, which is an extension of our interior point work on linear programming problems efficiently solves a wide class of largescale problems and forms the basis for a sequential quadratic programming (SQP) solver for general large scale nonlinear programs. The key to the algorithm is a three-dimensional cost improvement subproblem, which is solved at every interation. We have developed an approximate recentering procedure and a novel, adaptive big-M Phase I procedure that are essential to the sucess of the algorithm. We describe the basic method along with the recentering and big-M Phase I procedures. Details of the implementation and computational results are also presented.Contribution of the National Institute of Standards and Tedchnology and not subject to copyright in the United States. This research was supported in part by ONR Contract N-0014-87-F0053.     

A General Quadratic Programming Algorithm

An effective algorithm is presented for quadratic programmingwhich is of general applicability, but which is not dependentupon the availability of a linear programming code for its implementation.It is an algorithm of exchange type, the exchanges being chosenso as to avoid the accumulation of error to as large an extentas possible.     

一个关于二次规划问题的分段线性同伦算法

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。     

New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints

In Floudas and Visweswaran (1990, 1993), a deterministic global optimization approach was proposed for solving certain classes of nonconvex optimization problems. An algorithm, GOP, was presented for the solution of the problem through a series ofprimal andrelaxed dual problems that provide valid upper and lower bounds respectively on the global solution. The algorithm was proved to have finite convergence to an -global optimum. In this paper, new theoretical properties are presented that help to enhance the computational performance of the GOP algorithm applied to problems of special structure. The effect of the new properties is illustrated through application of the GOP algorithm to a difficult indefinite quadratic problem, a multiperiod tankage quality problem that occurs frequently in the modeling of refinery processes, and a set of pooling/blending problems from the literature. In addition, extensive computational experience is reported for randomly generated concave and indefinite quadratic programming problems of different sizes. The results show that the properties help to make the algorithm computationally efficient for fairly large problems.