Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints

Quadratic Convex Reformulation (QCR) is a technique that has been proposed for binary and mixed integer quadratic programs. In this paper, we extend the QCR method to convex quadratic programs with linear complementarity constraints (QPCCs). Due to the complementarity relationship between the nonnegative variables $y$ and $w$ , a term $y^{T}Dw$ can be added to the QPCC objective function, where $D$ is a nonnegative diagonal matrix chosen to maintain the convexity of the objective function and the global resolution of the QPCC. Following the QCR method, the products of linear equality constraints can also be used to perturb the QPCC objective function, with the goal that the new QP relaxation provides a tighter lower bound. By solving a semidefinite program, an equivalent QPCC can be obtained whose QP relaxation is as tight as possible. In addition, we extend the QCR to a general quadratically constrained quadratic program (QCQP), of which the QPCC is a special example. Computational tests on QPCCs are presented.     

A branch-and-bound algorithm for instrumental variable quantile regression

This paper studies a statistical problem called instrumental variable quantile regression (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NP-hard—we develop a branch-and-bound algorithm to solve it globally. We also derive bounds on key variables in the problem, which are valid asymptotically for increasing sample size. We compare our method with two well known global solvers, one of which requires the computed bounds. On random instances, our algorithm performs well in terms of both speed and robustness.     

A polyhedral study of nonconvex quadratic programs with box constraints

By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].Mathematics Subject Classification (2000): 90C26, 90C27, 90C20     

A branch-and-bound method for discretely-constrained mathematical programs with equilibrium constraints

We present a branch-and-bound algorithm for discretely-constrained mathematical programs with equilibrium constraints (DC-MPEC). This is a class of bilevel programs with an integer program in the upper-level and a complementarity problem in the lower-level. The algorithm builds on the work by Gabriel et al. (Journal of the Operational Research Society 61(9):1404–1419, 2010) and uses Benders decomposition to form a master problem and a subproblem. The new dynamic partition scheme that we present ensures that the algorithm converges to the global optimum. Partitioning is done to overcome the non-convexity of the Benders subproblem. In addition Lagrangean relaxation provides bounds that enable fathoming in the branching tree and warm-starting the Benders algorithm. Numerical tests show significantly reduced solution times compared to the original algorithm. When the lower level problem is stochastic our algorithm can easily be further decomposed using scenario decomposition. This is demonstrated on a realistic case.     

Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1?h of CPU time by a standard solver.     

On linear programs with linear complementarity constraints

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ ₀ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.     

An LPCC approach to nonconvex quadratic programs

Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving two linear programs with linear complementarity constraints, i.e., LPCCs. Specifically, this task can be divided into two LPCCs: the first confirms whether the QP is bounded below on the feasible set and, if not, computes a feasible ray on which the QP is unbounded; the second LPCC computes a globally optimal solution if it exists, by identifying a stationary point that yields the best quadratic objective value. In turn, the global resolution of these LPCCs can be accomplished by a parameter-free, mixed integer-programming based, finitely terminating algorithm developed recently by the authors, which can be enhanced in this context by a new kind of valid cut derived from the second-order conditions of the QP and by exploiting the special structure of the LPCCs. Throughout, our treatment makes no boundedness assumption of the QP; this is a significant departure from much of the existing literature which consistently employs the boundedness of the feasible set as a blanket assumption. The general theory is illustrated by 3 classes of indefinite problems: QPs with simple upper and lower bounds (existence of optimal solutions is guaranteed); same QPs with an additional inequality constraint (extending the case of simple bound constraints); and nonnegatively constrained copositive QPs (no guarantee of the existence of an optimal solution). We also present numerical results to support the special cuts obtained due to the QP connection.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

Solving mixed integer nonlinear programs by outer approximation

A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for thel ₁ norm is also given.This work is supported by SERC grant no. SERC GR/F 07972.Corresponding author.     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

A feasible filter SQP algorithm with global and local convergence

A feasible sequential quadratic programming (SQP) filter algorithm is proposed for general nonlinear programming. It is based on the modified quadratic programming (QP) subproblem in which each iteration proceeds in two phases. The first phase solves a general convex QP problem which does not require any feasibility restoration phase whose computation may be expensive. And, under some mild conditions, the global convergence is proved. The second phase can make the presented SQP method derive quadratic convergence by employing exact Hessian information.     

A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for the SVM QP with n variables, this rule can be implemented in O(n) operations using Rockafellar’s notion of conformal realization. Thus, for SVM training, our method requires only O(n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Descent algorithm for nonsmooth stochastic multiobjective optimization

An algorithm for solving nearly-separable quadratic optimization problems (QPs) is presented. The approach is based on applying a semismooth Newton method to solve the implicit complementarity problem arising as the first-order stationarity conditions of such a QP. An important feature of the approach is that, as in dual decomposition methods, separability of the dual function of the QP can be exploited in the search direction computation. Global convergence of the method is promoted by enforcing decrease in component(s) of a Fischer–Burmeister formulation of the complementarity conditions, either via a merit function or through a filter mechanism. The results of numerical experiments when solving convex and nonconvex instances are provided to illustrate the efficacy of the method.     

Error bounds and strong upper semicontinuity for monotone affine variational inequalities

Global error bounds for possibly degenerate or nondegenerate monotone affine variational inequality problems are given. The error bounds are on an arbitrary point and are in terms of the distance between the given point and a solution to a convex quadratic program. For the monotone linear complementarity problem the convex program is that of minimizing a quadratic function on the nonnegative orthant. These bounds may form the basis of an iterative quadratic programming procedure for solving affine variational inequality problems. A strong upper semicontinuity result is also obtained which may be useful for finitely terminating any convergent algorithm by periodically solving a linear program.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grants CCR-9101801 and CCR-9157632.     

A kind of nonmonotone filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. But the QP subproblem may be inconsistent. In this paper, we propose a kind nonmonotone filter method in which the QP subproblem is consistent. By means of nonmonotone filter, this method has no demand on the penalty parameter which is difficult to obtain. Moreover, the restoration phase is not needed any more. Under reasonable conditions, we obtain the global convergence of the algorithm. Some numerical results are presented.     

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region. As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods. In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method, which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior to doing (curved) line searches. As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration. The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical results are reported on all problems from the MCPLIB collection [8]. Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002 RID="★" ID="★" This work was supported in part by the Australian Research Council. Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence AMS subject classifications. 90C33, 90C30, 65H10