First-order sequential convex programming using approximate diagonal QP subproblems

Optimization algorithms based on convex separable approximations for optimal structural design often use reciprocal-like approximations in a dual setting; CONLIN and the method of moving asymptotes (MMA) are well-known examples of such sequential convex programming (SCP) algorithms. We have previously demonstrated that replacement of these nonlinear (reciprocal) approximations by their own second order Taylor series expansion provides a powerful new algorithmic option within the SCP class of algorithms. This note shows that the quadratic treatment of the original nonlinear approximations also enables the restatement of the SCP as a series of Lagrange-Newton QP subproblems. This results in a diagonal trust-region SQP type of algorithm, in which the second order diagonal terms are estimated from the nonlinear (reciprocal) intervening variables, rather than from historic information using an exact or a quasi-Newton Hessian approach. The QP formulation seems particularly attractive for problems with far more constraints than variables (when pure dual methods are at a disadvantage), or when both the number of design variables and the number of (active) constraints is very large.     

An augmented Lagrangian approach to non-convex SAO using diagonal quadratic approximations

Successful gradient-based sequential approximate optimization (SAO) algorithms in simulation-based optimization typically use convex separable approximations. Convex approximations may however not be very efficient if the true objective function and/or the constraints are concave. Using diagonal quadratic approximations, we show that non-convex approximations may indeed require significantly fewer iterations than their convex counterparts. The nonconvex subproblems are solved using an augmented Lagrangian (AL) strategy, rather than the Falk-dual, which is the norm in SAO based on convex subproblems. The results suggest that transformation of large-scale optimization problems with only a few constraints to a dual form via convexification need sometimes not be required, since this may equally well be done using an AL formulation.     

Sequential approximate optimization using dual subproblems based on incomplete series expansions

In this paper, dual formulations for nonlinear multipoint approximations with diagonal approximate Hessian matrices are proposed; these approximations for example derive from the incomplete series expansion (ISE) proposed previously. A salient feature of the ISE is that it may be used to formulate strictly convex and separable (recast) primal approximate subproblems for use in sequential approximate optimization (SAO). In turn, this allows for the formulation of highly efficient dual formulations, and different combinations of direct, reciprocal, and exponential intervening variables for the objective and the constraint functions may be used. Two frequently encountered problems in structural optimization, namely the weight minimization problem with sizing design variables and the minimum compliance topology optimization problem, are degenerate cases of the formulations we present. Computational experiments confirm the efficiency of our proposed methodology; to this end, comparative results for the method of moving asymptotes (MMA) are presented. Based on the paper entitled “Duality in Convex Nonlinear Multipoint Approximations with Diagonal Approximate Hessian Matrices Deriving from Incomplete Series Expansions,” presented at the 11th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Portsmouth, VA, USA, September 2006, paper no. AIAA-2006-7090.     

On concave constraint functions and duality in predominantly black-and-white topology optimization

We study the ‘classical’ discrete, solid-void or black-and-white topology optimization problem, in which minimum compliance is sought, subject to constraints on the available material resource. We assume that this problem is solved using methods that relax the discreteness requirements during intermediate steps, and that the associated programming problems are solved using sequential approximate optimization (SAO) algorithms based on duality. More specifically, we assume that the advantages of the well-known Falk dual are exploited. Such algorithms represent the state-of-the-art in (large-scale) topology optimization when multiple constraints are present; an important example being the method of moving asymptotes (MMA).We depart by noting that the aforementioned SAO algorithms are invariably formulated using strictly convex subproblems. We then numerically illustrate that strictly concave constraint functions, like those present in volumetric penalization, as recently proposed by Bruns and co-workers, may increase the difficulty of the topology optimization problem when strictly convex approximations are used in the SAO algorithm. In turn, volumetric penalization methods are of notable importance, since they seem to hold much promise for generating predominantly solid-void or discrete designs.We then argue that the nonconvex problems we study may in some instances efficiently be solved using dual SAO methods based on nonconvex (strictly concave) approximations which exhibit monotonicity with respect to the design variables.Indeed, for the topology problem resulting from SIMP-like volumetric penalization, we show explicitly that convex approximations are not necessary. Even though the volumetric penalization constraint is strictly concave, the maximum of the resulting dual subproblem still corresponds to the optimum of the original primal approximate subproblem.     

The application of gradient-only optimization methods for problems discretized using non-constant methods

We study the minimization of objective functions containing non-physical jump discontinuities. These discontinuities arise when (partial) differential equations are discretized using non-constant methods and the resulting numerical solutions are used in computing the objective function. Although the functions may become discontinuous, gradient information may be computed at every point. Gradient information is computable everywhere since every point has an associated discretization for which (semi) analytical sensitivities can be calculated. Rather than the construction of global approximations using only function value information to overcome the discontinuities, we propose to use only the gradient information. We elaborate on the modifications of classical gradient based optimization algorithms for use in gradient-only approaches, and we then present gradient-only optimization strategies using both BFGS and a new spherical quadratic approximation for sequential approximate optimization (SAO). We then use the BFGS and SAO algorithms to solve three problems of practical interest, both unconstrained and constrained.     

Incomplete series expansion for function approximation

We present an incomplete series expansion (ISE) as a basis for function approximation. The ISE is expressed in terms of an approximate Hessian matrix, which may contain second, third, and even higher order “main” or diagonal terms, but which excludes “interaction” or off-diagonal terms. From the ISE, a family of approximation functions may be derived. The approximation functions may be based on an arbitrary number of previously sampled points, and any of the function and gradient values at suitable previously sampled points may be enforced when deriving the approximation functions. When function values only are enforced, the storage requirements are minimal. However, irrespective of the conditions enforced, the approximate Hessian matrix is a sparse diagonal matrix. In addition, the resultant approximations are separable. Hence, the proposed approximation functions are very well-suited for use in gradient-based sequential approximate optimization requiring computationally expensive simulations; a typical example is structural design problems with many design variables and constraints. We derived a wide selection of approximations from the family of ISE approximating functions; these include approximations based on the substitution of reciprocal and exponential intervening variables. A comparison with popular approximating functions previously proposed illustrates the accuracy and flexibility of the new family of approximation functions. In fact, a number of popular approximating functions previously proposed for structural optimization applications derive from our ISE. Based on the similarly named paper presented at the Sixth World Congress on Structural and Multidisciplinary Optimization, Rio de Janeiro, Brazil, May 2005     

On Padé approximations, quadratic stability and discretization of switched linear systems

In this note we consider the stability preserving properties of diagonal Padé approximations to the matrix exponential. We show that while diagonal Padé approximations preserve quadratic stability when going from continuous-time to discrete-time, the converse is not true. We discuss the implications of this result for discretizing switched linear systems. We also show that for continuous-time switched systems which are exponentially stable, but not quadratically stable, a Padé approximation may not preserve stability.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.     

Efficient additive kernels via explicit feature maps

Large scale nonlinear support vector machines (SVMs) can be approximated by linear ones using a suitable feature map. The linear SVMs are in general much faster to learn and evaluate (test) than the original nonlinear SVMs. This work introduces explicit feature maps for the additive class of kernels, such as the intersection, Hellinger's, and χ2 kernels, commonly used in computer vision, and enables their use in large scale problems. In particular, we: 1) provide explicit feature maps for all additive homogeneous kernels along with closed form expression for all common kernels; 2) derive corresponding approximate finite-dimensional feature maps based on a spectral analysis; and 3) quantify the error of the approximation, showing that the error is independent of the data dimension and decays exponentially fast with the approximation order for selected kernels such as χ2. We demonstrate that the approximations have indistinguishable performance from the full kernels yet greatly reduce the train/test times of SVMs. We also compare with two other approximation methods: Nystrom's approximation of Perronnin et al., which is data dependent, and the explicit map of Maji and Berg for the intersection kernel, which, as in the case of our approximations, is data independent. The approximations are evaluated on a number of standard data sets, including Caltech-101, Daimler-Chrysler pedestrians, and INRIA pedestrians.     

Bandwidth allocation and scheduling of networked control systems with exponential and quadratic approximations

This paper investigates bandwidth allocation and scheduling of networked control systems (NCSs) with nonlinear-programming techniques. The bandwidth utilization (BU) is defined in terms of sampling frequency. An exponential and a quadratic approximation are formulated to describe system performance versus the sampling frequencies. The optimal sampling frequencies are obtained by solving the approximations with Karush–Kuhn–Tucker (KKT) conditions. Experimental results verify the effectiveness of the proposed approximations and scheduling algorithms. The two approximations could find an optimal BU of an NCS with a given sequence of plants and maximize the total BU up to 98% of the total available bandwidth.     

Safety index calculation using intervening variables for structural reliability analysis

This paper utilizes the intervening design variables concept for structural reliability analysis. This procedure was traditionally used in structural optimization, whereas this work applies to problems having stochastic information. The present algorithm is on the basis of a safety index algorithm present in Ref. [1] [L. P. Wang and R. V. Grandhi, Efficient safety index calculation for structural reliability analysis. Comput. Struct. 52, 103–111 (1994)], which utilized the nonlinear approximation of performance function in the original space of random variables. The proposed algorithm further develops this procedure by (i) implementing the adaptive nonlinear approximation of performance function in the standard normal space of random variables, (ii) using an improved intervening variable procedure for more accurate approximation, and (iii) adding an additional convergency check on safety index calculation using approximate gradients. The efficiency and robustness of the proposed algorithm are demonstrated by several examples with highly nonlinear, complex, and explicit/implicit performance functions.     

A globally convergent sequential convex programming using an enhanced two-point diagonal quadratic approximation for structural optimization

In this study, we propose a sequential convex programming (SCP) method that uses an enhanced two-point diagonal quadratic approximation (eTDQA) to generate diagonal Hessian terms of approximate functions. In addition, we use nonlinear programming (NLP) filtering, conservatism, and trust region reduction to enforce global convergence. By using the diagonal Hessian terms of a highly accurate two-point approximation, eTDQA, the efficiency of SCP can be improved. Moreover, by using an appropriate procedure using NLP filtering, conservatism, and trust region reduction, the convergence can be improved without worsening the efficiency. To investigate the performance of the proposed algorithm, several benchmark numerical examples and a structural topology optimization problem are solved. Numerical tests show that the proposed algorithm is generally more efficient than competing algorithms. In particular, in the case of the topology optimization problem of minimizing compliance subject to a volume constraint with a penalization parameter of three, the proposed algorithm is found to converge well to the optimum solution while the other algorithms tested do not converge in the maximum number of iterations specified.     

Numerical methods for heat equation with variable coefficients

In this paper, two methods are developed for linear parabolic partial differential equation with variable coefficients, which are based on rational approximation to the matrix exponential functions. These methods are L-stable, third-order accurate in space and time. In the development of these methods, second-order spatial derivatives are approximated by third-order finite-difference approximations, which give a system of ordinary differential equations whose solution satisfies a recurrence relation that leads to the development of algorithms. These algorithms are tested on heat equation with variable coefficients, subject to homogeneous and/or time-dependent boundary conditions, and no oscillations are observed in the experiments. The method is also modified for a nonlinear problem. All these methods do not require complex arithmetic, and based on partial fraction technique, which is very useful for parallel processing.     

Discrete variable optimization of plate structures using dual methods

This study presents an efficient method for optimum design of plate and shell structures, when the design variables are continuous or discrete. Both sizing and shape design variables are considered. First the structural responses, such as element forces, are approximated in terms of some intermediate variables. By substituting these approximate relations into the original design problem, an explicit nonlinear approximate design task with high quality approximation is achieved. This problem with continuous variables can be solved very efficiently by means of numerical optimization techniques, the results of which are then used for discrete variable optimization. Now, the approximate problem is converted into a sequence of second level approximation problems of separable form, each of which is solved by a dual strategy with discrete design variables. The approach is efficient in terms of the number of required structural analyses, as well as the overall computational cost of optimization. Examples are offered and compared with other methods to demonstrate the features of the proposed method.     

On Finding the Maximum Feasible Subsystem of a System of Linear Inequalities

Some methods for finding the maximum feasible subsystems of systems of linear inequalities are considered. The problem of finding the most accurate algorithm in a parametric family of linear classification algorithms is one of the most important problems in machine learning. In order to solve this discrete optimization problem, an exact (combinatorial) algorithm, its approximations (relaxation and greedy combinatorial descent algorithms), and the approximation algorithm are given. The latter consists in replacing the original discrete optimization problem with a nonlinear programming problem by changing from linear inequalities to their sigmoid functions. The initial results of their comparison are presented.     

A family of third-order parallel splitting methods for parabolic partial differential equations

A family of numerical methods, based upon a new rational approximation to the matrix exponential function, is developed for solving parabolic partial differential equations. These methods are L-acceptable, third-order accurate in space and time, and do not require the use of complex arithmetic. In these methods second-order spatial derivatives are approximated by third-order finite-difference approximations.- Parallel algorithms are developed and tested on the one-dimensional heat equation, with constant coefficients, subject to homogeneous boundary conditions and time-dependent boundary conditions. These methods are also extended to two- and three-dimensional heat equations, with constant coefficients, subject to homogeneous boundary conditions.     

Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis

Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.     

A family of homogeneous analysis models for the design of scalable structures

Research in optimum structural design has shown that mathematical programming techniques can be employed efficiently only in conjunction with explicit approximate constraints. In the course of time a well-established approximation for homogeneous functions (scalable structures) has emerged based on the linear Taylor expansion of the displacement functions in the compliance design space (Reciprocal approximation). It has been shown that the quality of this approximation is based on the property that homogeneity of the constraints is maintained and consequently the approximation is exact along the scaling line.The present paper presents a new family of approximations of homogenous functions which have the same properties as the Reciprocal approximation and which produce more accurate models in most of the tested cases. The approximations are obtained by mapping the direct linear Taylor expansion of the constraints unto a space spanned by intervening variables (original design variables to a powerm). Taking the envelope of these constraints along the scaling line yields a new family of approximations governed by the parameterm. It is shown that the Reciprocal approximation is a particular member of this family of approximations (m = –1).The new technique is illustrated with classical examples of truss optimization. An optimal plate design is also reported. A parametric study of the results for various values of the exponentm is presented. It is shown that for special values of the exponentm the new approximations usually yield better models than those based on the Reciprocal approximation.     

A Hierarchy of Approximations of the Master Equation Scaled by a Size Parameter

Solutions of the master equation are approximated using a hierarchy of models based on the solution of ordinary differential equations: the macroscopic equations, the linear noise approximation and the moment equations. The advantage with the approximations is that the computational work with deterministic algorithms grows as a polynomial in the number of species instead of an exponential growth with conventional methods for the master equation. The relation between the approximations is investigated theoretically and in numerical examples. The solutions converge to the macroscopic equations when a parameter measuring the size of the system grows. A computational criterion is suggested for estimating the accuracy of the approximations. The numerical examples are models for the migration of people, in population dynamics and in molecular biology. Financial support has been obtained from the Swedish Foundation for Strategic Research and the Swedish Graduate School in Mathematics and Computing.     

Advanced approximations for sequential optimization with discrete material interpolations

The DMO (discrete material optimization) technique is employed in structural synthesis dealing with the selection of a material belonging to a group of candidate materials. It has mainly been employed in the optimization for orientation of layers of composite laminates. The DMO is based on an interpolation in the form of a weighted sum of candidate materials. The weights are nonlinear functions of penalized design variables that are solved by continuous optimization, leading to proper material selection. The preferred way of solution has been by sequential approximate optimization (SAO), based on Taylor series approximations (TSA) as surrogate functions of the structural responses. However, due to the complexity of the DMO formulation the classical local surrogate techniques become of questionable efficiency in adequately capturing structural response behavior. To improve the quality of the surrogate models, it is here proposed the use of the weighting functions to form intermediate design variables in terms of which a higher quality TSA is created. Improvements in the convergence characteristics of the SAO is observed, opening new perspectives to the efficient application of the DMO concept.