Convergence of interval-type algorithms for generalized fractional programming

The purpose of this paper is to analyze the convergence of interval-type algorithms for solving the generalized fractional program. They are characterized by an interval [LB _k , UB _k ] including*, and the length of the interval is reduced at each iteration. A closer analysis of the bounds LB _k and UB _k allows to modify slightly the best known interval-type algorithm NEWMODM accordingly to prove its convergence and derive convergence rates similar to those for a Dinkelbach-type algorithm MAXMODM under the same conditions. Numerical results in the linear case indicate that the modifications to get convergence results are not obtained at the expense of the numerical efficiency since the modified version BFII is as efficient as NEWMODM and more efficient than MAXMODM.This research was supported by NSERC (Grant A8312) and FCAR (Grant 0899).     

An algorithm for generalized fractional programs

An algorithm is suggested that finds the constrained minimum of the maximum of finitely many ratios. The method involves a sequence of linear (convex) subproblems if the ratios are linear (convex-concave). Convergence results as well as rate of convergence results are derived. Special consideration is given to the case of (a) compact feasible regions and (b) linear ratios.The research of S. Schaible was supported by Grant Nos. A4534 and A5408 from NSERC. The authors thank two anonymous referees for their helpful remarks.     

Local convergence of filter methods for equality constrained non-linear programming

In Gonzaga et al. [A globally convergent filter method for nonlinear programming, SIAM J. Optimiz. 14 (2003), pp. 646–669] we discuss general conditions to ensure global convergence of inexact restoration filter algorithms for non-linear programming. In this article we show how to avoid the Maratos effect by means of a second-order correction. The algorithms are based on feasibility and optimality phases, which can be either independent or not. The optimality phase differs from the original one only when a full Newton step for the tangential minimization of the Lagrangian is efficient but not acceptable by the filter method. In this case a second-order corrector step tries to produce an acceptable point keeping the efficiency of the rejected step. The resulting point is tested by trust region criteria. Under the usual hypotheses, the algorithm inherits the quadratic convergence properties of the feasibility and optimality phases. This article includes a comparison between classical Sequential Quadratic Programming (SQP) and Inexact Restoration (IR) iterations, showing that both methods share the same asymptotic convergence properties.     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming （SOCP） by using the Alizadeh- Haeberly-Overton （AHO） search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.     

On the superlinear local convergence of a filter-SQP method

Transition to superlinear local convergence is shown for a modified version of the trust-region filter-SQP method for nonlinear programming introduced by Fletcher, Leyffer, and Toint [8]. Hereby, the original trust-region SQP-steps can be used without an additional second order correction. The main modification consists in using the Lagrangian function value instead of the objective function value in the filter together with an appropriate infeasibility measure. Moreover, it is shown that the modified trust-region filter-SQP method has the same global convergence properties as the original algorithm in [8].Mathematics Subject Classification (2000): 90C55, 65K05, 90C30     

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.     

补偿随机规划的一种新数值方法

本文给出解决两阶段求援随机规划的一种新的数值方法.由于引进了新的逼近技术,该方法具有全局收敛性和局部超线性收敛性.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

Two-step and three-step Q-superlinear convergence of SQP methods

This paper investigates the convergence rates of the variable-multiplier pair (x, ) in sequential quadratic programming methods for equality constrained optimization. The two main results of the paper are that the Q-superlinear convergence of {x _k } implies two-step Q-superlinear convergence for {(x _k , _k )} and that the two-step Q-superlinear convergence of {x _k } implies three-step Q-superlinear convergence for {(x _k , _k )}.The author is indebted to Professor Richard Tapia for many helpful comments and suggestions on the paper. The comments by Professors A. R. Conn and N. I. M. Gould on an earlier version are also acknowledged. This research was funded by SERC and ESRC research contracts.     

Augmented Lagrangian algorithms for linear programming

We introduce new augmented Lagrangian algorithms for linear programming which provide faster global convergence rates than the augmented algorithm of Polyak and Treti'akov. Our algorithm shares the same properties as the Polyak-Treti'akov algorithm in that it terminates in finitely many iterations and obtains both primal and dual optimal solutions. We present an implementable version of the algorithm which requires only approximate minimization at each iteration. We provide a global convergence rate for this version of the algorithm and show that the primal and dual points generated by the algorithm converge to the primal and dual optimal set, respectively.     

Penalty function theory for general convex programming problems

A class of penalty functions for solving convex programming problems with general constraint sets is considered. Convergence theorems for penalty methods are established by utilizing the concept of infimal convergence of a sequence of functions. It is shown that most existing penalty functions are included in our class of penalty functions.     

Some numerical experience with a globally convergent algorithm for nonlinearly constrained optimization

Global convergence properties are established for a quite general form of algorithms for solving nonlinearly constrained minimization problems. A useful feature of the methods considered is that they can be implemented easily either with or without using quadratic programming techniques. A particular implementation, designed to be both efficient and robust, is described in detail. Numerical results are presented and discussed.This work was carried out by the first author under the support of the Science Research Council (UK), Grant Nos. B/RG/95124 and GR/A/44480, which are gratefully acknowledged.     

Convergence of a Dinkelbach-type algorithm in generalized fractional programming

The convergence of a Dinkelbach-type algorithm in generalized fractional programming is obtained by considering the sensitivity of a parametrized problem. We show that the rate of convergence is at least equal to (1+5)/2 when regularity conditions hold in a neighbourhood of the optimal solution. We give also a necessary and sufficient condition for the convergence to be quadratic (which will be verified in particular in the linear case) and an idea of its implementation in the convex case.

---

Zusammenfassung Die Konvergenz eines Verfahrens i. S. von Dinkelbach zur Lösung verallgemeinerter Quotientenprogramme wird durch Untersuchung der Sensitivität eines parametrisierten Problems abgeleitet. Es wird gezeigt, daß die Konvergenzrate durch (1+5)/2 nach unten beschränkt ist, falls gewisse Regularitätsbedingungen in einer Umgebung der Optimallösung erfüllt sind. Ferner wird eine notwendige und hinreichende Bedingung zur quadratischen Konvergenz hergeleitet. Es wird gezeigt, wie diese im Falle konvexer Probleme implementiert werden kann.

     

Local analysis of Newton-type methods for variational inequalities and nonlinear programming

This paper presents some new results in the theory of Newton-type methods for variational inequalities, and their application to nonlinear programming. A condition of semistability is shown to ensure the quadratic convergence of Newton's method and the superlinear convergence of some quasi-Newton algorithms, provided the sequence defined by the algorithm exists and converges. A partial extension of these results to nonsmooth functions is given. The second part of the paper considers some particular variational inequalities with unknowns (x, ), generalizing optimality systems. Here only the question of superlinear convergence of {x ^k } is considered. Some necessary or sufficient conditions are given. Applied to some quasi-Newton algorithms they allow us to obtain the superlinear convergence of {x ^k }. Application of the previous results to nonlinear programming allows us to strengthen the known results, the main point being a characterization of the superlinear convergence of {x ^k } assuming a weak second-order condition without strict complementarity.     

The p-Factor-Lagrange Methods for Degenerate Nonlinear Programming

The paper presents a new approach to solving nonlinear programming (NLP) problems for which the strict complementarity condition (SCC), a constraint qualification (CQ), and a second-order sufficient condition (SOSC) for optimality are not necessarily satisfied at a solution. Our approach is based on the construction of p-regularity and on reformulating the inequality constraints as equalities. Namely, by introducing the slack variables, we get the equality constrained problem, for which the Lagrange optimality system is singular at the solution of the NLP problem in the case of the violation of the CQs, SCC and/or SOSC. To overcome the difficulty of singularity, we propose the p-factor method for solving the Lagrange system. The method has a superlinear rate of convergence under a mild assumption. We show that our assumption is always satisfied under a standard second-order sufficient condition (SOSC) for optimality. At the same time, we give examples of the problems where the SOSC does not hold, but our assumption is satisfied. Moreover, no estimation of the set of active constraints is required. The proposed approach can be applied to a variety of problems.     

New sequential quadratic programming algorithm with consistent subproblems

One of the most interesting topics related to sequential quadratic programming algorithms is how to guarantee the consistence of all quadratic programming subproblems. In this decade, much work trying to change the form of constraints to obtain the consistence of the subproblems has been done. The method proposed by De O. Pantoja J.F. A. and coworkers solves the consistent problem of SQP method, and is the best to the authors’ knowledge. However, the scale and complexity of the subproblems in De O. Pantoja’s work will be increased greatly since all equality constraints have to be changed into absolute form. A new sequential quadratic programming type algorithm is presented by means of a special ε-active set scheme and a special penalty function. Subproblems of the new algorithm are all consistent, and the form of constraints of the subproblems is as simple as one of the general SQP type algorithms. It can be proved that the new method keeps global convergence and Local superlinear convergence. Project partly supported by the National Natural Science Foundation of China.     

A constraint shifting homotopy method for general non-linear programming

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.     

广义半无限规划问题的一种可行方向算法

基于Zoutendijk可行方向算法,本文提出了一种求解广义半无限规划问题的可行方向算法,在保证算法收敛的情况下,此算法比以往的算法在假设条件的要求上有着一定的优势,且数值试验表明此法是可行的.     

存零约束优化问题的序列二次方法北大核心CSCD

存零约束优化(MPSC)问题是近年来提出的一类新的优化问题,因存零约束的存在,使得常用的约束规范不满足,以至于现有算法的收敛性结果大多不能直接应用于该问题.应用序列二次规划(SQP)方法求解该问题,并证明在存零约束的线性独立约束规范下,子问题解序列的聚点为原问题的Karush-Kuhn-Tucker点.同时为了完善各稳定点之间的关系,证明了强平稳点与KKT点的等价性.最后数值结果表明,序列二次规划方法处理这类问题是可行的.