Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

A feasible point adaptation of the Blankenship and Falk algorithm for semi-infinite programming

Discretization methods for semi-infinite programming do not provide a feasible point in a finite number of iterations. We propose a method that computes a feasible point with an objective value better than or equal to a target value f ₀ or proves that such a point does not exist. Then a binary search on the space of objective values can be performed to obtain a feasible, e{\epsilon}-optimal solution. The algorithm is based on the algorithm proposed in (Blankenship JW, Falk JE in J Optim Theory Appl 19(2):261–281, 1976). Under mild assumptions it terminates in a finite number of iterations.     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

Subgradient Method for Convex Feasibility on Riemannian Manifolds

In this paper, a subgradient type algorithm for solving convex feasibility problem on Riemannian manifold is proposed and analysed. The sequence generated by the algorithm converges to a solution of the problem, provided the sectional curvature of the manifold is non-negative. Moreover, assuming a Slater type qualification condition, we analyse a variant of the first algorithm, which generates a sequence with finite convergence property, i.e., a feasible point is obtained after a finite number of iterations. Some examples motivating the application of the algorithm for feasibility problems, nonconvex in the usual sense, are considered.     

Bass-Tits minimization of automata, quotients of trees and diameters

Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index.     

约束优化的一个改进的强次可行SQP算法及数值试验

本文对约束优化一个强次可行SQP算法进行改进,使之产生的迭代点在有限次迭代后全落入可行域;并对算法数值效果进行了大量的比较试验.     

A primal-dual projection method for solving systems of linear inequalities

An algorithm is described for finding a feasible point for a system of linear inequalities. If the solution set has nonempty interior, termination occurs after a finite number of iterations. The algorithm is a projection-type method, similar to the relaxation methods of Agmon, Motzkin, and Schoenberg. It differs from the previous methods in that it solves for a certain “dual” solution in addition to a primal solution.     

变量有广义界线性规划的叠累单纯形法

本文建立变量有广义界线性规划一个新的转轴算法,称之为叠累单纯形算法,新算法其有三个主要特征：１对于检验数为“坏”的非基变量 ｘｓ,进行一轮子转轴运算,使得ｘｓ进基,转轴中具有“好”的检验数的变量始终保持“好”的检验数;２ｘ．进基的子转轴所产生的基既不是原始可行基,也不是对偶可行基,但子转轴结束时产生的基是原始可行的;３目标函数值在整个转抽运算中是单调下降,从而算法可有限步终止．     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Active set algorithm for mathematical programs with linear complementarity constraints

In the paper, an incomplete active set algorithm is given for mathematical programs with linear complementarity constraints (MPLCC). At each iteration, a finite number of inner-iterations are contained for approximately solving the relaxed nonlinear optimization problem. If the feasible region of the MPLCC is bounded, under the uniform linear independence constraint qualification (LICQ), any cluster point of the sequence generated from the algorithm is a B-stationary point of the MPLCC. Preliminary numerical tests show that the algorithm is promising.     

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 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.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

Optimization under nonnegativity constraints

Summary The problem [maximizef(x), subject tox0] is considered. McCormick has proposed a theoretically convergent feasible direction method that takes advantage of the special structure of this problem. However, the one-dimensional subproblem of the method requires an exact solution, which cannot be obtained by a finite procedure. Goldstein has used in unconstrained optimization a one-dimensional subproblem for which any point within certain real line intervals is an acceptable solution. A similar subproblem is applied to McCormick's method and convergence to aK-T point is proven. A finite search procedure for the subproblem and a finite stopping rule for the algorithm are given.This paper is an outgrowth of a Ph.D. dissertation [3], submitted to Yale University in 1973. I am thankful to my advisors, Professors R. Mifflin (chairman), H. M. Wagner, and M. Shubik, for their guidance and assistance     

一类逼近l1精确罚函数的罚函数

本文对可微非线性规划问题提出了一个渐近算法,它是基于一类逼近l1精确罚函数的罚函数而提出的,我们证明了算法所得的极小点列的聚点均为原问题的最优解,并在Mangasarian-Fromovitz约束条件下,证明了有限次迭代之后,所有迭代均为可行的,即迭代所得的极小点为可行点.     

A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results

We introduce a new and very simple algorithm for a class of smooth convex constrained minimization problems which is an iterative scheme related to sequential quadratically constrained quadratic programming methods, called sequential simple quadratic method (SSQM). The computational simplicity of SSQM, which uses first-order information, makes it suitable for large scale problems. Theoretical results under standard assumptions are given proving that the whole sequence built by the algorithm converges to a solution and becomes feasible after a finite number of iterations. When in addition the objective function is strongly convex then asymptotic linear rate of convergence is established.     

Subdivision of simplices relative to a cutting plane and finite concave minimization

In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched.     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.