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
0 votes
1 answer
36 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{...
UserX's user avatar
  • 103
2 votes
1 answer
145 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 ...
Mohammad Namakshenas's user avatar
2 votes
2 answers
83 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 (...
Muhammad Wasif's user avatar
1 vote
1 answer
32 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 ...
Muhammad Wasif's user avatar
1 vote
1 answer
52 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 ...
svanderk's user avatar
1 vote
1 answer
123 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$). ...
Carol Eisen's user avatar
5 votes
2 answers
293 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 ...
Pipob Puthipiroj's user avatar
3 votes
1 answer
129 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,...
Abbas Khademi's user avatar
-2 votes
1 answer
71 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?
scouse_s's user avatar
1 vote
1 answer
97 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{...
happy's user avatar
  • 63
3 votes
2 answers
814 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 ...
happy's user avatar
  • 63
1 vote
1 answer
196 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 ...
jbuddy_13's user avatar
  • 471
3 votes
0 answers
90 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[...
christouandr7's user avatar
1 vote
2 answers
198 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}\...
happy's user avatar
  • 63
2 votes
1 answer
170 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},\ ...
cfp's user avatar
  • 235
3 votes
2 answers
285 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 ...
twaits791's user avatar
4 votes
0 answers
107 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 ...
kchnkrml's user avatar
4 votes
1 answer
415 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 ...
overboxed's user avatar
  • 573
1 vote
0 answers
65 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. ...
worldsmithhelper's user avatar
6 votes
2 answers
174 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$-...
Ramin Fakhimi's user avatar
10 votes
1 answer
260 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$ ...
ntrstd11's user avatar
  • 235
2 votes
2 answers
188 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,...
Mike's user avatar
  • 147
1 vote
0 answers
180 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 ...
Mike's user avatar
  • 147
1 vote
0 answers
61 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}...
orpanter's user avatar
  • 423
5 votes
3 answers
147 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_{...
AspiringMat's user avatar
2 votes
1 answer
399 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 ...
GTek's user avatar
  • 307
5 votes
1 answer
160 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-...
Displayed_Name's user avatar
5 votes
1 answer
328 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 ...
Displayed_Name's user avatar
3 votes
1 answer
132 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 ...
inf's user avatar
  • 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 ...
Alberto Santini's user avatar
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 ...
Daniel Paleka's user avatar
4 votes
1 answer
236 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 ...
gjgutier545's user avatar
2 votes
1 answer
316 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 ...
Saba Kiani's user avatar
2 votes
1 answer
106 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\}$ ...
worldsmithhelper's user avatar
3 votes
0 answers
90 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 = ...
Martin Koutecký's user avatar
7 votes
1 answer
939 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 ...
cyy's user avatar
  • 73
3 votes
1 answer
78 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 ...
sayda's user avatar
  • 31
2 votes
2 answers
131 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 ...
wayne's user avatar
  • 21
2 votes
1 answer
78 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 ...
sayda's user avatar
  • 23
4 votes
1 answer
161 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: $$...
Qurious Cube's user avatar
7 votes
1 answer
371 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, ...
TUI lover's user avatar
  • 173
3 votes
1 answer
139 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 ...
Qurious Cube's user avatar
7 votes
2 answers
297 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 ...
Qurious Cube's user avatar
4 votes
1 answer
162 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$...
Koli's user avatar
  • 43
1 vote
0 answers
151 views

Optimization Multiple Constraints

I am trying to solve a linear algebra problem: an optimization problem and I am using CVXOPT. I've split the problem into 3 components In its simplest form, The general formulation for CVXOPT is \...
Marco_sbt's user avatar
  • 173
2 votes
1 answer
82 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_{...
Ibrahim Amer's user avatar
3 votes
1 answer
209 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}=\...
Steve Deltora's user avatar
3 votes
1 answer
866 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 ...
Ibrahim Amer's user avatar
1 vote
0 answers
202 views

Solver issue? Xpress (slp) - Nonlinear - Python - Pyomo

I tried solving my model with xpress: pip install xpress And then in the model: ...
PM0087's user avatar
  • 111
11 votes
1 answer
563 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 ...
Sune's user avatar
  • 6,072