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.
76
questions
0
votes
0
answers
49
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
150
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
0
votes
0
answers
11
views
Estimating/Tuning a Coefficient from a Quadratic Programming Objective Function so Optimal Solution Reflects Data
I am working on a problem that is a modified version of a two-knapsack knapsack problem. I am able to find the optimal choices by using Gurobi. However, I would like to estimate a coefficient that is ...
3
votes
1
answer
86
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
42
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
299
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
181
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
273
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
88
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
47
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 ...
- 193
8
votes
1
answer
352
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
53
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
104
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
195
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 ...
- 400
3
votes
0
answers
236
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 ...
- 411
1
vote
2
answers
174
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 ...
- 411
5
votes
1
answer
285
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 ...
- 411
5
votes
1
answer
139
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 ...
- 408
1
vote
1
answer
6k
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
144
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,341
-1
votes
1
answer
98
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 ...
- 400
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
96
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
115
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
665
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
2
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 + ...
- 161
5
votes
0
answers
158
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,341
3
votes
2
answers
120
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 ...
- 183
1
vote
2
answers
134
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
165
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
83
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
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. ...
1
vote
0
answers
56
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
59
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
176
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
69
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,341
1
vote
1
answer
601
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
58
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
156
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
213
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 ...
- 378
4
votes
0
answers
174
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,341
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
602
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
97
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 ...
6
votes
1
answer
6k
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
\...
- 63
4
votes
1
answer
131
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 ...
- 163
2
votes
1
answer
148
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.
- 23