On the Pironneau-Polak method of centers

The method of centers is a well-known method for solving nonlinear programming problems having inequality constraints. Pironneau and Polak have recently presented a new version of this method. In the new method, the direction of search is obtained, at each iteration, by solving a convex quadratic programming problem. This direction finding subprocedure is essentially insensitive to the dimension of the space on which the problem is defined. Moreover, the method of Pironneau and Polak is known to converge linearly for finite-dimensional convex programs for which the objective function has a positive-definite Hessian near the solution (and for which the functions involved are twice continuously differentiable). In the present paper, the method and a completely implementable version of it are shown to converge linearly for a very general class of finite-dimensional problems; the class is determined by a second-order sufficiency condition and includes both convex and nonconvex problems. The arguments employed here are based on the indirect sufficiency method of Hestenes. Furthermore, the arguments can be modified to prove linear convergence for a certain class of infinite-dimensional convex problems, thus providing an answer to a conjecture made by Pironneau and 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).     

An inexact Newton method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is an application of Newton's method to a nonlinear differential operator equation. Since the linear boundary-value problem to be solved at each iteration must be discretized, it is natural to consider quasilinearization in the framework of an inexact Newton method. More importantly, each linear problem is only a local model of the nonlinear problem, and so it is inefficient to try to solve the linear problems to full accuracy. Conditions on size of the relative residual of the linear differential equation can then be specified to guarantee rapid local convergence to the solution of the nonlinear continuous problem. If initial-value techniques are used to solve the linear boundary-value problems, then an integration step selection scheme is proposed so that the residual criteria are satisfied by the approximate solutions. Numerical results are presented that demonstrate substantial computational savings by this type of economizing on the intermediate problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor R. A. Tapia and Professor J. E. Dennis, Jr.     

The nearest adjoining order method for pairwise comparisons in the form of difference of ranks

The problem of ranking of elements from some finite set on the basis of nearest adjoining order method for pairwise comparisons is investigated in this paper. It is assumed that in the set under consideration there exists a weak preference relation, which is to be identified (estimated) on the basis of pairwise comparisons in the form of difference of ranks. Moreover, the results of comparisons may be disturbed with random errors; the assumptions made about error distributions are not restrictive. The paper comprises: the problem formulation (definitions, assumptions, and optimisation problem, which provides the NAO solution) and the theoretical background – the form of distributions of random variables which make it possible to determine the properties of NAO solution, in particular, evaluation of the probability, that the NAO solution is equivalent to the errorless one. The approach presented in the paper can be extended to the case of more than one comparison for each pair of elements, i.e., completely formalised multi-experts ranking procedure. This revised version was published online in June 2006 with corrections to the Cover Date.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

Computational comparison of two methods for constrained global optimization

For constrained concave global minimization problems, two very different solution techniques have been investigated. The first such method is a stochastic mulitstart approach which typically finds, with high probability, all local minima for the problem. The second method is deterministic and guarantees a global minimum solution to within any user specified tolerance. It is the purpose of this paper to make a careful comparison of these two methods on a range of test problems using separable concave objectives over compact polyhedral sets, and to investigate in this way the advantages and disadvantages of each method. A direct computational comparison, on the same set of over 140 problems, is presented.     

Single-job lot streaming in m − 1 two-stage hybrid flowshops

This paper studies the single-job lot streaming problem in a two-stage hybrid flowshop that has m identical machines at the first stage and one machine at the second stage, to minimise the makespan. A setup time is considered before processing each sublot on a machine. For the problem with the number of sublots given, we prove that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines. With such allocation and sequencing, the sublot sizes are then optimised using linear programming. We then consider the problem with equal sublot sizes and develop an efficient solution to determining the optimal number of sublots. Finally optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analysed. Computational results are also reported demonstrating the close-to-optimal performances of the heuristic methods in different problem settings.     

ORDER RESULTS FOR ALGEBRAICALLY STABLE MONO-IMPLICIT RUNGE-KUTTA METHODS

1.IntroductionConsidertheinitialvalueproblemwhichisassumedtohaveauniquesolutiony(t)ontheinterval[0, co).Forsolving(1.1),considerthes--stageimplicitRunge-Kutta(IRK)methodandthes-stagemono-implicitRunge-Kutta(MIRK)method{2,51swhereh)0isthestepsize,hi,c...     

An inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

New projection-type methods for monotone LCP with finite termination

Summary. In this paper we establish two new projection-type methods for the solution of monotone linear complementarity problem (LCP). The methods are a combination of the extragradient method and the Newton method, in which the active set strategy is used and only one linear system of equations with lower dimension is solved at each iteration. It is shown that under the assumption of monotonicity, these two methods are globally and linearly convergent. Furthermore, under a nondegeneracy condition they have a finite termination property. At last, the methods are extended to solving monotone affine variational inequality problem. Received October 10, 2000 / Revised version received May 22, 2001 / Published online October 17, 2001     

A modified standard embedding with jumps in nonlinear optimization

The paper deals with a combination of pathfollowing methods (embedding approach) and feasible descent direction methods (so-called jumps) for solving a nonlinear optimization problem with equality and inequality constraints. Since the method that we propose here uses jumps from one connected component to another one, more than one connected component of the solution set of the corresponding one-parametric problem can be followed numerically. It is assumed that the problem under consideration belongs to a generic subset which was introduced by Jongen, Jonker and Twilt. There already exist methods of this type for which each starting point of a jump has to be an endpoint of a branch of local minimizers. In this paper the authors propose a new method by allowing a larger set of starting points for the jumps which can be constructed at bifurcation and turning points of the solution set. The topological properties of those cases where the method is not successful are analyzed and the role of constraint qualifications in this context is discussed. Furthermore, this new method is applied to a so-called modified standard embedding which is a particular construction without equality constraints. Finally, an algorithmic version of this new method as well as computational results are presented.     

Superlinear Noninterior One-Step Continuation Method for Monotone LCP in the Absence of Strict Complementarity

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).     

Inexact implicit methods for monotone general variational inequalities

Solving a variational inequality problem is equivalent to finding a solution of a system of nonsmooth equations. Recently, we proposed an implicit method, which solves monotone variational inequality problem via solving a series of systems of nonlinear smooth (whenever the operator is smooth) equations. It can exploit the facilities of the classical Newton–like methods for smooth equations. In this paper, we extend the method to solve a class of general variational inequality problems Moreover, we improve the implicit method to allow inexact solutions of the systems of nonlinear equations at each iteration. The method is shown to preserve the same convergence properties as the original implicit method. Received July 31, 1995 / Revised version received January 15, 1999? Published online May 28, 1999     

An acyclic days-off scheduling problem

This paper studies the days off scheduling problem when the demand for staffing fluctuates from day to another and when the number of total workdays is fixed in advance for each employee. The scheduling problem is then to allocate rests to employees with different days off policies: (1) two or three consecutive days off for each employee per week and (2) at least three consecutive days off for each employee per month. For each one, we propose a polynomial time algorithm to construct a solution if it exists. Received: April 2005 / Revised version: October 2005 AMS classification: 60K25, 60K30     

A robust APTAS for the classical bin packing problem

Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions. A preliminary version of this paper appeared in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP2006), part I, pp. 214–225.     

Optimal m-stage Runge-Kutta schemes for steady-state solutions of hyperbolic equations

A numerical scheme is developed to find optimal parameters and time step of m-stage Runge-Kutta (RK) schemes for accelerating the convergence to -steady-state solutions of hyperbolic equations. These optimal RK schemes can be applied to a spatial discretization over nonuniform grids such as Chebyshev spectral discretization. For each m given either a set of all eigenvalues or a geometric closure of all eigenvalues of the discretization matrix, a specially structured nonlinear minimax problem is formulated to find the optimal parameters and time step. It will be shown that each local solution of the minimax problem is also a global solution and therefore the obtained m-stage RK scheme is optimal. A numerical scheme based on a modified version of the projected Lagrangian method is designed to solve the nonlinear minimax problem. The scheme is generally applicable to any stage number m. Applications in solving nonsymmetric systems of linear equations are also discussed. © 1993 John Wiley & Sons, Inc.     

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.     

IMinpert： An Incomplete Minimum Perturbation Algorithm for Large Unsymmetric Linear Systems

This paper gives the truncated version of the Minpert method:the incomplete minimum perturbation algorithm(IMinpert).It is based on an incomplete orthogonal- ization of the Krylov vectors in question,and gives a quasi-minimum backward error solution over the Krylov subspace.In order to make the practical implementation of IMinpert easy and convenient,we give another approximate version of the IMinpert method:A-IMinpert.Theoretical properties of the latter algorithm are discussed.Nu- merical experiments are reported to show the proposed method is effective in practice and is competitive with the Minpert algorithm.     

Trigonometric–fitted hybrid four–step methods of sixth order for solving

A two–stage, explicit, hybrid four–step method of sixth order for the solution of the special second order initial value problem is presented here. The new method is trigonometric fitted, thus it uses variable coefficients. Numerical tests illustrate the superiority of our proposal over similar methods found in the relevant literature on a set of standard problems.