Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
106
questions
3
votes
0
answers
111
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,198
0
votes
0
answers
15
views
Problem in understanding an equation from a paper about iterative Linear-Quadratic Regulator
I'm reading a paper about iterative Linear-Quadratic Regulator (iLQR) and there are a lot of points that I don't understand.
https://homes.cs.washington.edu/~todorov/papers/TassaICRA14.pdf
I think ...
- 101
1
vote
0
answers
34
views
Convex quadratic maximization over cartesian product of simplices
Suppose we are maximizing $f(x^1,\ldots,x^t)= \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}^\top Q \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}$ ...
- 3,980
2
votes
0
answers
80
views
Does the value function of a quadratic program stay convex when adding constraints?
I am interested in the value function of a quadratic program of the form
$$
v(y)=\min_x \frac{1}{2} x^\top Q(y) x,
$$
subject to a linear equality constraint
$$
E(y)x=d(y),
$$
and a linear inequality ...
- 121
2
votes
1
answer
68
views
How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?
This question is about an optimization problem that arises in support vector regression (SVR). Suppose you have $N$ pairs $(\vec{x}_n, y_n)$ as data and would like to find a vector of weights $\vec w \...
- 123
0
votes
0
answers
61
views
How do I implement this convex problem in CVXPY?
I am looking to implement the following optimization problem in CVXPY.
$$ \max _{x_t} x_t' \mu - \frac{\gamma}{2} x'_t \Sigma x_t - x'_t\Lambda \Delta x_t $$
where $\Delta x_t := x_t - x_{t-1}$ and $\...
- 1
5
votes
3
answers
213
views
Randomly constructing a bounded ellipsoid
In a project, I am working with constraints of the following type
$$ \frac{1}{2}{x}^\top Q x + q^\top x + q_0 \leq 0 $$
where I randomly generate the data by (randn...
- 3,980
2
votes
1
answer
59
views
epigraphs for quadratic constraints
I have a constraint of the following form
\begin{equation}
x^{\top}x + y^{\top}y \leq t
\end{equation}
where x, y are vector variables and t is a scalar variable. I can augment the variables x and y, ...
- 153
3
votes
2
answers
153
views
Simplest Quadratic Programming algorithm for teaching
Can anyone recommend a straightforward quadratic programming (QP) algorithm suitable for an undergraduate engineering class? I'm interested in finding an algorithm that they can easily grasp and ...
0
votes
1
answer
81
views
Simulating an integer quadratic knapsack problem
I am trying to simulate the following quadratic integer program using $\textsf{cvxpy}$:
$$ \begin{array}{ll} \underset {x_1, \dots, x_K} {\text{minimize}} & \displaystyle\sum\limits_{i=1}^{K}\frac{...
- 103
2
votes
1
answer
207
views
Looking for a reliable and scalable open source quadratic solver
In the convex optimization community, there has been a growing concern regarding the search for a reliable open-source solver (especially a quadratic programming solver) that can effectively deliver ...
2
votes
2
answers
97
views
Potential methods for solving quadratic optmization problem
I am trying to solve a non-convex optimization problem with the help of sequential quadratic programming.
I need to develop an algorithm inside SQP to solve this subproblem. What potential methods (...
- 67
1
vote
1
answer
33
views
Non convex quadratic problem with complex variables
I am trying to solve a non convex optimization problem with the help of sequential quadric programing. My optimization variables are complex and I have expressions for gradients, hessian etc but all ...
- 67
1
vote
1
answer
55
views
Quadratic optimization with non-constant coefficients
I have a series of functions (very similar to convex quadratic equations, see the first comment below) $f_1(x), f_2(x), \dots, f_n(x)$. Each of these functions touches the $x$-axis at $a_i$, which can ...
- 13
3
votes
1
answer
204
views
Solver for quadratically constrained mixed-integer linear programs
I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
- 203
5
votes
2
answers
422
views
Simple OLS problem can only be solved in SCS. Is the dual infeasible?
Essentially, I am trying to solve a simple orthogonal least-squares (OLS) problem with some constraints — the coefficients must sum to $1$, no coefficient can be less than $0$, and no coefficient can ...
3
votes
1
answer
175
views
How do I pass an objective bound to Gurobi?
I have a non-convex Quadratic Programming over unite simplex set. I have a valid lower bound on the objective function (goal is minimization problem).
If I add a constraint like
$$f(x)\geq lower~bound,...
-2
votes
1
answer
92
views
Converting a quadratic objective function in piecewise linear function
The objective function is of the form:
$max$ $x^2/2+y^2/2+z^2/2$
I would like to convert it to piecewise linear function. How do I achieve that?
- 1
1
vote
1
answer
106
views
How to model and solve such a 0-1 programming problem
My problem is described in this picture(It's like a Pyramid structure):
The objective function is below: $$\min\sum_{k=1}^\ell\sum_{i=0}^{2^k-1}\sum_{j=0}^{2^k-1}\left(A_{i,j}^k-A_{i,j+1}^k\cdot\frac{...
- 63
3
votes
2
answers
930
views
Is solving a quadratic programming optimization problem using python slower than C++？
I am using the cvxpy library in python to solve a quadratic programming problem and the solver used is scip. I found that when the amount of data becomes large, the solution process will be ...
- 63
2
votes
1
answer
357
views
MIQP — CVXPY unable to treat summation of variables as a variable
I have a quadratic integer programming assignment problem. The goal is to assign riders seats on a bus such that distance between any two riders is maximized; however, the importance of each objective ...
- 501
3
votes
0
answers
117
views
Linearize objective function with non-linear terms
I have a problem with linear constraints but in the objective function I want to have some linear terms along with a $x^2$ term. So it is like the following:
$$\min \sum \limits _i \sum \limits _j (a[...
1
vote
2
answers
256
views
How to solve this mixed integer quadratic program using cvxpy or other method?
My problem is described in this picture:
$$
\begin{array}{l}
\left\{\begin{array}{l}
\text { objective function: } \\
f = \min \sum_\limits{l=1}^2 \sum_\limits{i=0}^{2^l-1} \sum_\limits{j=0}^{2^l-2}\...
- 63
2
votes
1
answer
258
views
Poorly conditioned quadratic programming with "simple" linear constraints
I have many quadratic programming problems of the following form:
$$\min_{x\in\mathbb{R}^n} { \tfrac{1}{2} {\lVert Cx-d \rVert}^2} $$
$$\textrm{s.t.}\ x_1\le 0,\ x_n\le 0,\ x_n\le a_1^\top x_{1:n-1},\ ...
- 235
3
votes
2
answers
368
views
How to view pause and view current solution in CPLEX Optimization Studio?
I am solving my first model in CPLEX 22.1. I have setup a quadratic MIP with 100 variables and the model has been running for a day already with the best integer and best bound solutions barely ...
- 63
4
votes
0
answers
140
views
Analytical solution of constrained quadratic program
I'm trying to solve a "simple" (= small) optimization problem often, with only minor changes to the objective function. Therefore it's important to keep the "time per solve" as low ...
- 41
4
votes
1
answer
470
views
Is this a non-linear integer model?
Let's say if I have two decision variables, $f$ and $g$ respectively, where $f$ is continuous, and $g$ is binary.
If I have a constraint like this,
$$ f\cdot g \le C$$
Does this make my model ...
- 593
1
vote
0
answers
71
views
Does Gurobi solve QCQMIPs with Quadratic terms faster with then Bi-Linear terms in general?
Based on the color distance function defined here i try to find $n$ RGB colors with large inter set color distances and good color distance to white.
...
- 3,975
6
votes
2
answers
200
views
When should we avoid linearizing a quadratic term?
Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-...
- 169
10
votes
1
answer
372
views
Sensitivity analysis of QP
Given a quadratic program
$$
f^* \equiv x^\top Q x + b^\top x \\
x \geq 0 \\
A^\top x = d \\
x \in \mathbb{R}^n
$$
I would like to analyze the sensitivity of the solution $x^*$ to perturbations in $Q$ ...
- 235
2
votes
2
answers
224
views
Difference between constraint formulation and performance
I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.
At first:
$$
a,b,...
- 147
1
vote
0
answers
227
views
Converting quadratic constrains to linear constraint [closed]
I try to convert a quadratic constraint to a linear one:
$$
w_j = \sum w_\text{j,i} \\
w_\text{j,i} = \frac{w_j}{D} \times u \\
w_j,D,u \in \mathbb{N} \\
$$
The values for $w_j$ and $D$ are constant ...
- 147
1
vote
0
answers
65
views
Dual of a quadratic constraint
This is my model.
\begin{align}
\min_x&\quad\sum_{e\in E} X_e p_e \\
\text{s.t.}&\quad\sum_{e \in E: T(e)=i} X_e - \sum_{e \in E: H(e)=i} X_e = \begin{cases}1, \;\text{if}\;i=s\\-1,\;\text{if}...
- 507
5
votes
3
answers
152
views
What is the go-to practical method for optimizing separable quadratic programs?
I have a quadratic program that looks like this:
For fixed vector $b$, and matrices $A_1, ..., A_n$, Find column vectors $x_1, ..., x_n$ that minimize $\sum_{i=1}^n x_i ^T 1 1^T x_i$ subject to $\sum_{...
- 151
2
votes
1
answer
492
views
Can docplex solve a mixed integer quadratic programming (MIQP) problem?
I am trying to solve a mixed integer quadratic programming (MIQP) problem.
The objective function contains the product of two continuous decision variables, some of constraints are non-linear too. I ...
- 307
5
votes
1
answer
184
views
How to handle a non-separable bilinear objective function in the special case of decoupled constraints?
I have a large number of (10000+) non-negative, real decision variables $x_i$ and $y_j$.
Let $I$ and $J$ be the index sets associated with $x$ and $y$, respectively.
Let $\bar{I}$ and $\bar{J}$ be non-...
- 135
5
votes
1
answer
371
views
How to handle a bilinear objective function in the special case of decoupled constraints?
I have decision variables $x_i$ and $y_j$, real positive variables.
I would like to minimize objective function
\begin{aligned}
\min \quad & \sum_{ij} x_iy_j \\
\end{aligned}
All constraints are ...
- 135
3
votes
1
answer
175
views
Translate standard weighted least square regression to quadratic programming
Sorry if this is really easy for you gurus. I'm trying to derive the reformulation of a weighted least square regression to a quadratic programming form. I understand there is a closed form solution ...
- 129
11
votes
5
answers
3k
views
A Stack Overflow user's curious problem of maximising unsortedness
User ddofborg posted on Stack Overflow a programming question which hides a combinatorial optimisation problem.
The idea is the following: given a list of URLs with their respective domain names, he ...
- 2,073
3
votes
1
answer
67
views
Maximizing the number of nonnegative coordinates of $Wx$
I want to find good incumbent solutions to the following problem:
$\newcommand{\RR}{\mathbb{R}}$
$\newcommand{\norm}[1]{\left\Vert#1\right\Vert}$
Given a matrix $W \in \RR^{m \times n}$, find the ...
- 133
4
votes
1
answer
292
views
Can you calculate the mean of some MIP variables using linear constraints?
got a lingering question from a graduate course in integer programming that's been bugging me ever since.
Is it possible to find the mean of some variables in a MIP without resorting to quadratic ...
- 140
2
votes
1
answer
357
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 ...
- 45
2
votes
1
answer
118
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,975
3
votes
0
answers
95
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 = ...
7
votes
1
answer
1k
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 ...
- 73
3
votes
1
answer
98
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 ...
- 131
2
votes
2
answers
137
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 ...
- 21
2
votes
1
answer
79
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 ...
- 23
4
votes
1
answer
166
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:
$$...
- 523
7
votes
1
answer
430
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, ...
- 173