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.     

An interior point method for quadratic programs based on conjugate projected gradients

We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrixQ. The interior point method we describe is a doubly iterative algorithm that invokes aconjugate projected gradient procedure to obtain the search direction. The effect is thatQ appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method istheoretically convergent with onlyone matrix factorization throughout the procedure.     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions

This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse's interior ellipsoid algorithm for convex quadratic programming is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.Research supported in part by the NSF under grant DDM-8721709.     

A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems

There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems). While the algebraic definitions of these problems are different from each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these properties, we propose and analyze a simple infeasible-interior-point algorithm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is smaller than the initial point, and quadratic convergence if there is a strictly complementary solution.This research was performed while the first author was visiting the Institute of Applied Mathematics and Statistics, Würzburg University as a Research Fellow of the Alexander von Humboldt Foundation.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

An implementation of a reduced subgradient method via Luenberger-Mokhtar variant

We present an implementable algorithm for minimizing a convex function which is not necessarily differentiable subject to linear equality constraints and to nonnegativity bounds on the variables. The algorithm is based on extending the variant proposed by Luenberger to the nondifferentiable case and using the bundle techniques introduced by Lemaréchal to approximate the subdifferential of the objective function. In particular, at each iteration, we compute a search direction by solving a quadratic subproblem, and an inexact line search along this direction yields a decrease in the objective value. Under some assumptions, the convergence of the proposed algorithm is analysed. Finally, some numerical results are presented, which show that the algorithm performs efficiently.     

An Interior-Point Method for a Class of Saddle-Point Problems

We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization formulations of convex quadratic programming problems with uncertain input parameters. As an application of our approach, we discuss a robust formulation of the Markowitz portfolio selection model.     

On the continuous quadratic knapsack problem

We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000.