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
2
votes
1answer
109 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
1answer
119 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 \...
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 ...
0
votes
0answers
40 views

Implementation method selection for sparse constrained linear least squares or quadratic programming

I need to slove one optimization problem of quadratic programming. The number of optimization variables is about 16,000. The constraints include equality constraints and inequality constraints. I have ...
8
votes
1answer
275 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 ...
1
vote
0answers
51 views

Quadratic optimization with nonlinear vector term

I wish to minimize the quantity $$W=1/2x^TAx-x^Tg(y)$$ with respect to $x$ and $y$, which are vectors of unknowns. $A$ is a sparse square symmetric positive definite matrix and $g(y)$ is a vector with ...
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
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 ...
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 ...
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 ...
4
votes
1answer
230 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 ...
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 ...
1
vote
1answer
2k views

Why am I getting this DCPError?

I'm trying to optimize a binary portfolio vector to be greater than a benchmark using CVXPY. ...
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 ...
1
vote
1answer
801 views

Reformulate a strictly convex QP problem containing absolute value term

Can the following strictly convex optimization problem be reformulated into a standard form that is also a strictly convex problem? $$\begin{align} &\text{Minimize }\frac{1}{2} x^T Q x + a^T x + ...
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
votes
1answer
37 views

Minimize squared error of linear function

Let $M$ be a $m \times n$ matrix, $x$ a $n$-vector, $y$ a $m$-vector, and $\|\cdot\|_2$ represent the $L_2$ norm (i.e., Euclidean norm). Given $M,y$, the goal is to find $x$ that minimizes the ...
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 ...
3
votes
1answer
76 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 ...
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 ...
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. ...
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$$ ...
3
votes
1answer
349 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 ...
0
votes
1answer
2k views

How to define the derivative for Scipy.Optimize.Minimize

I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...
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 ...
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 ...
1
vote
1answer
158 views

How can I solve on a computer a large projection problem with redundant constraints?

This question is the essence of this one. After we remove all the cruft, we can recast it as follows: Problem: Given $b \in \mathbb{R}^n$, $C\in \mathbb{R}^{n\times m}$, and $g\in \mathrm{Range}(C^...
4
votes
2answers
998 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. ...
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 ...
1
vote
0answers
53 views

energy computation for BVP with Dirichlet boundary conditions

I am solving quadratic minimization problem \begin{align} \min_{x}\ \frac{1}{2} x^T A x -b^T x, \end{align} where matrix A results from discretization of Laplacian by FEM method, subjected to ...
1
vote
0answers
55 views

minimization a quadratic form with linear constraints (Prospective method SMIC 74 method)

my problem is a ecuation i don't understand, I have no idea how to solve that, is a classic minimisation programme of quadratic form with linear constraints, here is the ecuation: $$\sum_{i,j}^n[P(i/...
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 $ ...
0
votes
1answer
166 views

Optimization with Yalmip [closed]

I would like to solve in Matlab the following optimization problem $$\begin{array}{ll} \text{maximize} & \bigg\| \displaystyle\sum_{l=1}^{2}\alpha_l \int_{\tau_{m+l-1}}^{\alpha_1\tau_m+\alpha_2\...
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}$$...
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 $...
1
vote
1answer
200 views

Reformulation of optimization problem

I am looking for some helps concerning an optimization problem. I have an optimization problem defined on two sets $\mathcal{X}=\{x_i\}_{i=1}^n $ and $\mathcal{Y}=\{y_j\}_{j=1}^m $ and described as ...
1
vote
1answer
408 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
0answers
51 views

Admissible box constraint for a quadratically constrained linear program [closed]

I am looking at a real-world resource allocation problem that is cast as a quadratically-constrained linear program of the form $$ \max\langle f,x\rangle $$ subject to $$ \begin{aligned} m \leq\,\, &...
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}\...
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 ...
4
votes
0answers
164 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 ...
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
1answer
450 views

How to formulate variance minimization as a mixed integer quadratic program

I have a mixed integer quadratic problem and my objective function is as follows $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$ $d$ are ...
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, ...
0
votes
1answer
85 views

Can Variance be replaced by absolute value in this optimization problem

Initially I modeled my objective function as $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$, $x$ are linear functions. To be able to solve ...
0
votes
2answers
217 views

Convex quadratic problem solver gives different answers?

I am pretty sure that the following variance objective function should be a convex quadratic problem. My objective function is as follows: $$ \text{argmin } \text{var }(X*L) \xi \geq 1, \text{ where }...
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 \...
0
votes
1answer
713 views

CPLEX claims to have solved QP minimisation but solution is not optimal

I am trying to solve a small QP problem in CPLEX. The problem has several linear constraints. The optimiser runs and finds a solution which satisfies these constraints and CPLEX returns a success code....
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 ...
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.