Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
65
questions
2
votes
1answer
115 views
CPLEX solver for quadratic problems with barrier algorithm
I'm writing a convex minimization model with a quadratic objective function and linear constraints in C#.
I set CPLEX to solve the problem with the barrier algorithm. The interesting thing is when I ...
2
votes
1answer
72 views
Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP
I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
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 = ...
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 ...
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 ...
2
votes
2answers
69 views
How to use `cplexAPI` to solve quadratic programs/quadratically constrained linear programs?
I am trying to use cplexAPI to solve quadratic programs or quadratically constrained linear program.
While it seems to be pretty straightforward to use ...
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 ...
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:
$$...
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, ...
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 ...
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 ...
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$...
1
vote
0answers
76 views
Optimisation Multiple Constraints
I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components
In its simplest form, The general formulation for CVXOPT is \...
2
votes
1answer
71 views
Subtracting Values from a Positive semidefinite Matrix in a Semidefinite Program
I'm trying to construct an SDP relaxation for a non-convex quadratic program ($x^{\intercal}\mathbf{H}x$) with the following objective function:
\begin{equation}
x_{11}y_{11} + x_{12}y_{12} + x_{21}y_{...
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
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 ...
1
vote
0answers
69 views
Solver issue? Xpress (slp) - Nonlinear - Python - Pyomo
I tried solving my model with xpress:
pip install xpress
And then in the model:
...
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 ...
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 ...
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 ...
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 ...
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 ...
1
vote
1answer
67 views
Integral of PWL-Constraint in Gurobi (Java)
In my optimization model, I use piecewise-linear constraints with the output of $y[m]$. The question or problem I have now is whether there is a way in Gurobi (Java) to form the integral for this PWL ...
1
vote
1answer
105 views
Method (Algorithm) and Objective used in Gurobi Model
How can I find out which method or algorithm was used to solve my model? When I use GRB.IntParam.Method- to output the method, I get ...
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 ...
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= ...
2
votes
0answers
41 views
Is this semidefinite constraint in fact pointless?
On Wikipedia, I encountered a statement that the semidefinite relaxation of a quadratically constrained quadratic program can be solved more efficiently (using only LP) in the case that no variable is ...
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 ...
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 ...
2
votes
1answer
93 views
Minimizing a quadratic binary nonconvex function by CPLEX
I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX.
In particular, my function is the following:
$$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{...
2
votes
1answer
58 views
Non RLT-Cutting planes for nonconvex QPs?
Consider a general nonconvex QP $x^\top Qx$. This can be linearized in an extended space by using the variable $Y=xx^\top$.
Now a valid inequality $a^\top x \le b$ can be strengthend by the RLT ...
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(...
2
votes
0answers
77 views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
2
votes
0answers
60 views
Determine set of "arbitrage-free" regional prices
I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market.
There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
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 ...
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
0answers
85 views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
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 ...
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_{...
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 ...
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\...
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
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{...
1
vote
0answers
84 views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
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.
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 ...
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
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, ...
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.
