Genetic algorithms in constrained optimization

The behavior of the two-point crossover operator, on candidate solutions to an optimization problem that is restricted to integer values and by some set of constraints, is investigated theoretically. This leads to the development of new genetic operators for the case in which the constraint system is linear.The computational difficulty asserted by many optimization problems has lead to exploration of a class of randomized algorithms based on biological adaption. The considerable interest that surrounds these evolutionary algorithms is largely centered on problems that have defied satisfactory illation by traditional means because of badly behaved or noisy objective functions, high dimensionality, or intractable algorithmic complexity. Under such conditions, these alternative methods have often proved invaluable.Despite their attraction, the applicability of evolutionary algorithms has been limited by a deficiency of general techniques to manage constraints, and the difficulty is compounded when the decision variables are discrete. Several new genetic operators are presented here that are guaranteed to preserve the feasibility of discrete aspirant solutions with respect to a system of linear constraints.To avoid performance degradation as the probability of finding a feasible and meaningful information exchange between two candidate solutions decreases, relaxations of the modified genetic crossover operator are also proposed. The effective utilization of these also suggests a manipulation of the genetic algorithm itself, in which the population is evanescently permitted to grow beyond its normal size.     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

New algorithms for constrained minimax optimization

A constrained minimax problem is converted to minimization of a sequence of unconstrained and continuously differentiable functions in a manner similar to Morrison's method for constrained optimization. One can thus apply any efficient gradient minimization technique to do the unconstrained minimization at each step of the sequence. Based on this approach, two algorithms are proposed, where the first one is simpler to program, and the second one is faster in general. To show the efficiency of the algorithms even for unconstrained problems, examples are taken to compare the two algorithms with recent methods in the literature. It is found that the second algorithm converges faster with respect to the other methods. Several constrained examples are also tried and the results are presented.     

Convergent stepsizes for constrained optimization algorithms

A fundamental problem in constrained nonlinear optimization algorithms is the design of a satisfactory stepsize strategy which converges to unity. In this paper, we discuss stepsize strategies for Newton or quasi-Newton algorithms which require the solution of quadratic optimization subproblems. Five stepsize strategies are considered for three different subproblems, and the conditions under which the stepsizes will converge to unity are established. It is shown that these conditions depend critically on the convergence of the Hessian approximations used in the algorithms. The stepsize strategies are constructed using basic principles from which the conditions to unit stepsizes follow. Numerical results are discussed in an Appendix.Paper presented to the XI Symposium on Mathematical Programming, Bonn, Germany, 1982.This work was completed while the author was visiting the European University in Florence where, in particular, Professors Fitoussi and Velupillai provided the opportunity for its completion. The author is grateful to Dr. L. C. W. Dixon for his helpful comments and criticisms on numerous versions of the paper, and to R. G. Becker for programming the algorithms in Section 3 and for helpful discussions concerning these algorithms.     

Second-order conditions in stability analysis for state constrained optimal control

The paper presents an outline of the stability results, for state-constrained optimal control problems, recently obtained in Malanowski (Appl. Math. Optim. 55, 255–271, 2007), Malanowski (Optimization, to be published), Malanowski (SIAM J. Optim., to be published). The pricipal novelty of the results is a weakening of the second-order sufficient optimality conditions, under which the solutions and the Lagrange multipliers are locally Lipschitz continuous functions of the parameter. The conditions are weakened by taking into account strongly active state constraints.     

Numerical algorithms for multicriterion optimization

Translated from Programmnoe Obespechenie i Modeli Issledovaniya Operatsii, pp. 155–168, 1986.     

Building correct estimation algorithms as a constrained optimization problem

For estimation algorithms, the problem of building correct algorithms by modifying weights of features and weights of objects is examined. Criteria for the possibility to build a correct algorithm are obtained for certain cases. Conditions of the possibility to build a correct algorithm are obtained in terms of solving a constrained optimization problem. An optimization method is proposed. Under these conditions, the proposed method significantly reduces the computational complexity of synthesizing a correct algorithm.     

Superlinearly convergent quasi-newton algorithms for nonlinearly constrained optimization problems

A class of algorithms for nonlinearly constrained optimization problems is proposed. The subproblems of the algorithms are linearly constrained quadratic minimization problems which contain an updated estimate of the Hessian of the Lagrangian. Under suitable conditions and updating schemes local convergence and a superlinear rate of convergence are established. The convergence proofs require among other things twice differentiable objective and constraint functions, while the calculations use only first derivative data. Rapid convergence has been obtained in a number of test problems by using a program based on the algorithms proposed here.Research supported by NSF Grant GJ-35292 at the University of Wisconsin.     

On boundary state constrained control problems

The aim of this paper is to present a simple qualification condition for control elliptic problems involving constraints both on the control and the state, when there are both a distributed and a boundary control. We establish a general maximum principle and give some examples. Then we study the particular case when the control is only a boundary one and we present a Lagrangian Algorithm with a few numerical results.     

Global optimization of general constrained grey-box models: new method and its application to constrained PDEs for pressure swing adsorption

This paper introduces a novel methodology for the global optimization of general constrained grey-box problems. A grey-box problem may contain a combination of black-box constraints and constraints with a known functional form. The novel features of this work include (i) the selection of initial samples through a subset selection optimization problem from a large number of faster low-fidelity model samples (when a low-fidelity model is available), (ii) the exploration of a diverse set of interpolating and non-interpolating functional forms for representing the objective function and each of the constraints, (iii) the global optimization of the parameter estimation of surrogate functions and the global optimization of the constrained grey-box formulation, and (iv) the updating of variable bounds based on a clustering technique. The performance of the algorithm is presented for a set of case studies representing an expensive non-linear algebraic partial differential equation simulation of a pressure swing adsorption system for \(\hbox {CO}_{2}\). We address three significant sources of variability and their effects on the consistency and reliability of the algorithm: (i) the initial sampling variability, (ii) the type of surrogate function, and (iii) global versus local optimization of the surrogate function parameter estimation and overall surrogate constrained grey-box problem. It is shown that globally optimizing the parameters in the parameter estimation model, and globally optimizing the constrained grey-box formulation has a significant impact on the performance. The effect of sampling variability is mitigated by a two-stage sampling approach which exploits information from reduced-order models. Finally, the proposed global optimization approach is compared to existing constrained derivative-free optimization algorithms.     

On a subproblem of trust region algorithms for constrained optimization

We study a subproblem that arises in some trust region algorithms for equality constrained optimization. It is the minimization of a general quadratic function with two special quadratic constraints. Properties of such subproblems are given. It is proved that the Hessian of the Lagrangian has at most one negative eigenvalue, and an example is presented to show that the Hessian may have a negative eigenvalue when one constraint is inactive at the solution.Research supported by a Research Fellowship of Fitzwilliam College, Cambridge, and by a research grant from the Chinese Academy of Sciences.     

Some theoretical limitations of second-order algorithms for smooth constrained optimization

In second-order algorithms, we investigate the relevance of the constant rank of the full set of active constraints in ensuring global convergence to a second-order stationary point under a constraint qualification. We show that second-order stationarity is not expected in the non-constant rank case if the growth of so-called tangent AKKT2 sequences is not controlled. Since no algorithm controls their growth, we argue that there is a theoretical limitation of algorithms in finding second-order stationary points without constant rank assumptions.     

Inexactly constrained discrete adjoint approach for steepest descent-based optimization algorithms

The problem of constrained optimization via the gradient-based discrete adjoint steepest descent method is studied under the assumption that the constraint equations are solved inexactly. Error propagation from the constraint equations to the gradient is studied analytically, as is the convergence rate of the inexactly constrained algorithm as it relates to the exact algorithm. A method is developed for adapting the residual tolerance to which the constraint equations are solved. The adaptive tolerance method is applied to two simple test cases to demonstrate the potential gains in computational efficiency.     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

The Euler approximation in state constrained optimal control

We analyze the Euler approximation to a state constrained control problem. We show that if the active constraints satisfy an independence condition and the Lagrangian satisfies a coercivity condition, then locally there exists a solution to the Euler discretization, and the error is bounded by a constant times the mesh size. The proof couples recent stability results for state constrained control problems with results established here on discrete-time regularity. The analysis utilizes mappings of the discrete variables into continuous spaces where classical finite element estimates can be invoked.

     

Finite element approximations of stochastic optimal control problems constrained by stochastic elliptic PDEs

In this paper we study mathematically and computationally optimal control problems for stochastic elliptic partial differential equations. The control objective is to minimize the expectation of a tracking cost functional, and the control is of the deterministic, distributed type. The main analytical tool is the Wiener-Itô chaos or the Karhunen-Loève expansion. Mathematically, we prove the existence of an optimal solution; we establish the validity of the Lagrange multiplier rule and obtain a stochastic optimality system of equations; we represent the input data in their Wiener-Itô chaos expansions and deduce the deterministic optimality system of equations. Computationally, we approximate the optimality system through the discretizations of the probability space and the spatial space by the finite element method; we also derive error estimates in terms of both types of discretizations.     

Exploiting additional structure in equality constrained optimization by structured SQP secant algorithms

In 1988, Tapia (Ref. 1) developed and analyzed SQP secant methods in equality constrained optimization taking explicitly the additive structure of the problem setting into account. In this paper, we extend Tapia's augmented scale Lagrangian secant method to the case where additional structure coming from the objective function is available. Using the example of nonlinear least squares with equality constraints, we demonstrate these ideas and develop a convergence theory proving local and q-superlinear convergence for this kind of structured SQP-algorithms.This research was supported by the Studienstiftung des Deutschen Volkes.     

A note on ‘new algorithms for constrained minimax optimization’

An unconstrained minimax algorithm of Charalambous and Conn is easily modified to solve the constrained case. Here we present some numerical results and find that this algorithm compares favourably to those of Dutta and Vidyasagar.This research was supported in part by Natural Sciences and Engineering Research Council grant number A8639.