Persistency in quadratic 0–1 optimization

This paper is concerned with persistency properties which allow the evaluation of some variables at all maximizing points of a quadratic pseudo-Boolean function. Hammer, Hansen and Simeone (1984) have proposed to determine these variables using a procedure described by Balinski for computing a strongly complementary pair of optimal primal and dual solutions for arbitrary linear programs. We propose a linear time algorithm for determining these variables from a best roof off, i.e. from a lowest upper linear bound off.     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Generalizations of Slater's constraint qualification for infinite convex programs

In this paper we study constraint qualifications and duality results for infinite convex programs (P) = inf{f(x): g(x) – S, x C}, whereg = (g ₁,g ₂) andS = S ₁ ×S ₂,S _i are convex cones,i = 1, 2,C is a convex subset of a vector spaceX, andf andg _i are, respectively, convex andS _i -convex,i = 1, 2. In particular, we consider the special case whenS ₂ is in afinite dimensional space,g ₂ is affine andS ₂ is polyhedral. We show that a recently introduced simple constraint qualification, and the so-called quasi relative interior constraint qualification both extend to (P), from the special case thatg = g ₂ is affine andS = S ₂ is polyhedral in a finite dimensional space (the so-called partially finite program). This provides generalized Slater type conditions for (P) which are much weaker than the standard Slater condition. We exhibit the relationship between these two constraint qualifications and show how to replace the affine assumption ong ₂ and the finite dimensionality assumption onS ₂, by a local compactness assumption. We then introduce the notion of strong quasi relative interior to get parallel results for more general infinite dimensional programs without the local compactness assumption. Our basic tool reduces to guaranteeing the closure of the sum of two closed convex cones.     

ε-optimality criteria for convex programming problems via exact penalty functions

In this paper, we present-optimality criteria for convex programming problems associated with exact penalty functions. Several authors have given various criteria under the assumption that such convex problems and the associated dual problems can be solved. We assume the solvability of neither the convex problem nor the dual problem. To derive our criteria, we estimate the size of the penalty parameter in terms of an-solution for the dual problem.     

Value function and optimality conditions for semilinear control problems

This paper is concerned with optimal control problems of Mayer and Bolza type for systems governed by a semilinear state equationx(t)=Ax(t) + f(t, x(t), u(t)), u(t) U, whereA is the infinitesimal generator of a strongly continuous semigroup in a Banach spaceX. We prove necessary and sufficient conditions for optimality and then use these conditions to investigate properties of the value function related to superdifferentials. Conversely, we use the value function to obtain criteria for optimality and feedback systems.Work (partially) supported by the Research Project Equazioni di evoluzione e applicazioni fisicomatematiche (M.U.R.S.T.-Italy).     

Random and cooperative sequential adsorption on infinite ladders and strips

We analyze various processes where particles are added irreversibly and sequentially at the sites of infinite ladders or broader strips (i.e., on terraces) of adsorption sites. For sufficiently narrow strips or ladders, exact solution in closed form is possible for a variety of processes. Often this is most naturally achieved by mapping the process onto an equivalent one-dimensional process typically involvingcompetitive adsorption. We demonstrate this procedure for sequential adsorption with nearest-neighbor exclusion on a 2× square ladder. For other select processes on strips slightly too broad for exact solution, almost exact analysis is possible exploiting an empty-site shielding property. In this way, we determine a jamming coverage of 0.91556671 for random sequential adsorption of dimers on a 2× square ladder. For broader strips, we note that the complexity of these problems quickly approaches that for × lattices.     

Numerical solution of minimax problems of optimal control,part 1

This paper contains general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We consider two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).For Problem (Q), we exploit the analogy with a bounded-state problem in combination with a transformation of the Jacobson type. This requires the proper augmentation of the state vectorx(t), the control vectoru(t), and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.For Problem (R), we exploit the analogy with a bounded-control problem in combination with a transformation of the Valentine type. This requires the proper augmentation of the control vectoru(t) and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.In a subsequent paper (Part 2), the transformation techniques presented here are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer; both the single-subarc approach and the multiple-subarc approach are discussed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

Higher-order necessary conditions for infinite and semi-infinite optimization

In this paper, we present a unified theory of first-order and higher-order necessary optimality conditions for abstract vector optimization problems in normed linear spaces. We prove general multiplier rules, from which nearly all known first-order, second-order, and higher-order necessary conditions can be derived. In the last section, we prove higher-order necessary conditions for semi-infinite programming problems.This work was developed within the Forschungsschwerpunkt Dynamische Systeme, Universität Bremen, Bremen, West Germany.The author wishes to thank Prof. Dr. D. Hinrichsen for his helpful remarks and discussions during the preparation of this work.     

Use of Local Lagrange Interpolation for calculation of retention indices in linear temperature-programmed gas chromatrography

Summary The influence of the isothermal temperature, program rate, initial temperature and flow rate on retention indices was studied. The methods of Kováts, Van Den Dool and Local Lagrange Interpolation are compared. Ten experimental measurements were carried out on a capillary column coated with OV-101 stationary phase.