Skip to main content

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
4 votes
2 answers
1k 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-...
user36313's user avatar
  • 143
0 votes
0 answers
53 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 ...
Nicholas Pipitone's user avatar
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 ...
user45682's user avatar
2 votes
1 answer
153 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} \\...
SPARSE's user avatar
  • 169
0 votes
0 answers
12 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 ...
Jack Keefer's user avatar
3 votes
1 answer
88 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 ...
Bananach's user avatar
  • 799
0 votes
0 answers
43 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}...
amhen's user avatar
  • 1
2 votes
2 answers
403 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 ...
Kevin Choon Liang Yew's user avatar
0 votes
0 answers
213 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?
lichgo's user avatar
  • 109
3 votes
1 answer
310 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 ...
ckrk's user avatar
  • 141
1 vote
1 answer
90 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 ...
Tim Kuipers's user avatar
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 ...
Jogging Song's user avatar
8 votes
1 answer
370 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 ...
Morten Silcowitz's user avatar
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 ...
Charlie S's user avatar
  • 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} $$ ...
Kreol's user avatar
  • 151
3 votes
1 answer
202 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 ...
D.W.'s user avatar
  • 400
3 votes
0 answers
244 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 ...
Natasha's user avatar
  • 421
1 vote
2 answers
183 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 ...
Natasha's user avatar
  • 421
5 votes
1 answer
286 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 ...
Natasha's user avatar
  • 421
5 votes
1 answer
145 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 ...
jf328's user avatar
  • 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. ...
George's user avatar
  • 113
5 votes
0 answers
155 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 ...
Justin Solomon's user avatar
-1 votes
1 answer
101 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 ...
D.W.'s user avatar
  • 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 ...
John Smith's user avatar
2 votes
1 answer
97 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 ...
Bananach's user avatar
  • 799
3 votes
1 answer
121 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 ...
reicja's user avatar
  • 33
3 votes
1 answer
723 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 ...
Big AL's user avatar
  • 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 ...
Zac's user avatar
  • 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 + ...
Zero's user avatar
  • 161
5 votes
0 answers
160 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 ...
Justin Solomon's user avatar
3 votes
2 answers
122 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 ...
Alex's user avatar
  • 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 ...
user25340's user avatar
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^...
fred's user avatar
  • 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 ...
Uri Cohen's user avatar
  • 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. ...
Bryson of Heraclea's user avatar
1 vote
0 answers
57 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 ...
SmallElephant's user avatar
1 vote
0 answers
62 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/...
renzo.barrios1407's user avatar
0 votes
1 answer
178 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\...
Betelgeuse's user avatar
2 votes
0 answers
70 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 $...
Justin Solomon's user avatar
1 vote
1 answer
615 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 ...
user85361's user avatar
  • 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\,\, &...
Drake's user avatar
  • 111
1 vote
1 answer
157 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}\...
f10w's user avatar
  • 515
1 vote
1 answer
221 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 ...
alya's user avatar
  • 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 ...
jlperla's user avatar
  • 376
4 votes
0 answers
176 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 ...
Justin Solomon's user avatar
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, ...
LCFactorization's user avatar
1 vote
1 answer
610 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 ...
sarah daneshvar's user avatar
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 ...
sarah daneshvar's user avatar
7 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 \...
Bill Z's user avatar
  • 73
4 votes
1 answer
132 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 ...
Ilya Palachev's user avatar