Reformulation and convex relaxation techniques for global optimization

We survey the main results obtained by the author in his PhD dissertation supervised by Prof. Costas Pantelides. It was defended at the Imperial College, London. The thesis is written in English and is available from . The most widely employed deterministic method for the global solution of nonconvex NLPs and MINLPs is the spatial Branch-and-Bound (sBB) algorithm, and one of its most crucial steps is the computation of the lower bound at each sBB node. We investigate different reformulations of the problem so that the resulting convex relaxation is tight. In particular, we suggest a novel technique for reformulating a wide class of bilinear problems so that some of the bilinear terms are replaced by linear constraints. Moreover, an in-depth analysis of a convex envelope for piecewise-convex and concave terms is performed. All the proposed algorithms were implemented in , an object-oriented callable library for constructing MINLPs in structured form and solving them using a variety of local and global solvers.Received: March 2004, MSC classification: 90C26, 90C20, 90C06     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Surrogate duality for robust optimization

Robust optimization problems, which have uncertain data, are considered. We prove surrogate duality theorems for robust quasiconvex optimization problems and surrogate min–max duality theorems for robust convex optimization problems. We give necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, and show some examples at which such duality results are used effectively. Moreover, we obtain a surrogate duality theorem and a surrogate min–max duality theorem for semi-definite optimization problems in the face of data uncertainty.     

A robust robust optimization result

We study the loss in objective value when an inaccurate objective is optimized instead of the true one, and show that “on average” this loss is very small, for an arbitrary compact feasible region.     

Likelihood robust optimization for data-driven problems

We consider optimal decision-making problems in an uncertain environment. In particular, we consider the case in which the distribution of the input is unknown, yet there is some historical data drawn from the distribution. In this paper, we propose a new type of distributionally robust optimization model called the likelihood robust optimization (LRO) model for this class of problems. In contrast to previous work on distributionally robust optimization that focuses on certain parameters (e.g., mean, variance, etc.) of the input distribution, we exploit the historical data and define the accessible distribution set to contain only those distributions that make the observed data achieve a certain level of likelihood. Then we formulate the targeting problem as one of optimizing the expected value of the objective function under the worst-case distribution in that set. Our model avoids the over-conservativeness of some prior robust approaches by ruling out unrealistic distributions while maintaining robustness of the solution for any statistically likely outcomes. We present statistical analyses of our model using Bayesian statistics and empirical likelihood theory. Specifically, we prove the asymptotic behavior of our distribution set and establish the relationship between our model and other distributionally robust models. To test the performance of our model, we apply it to the newsvendor problem and the portfolio selection problem. The test results show that the solutions of our model indeed have desirable performance.     

鲁棒信用风险优化的线性锥优化模型

考虑了具有强健性的信用风险优化问题. 根据最差条件在值风险度量信用风险的方法,建立了信用风险优化问题的模型. 由于信用风险的损失分布存在不确定性,考虑了两类不确定性区间,即箱子型区间和椭球型区间. 把具有强健性的信用风险优化问题分别转化成线性规划问题和二阶锥规划问题. 最后,通过一个信用风险问题的例子来说明此模型的有效性.     

Data-driven robust optimization

Mathematical Programming - The last decade witnessed an explosion in the availability of data for operations research applications. Motivated by this growing availability, we propose a novel schema...     

Aggregation-based cutting-planes for packing and covering integer programs

Mathematical Programming - In this paper, we study the strength of Chvátal–Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs)....     

Duality for constrained robust sum optimization problems

Mathematical Programming - Given an infinite family of extended real-valued functions $$f_{i}$$ , $$i\in I,$$ and a family $${\mathcal {H}}$$ of nonempty finite subsets of I,  the...     

An approximation technique for robust nonlinear optimization

Nonlinear equality and inequality constrained optimization problems with uncertain parameters can be addressed by a robust worst-case formulation that is, however, difficult to treat computationally. In this paper we propose and investigate an approximate robust formulation that employs a linearization of the uncertainty set. In case of any norm bounded parameter uncertainty, this formulation leads to penalty terms employing the respective dual norm of first order derivatives of the constraints. The main advance of the paper is to present two sparsity preserving ways for efficient computation of these derivatives in the case of large scale problems, one similar to the forward mode, the other similar to the reverse mode of automatic differentiation. We show how to generalize the techniques to optimal control problems, and discuss how even infinite dimensional uncertainties can be treated efficiently. Finally, we present optimization results for an example from process engineering, a batch distillation.     

Mixed uncertainty sets for robust combinatorial optimization

In robust optimization, the uncertainty set is used to model all possible outcomes of uncertain parameters. In the classic setting, one assumes that this set is provided by the decision maker based on the data available to her. Only recently it has been recognized that the process of building useful uncertainty sets is in itself a challenging task that requires mathematical support. In this paper, we propose an approach to go beyond the classic setting, by assuming multiple uncertainty sets to be prepared, each with a weight showing the degree of belief that the set is a “true” model of uncertainty. We consider theoretical aspects of this approach and show that it is as easy to model as the classic setting. In an extensive computational study using a shortest path problem based on real-world data, we auto-tune uncertainty sets to the available data, and show that with regard to out-of-sample performance, the combination of multiple sets can give better results than each set on its own.

     

Generating hard instances for robust combinatorial optimization

While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution.In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances.     

Exact relaxations for parametric robust linear optimization problems

We first show that the closedness of the characteristic cone of the constraint system of a parametric robust linear optimization problem is a necessary and sufficient condition for each robust linear program with the finite optimal value to admit exact semidefinite linear programming relaxations. We then provide the weakest regularity condition that guarantees exact second-order cone programming relaxations for parametric robust linear programs.     

Modal criteria for robust optimization of vibroacoustic systems

This work is an extension of the work done in previous papers (Besset and Jézéquel in Intern J Numer Method Eng 70(5):523–542, 2007; J Vib Acoust 130(1):011008, 2008; Intern J Numer Method Eng 73:1347–1373, 2008; J Vib Acoust 130(3):031009, 2008). It deals with modal criteria allowing to process optimization of structures including robustness. The system considered in the paper is a fluid-structure system. The aim of the paper is to use component mode synthesis methods to optimize the geometry of the structure and the robustness with respect to the design parameter variations of its vibroacoustic behaviour. Two criteria will be proposed. The first one is directly linked to the pressure level in the acoustic cavity. The second one is linked to the robustness of the methods. It comes from the polynomial chaos study of the considered system. A classical multiobjective optimization is then processed and Pareto graphics are proposed to represent the optimal solutions of the optimization problem.     

Derivative-free optimization and neural networks for robust regression

Large outliers break down linear and nonlinear regression models. Robust regression methods allow one to filter out the outliers when building a model. By replacing the traditional least squares criterion with the least trimmed squares (LTS) criterion, in which half of data is treated as potential outliers, one can fit accurate regression models to strongly contaminated data. High-breakdown methods have become very well established in linear regression, but have started being applied for non-linear regression only recently. In this work, we examine the problem of fitting artificial neural networks (ANNs) to contaminated data using LTS criterion. We introduce a penalized LTS criterion which prevents unnecessary removal of valid data. Training of ANNs leads to a challenging non-smooth global optimization problem. We compare the efficiency of several derivative-free optimization methods in solving it, and show that our approach identifies the outliers correctly when ANNs are used for nonlinear regression.     

Algorithm robust for the bicriteria discrete optimization problem

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.     

Min-max and robust polynomial optimization

We consider the robust (or min-max) optimization problem

$J^*:=\max_{\mathbf{y}\in{\Omega}}\min_{\mathbf{x}}\{f(\mathbf{x},\mathbf{y}): (\mathbf{x},\mathbf{y})\in\mathbf{\Delta}\}$

where f is a polynomial and \({\mathbf{\Delta}\subset\mathbb{R}^n\times\mathbb{R}^p}\) as well as \({{\Omega}\subset\mathbb{R}^p}\) are compact basic semi-algebraic sets. We first provide a sequence of polynomial lower approximations \({(J_i)\subset\mathbb{R}[\mathbf{y}]}\) of the optimal value function \({J(\mathbf{y}):=\min_\mathbf{x}\{f(\mathbf{x},\mathbf{y}): (\mathbf{x},\mathbf{y})\in \mathbf{\Delta}\}}\). The polynomial \({J_i\in\mathbb{R}[\mathbf{y}]}\) is obtained from an optimal (or nearly optimal) solution of a semidefinite program, the ith in the “joint + marginal” hierarchy of semidefinite relaxations associated with the parametric optimization problem \({\mathbf{y}\mapsto J(\mathbf{y})}\), recently proposed in Lasserre (SIAM J Optim 20, 1995-2022, 2010). Then for fixed i, we consider the polynomial optimization problem \({J^*_i:=\max\nolimits_{\mathbf{y}}\{J_i(\mathbf{y}):\mathbf{y}\in{\Omega}\}}\) and prove that \({\hat{J}^*_i(:=\displaystyle\max\nolimits_{\ell=1,\ldots,i}J^*_\ell)}\) converges to J* as i → ∞. Finally, for fixed ? ≤ i, each \({J^*_\ell}\) (and hence \({\hat{J}^*_i}\)) can be approximated by solving a hierarchy of semidefinite relaxations as already described in Lasserre (SIAM J Optim 11, 796–817, 2001; Moments, Positive Polynomials and Their Applications. Imperial College Press, London 2009).

     

鲁棒优化中的Pareto有效性

对于一般的不确定优化问题, 研究了鲁棒解的~Pareto 有效性. 首先, 证明了Pareto 鲁棒解集即是鲁棒解集的Pareto 有效集, 因此求Pareto 鲁棒解等价于求鲁棒解集的Pareto 有效元. 其次, 基于推广的epsilon-约束方法, 得到了Pareto 鲁棒解的生成方法.     

Design and verify: a new scheme for generating cutting-planes

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory–Chvátal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality $cx \le d$ where $c$ and $d$ are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set $P \cap \{x\in \mathbb R ^n \mid cx \ge d + 1\} \cap \mathbb Z ^n$ is empty using cutting-planes from the black-box. Here $P$ is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures.