Questions tagged [quadratic-programming]

For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).

Filter by
Sorted by
Tagged with
16
votes
3answers
994 views

Bin Packing with Relational Penalization

There are $ N $ bins with equal capacity $ C $. In addition, there are $ N $ objects $x_1, x_2, \dots, x_N $ that need to be accommodated using the least amount of bins. Each object $x_i$ has a volume ...
16
votes
3answers
432 views

How to model nonlinear regression?

As part of my research in statistics, I recently stumbled upon this paper1 which provides an operational perspective into linear models. In simple linear regression, quadratic programming can be used ...
16
votes
2answers
946 views

Divisibility constraints in integer programming

In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer ...
16
votes
2answers
527 views

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

The closest thing I know is the computer vision problem, in which an image is de-blurred and/or de-noised by quadratizing a quartic problem into a quadratic optimization problem (QUBO) and then the ...
16
votes
2answers
270 views

Can we replace a binary variable with a continuous variable using a quadratic equality constraint?

Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$? The function $f(x) = x^2 -x$ is not a convex function. Can ...
14
votes
4answers
1k views

CPLEX non-convex Quadratic Programming algorithms

CPLEX solves non-convex quadratic problems to global optimality with a global optimality option (in version 12). The relevant pages are this and this. I benchmarked many solvers, and see that CPLEX ...
14
votes
1answer
853 views

What is quadratization?

In the context of discrete optimization, what exactly does it mean to "quadratize" a function? The term seems to be used mainly by operations researchers, in my experience.
12
votes
2answers
256 views

Where can I find test instances for convex quadratic programming?

I am looking for (sources of) convex quadratic programming instances with linear constraints. I am open for both continuous and mixed integer problems, but do not want randomly generated instances. ...
11
votes
1answer
441 views

Efficient way to solve "easy" quadratic optimization problem

The linear program \begin{align} \min &\sum_{i=1}^nc_{i}x_{i}\\\ \mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\ &x_{i}\geq 0,&&\forall i=1,\dots,n \end{align} has a trivial optimal solution ...
11
votes
1answer
159 views

Quadratic programming using CPLEX: how to check whether candidate is an extreme point?

I am currently solving an indefinite quadratic program with linear constraints using CPLEX. Moreover, I am trying to determine whether the candidate point CPLEX is feeding my callback function is an ...
10
votes
6answers
2k views

Nonlinear integer (0/1) programming solver

I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
10
votes
4answers
1k views

Integer programming problem with simple quadratic objective function in Python

I have $n$ objects that need to be divided among $k$ groups. Each group must receive at least $5$ objects. In addition, the percentage of objects in group $i$ should be as close as possible to $p_i$ ...
10
votes
2answers
150 views

Global optimality condition of non-convex quadratic programs

We know that a convex quadratic maximization (not minimization!) on a polyhedron has its global optimal value on a vertex. Also, I have read in some papers that checking whether a vertex is globally ...
9
votes
1answer
254 views

How can I model regression with an asymmetric loss function?

Mosek provided a concrete example of using the Huber loss function, Huber loss, which is great! One problem I am trying to tackle is to use asymmetric loss, as described in the answer of asymmetric ...
9
votes
2answers
335 views

Convexity of a QP

In quadratic programming (QP), you encounter an objective of the following form: $$x^TQx + c^Tx$$ and often it's desirable to know if the QP is convex. One method to check for convexity is by ...
8
votes
2answers
186 views

Inverse Ising problem

Inverse Ising Problem The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins. Each spin $s_{i}$ is either +1 or -1. The ...
8
votes
2answers
124 views

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$ I would like to efficiently solve the following problem: Problem 1 Choose $\alpha,z\in\mathbb{R}^m,\beta\...
8
votes
0answers
92 views

For subset selection regression as a mixed integer program, how tightly should the bounding box be set?

When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
7
votes
3answers
968 views

How do Quadratic Programming solvers handle variables without bounds?

Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound. This requires that $x$ and $y$ have given bounds, how do they handle the case ...
7
votes
2answers
379 views

How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint. $\max \eta$ subject to ${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$ here $\bf{A}$ is a Binary ...
7
votes
1answer
133 views

Bilinear programming vs Mixed integer linear programming performance comparison

I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, ...
7
votes
1answer
166 views

Why is there a constant in the objective function of the *best subset selection problem*?

This article presents the following formulation of the best subset selection problem $$\min_{\|\beta\|_0\leq k}\frac{1}{2}\|y-X\beta\|^2_2$$ I wonder where the $1/2$ comes from. Help appreciated.
6
votes
4answers
166 views

Sequential quadratic programming source

What are the good text books to learn SQP? Are there any online courses that you can suggest?
6
votes
2answers
114 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019. It's a problem about minimizing a sum of terms that are ...
6
votes
2answers
444 views

Assignment problem where assignments must be done sequentially

I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, ...
6
votes
1answer
413 views

Is there any open source quadratic programming solver with C# API

I have a quadratic programming model (i.e., quadratic objective function and linear constraint) and, I want to solve it on an open-source solver. Since our project developed on C#, we also would like ...
6
votes
0answers
120 views

Water quality component optimization

I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain ...
6
votes
0answers
94 views

Cases where RLT/SDP relaxation does not work well with standard quadratic optimization

(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax ...
5
votes
1answer
265 views

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
5
votes
2answers
192 views

Piecewise linear and global optimization

I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data. I would like to understand: Can this ...
5
votes
1answer
196 views

PAVA-like solution to simple QP

Let $l,u\in\mathbb{R}^n$, and consider the QP: $$\min_{l\le x\le u} {(\Delta x)^\top (\Delta x)}$$ where $\Delta x=[x_2-x_1,\,x_3-x_2,\,\dots,\,x_n-x_{n-1}]^\top$. I.e. we want to minimize the squared ...
5
votes
2answers
237 views

How to linearize a quadratic constraint to add it then via a callback function

Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound. How can we linearize the term $x^2$? Detailled problem: Suppose that via a callback we compute a ...
5
votes
1answer
152 views

Solver Recommendation : Discrete Variables and Quadratic Constraints

I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is ...
4
votes
1answer
95 views

Continuous minimax with linear objective and constraints

How to solve the following minimax problem quickly? The variables are all continuous. $$\max_{x_{1}, x_{4}, x_{5}} \min_{x_2,x_3} \vec{c}^{\intercal} \vec{x}$$ subject to the following constraints: $$...
4
votes
1answer
117 views

How do I formulate constraints that check if a parameter is between certain values, using binary variables?

I have $3$ parameters $a_1,a_2,a_3$ and a variable $d$ and $3$ binary variables $b_1,b_2,b_3$ and a "result" variable $s$. How do I model constraints so that: If $d$ is between $0$ and $a_1$...
4
votes
1answer
112 views

Linear objective function with power term in constraint

Given $n$ variables $x_{i}$ where $i\in [0,n)$, denoted as a vector $x$, given a linear objective function that we want to minimize $c^\top x$ with 2 constraints: $\sum x_{i}^{2} < n+1$ $\sum\log(...
4
votes
1answer
356 views

Transforming a Quadratic constraint to SOCP

I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
4
votes
1answer
173 views

Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?

I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf One of the steps is to transform the inequalities ...
3
votes
1answer
303 views

Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program

A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive ...
3
votes
2answers
89 views

Implementing NLP as QP on docplex

I wanna learn how to solve non-linear programs using the docplex library. according to this link I should be able to run the model as a QP. But when running the model I got the error: ...
3
votes
1answer
182 views

Linearizing a quadratic function with more variables or not in Gurobi?

Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= ...
3
votes
1answer
161 views

Linearizing power term in objective function

I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to ...
3
votes
1answer
60 views

optimizing quadratic form over bounded polytope

As a followup to this question, I am looking for references for the problem of maximizing $x^TQx$, where $Q$ is positive definite, subject to linear equality and inequality constraints bounding all ...
3
votes
1answer
94 views

How to exponentiate binary variables in QUBO-type problems?

Ising Model In an Ising model, the Hamiltonian of one configuration of spins $\vec{s}$ is: $$ H(\vec{s}, \mathcal{J}, \mathcal{h}) = \sum_{i} h_{i} s_{i} + \sum_{i \ne j}J_{ij} s_{i}s_{j} $$ where ...
3
votes
1answer
105 views

How do I arrive at the form given in this paper, for the QUBO version of the number partitioning problem?

In this article A new modeling and solution approach for the number partitioning problem1, it transforms the number partition problem into a QUBO form like equation (2.1) on page 2. $$\text{diff}=\...
3
votes
1answer
330 views

Supported pyomo free solvers for (non-convex) quadratic programming

Any one had the chance to use pyomo with free/open-source solvers that handle quadratic optimization problems, which they could be convex or not, but preferably as general as possible.
3
votes
0answers
48 views

Automatic quadratization of constraints in pyomo for gurobi

Gurobi 9 can solve QCQPs, and QCQPs capture all of polynomial optimization by the obvious trick that e.g. a cubic term $x_1 x_2 x_3$ can be turned into a quadratic term $y x_3$ and a constraint $y = ...
3
votes
0answers
129 views

SDP relaxation with greater-than and less-than inequalities at the same time

I am dealing with the following nonconvex fractional quadratic optimization problem \begin{align} & \min_{\boldsymbol{x}} && \max_{t \in \mathcal{T}} \frac{\boldsymbol{a}_t^T \boldsymbol{...
2
votes
3answers
316 views

Why can quadratic functions over polyhedrons be minimized exactly in finite time?

I have heard it said that QP problems $$\min f(x) = \frac 12 x^TAx + b^T x$$ $$x \in P$$ where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can ...
2
votes
1answer
70 views

Convex function subject to $0\le x_1\le \ldots \le x_n\le 1$ and linear constraint

I am maximizing a convex function (a positive definite quadratic form, if it makes a difference) subject to $0\le x_1\le \ldots \le x_n\le 1$ and a linear constraint $a^\top x+b=0$. Can I conclude ...