Global Convergence Analysis of Algorithms for Finding Feasible Points in Norm-Relaxed MFD

This paper introduces two new algorithms for finding initial feasible points from initial infeasible points for the recently developed norm-relaxed method of feasible directions (MFD). Their global convergence is analyzed. The theoretical results show that both methods are globally convergent; one of them guarantees finding a feasible point in a finite number of steps. These two methods are very convenient to implement in the norm-relaxed MFD. Numerical experiments are carried out to demonstrate their performance on some classical test problems and to compare them with the traditional method of phase I problems. The numerical results show that the methods proposed in this paper are more effective than the method of phase I problems in the norm-relaxed MFD. Hence, they can be used for finding initial feasible points for other MFD algorithms and other nonlinear programming methods.     

A Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

Convergence analysis of norm-relaxed method of feasible directions

This paper gives a complete treatment of the asymptotic rate of convergence for a class of feasible directions methods, including those studied by Pironneau and Polak and by Cawood and Kostreva. Rate estimates of Pironneau and Polak are sharpened in an analysis which shows the dependence on certain parameters of the direction-finding subproblem and the problem functions. Special cases of interior optimal solution, linear constraints, and fixed matrix norm are analyzed in detail. Numerical verification is provided.     

Norm-relaxed method of feasible directions for solving nonlinear programming problems

A variation of the Polak method of feasible directions for solving nonlinear programming problems is shown to be related to the Topkis and Veinott method of feasible directions. This new method is proven to converge to a Fritz John point under rather weak assumptions. Finally, numerical results show that the method converges with fewer iterations than that of Polak with a proper choice of parameters.     

Inexact-Restoration Algorithm for Constrained Optimization1

We introduce a new model algorithm for solving nonlinear programming problems. No slack variables are introduced for dealing with inequality constraints. Each iteration of the method proceeds in two phases. In the first phase, feasibility of the current iterate is improved; in second phase, the objective function value is reduced in an approximate feasible set. The point that results from the second phase is compared with the current point using a nonsmooth merit function that combines feasibility and optimality. This merit function includes a penalty parameter that changes between consecutive iterations. A suitable updating procedure for this penalty parameter is included by means of which it can be increased or decreased along consecutive iterations. The conditions for feasibility improvement at the first phase and for optimality improvement at the second phase are mild, and large-scale implementation of the resulting method is possible. We prove that, under suitable conditions, which do not include regularity or existence of second derivatives, all the limit points of an infinite sequence generated by the algorithm are feasible, and that a suitable optimality measure can be made as small as desired. The algorithm is implemented and tested against the LANCELOT algorithm using a set of hard-spheres problems.     

非线性规划的拟罚函数—强次可行方向法

本文首先提出非线性规划的拟Ｋｕｈｎ—Ｔｕｃｋｅｒ点和拟罚函数法的概念和思想，然后结合强次可行方向法思想给出问题的两个新型算法，称之为拟罚函数—强次可行方向法．证明了该算法收敛到原问题的拟Ｋｕｈｎ—Ｔｕｃｋｅｒ点．     

Feasible directions in economic policy

Zoutendijk's method of feasible directions is used in this paper to derive numerical control strategies for the United Kingdom economy. The way in which the algorithm permits an examination of the sensitivity of the optimum short-term economic policy to changes in various assumptions demonstrates the versatility of the algorithm. Examined are the implications of different forms for the social welfare function; altering the length of the planning horizon, varying the magnitude of the terminal capital constraint, reducing the maximum permitted level of unemployment, changing the initial endowment of foreign currency reserves, fixing the interest rate for the whole planning period, and imposing a minimum growth rate for public expenditure.This work was supported in part by the National Science Foundation, Grant No. GK-10656X7.     

Feasible Direction Interior-Point Technique for Nonlinear Optimization

We propose a feasible direction approach for the minimization by interior-point algorithms of a smooth function under smooth equality and inequality constraints. It consists of the iterative solution in the primal and dual variables of the Karush–Kuhn–Tucker first-order optimality conditions. At each iteration, a descent direction is defined by solving a linear system. In a second stage, the linear system is perturbed so as to deflect the descent direction and obtain a feasible descent direction. A line search is then performed to get a new interior point and ensure global convergence. Based on this approach, first-order, Newton, and quasi-Newton algorithms can be obtained. To introduce the method, we consider first the inequality constrained problem and present a globally convergent basic algorithm. Particular first-order and quasi-Newton versions of this algorithm are also stated. Then, equality constraints are included. This method, which is simple to code, does not require the solution of quadratic programs and it is neither a penalty method nor a barrier method. Several practical applications and numerical results show that our method is strong and efficient.     

求线性规划问题可行基的一种方法

文章给出了一般情形下从线性规划问题的标准型求可行基的一种方法,并通过与大Ｍ法、两阶段法及文［１］方法进行对比分析,说明这是一种有效可行且有可能较简便的方法     

Enhanced methods of feasible directions for engineering design problems

After the advantages of methods of feasible directions in an engineering design environment are pointed out, several modifications to the classical scheme are proposed, aimed at improving computational efficiency while preserving convergence properties.First, an abstract algorithm model is set up and a set of sufficient conditions to ensure convergence is given. Several modifications are proposed, inspired by difficulties arising in an engineering design environment, and it is shown that the resulting algorithms satisfy the sufficient conditions just mentioned. An integrated-circuit bipolar operational amplifier is optimized in order to show the improvement in computation efficiency that the proposed enhancements can provide.This research was supported by the National Science Foundation, Grant No. ECS-82-04452 and by a grant from the Semiconductor Division of the Harris Corporation. The authors wish to thank K.H. Fan, for making numerous useful remarks and for carrying out the numerical experiments, and an anonymous reviewer for pointing out important flaws in an early version of the paper.     

非线性规划的摄动可行方向法

本文提出了二类新的摄动可行方向法,发展和完善了这类方法.新方法形式简单而且不必用Polak程序.适当选择算法中有关参数可减少计算量,还可加快算法的收敛速度.     

A two-stage feasible directions algorithm for nonlinear constrained optimization

We present a feasible directions algorithm, based on Lagrangian concepts, for the solution of the nonlinear programming problem with equality and inequality constraints. At each iteration a descent direction is defined; by modifying it, we obtain a feasible descent direction. The line search procedure assures the global convergence of the method and the feasibility of all the iterates. We prove the global convergence of the algorithm and apply it to the solution of some test problems. Although the present version of the algorithm does not include any second-order information, like quasi-Newton methods, these numerical results exhibit a behavior comparable to that of the best methods known at present for nonlinear programming. Research performed while the author was on a two years appointment at INRIA, Rocquencourt, France, and partially supported by the Brazilian Research Council (CNPq).     

Local Convergence of an Inexact-Restoration Method and Numerical Experiments

Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear programming algorithm. This work was supported by PRONEX-CNPq/FAPERJ Grant E-26/171.164/2003-APQ1, FAPESP Grants 03/09169-6 and 01/04597-4, and CNPq. The authors are indebted to Juliano B. Francisco and Yalcin Kaya for their careful reading of the first draft of this paper.     

直接求线性规划可行基的一种方法

本文给出直接求线性规划问题基可行解的一种简易方法,该方法既避免了引入人工变量,减少存储,一般又能较快地得到一个较好的基可行解.     

Feasible direction method for large-scale nonconvex programs: Decomposition approach

In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by dual decomposition. Results are extended for dynamical problems which include distributed delays and constraints both in state and control variables. The approach is compared with other feasible-direction approaches, and the method is applied to a power generation problem. Some computational results are included.This work was supported by the Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, Brasilia, Brasil, and by the Fundaçao de Amparo a Pesquisa do Estado de Sao Paulo, Sao Paulo, Brazil.On leave from UNICAMP, Campinas, Brazil.     

Numerical study of some feasible direction methods in mathematical programming

Some feasible direction methods for the minimization of a linearly constrained convex function are studied. Special emphasis is placed on the analysis of the procedures which find the search direction, by developing active set methods which use orthogonal or Gauss-Jordan-like transformations.Numerical experiments are performed on a class of quadratic problems depending on two parameters, related to the conditioning of the matrix associated with the quadratic form and the matrix of active constraints at the optimal point. Results are given for the rate of convergence and the average iteration time.This research was partially supported by the Progetto Finalizzato Informatica, CNR, Rome, Italy.     

超线性与二次收敛的序列方程组可行方法

本文讨论不等式约束规划问题,给出一个线性方程组与辅助方向相结合的新可行算法,算法用一种新型的直线搜索产生步长.在一定条件下,当k充分大后,求方向dk每次只需解一个线性方程组.文中证明了算法的全局收敛性与超线性的收敛速度以及二次收敛性,并给出了方法初步的数值试验.     

非线性约束最优化一族超线性收敛的可行方法

本文建立求解非线性不等式约束最优化一族含参数的可行方法．算法每次迭代仅需解一个规模较小的二次规划．在一定的假设条件下,证明了算法族的全局收敛性和超线性收敛性．     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

初始可行基的判定

用高等数学的理论和方法,对无初始可行基的线性规划问题解的存在性及求解方法进行研究,得出关于无初始可行基的线性规划问题解的存在性的六个定理,回答了无初始可行基的线性规划问题解的存在条件和该问题的初始可行基的确定方法.