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.     

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     

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.     

Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.     

Solving asymmetric variational inequalities via convex optimization

Using duality, we reformulate the asymmetric variational inequality (VI) problem over a conic region as an optimization problem. We give sufficient conditions for the convexity of this reformulation. We thereby identify a class of VIs that includes monotone affine VIs over polyhedra, which may be solved by commercial optimization solvers.     

On approximating the nearest Ω‐stable matrix

In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples.     

A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints

We consider distributionally robust two-stage stochastic linear optimization problems with higher-order (say \(p\ge 3\) and even possibly irrational) moment constraints in their ambiguity sets. We suggest to solve the dual form of the problem by a semi-infinite programming approach, which deals with a much simpler reformulation than the conic optimization approach. Some preliminary numerical results are reported.     

Cascading: an adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust conic problem.      

“Cone-free” primal-dual path-following and potential-reduction polynomial time interior-point methods

We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.Part of the research was done while the author was a Visiting Professor at the University of Waterloo.Research of this author is supported in part by a PREA from Ontario and by a NSERC Discovery Grant. Tel: (519) 888-4567 ext.5598, Fax: (519) 725-5441Mathematics Subject Classification (2000): 90C51, 90C25, 65Y20,90C28, 49D49     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Distributionally robust chance constraint with unimodality-skewness information and conic reformulation

Moment-based ambiguity sets are mostly used in distributionally robust chance constraints (DRCCs). Their conservatism can be reduced by imposing unimodality, but the known reformulations do not scale well. We propose a new ambiguity set tailored to unimodal and seemingly symmetric distributions by encoding unimodality-skewness information, which leads to conic reformulations of DRCCs that are more tractable than known ones based on semi-definite programs. Besides, the conic reformulation yields a closed-form expression of the inverse of unimodal Cantelli's bound.     

On self-concordant barrier functions for conic hulls and fractional programming

Given a self-concordant barrier function for a convex set , we determine a self-concordant barrier function for the conic hull of . As our main result, we derive an “optimal” barrier for based on the barrier function for . Important applications of this result include the conic reformulation of a convex problem, and the solution of fractional programs by interior-point methods. The problem of minimizing a convex-concave fraction over some convex set can be solved by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to an equivalent convex reformulation of the original problem. Our main result allows to analyze the second approach showing that the rate of convergence is of the same order in both cases.     

Completely positive reformulations of polynomial optimization problems with linear constraints

A polynomial optimization problem (POP) is an optimization problem in which both the objective and constraints can be written in terms of polynomials on the decision variables. Recently, it has been shown that under appropriate assumptions POPs can be reformulated as conic problems over the cone of completely positive tensors; which generalize the set of completely positive matrices. Here, we show that by explicitly handling the linear constraints in the formulation of the POP, one obtains a generalization of the completely positive reformulation of quadratically constrained quadratic programs recently introduced by Bai et al. (Math Program 1–28, 2016).     

Quadratic double-ratio minimax optimization

The quadratic double-ratio minimax optimization (QRM) admits a generalized linear conic fractional reformulation. It leads to two algorithms to globally solve (QRM) from the primal and dual sides, respectively. The hidden convexity of (QRM) remains unknown except for the special case when both denominators are equal.     

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 %.     

Stronger upper and lower bounds for a hard batching problem to feed assembly lines

In this paper we present an Integer Programming reformulation for a hard batching problem encountered in feeding assembly lines. The study was motivated by the real process to feed the production flow through the shop floor in a leading automobile industry in Brazil. The problem consists of deciding the assignment of items to containers and the frequency of moves from the storage area to the line in order to meet demands with minimum cost. Better lower and upper bounds were obtained by a branch-and-bound algorithm based on the proposed reformulation. We also present valid inequalities that may improve such algorithm even further.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.     

From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

   Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

Symmetry-exploiting cuts for a class of mixed-0/1 second-order cone programs

We will analyze mixed-0/1 second-order cone programs where the continuous and binary variables are solely coupled via the conic constraints. We devise a cutting-plane framework based on an implicit Sherali–Adams reformulation. The resulting cuts are very effective as symmetric solutions are automatically cut off and each equivalence class of 0/1 solutions is visited at most once. Further, we present computational results showing the effectiveness of our method and briefly sketch an application in optimal pooling of securities.