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.
77
questions
2
votes
2
answers
108
views
Can this problem be solved using convex optimization?
I have the following problem:
$$\begin{align}
\max & \quad \frac{\mu^\top x - c^\top|x - x_0|}{x^{\top}\Sigma x} \tag{1} \\
\text{subject to }
& \quad x \leq \mathbb{1} \tag{2}\\
& \quad ...
- 23
4
votes
2
answers
2k
views
Small quadratic programming problem - a simple Fortran code needed
I need to find a distance from a point in 3D space to a parallelepiped (a crystal lattice cell). The problem boils down to a quadratic programming task:
Let $L$ be a matrix of lattice vectors (row-...
- 143
0
votes
0
answers
57
views
Linear Programming with bounds on magnitude
I have a set of halfplanes $H$, and a target vector $T$. My goal is to find the vector $v$ closest (2-norm) to vector $T$, such that $v$ is in the intersection of all of the halfplanes.
This can be ...
1
vote
0
answers
64
views
How to show that the solution of the following quadratic programming is non-negative
I have the following quadratic problem:
$max$ $a^Tx+0.5x^TAx$
$s.t: 1^Tx=1$
in which $a=[a_1, a_2,...,a_n]$ is a non-negative vector, and $1^T=[1,1, ..., 1]$. The hessian matrix $A$ has the ...
- 11
2
votes
1
answer
154
views
Numerical Simulation of a Quadratic MIP with a highly rational term
I am interested in solving the following minimization problem:
$$
\begin{array}{cl}
\displaystyle\min_{x,y}&\displaystyle\frac{1}{K}\sum_{i=1}^{K}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2} \\...
- 169
3
votes
1
answer
93
views
Reuse linear mapping that provides the solution to least squares problem using LAPACK
LAPACK.gglse allows me to solve
min x^T Q x
s.t. A x = y
(in my present use case, $Q$ is symmetric positive definite)
without having to think about the numerical ...
- 799
0
votes
0
answers
45
views
Reformulate a problem with concave objective function into a QP
I would like to convert this problem into a QP (Quadratic program).
$$\text{Maximize } \sum_{k=1}^{K}\sum_{n=1}^{N}log2(1+p_{kn}b_{kn})\\
\text{subject to } \sum_{k=1}^{K}\sum_{n=1}^{N}p_{kn}\leq P_{0}...
- 1
2
votes
2
answers
495
views
How to ensure the numeric value is always positive in Optimization Python?
I am currently performing optimization onto a quadratic function by manually coding the algorithm:
$$\min f = x^T v x - r^T x\\
\text{subject to } x \geq 0\, .$$
Here, optimizing the function without ...
0
votes
0
answers
241
views
Absolute value constraint in quadratic programming optimization
$$
argmin(x,y)=x^2+y^2+2y
$$
$$
s.t.\ \ y=|x-10|
$$
How can I convert the absolute value constraint to the constraint matrix (GX<=h, AX=b) in cvxopt?
- 109
3
votes
1
answer
363
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 ...
- 141
1
vote
1
answer
107
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 ...
- 111
0
votes
0
answers
48
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 ...
- 203
8
votes
1
answer
377
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
0
answers
54
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 ...
- 661
5
votes
0
answers
105
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} $$
...
- 151
3
votes
1
answer
209
views
Project to nearest point on convex polytope
I have a point $y \in \mathbb{R}^d$ and a convex polytope $\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 \le ...
- 477
3
votes
0
answers
249
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 ...
- 433
1
vote
2
answers
189
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 ...
- 433
5
votes
1
answer
290
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 ...
- 433
5
votes
1
answer
156
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 ...
- 482
1
vote
1
answer
7k
views
Why am I getting this DCPError?
I'm trying to optimize a binary portfolio vector to be greater than a benchmark using CVXPY.
...
- 113
5
votes
0
answers
173
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,423
-1
votes
1
answer
103
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 ...
- 477
4
votes
1
answer
3k
views
Discrete-time Algebraic Riccati Equation (DARE) solver in C++
I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
- 41
2
votes
1
answer
99
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
...
- 799
3
votes
1
answer
126
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 ...
- 33
3
votes
1
answer
818
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 ...
- 133
0
votes
1
answer
3k
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 ...
- 127
3
votes
1
answer
2k
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 + ...
- 191
5
votes
0
answers
161
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 ...
- 1,423
3
votes
2
answers
123
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 ...
- 173
1
vote
2
answers
136
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 ...
- 11
1
vote
1
answer
166
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^...
- 1,000
3
votes
1
answer
85
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 ...
- 177
4
votes
2
answers
2k
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. ...
1
vote
0
answers
58
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
0
answers
67
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/...
0
votes
1
answer
181
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\...
- 177
2
votes
0
answers
71
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,423
1
vote
1
answer
621
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 ...
- 221
1
vote
0
answers
59
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\,\, &...
- 111
1
vote
1
answer
160
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}\...
- 515
1
vote
1
answer
228
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 ...
- 11
6
votes
1
answer
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 ...
- 376
4
votes
0
answers
178
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 ...
- 1,423
5
votes
2
answers
4k
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, ...
- 729
1
vote
1
answer
617
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 ...
0
votes
1
answer
99
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 ...
7
votes
1
answer
7k
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
\...
- 73
4
votes
1
answer
134
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 ...
- 173