65K05 Mathematical programming methods [See also 90Cxx]
Uncertainty is inevitable when solving science and engineering application problems. In the face of
uncertainty, it is essential to determine robust and risk-averse solutions. In this work,
we consider a class of PDE-constrained optimization problems in which the PDE coefficients
and inputs may be uncertain. We introduce two approximations for minimizing the
conditional value-at-risk for such PDE-constrained optimization problems. These approximations are based
on the primal and dual formulations of the conditional value-at-risk. For the primal problem,
we introduce a smooth approximation of the conditional value-at-risk in order to utilize
derivative-based optimization algorithms and to take advantage of the convergence properties
of quadrature-based discretizations. For this smoothed conditional value-at-risk, we prove
differentiability as well as consistency of our approximation. For the dual problem, we
regularize the inner maximization problem, rigorously derive optimality conditions, and demonstrate
the consistency of our approximation. Furthermore, we propose a fixed-point iteration that takes
advantage of the structure of the regularized optimality conditions and provides a means of calculating
worst-case probability distributions based on the given probability level. We conclude with numerical
results.
Using a standard first-order optimality condition for nonsmooth optimization problems, a general framework for a descent method is developed. This setting is applied to a class of mathematical programs with equilibrium constraints in function space from which a new algorithm is derived. Global convergence of the algorithm is demonstrated in function space and the results are then illustrated by numerical experiments.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use.
We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.
Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field.
In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.
This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies.
CIP is a generalization of MIP that supports the notion of general constraints as in CP.
This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving.
SCIP is available in source code and free for non-commercial use.
We demonstrate the usefulness of CIP on two tasks.
First, we apply the constraint integer programming approach to pure mixed integer programs.
Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers.
Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers.
The CIP approach is very effective here:
it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.
A new concept is introduced for the adaptive finite element discretization of partial differential equations that have a sparsely
representable solution. Motivated by recent work on compressed sensing, a recursive mesh refinement procedure is presented that uses linear programming to find a good approximation to the sparse solution on a given refinement level. Then only those parts of the mesh are refined that belong to nonzero expansion coefficients. Error estimates for this procedure are refined and the behavior of the procedure is demonstrated via some simple elliptic model problems.
In this paper we introduce a new method for the computation of KKT matrices that arise from solving constrained, nonlinear optimization problems. This method requires updating of null-space factorizations after a low rank modification. The update procedure has the advantage that it is significantly cheaper than a re-factorization of the system at each new iterate. This paper focuses on the cheap update of a rectangular LU decomposition after a rank-1 modification.
Two different procedures for updating the LU factorization are presented in detail and compared regarding their costs of computation and their stability. Moreover we will introduce an extension of these algorithms which further improves the computation time. This turns out to be an excellent alternative to algorithms based on orthogonal transformations.