Questions tagged [quadratic-programming]

For questions about optimizing an objective function that is quadratic in its input variables. This could include questions about implementing solver methods or choosing the right solver for a given problem.

Filter by
Sorted by
Tagged with
12
votes
2answers
6k views

Solving a least squares problem with linear constraints in Python

I need to solve \begin{alignat}{1} & \min_{x}\|Ax - b\|^2_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat} I think it is a ...
10
votes
2answers
4k views

Calculating Lagrange coefficients for SVM in Python

I'm trying to write a full SVM implementation in Python and I have a few issues computing the Lagrange coefficients. First let me rephrase what I understand from the algorithm to make sure I'm on the ...
8
votes
1answer
276 views

Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?

I'm interested in a type of problem on this form $$\min_{x} x^{T}Ax+x^{T}b \quad \text{s.t} \quad x^{T}x=1 $$ where $A$ is positive definite. As you can see, if it weren't for the $x^{T}b$ term in the ...
6
votes
1answer
1k views

Algorithm for solving system of quadratic equations and linear equations

Let $x \in R^N$. From a Spectral Chebyshev collocation method, I have a system of quadratic and linear equations. Denote them, $$ x^T Q_i x + L_i^T x = 0 $$ and $$ A x = 0 $$ Furthermore, I know ...
5
votes
2answers
3k views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
5
votes
1answer
5k views

Convex Optimization problem with sum of absolute value constraints

How to solve the optimization problem written below? $$\begin{align} &\operatorname{argmax}\limits_{a}\; a^T b - \frac{1}{2} a^T X a\\ &\text{subject to } \sum_i |a_i|=4,\; \sum_i a_i = 0 \...
5
votes
1answer
115 views

Complementary quadratic knapsack problem

The quadratic knapsack problem (QKP) $$\max_x x^TPx$$ $$\mathrm{s.t.}\;\;w^Tx\leq c,\; x\in\{0,1\}$$ where $P\geq0, w\geq0$ elementwise, is well studied and has existing solvers. My problem below ...
5
votes
2answers
235 views

What is a suitable algorithm for solving a large mixed-integer quadratic program?

I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n \...
5
votes
0answers
95 views

Generally quadratic convex problem with one non-convex term

How would you approach a standard convex quadratic problem with convex constraints but one non-convex term ? Say $|x|^{0.4}$. $$\min_x \frac{1}{2} x^{T}Qx + g^Tx + c^T \mathrm{sign}(x) |x|^{0.4} $$ ...
5
votes
0answers
106 views

Minimum of quadratic assignment (QAP) with convex objective

Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem: $$ \min_{\textrm{permutation matrices }P} \mathrm{tr}(BP^\top AP+C^\top ...
5
votes
0answers
154 views

Multi-matrix orthogonal basis problem

Suppose we are given a set of symmetric, positive definite matrices $A_1,A_2,\ldots,A_k\in\mathbb{R}^{n\times n}$. Is there any numerical method or reduction to a known problem (e.g. eigenvalue ...
4
votes
1answer
2k views

Why does MATLAB's quadprog outperform MOSEK for my problem?

For a problem I am trying to solve it appears MOSEK's Quadratic Program solver is 100 times slower than MATLAB's Interior Point solver. Has anyone encountered this behavior in the past, or maybe ...
4
votes
2answers
1k views

Quadratic programs with rank deficient positive semidefinite matrices

Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
4
votes
1answer
1k views

Converting convex quadratic constraint to linear matrix inequality (LMI)

I have the quadratic programming problem in $x$ $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{25mm}\boldsymbol{1}^Tx=1$$ ...
4
votes
1answer
1k views

Solver suggestion for many small quadratic problem in C++

I have a C++ program/model that in some parts already use IPOPT (with ADOL-C and ColPack) to solve some pretty large non linear problems. Now in an other part of the program I need to solve a large ...
4
votes
1answer
231 views

Which optimization method can be used to do the following?

I've the following system of equations for studying information flow in the below graph, $$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$ Here, M is the incidence ...
4
votes
3answers
171 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
4
votes
0answers
165 views

Eigenvalue-style optimization with quadratic constraints

Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric and positive definite and that we have several symmetric matrices $B_i\in\mathbb{R}^{n\times n}$ that are low-rank and indefinite. I need an ...
3
votes
2answers
660 views

Solver for a MIQP with an indefinite coefficient matrix

Do CPLEX or Gurobi handle MIQPs with indefinite coefficient matrices? The problem I am dealing with has quadratic terms in which one variable is binary and the other variable is continuous. The ...
3
votes
3answers
1k views

Minimizing a negative definite quadratic function with specified bounds

I have the following quadratic program $$\begin{array}{ll} \text{minimize} & f(x) = \frac{1}{2} x^T D x + c^T x\\ \text{subject to} & x_{\text{lower}} < x < x_{\text{upper}}\end{array}$$...
3
votes
2answers
115 views

Approximating solutions to quadratic recurrence boundary value problem

Cross-posted from Math Stackexchange: https://math.stackexchange.com/questions/2421964/approximating-solutions-to-quadratic-recurrence I have a branching process problem that has been reduced to ...
3
votes
2answers
455 views

Quadratic Programming: Quadprog

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
3
votes
1answer
353 views

What is the fastest way to solve Ax=b (subject to constraints and an absolute term)

I am trying to solve/optimize $Ax=b$ in the least squares sense subject to box constraints; a few (less than 5) equality/inequality constraints; and an absolute function penalty (or some other ...
3
votes
2answers
143 views

A separable nonnegative quadratic program

I have spent quite some time trying to solve the following quadratic program: $$\min \sum_{i=1}^n (\frac{1}{2}x_i^TQx_i+c_i^Tx_i), \quad \mathrm{s.t. } \quad x_i\ge 0 \quad \forall i,$$ where $n$ is ...
3
votes
1answer
1k views

Sparse quadratic programming solver

For a hobby project I need to solve a series of quadratic programming problems each with about 500 variables about 1000 constraints, each of the form $x_i-x_j\le c_{ij}$ the objective function is the ...
3
votes
1answer
77 views

Improve optimization speed for a set of similar problems: Quadratic programming with a warm start

I am repeatedly solving quadratic program, $x^T Q x$ with time dependent linear constraints $Ax=b_t$. Dimension of $x$ is around 10000 and there are around 50 constraints. I want to solve the ...
3
votes
1answer
76 views

Solving multiple least-square problems with the same constraints

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin): $$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$ where the parameters of the ...
3
votes
0answers
159 views

Automatically generate constraints for trajectory optimization

This is a follow up to my previous post here I'm interested in performing trajectory optimization from the problem mentioned in abov link. I want to supply the following as dynamical constraints to ...
2
votes
2answers
1k views

Modeling a quadratic constraint with a linear expression

In a problem I am trying to model with a MIP program, the following scenario occurs: I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. ...
2
votes
1answer
89 views

Checking positive definiteness on a hyperplane

Is there a faster way to check whether $A\in\mathbb{R}^{n\times n}$ is positive definite on $b^{\bot}:=\{x\in \mathbb{R}^{n}: x\cdot b=0\}$ than ...
2
votes
1answer
145 views

Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
2
votes
1answer
471 views

0,1 binary polynomial programming

Is there a mathematical optimization branch that explicitly tries to optimize this (type) problem? $$\eqalign{ & \min \cr & \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + {J_2}...
2
votes
2answers
1k views

Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is ...
2
votes
1answer
112 views

Is solving QP easier than a QCQP with linear objective?

Is solving a $QP$ (i.e.: quadratic program, hence a quadratic objective function with linear constraints) easier than solving a $QCQP$ (ie.: quadratic constrained quadratic problem) with linear ...
2
votes
2answers
354 views

Approach to handle a quadratic constraint xy <= z

I have non-linear constraints like $ x_1x_2\leq x_3 $ where $ x_1,x_2,x_3\geq 0 $. The objective is linear, and all other constraints are linear, too. I know that I can transform the product as $ ...
2
votes
1answer
183 views

Solving the quadratic in the Fast Iterative Method

The Fast Iterative Method is a way of solving the Eikonal Equation on a discrete grid, similar to the Fast Marching Method discussed in another question here. The paper describes the overall ...
2
votes
1answer
121 views

Project to nearest point on convex polyhedron

I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
2
votes
0answers
25 views

Barrier algorithm Gurobi and interior-point quadprog; what kind of matrices can it handle the best (sparse or dense, large or small problems)?

I am trying to solve a QP problem. Does anybody know the differences between the interior-point-convex algorithm of quadprog and the barrier method of Gurobi in terms which kind of matrices can the ...
2
votes
0answers
67 views

"Solution path" for quadratic program as regularizer changes

I am solving a quadratic program with regularization parameter $\alpha\geq0$ to get the solution to a problem of the form $$ p(\alpha):= \arg\min_{p\in\mathbb{R}^n}\ [\alpha(v^\top p)+f(p)], $$ where $...
2
votes
0answers
89 views

Disjunctive programming software

Can you advise me any kind of existing software that can help to solve the disjunctive programming problem? The problem is the following. We have unit 3D planes $\Pi_{1}, \ldots, \Pi_{N}$ (they are ...
1
vote
3answers
2k views

Minimize quadratic form with equality constraints

I want to minimize function: $f(x) = x^T \cdot A \cdot x + b \cdot x$ given constraints: $B \cdot x = 0$. Here: $x$ is a vector ($x \in \mathbb{R}^n$), $A$ is a matrix of size $n \times n$, $b$ ...
1
vote
2answers
1k views

Solving absolute value quadratic optimization problem

would you please help me to solve following problem $$x^*= \text{argmin}\ xLx^T+ |P^Tx|$$ $x$ is binary $P$ is a known vector (with positive and negative values) $L$ is Laplacian matrix I have ...
1
vote
3answers
386 views

rank-deficient NNLS

I want to find the minimum-norm solution to a rank-deficient least-squares problem, subject to positivity constraints, e.g. $$\min_x\ \|x\|^2 \quad s.t.\quad Ax = b,\ x \geq 0$$ where $A$ is large, ...
1
vote
2answers
141 views

Solving a parameter estimation problem using trajectory optimization

This is a follow-up to my previous question here I've the following system of equations for studying information flow in the below graph, $$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise ...
1
vote
2answers
132 views

Factoring a quadratic function

I have a quadratic binary optimization problem of the form \begin{align} &\max x^TQx \cr &\text{subject to }x\in\mathcal{X}\subseteq\{0,1\}^n, \end{align} where $\mathcal{X}$ is the feasible ...
1
vote
1answer
53 views

Overconstraining in SQP

In Sequential Quadratic Programming we use an active set of the inequality constraints and handle them as equality constraints in the quadratic subproblem. SQP is said to be able to deal with ...
1
vote
1answer
410 views

What is the fastest method for solving a quadratic programm repeatedly,( warmstarted)?

I would like to solve the following optimization problem \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} $Q$ is a positive semidefinite matrix. $\lambda>0$ is a ...
1
vote
1answer
150 views

How to efficently solve: min $\sum_{ij}(a_{ij}x_{ij}^2 + b_{ij}x_{ij})$ s.t

I am trying to solve the following problem, where $a_{ij} \ge 0 \ \forall i,j$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject to}\...
1
vote
1answer
505 views

Mixed-integer quadratic programming, state of art [closed]

I used Gurobi with a MIQP with 26 binary variables and 26*4 interaction term without any other constraint. The speed is very slow already.... I want to ask what is the state of art of MIQP solvers. ...
1
vote
1answer
754 views

Quadratic Programming bound constraints

I have a quadratic programming problem with constraints of the general form: Minimize w.r.t. x: f(x) = (1/2) x^T * Q * x + c^T * x subject to one or more ...