Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

Maximum Entropy Estimates for Risk-Neutral Probability Measures with Non-Strictly-Convex Data

This article investigates use of the Principle of Maximum Entropy for approximation of the risk-neutral probability density on the price of a financial asset as inferred from market prices on associated options. The usual strict convexity assumption on the market-price to strike-price function is relaxed, provided one is willing to accept a partially supported risk-neutral density. This provides a natural and useful extension of the standard theory. We present a rigorous analysis of the related optimization problem via convex duality and constraint qualification on both bounded and unbounded price domains. The relevance of this work for applications is in explaining precisely the consequences of any gap between convexity and strict convexity in the price function. The computational feasibility of the method and analytic consequences arising from non-strictly-convex price functions are illustrated with a numerical example.     

Robust combinatorial optimization with variable budgeted uncertainty

We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty while being less conservative for vectors with few non-zero components. The feasibility set of the resulting optimization problem is in general non-convex so that we propose a mixed-integer programming reformulation for the problem, based on the dualization technique often used in robust linear programming. We show how to extend these results to non-binary variables and to more general multifunctions involving uncertainty set defined by conic constraints that are affine in the problem variables. We present a computational comparison of the budgeted uncertainty and the variable budgeted uncertainty on the robust knapsack problem. The experiments show a reduction of the price of robustness by an average factor of 18 %.     

CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization

The Conic Benchmark Library is an ongoing community-driven project aiming to challenge commercial and open source solvers on mainstream cone support. In this paper, 121 mixed-integer and continuous second-order cone problem instances have been selected from 11 categories as representative for the instances available online. Since current file formats were found incapable, we embrace the new Conic Benchmark Format as standard for conic optimization. Tools are provided to aid integration of this format with other software packages.     

A Full Nesterov–Todd Step Infeasible Interior-Point Method for Second-Order Cone Optimization

After a brief introduction to Jordan algebras, we present a primal–dual interior-point algorithm for second-order conic optimization that uses full Nesterov–Todd steps; no line searches are required. The number of iterations of the algorithm coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization to second-order conic optimization. As usual for infeasible interior-point methods, the starting point depends on a positive number. The algorithm either finds a solution in a finite number of iterations or determines that the primal–dual problem pair has no optimal solution with vanishing duality gap.     

Market neutral portfolios

In this paper we consider the problem of constructing a market neutral portfolio. This is a portfolio of financial assets that (ideally) exhibits performance independent from that of an underlying market as represented by a benchmark index. We formulate this problem as a mixed-integer nonlinear program, minimising the absolute value of the correlation between portfolio return and index return. Our model is a flexible one that incorporates decisions as to both long and short positions in assets. Computational results, obtained using the software package Minotaur, are given for constructing market neutral portfolios for eleven different problem instances derived from universes defined by S&P international equity indices. We also compare our approach against an alternative approach based on minimising the absolute value of regression slope (the zero-beta approach).     

Modeling, inference and optimization of regulatory networks based on time series data

In this survey paper, we present advances achieved during the last years in the development and use of OR, in particular, optimization methods in the new gene-environment and eco-finance networks, based on usually finite data series, with an emphasis on uncertainty in them and in the interactions of the model items. Indeed, our networks represent models in the form of time-continuous and time-discrete dynamics, whose unknown parameters we estimate under constraints on complexity and regularization by various kinds of optimization techniques, ranging from linear, mixed-integer, spline, semi-infinite and robust optimization to conic, e.g., semi-definite programming. We present different kinds of uncertainties and a new time-discretization technique, address aspects of data preprocessing and of stability, related aspects from game theory and financial mathematics, we work out structural frontiers and discuss chances for future research and OR application in our real world.     

On a class of bilevel linear mixed-integer programs in adversarial settings

We consider a class of bilevel linear mixed-integer programs (BMIPs), where the follower’s optimization problem is a linear program. A typical assumption in the literature for BMIPs is that the follower responds to the leader optimally, i.e., the lower-level problem is solved to optimality for a given leader’s decision. However, this assumption may be violated in adversarial settings, where the follower may be willing to give up a portion of his/her optimal objective function value, and thus select a suboptimal solution, in order to inflict more damage to the leader. To handle such adversarial settings we consider a modeling approach referred to as \(\alpha \)-pessimistic BMIPs. The proposed method naturally encompasses as its special classes pessimistic BMIPs and max–min (or min–max) problems. Furthermore, we extend this new modeling approach by considering strong-weak bilevel programs, where the leader is not certain if the follower is collaborative or adversarial, and thus attempts to make a decision by taking into account both cases via a convex combination of the corresponding objective function values. We study basic properties of the proposed models and provide numerical examples with a class of the defender–attacker problems to illustrate the derived results. We also consider some related computational complexity issues, in particular, with respect to optimistic and pessimistic bilevel linear programs.     

An extension of the Clark–Haussmann formula and applications

ABSTRACT

This work considers a financial market stochastic model where the uncertainty is driven by a multidimensional Brownian motion. The market price of the risk process makes the transition between real world probability measure and risk neutral probability measure. Traditionally, the martingale representation formulas under the risk neutral probability measure require the market price of risk process to be bounded. However, in several financial models the boundedness assumption of the market price of risk fails; for example a financial market model with the market price of risk following an Ornstein–Uhlenbeck process. This work extends the Clark–Haussmann representation formula to underlying stochastic processes which fail to satisfy the standard requirements. Our methodology is classical, and it uses a sequence of mollifiers. Our result can be applied to hedging and optimal investment in financial markets with unbounded market price of risk. In particular, the mean variance optimization problem can be addressed within our framework.     

Mixed-integer minimax dynamic optimization for structure identification of glycerol metabolic network

Cell metabolism is a dynamic regulation process, in which its network structure and/or regulatory mechanisms can change constantly over time due to internal and external perturbations. This paper models glycerol metabolism in continuous fermentation as a nonlinear mixed-integer dynamic system by defining the time-varying metabolic network structure as an integer-valued function. To identify the dynamic network structure and kinetic parameters, we establish a mixed-integer minimax dynamic optimization problem with concentration robustness as its objective functional. By direct multiple shooting strategy and a decomposition approach consisting of convexification, relaxation and rounding strategy, the optimization problem is transformed into a large-scale approximate multistage parameter optimization problem. It is then solved using a competitive particle swarm optimization algorithm. We also show that the relaxation problem yields the best lower bound for the optimization problem, and its solution can be arbitrarily approximated by the solution obtained from rounding strategy. Numerical results indicate that the proposed mixed-integer dynamic system can better describe cellular self-regulation and response to intermediate metabolite inhibitions in continuous fermentation of glycerol. These numerical results show that the proposed numerical methods are effective in solving the large-scale mixed-integer dynamic optimization problems.     

Polyhedral approximation in mixed-integer convex optimization

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.     

Conic approximation to quadratic optimization with linear complementarity constraints

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm.     

Multi‐period mean variance portfolio selection under incomplete information

This paper solves an optimal portfolio selection problem in the discrete‐time setting where the states of the financial market cannot be completely observed, which breaks the common assumption that the states of the financial market are fully observable. The dynamics of the unobservable market state is formulated by a hidden Markov chain, and the return of the risky asset is modulated by the unobservable market state. Based on the observed information up to the decision moment, an investor wants to find the optimal multi‐period investment strategy to maximize the mean‐variance utility of the terminal wealth. By adopting a sufficient statistic, the portfolio optimization problem with incompletely observable information is converted into the one with completely observable information. The optimal investment strategy is derived by using the dynamic programming approach and the embedding technique, and the efficient frontier is also presented. Compared with the case when the market state can be completely observed, we find that the unobservable market state does decrease the investment value on the risky asset in average. Finally, numerical results illustrate the impact of the unobservable market state on the efficient frontier, the optimal investment strategy and the Sharpe ratio. Copyright © 2016 John Wiley & Sons, Ltd.     

Communication protocols for options and results in a distributed optimization environment

Much has been written about optimization instance formats. The MPS standard for linear mixed-integer programs is well known and has been around for many years. Other extensible formats are available for other optimization categories such as stochastic and nonlinear programming. However, the problem instance is not the only piece of information shared between the instance generator and the solver. Solver options and solver results must also be communicated. To our knowledge there is no commonly accepted format for representing either solver options or solver results. In this paper we propose a framework and theory for solver option and solver result representation in a modern distributed computing environment. A software implementation of the framework is available as an open-source COIN-OR project.     

Minimization of the root of a quadratic functional under an affine equality constraint

We present a way of solving the problem of minimizing the root of quadratic functional subject to an affine constraint. We give an explicit formula for computing the solutions of such a problem. This is of interest for solving significant problems of financial economics as well as some classes of feasibility and optimization problems which frequently occur in tomography and other fields.     

Lifting for conic mixed-integer programming

Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming as one may expect.     

Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we discuss the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition which we propose as a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical experiments on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.     

Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization

We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow–Schwartz regularization method, which has already been applied to Markowitz portfolio problems.     

Distributionally robust simple integer recourse

The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.