65K05 Mathematical programming methods [See also 90Cxx]
A strictly feasible sequential convex programming method
- In free material optimization (FMO), one tries to find the best mechanical structure by minimizing the weight or by maximizing the stiffness with respect to given load cases. Design variables are the material properties represented by elasticity tensors or elementary material matrices, respectively, based on a given finite element discretization. Material properties are as general as possible, i.e., anisotropic, leading to positive definite elasticity tensors, which may be arbitrarily small in case of vanishing material. To guarantee a positive definite global stiffness matrix for computing design constraints, it is required that all iterates of an optimization algorithm retain positive definite tensors. Otherwise, some constraints, e.g., the compliance, cannot be evaluated and the algorithm fails. FMO problems are generalizations of topology optimization problems. The goal of topology optimization is to find the stiffest structure subject to given loads and a limited amount of material. In contrast to FMO the material is explicitly given and cannot vary. Based on a finite element discretization, in each element it is decided whether to use material or not. The regions with vanishing material are interpreted as void. The resulting optimization problem can be solved by numerous efficient nonlinear optimization methods, for example sequential convex programming methods. Sequential convex programming (SCP) formulates separable and strictly convex nonlinear subproblems iteratively by approximating the objective and the constraints. Lower and upper asymptotes are introduced to truncate the feasible region. Due to the special structure, the resulting subproblems can be solved efficiently by appropriate methods, e.g., interior point methods. To ensure global convergence, a line search procedure is introduced. Moreover, an active set strategy is applied to reduce computation time. The iterates of SCP are not guaranteed to be inside the corresponding feasible region described by the constraints. As a consequence it is not able to solve free material optimization problems as the compliance function is only well-defined on the feasible region of some of the constraints. We propose a modification of a SCP method that ensures feasibility with respect to a given set of inequality constraints. The resulting procedure is called feasible sequential convex programming method (SCPF). SCPF expands the resulting subproblems by additional nonlinear constraints, that are passed to the subproblem directly to ensure their feasibility in each iteration step. They are referred as feasibility constraints. In addition, other constraints may be violated within the optimization process. As globalization technique a line search procedure is used to ensure convergence. The resulting subproblems can be solved efficiently taking the sparse structure into account. Moreover, semidefinite constraints have to be replaced by nonlinear ones, such that SCPF is applicable. SCPF successfully solved FMO problems with up to 120.000 variables and 60.000 constraints. Within a theoretical analysis global convergence of SCPF is shown for convex feasibility constraints.
On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems
- In this thesis we focus on solution methods for convex mixed-integer nonlinear
optimization problems (MINLP). As one main result, we propose a new algorithm
guaranteeing global optimality for convex MINLPs under standard
assumptions. The new algorithm called MIQP-supported outer approximation
(MIQPSOA) incorporates the successive solution of convex mixed-integer
quadratic programs (MIQP) in a linear outer approximation framework. An extensive
numerical competitive study based on several different MINLP solvers shows,
that a first implementation of the new method performs well in terms of both
the reliability and the efficiency. Since the new method is designed to solve simulation-based optimization problems arising in practical engineering applications, the main performance criterion is the number of function evaluations required to solve a problem.
Furthermore, the test results indicate, that the integration of mixed-integer search steps, resulting from the solution of convex MIQPs, significantly improves the reliability and the efficiency compared to well-known linear outer approximation methods.
After reviewing available solution techniques for convex MINLP problems, we present the algorithmic set-up as well as the convergence proof of MIQPSOA. As pointed out in this dissertation, MIQPSOA is a first step towards a convergent MINLP solution method, that solely relies on the successive solution of convex MIQPs as proposed by Exler and Schittkowski. Finally, we present an extensive numerical test case study considering different solution methods for convex MINLPs.
The second part of this thesis deals with efficient solution techniques for
convex mixed-integer quadratic programs, that arise as subproblems during the
solution of MINLPs by MIQP-based algorithms, such as MIQPSOA. First, we
briefly review latest developments in state-of-the-art mixed-integer linear
(MILP) solvers, since we want to develop a MIQP solver that incorporates the most successful components of MILP solvers. As we focus on branch-and-bound methods, one main component is an efficient and robust sub-solver for continuous quadratic programs, which is able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs.
Extensive numerical tests show, that the performance of a branch-and-bound solver can be significantly increased by exploiting warmstarts. Furthermore, it turns out, that in a majority of the test cases, where disjunctive cutting planes exist, the calculation times are reduced up to a factor of more than 5. Nevertheless there are also instances, where the presents of disjunctive cutting planes significantly slows down the performance. Due to the efficient cut generation method developed within this thesis, the generation of cutting planes has almost no influence on the calculation time, if no disjunctive cuts exist, which is the case in about 45 \% of all test instances. As a consequence, the application of cutting planes for MIQPs needs further attention and especially a dynamic cut management might be very profitable. Finally, we compare the performance of our branch-and-cut solver MIQL with the solver SCIP, which is one of the state-of-the-art MILP solvers, that can also solve MIQPs. These tests indicate, that MIQL outperforms SCIP on hard MIQP instances, while SCIP is faster for simpler test cases.
New Trust Region SQP Methods for Continuous and Integer Optimization
- In this thesis new algorithms are presented that address nonlinear optimization problems. The algorithms belong to the class of sequential quadratic programming (SQP) methods. Two problem formulations that arise frequently in real-world applications are considered. Both have in common that functions are nonlinear and the formulations contain equality and inequality constraints. For the one class of problems the domain of all variables is R. These problems are called nonlinear programming (NLP) problems. Many applications also require that some of the featured variables are restricted to the domain Z. Problems with additional integer variables are called mixed-integer nonlinear programs (MINLP) and are also considered here.
This work is motivated by the advancement of an algorithm for solving MINLPs that was first discussed by Exler and Schittkowski (2007). The algorithm adapts concepts of SQP methods to mixed-integer nonlinear optimization. The new approach replaces the continuous quadratic problems by mixed-integer quadratic problems. The aim is to profit from the fast local convergence properties of SQP methods at least with respect to the continuous variables when integer variables remain fixed. Two new versions of the underlying algorithm of Exler and Schittkowski are presented.
It is well-known that SQP methods might not converge for any arbitrary starting point. To obtain global convergence, techniques of trust region methods are employed by the new algorithms. The first version of an algorithm for MINLPs presented in this thesis employs the Linf-penalty function as merit function. Applying this penalty function might lead to a slow convergence. The so-called Maratos effect requires the reduction of the step length so that fast convergence is lost. Hence, safeguards have to be added. The presented algorithm calculates additional second order correction (SOC) steps. Calculating SOC steps is a frequently used approach to obtain fast local convergence. There also exist other techniques. The SOC steps require additional function evaluations. Frequently, function values of mixed-integer problems arising in the field of engineering are evaluated by running time-consuming simulation tools, where a single function evaluation can take minutes or even hours. Thus, the goal of the development of an efficient method has to be that the number of needed function evaluations is as small as possible.
For that reason the investigation of methods that obtain fast local convergence without calculating SOC steps is the key aspect of this thesis. As a fundamental theory is available for NLPs, whereas MINLPs lack in most of these concepts, the main part of this thesis presents and analyzes a new trust region SQP algorithm addressing NLPs. The algorithm proposed here avoids the calculation of SOC steps by using an augmented Lagrangian function as merit function. In trust region methods a differentiable merit function, such as an augmented Lagrangian function, was employed in the past for equality constrained problems. Methods that also treat inequality constraints, transform these constraints into equality constraints. The new algorithm does not reformulate the underlying problem.
The proposed algorithm for NLPs is described in detail. The global and local convergence properties of the new algorithm are investigated. Under suitable assumptions it is shown that for any arbitrary starting point the sequence of generated iterates contains at least one accumulation point that is a Karush-Kuhn-Tucker point of the underlying NLP. Under certain conditions fast local convergence is proved, as full SQP steps will be accepted close to a solution. Thus, no additional SOC steps are required.
Due to the insight that is gained by the development of the algorithm for NLPs, an additional version of the algorithm for MINLPs can be stated. The second algorithm also enhances the algorithm of Exler and Schittkowski (2007), but does not calculate SOC steps anymore and the extra function evaluations are avoided.
All presented algorithms are implemented in FORTRAN and completely documented. The code is evaluated on a set of almost 500 test problems. Numerical results show the good performance of the new algorithms. The numerical tests of the algorithm for NLPs indicate that the theoretical convergence results hold in practice. Moreover, the efficiency of the second algorithm for MINLPs that does not calculate SOC steps has improved compared to the first version with SOC steps