Quadratic Programming

Solution of Binary-Constrained Quadratic-Defined Optimization Problems by a Progressive Integer Programming Method

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the … Read more

Two-stage approach for the predispatch problem with uncertain demand using splitting variables in interior-point methods

Categories Applications - Science and Engineering, Quadratic Programming, Stochastic Programming Tags , , ,

The stochastic predispatch optimal power flow problem aims to minimize generation costs and transmission losses subject to network constraints under demand uncertainty. We formulate it as a two-stage stochastic quadratic optimization problem with fixed recourse, in which hydroelectric generation constitutes the here-and-now decision, while thermal generation and transmission flows are recourse decisions. Using a splitting-variable … Read more

Integer quadratic programming in fixed dimension is polynomial-time solvable

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , ,

We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether \(d^{\mathsf{T}}Qd\ge 0\) for every integer point \(d\) of a bounded symmetric … Read more

Sparsity-Preserving Integration of Convex Curvature Information into Linear Relaxations for Quadratic Unconstrained Binary Optimization

Categories Linear Programming, Quadratic Programming, Semi-definite Programming

We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags , , , ,

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective … Read more

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Categories Data Science Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more

Convexlikeness and Supportedness in Quadratic Multiobjective Optimization

Categories Multi-Criteria Optimization, Quadratic Programming Tags , , , , , , ,

This paper studies geometric and structural properties of quadratic multiobjective optimization problems. Thereby, a multiobjective optimization problem is called convexlike if the upper image, i.e., the image set plus the nonnegative orthant, is a convex set. Moreover, we say that a feasible point is supported in case it is a minimal solution of a weighted … Read more

Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion

Categories Cone Programming, Global Optimization Applications, Quadratic Programming Tags , , , ,

We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by sparse QCQPs whose lifted matrix variables include elements not directly specified by the objective or constraints, we interpret tightness as a rank-one completion property for the unspecified elements. For sparsity patterns whose blocks … Read more

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , , , , ,

We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more