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.     

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.     

The method of feasible directions for mathematical programming problems with preconvex constraints

The convergence of the method of feasible directions is proved for the case of the smooth objective function and a constraint in the form of the difference of convex sets (the so-called preconvex set). It is shown that the method converges to the set of stationary points, which generally is narrower than the corresponding set in the case of a smooth function and smooth constraints. The scheme of the proof is similar to that proposed earlier by Karmanov.     

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

A feasible directions algorithm for time-lag optimal control problems with control and terminal inequality constraints

A computational algorithm for a class of time-lag optimal control problems involving control and terminal inequality constraints is presented. The convergence properties of the algorithm is also investigated. To test the algorithm, an example is solved.This work was partially supported by the Australian Research Grant Committee.     

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.     

Unified steerable phase I-phase II method of feasible directions for semi-infinite optimization

In this paper, we complete a cycle in the construction of methods of feasible directions for solving semi-infinite constrained optimization problems. Earlier phase I-phase II methods of feasible directions used one search direction rule in all of ⁿ with two stepsize rules, one for feasible points and one for infeasible points. The algorithm presented in this paper uses both a single search direction rule and a single stepsize rule in all of ⁿ . In addition, the new algorithm incorporates a steering parameter which can be used to control the speed with which feasibility is achieved. The new algorithm is simpler to analyze and performs somewhat better than existing, first order, phase I-phase II methods. The new algorithm is globally convergent, with linear rate.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.The authors would like to thank Dr. J. Higgins for providing the C-code of Algorithm 3.1.     

Probabilistic version of the method of feasible directions

A probabilistic version of the method of feasible directions (MFD) for solving nonlinear programming (NLP) problems of the type min{f(x): f_j(x)0,j=1,2,…,m} is presented. Randomization is applied to modify the algorithm and a global convergence Theorem is used in the analysis of convergence. Some numerical experiments on problems with known solutions serve to compare this method with the traditional deterministic versions.     

Convergence of a feasible directions algorithm for relaxed controls in time-lag systems

In this paper, we consider a class of time-lag optimal control problems involving control and terminal inequality constraints. A feasible direction algorithm has been obtained by Teo, Wong, and Clements for solving this class of optimal control problems. It was shown that anyL accumulation points of the sequence of controls generated by the algorithm satisfy a necessary condition for optimality. However, suchL accumulation points need not exist. The aim of this paper is to prove a convergence result, which ensures that the sequence of controls generated by the algorithm always has accumulation points in the sense of control measure, and these accumulation points satisfy a necessary condition for optimality for the corresponding relaxed problem.This work was done when the first author was on sabbatical leave at the School of Mathematics, University of New South Wales, Australia.     

An outer approximations algorithm for computer-aided design problems

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.This research was sponsored by the National Science Foundation, Grant No. ENG73-08214A01, and the National Science Foundation (RANN), Grant No. ENV76-04264.     

A norm-relaxed method of feasible directions for finely discretized problems from semi-infinite programming

In this paper, a class of finely discretized Semi-Infinite Programming (SIP) problems is discussed. Combining the idea of the norm-relaxed Method of Feasible Directions (MFD) and the technique of updating discretization index set, we present a new algorithm for solving the Discretized Semi-Infinite (DSI) problems from SIP. At each iteration, the iteration point is feasible for the discretized problem and an improved search direction is computed by solving only one direction finding subproblem, i.e., a quadratic program, and some appropriate constraints are chosen to reduce the computational cost. A high-order correction direction can be obtained by solving another quadratic programming subproblem with only equality constraints. Under weak conditions such as Mangasarian–Fromovitz Constraint Qualification (MFCQ), the proposed algorithm possesses weak global convergence. Moreover, the superlinear convergence is obtained under Linearly Independent Constraint Qualification (LICQ) and other assumptions. In the end, some elementary numerical experiments are reported.     

Search directions for a class of projective methods

For solving linear programming problems, we describe and evaluate descent directions for projective methods in the setting of the method of de Ghellinck and Vial (1986). It is shown that choosing search directions from the projected simplex centered at 1 in transformed space guarantees a polynomial time bound. In particular, the projection of 1 coincides with the direction chosen by de Ghellinck and Vial (1986) which is well known to be equivalent to Karmarkar's search direction when the initial solution is feasible. Close to that search direction the complexity of the method is unchanged [0(nL) iterations] while in general the bound is 0(n² ·L), whereL is the size of the linear programming problem.The investigations were not made in order to improve worst case bounds, but rather to enable a free choice of search directions from a quite large class of polynomial directions. We show how different directions can be computed in one iteration using the projection of 1 with relatively small extra computational effort. In projective methods linear programming is reformulated as one-parametric feasibility problem where the parameter is the currently known upper bound on the optimal value. It is therefore very important to improve that bound whenever possible. Generalizing bounds from de Ghellinck and Vial (1986) we prove some infeasibility criteria. In particular, any computed search direction yields some upper bound which eventually improves that currently used. All bounds can be computed by solving sets of simple linear and quadratic equations.

---

Zusammenfassung Zur Lösung linearer Optimierungsaufgaben beschreiben und bewerten wir Abstiegsrichtungen bei projektiven Methoden in der Formulierung von de Ghellinck and Vial (1986). Es zeigt sich, daß bei Wahl von Suchrichtungen aus dem projizierten Simplex um 1 im transformierten Raum stets polynomiale Laufzeitabschätzungen gelten. Insbesondere die Projektion der 1 stimmt mit der von de Ghellinck and Vial (1986) gewählten Suchrichtung überein, die bekanntlich bei zulässiger Startlösung äquivalent zu Karmarkar's Suchrichtung ist. Nahe bei dieser Suchrichtung bleibt die Komplexität der Methode unverändert [0(nL) Iterationen], während im allgemeinen die Schranke 0(n² ·L) gilt, wobeiL die Größe des Linearen Optimierungsproblemes beschreibt.Die Untersuchungen zielen nicht darauf ab, Schranken für den ungünstigsten Fall zu verbessern, sondern sollen die freie Wahl von Suchrichtungen aus einer großen Klasse polynomialer Richtungen zulassen. Wir zeigen, wie man unterschiedliche Suchrichtungen innerhalb einer Iteration aus der Projektion der 1 mit relativ kleinem zusätzlichen Aufwand berechnen kann. In projektiven Methoden wird die Lineare Optimierungsaufgabe als einparametrisches Zulässigkeitsproblem reformuliert, wobei als Parameter die jeweils bekannte obere Schranke des Optimalwertes dient. Daher ist es sehr wichtig, diese Schranke bei jeder Gelegenheit zu verbessern. Durch Verallgemeinerung von Schranken aus de Ghellinck and Vial (1986) leiten wir einige Unzulässigkeitstests her. Insbesondere liefert jede berechnete Suchrichtung eine obere Schranke, die möglicherweise die bekannte obere Schranke verbessert. Alle Schranken können durch Lösung einer Reihe einfacher linearer und quadratischer Gleichungen berechnet werden.

     

Self-Tuning Norm-Relaxed Method of Feasible Directions

This paper presents three updating techniques for the scaling matrix or the scalar weight used in the norm-relaxed method of feasible directions, a generalization of the popular Pironneau–Polak algorithm. These techniques include variable metric updates and tuning of a scalar weight in a way characteristic of trust-region methods, and also techniques based on the idea of multiple directions, where the update decision is made by comparing results of searching along several directions determined by distinct values of weights. Numerical results obtained on a standard test set are provided. These results indicate that the updating techniques allow considerable computational savings when compared with the original Pironneau-Polak method.     

A feasible decomposition method for constrained equations and its application to complementarity problems

In this paper, by analyzing the propositions of solution of the convex quadratic programming with nonnegative constraints, we propose a feasible decomposition method for constrained equations. Under mild conditions, the global convergence can be obtained. The method is applied to the complementary problems. Numerical results are also given to show the efficiency of the proposed method.     

Generalized reduced gradient method as an extension of feasible direction methods

The paper presents modifications of the generalized reduced gradient method which allows for a convergence proof. For that, a special construction of the basis is introduced, and some tools of the theory of feasible direction are used to modify the common choice of the direction at every step.Thanks are due to G. de Ghellinck and E. Loute for many fruitful discussions on this paper.     

Error bounds and convergence analysis of feasible descent methods: a general approach

We survey and extend a general approach to analyzing the convergence and the rate of convergence of feasible descent methods that does not require any nondegeneracy assumption on the problem. This approach is based on a certain error bound for estimating the distance to the solution set and is applicable to a broad class of methods.The research of the first author is supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. OPG0090391, and the research of the second author is supported by the National Science Foundation, Grant No. CCR-9103804.     

Fractional programming and characterization of some vertices of the feasible region

This paper considers a problem of nonlinear programming in which the objective function is the ratio of two linear functions and the constraints define a bounded and connected feasible region. Using a coordinate transformation, this problem is transformed into a simpler one, whose geometric interpretation is of particular significance. The transformation leads to a characterization of some special vertices of the feasible region from both the theoretical and operational points of view.     

A new approach to the analysis of random methods for detecting necessary linear inequality constraints

A new approach is given for the analysis of random methods for detecting necessary constraints in systems of linear inequality constraints. This new approach directly accounts for the fact that two constraints are detected as necessary (hit) at each iteration of a random method. The significance of this two-hit analysis is demonstrated by comparing it with the usual one-hit analysis.     

A feasible direction method for linear programming

We discuss a finite method of a feasible direction for linear programming problems. The method begins with a feasible basic vector for the problem, constructs a profitable direction to move using the updated column vectors of the nonbasic variables eligible to enter this basic vector. It then moves in this direction as far as possible, while retaining feasibility. This move in general takes it though the relative interior of a face of th set of a feasible solutions. The final point, $\text{x}$, obtained at the end of this move will not in general be a basic solution. Using $\text{x}$ the method then constructs a basic feasible solution at which the objective value is better than, or the same as that at $\text{x}$. The whole process repeats with the new basic feasible solution. We show that this method can be implemented using basis inverses. Initial computer runs of this method in comparison with the usual edge following primary simplex algorithms are very encouraging.     

On controlling the parameter in the logarithmic barrier term for convex programming problems

We present a log-barrier based algorithm for linearly constrained convex differentiable programming problems in nonnegative variables, but where the objective function may not be differentiable at points having a zero coordinate. We use an approximate centering condition as a basis for decreasing the positive parameter of the log-barrier term and show that the total number of iterations to achieve an -tolerance optimal solution isO(|log()|)×(number of inner-loop iterations). When applied to then-variable dual geometric programming problem, this bound becomesO(n ² U/), whereU is an upper bound on the maximum magnitude of the iterates generated during the computation.The authors gratefully acknowledge very constructive and insightful comments and suggestions from the two anonymous referees and the correspondence from A. V. Fiacco (Ref. 1).