A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

求解中大规模复杂凸二次整数规划问题的新型分枝定界算法

针对现有分枝定界算法在求解高维复杂二次整数规划问题时所存在的诸多不足，本文通过充分挖掘二次整数规划问题的结构特性来设计选择分枝变量与分枝方向的新方法，并将HNF算法与原问题松弛问题的求解相结合来寻求较好的初始整数可行解，由此导出可用于有效求解中大规模复杂二次整数规划问题的改进型分枝定界算法．数值试验结果表明所给算法大大改进了已有相关的分枝定界算法，并具有较好的稳定性与广泛的适用性．     

A New Superlinearly Convergent Strongly Subfeasible Sequential Quadratic Programming Algorithm for Inequality-Constrained Optimization

Combining the ideas of generalized projection and the strongly subfeasible sequential quadratic programming (SQP) method, we present a new strongly subfeasible SQP algorithm for nonlinearly inequality-constrained optimization problems. The algorithm, in which a new unified step-length search of Armijo type is introduced, starting from an arbitrary initial point, produces a feasible point after a finite number of iterations and from then on becomes a feasible descent SQP algorithm. At each iteration, only one quadratic program needs to be solved, and two correctional directions are obtained simply by explicit formulas that contain the same inverse matrix. Furthermore, the global and superlinear convergence results are proved under mild assumptions without strict complementarity conditions. Finally, some preliminary numerical results show that the proposed algorithm is stable and promising.     

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…     

The semi-continuous quadratic mixture design problem: Description and branch-and-bound approach

The semi-continuous quadratic mixture design problem (SCQMDP) is described as a problem with linear, quadratic and semi-continuity constraints. Moreover, a linear cost objective and an integer valued objective are introduced. The goal is to deal with the SCQMD problem from a branch-and-bound perspective generating robust solutions. Therefore, an algorithm is outlined which identifies instances where decision makers tighten requirements such that no ε-robust solution exists. The algorithm is tested on several cases derived from industry.     

Line search SQP method with a flexible step acceptance procedure

This paper describes a new algorithm for nonlinear programming with inequality constraints. The proposed approach solves a sequence of quadratic programming subproblems via the line search technique and uses a new globalization strategy. An increased flexibility in the step acceptance procedure is designed to promote long productive steps for fast convergence. Global convergence is proved under some reasonable assumptions and preliminary numerical results are presented.     

Sequential quadratically constrained quadratic programming norm-relaxed algorithm of strongly sub-feasible directions

In this paper, we present a sequential quadratically constrained quadratic programming (SQCQP) norm-relaxed algorithm of strongly sub-feasible directions for the solution of inequality constrained optimization problems. By introducing a new unified line search and making use of the idea of strongly sub-feasible direction method, the proposed algorithm can well combine the phase of finding a feasible point (by finite iterations) and the phase of a feasible descent norm-relaxed SQCQP algorithm. Moreover, the former phase can preserve the “sub-feasibility” of the current iteration, and control the increase of the objective function. At each iteration, only a consistent convex quadratically constrained quadratic programming problem needs to be solved to obtain a search direction. Without any other correctional directions, the global, superlinear and a certain quadratic convergence (which is between 1-step and 2-step quadratic convergence) properties are proved under reasonable assumptions. Finally, some preliminary numerical results show that the proposed algorithm is also encouraging.     

A Conic Trust-Region Method for Nonlinearly Constrained Optimization

Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.