Questions tagged [quadratic-programming]
Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.
783
questions
1
vote
1
answer
49
views
Closed-form solution to linear regression under positive semi-definite constraint
Let $X,Y\in \mathbb{R}^{d\times n}$ and $W\in\mathbb{R}^{d\times d}$.
Is there a closed-form solution to the following minimization problem?
$$\min_W \|WX - Y\|_F^2, \quad W \succeq 0.$$
- 403
-4
votes
0
answers
16
views
Computational Time of Interior Point Methods Per Iteration for Nonconvex QP [closed]
The title is pretty much self-explanatory. I am trying to find the computational time of interior point methods per iteration for nonconvex QP. As far as I know, it is $ \mathcal {O}(n^3)$ for a ...
1
vote
0
answers
40
views
solving trace minimization problem in quadratic programming
I'd like to minimize the trace of
$P - XHP - PH^T X^T + XSX^T$
with the constraints that every entry of $X \geq 0$
here $P$ is $n$ by $n$ positive definite, $H$ is $m$ by $n$, S is $m$ by $m$ positive ...
- 189
0
votes
0
answers
26
views
What am I missing in deriving the dual of this soft margin support vector machine?
I am trying to derive the dual form of a support vector machine from its primal form (see top of section "Kernel SVM").
While missing from the formulation linked above, I've proceeded thus ...
- 1,964
1
vote
0
answers
24
views
Quadratic Optimization with positivity, equality constraints - Literature Review?
I'm trying to solve a problem of the form $\min x^T Q x$ such that $Ax = b$ and $x_i \ge 0$ for all components $i$; $x, b$ are vectors; and $Q, A$ are matrices. In this case $Q$ is square and positive ...
- 1,300
0
votes
1
answer
35
views
Orthogonal Projection onto a Polyhedron (Matrix Inequality)
How to efficiently solve:
$$\begin{align*}
\arg \min_{\boldsymbol{X}} \quad & \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} \\
\text{subject to} \quad & \begin{aligned}...
- 9,067
0
votes
0
answers
28
views
Quadratic Programming and Betweenness Problem
Given Betweenness problem of $n$ variables $x_1,...,x_n$ and $m$ triplets $(x_i,x_j,x_k)$, I build a Quadratic Programming for the triplets such that for every triplet $(x_i,x_j,x_k)$ I add $(2x_j-x_i-...
user411780
2
votes
2
answers
126
views
Is there a Python library that would solve a quadratic optimization problem?
I am trying to optimize a quadratic formula, where I have to simultaneously find a maximum wrt. $x$ and a minimum wrt. $y$.
More precisely, let
$F(x, y) = x M y + x 1^n$, where:
$x$ - is an n-...
- 410
0
votes
0
answers
39
views
Converting a Quartic Term into Quadratic Form in QUBO for Prime Factorization
I'm trying to embed the prime factorization problem into the form of a QUBO. To do so, let $p$ and $q$ be two real positive numbers. We can represent these two numbers as binary numbers, which itself ...
1
vote
1
answer
48
views
How to make this conversion from a binary integer linear program to a quadratic program?
I saw a conversion from a binary integer linear program (BLP) to a quadratic program (QP) in this link https://qr.ae/psu9Wr. I will repeat the problem below. The original problem is
\begin{align}
\...
- 11
1
vote
1
answer
44
views
Solve the Soft SVM Dual Problem with L1 Regularization
I'm considering a support vector regression model with a prediction
$$ \hat{y}(\mathbf{x}_\star)=\boldsymbol{\theta}^{\top} \boldsymbol{\phi}(\mathbf{x}_\star)$$
where $\boldsymbol{\theta}$ are the ...
- 239
0
votes
1
answer
27
views
Convert 0-1 integer linear program to quadratic form.
I am searching for a general conversion from 0-1 integer linear programs to (integer) quadratic programs. And I see this answer using a general example. https://qr.ae/psu9Wr. I checked the optimality ...
- 11
0
votes
0
answers
22
views
Minimising quadratic function subject to linear equality constraints.
The Problem
At a higher level, I am trying to minimise a function that looks a bit like this
\begin{equation}
(x_2-x_1+c_1)^2 + (x_3-x_2+c_2)^2 + ...
\end{equation}
Subject to the constraint that $x_1+...
- 1
1
vote
0
answers
20
views
Can this difference of covariance optimization be represented as convex optimization?
I have 2 estimates of covariance: $\Omega_a$ and $\Omega_b$.
I want to find the vector $x$ that minimizes the following
$x'\Omega_ax - x'\Omega_bx$
subject to
$x>0$ (each element is positive)
$1'x=...
- 385
1
vote
0
answers
26
views
Finding the largest volume ellipsoidal hole within a set of points [duplicate]
Suppose we have a set of points $x_1, \ldots, x_N$ in $R^d$ which we call the "bad set." Now we want an ellipse in $R^d$ of maximal volume, centered at point $c$, which does not contain any ...
- 5,878
0
votes
0
answers
89
views
Dual of Quadratic Programming with inequality constraints
I am new to duality concepts and I was reading a document that dualizes the following problem:
\begin{equation}
\min_{x,y} \ ||x-y||^2
\\s.t. \ A_x x \leq b_x, \ A_y y \leq b_y
\end{equation}
into:
\...
- 31
2
votes
0
answers
35
views
Minimize a quadratic form constrained to the vector being non-negative and sum up to one
I want to solve the following optimization problem with respect to $\mathsf{x} = (x_1, \ldots, x_n)^\top$
$$
\min_{\mathbf{x}} \,\, \mathbf{x}^\top A \mathbf{x} \qquad\qquad\text{such that }\,\, x_i \...
- 5,277
2
votes
0
answers
51
views
Book/Notes Recommendation for Quadratic Optimization
While self-studying and planning on doing some small-time research/fun based on Philip Wolf's "The Simplex Method for Quadratic Programming", I got interested in the notion of quadratic ...
- 2,021
0
votes
0
answers
22
views
Feasible set formed by exclusion of two convex sets
I'm working on an optimal control problem which is almost entirely composed by elements of a quadratic programming problem. The decision variable is $u \in \mathbb{U} \subseteq \mathbb{R}^2$, where $\...
- 1
0
votes
1
answer
45
views
Does a convex quadratic program have a unique dual solution?
As shown in Does a convex quadratic program have a unique solution?, a convex quadratic program has a unique primal solution $x$ if $Q$ is PD.
$$\min \; x^T Q x \\ s.t. \ Ax= b : \lambda \\ \ \ \ \ \ \...
- 1
0
votes
1
answer
50
views
Efficiency of constrained LQR formulation in CVXPY via batch-approach
I am interested in formulating a discrete finite time constrained LQR in CVXPY.
\begin{align}
\text{minimize } J = & \sum_{k=0}^N x'(k)Qx(k) + u'(k)Ru(k) \\\\
\text{subject to } & x(k+1) = Ax(...
- 103
0
votes
1
answer
66
views
Symmetric linear least-squares solution with known diagonal elements
Given matrices $\pmb{A}\in\mathbb{R}^{p\times n}$ and $\pmb{B}\in\mathbb{R}^{p\times n}$ with $p>n$, I need to solve the following linear system in symmetric matrix $\pmb{X}\in\mathbb{R}^{p\times p}...
- 83
0
votes
0
answers
29
views
SQP and first order Taylor approximation
I am trying to use the SQP solver with a nonlinear constraint. The solver requires a linear constraint so I am trying to approximate the constraint with the first-order Taylor approximation. Is this ...
- 1
1
vote
1
answer
25
views
Reference Request: Quadratic Optimization with affine constraints
I was wondering what is a standard textbook/source that I can reference this fact:
$\min_y \frac{1}{2} y^T C^{-1} y - b^T y$
such that $A^T y = f,$
where $C^{-1}$ is am $m \times m$ symmetric ...
- 820
0
votes
0
answers
30
views
Non-negative QP
I have a rather peculiar contrained quadratic programming problem where I try to fit a left-stochastic matrix and I am not sure how to properly solve it. Consider matrices $S\in\mathbb R^{D\times N}$, ...
- 874
0
votes
0
answers
36
views
Minimax theorem for convex quadratic programming
I have a simple and stupid question if I have a convex quadratic optimization problem with polyhedral constraints as follows:
$$
\begin{aligned}
\inf_{x \in \mathbb{R}^{n}} & x^{\top} Ax + b^{\top}...
- 139
3
votes
1
answer
162
views
reduction from QCQP to SOCP
Suppose a QCQP problem :
$$ \min_{x\in\mathbb{R}^{n}}f\left(x\right)=\frac{1}{2}x^{T}P_{0}x+q_{0}^{T}x$$
$$ s.t:\begin{cases}
\frac{1}{2}x^{T}P_{i}x+q_{i}^{T}x+r_{i}\le0 & i=1,2\dots,m:m\le n
\...
- 892
1
vote
0
answers
25
views
LCP of KKT from a QP without non-negativity constraint and semidefinite Q matrix
Most formulations of the LCP derived from the KKT conditions of a QP tackle problems with non-negativity constraints $x\ge 0$. Wikipedia presents an alternative without the non-negative constraints ...
- 19
0
votes
0
answers
25
views
Graphing machine for a quadratic equation representing braking speed of a vehicle over time
I am solving for a particular situation. A two vehicles approach an intersection and are on a collision course. To avoid the collision, one vehicle needs to apply the brakes such that it slows to ...
0
votes
0
answers
54
views
Quadratic programming optimization with rank 1 matrix
Let $a,b\neq \vec{0}$ be vectors in $\mathbb{R}^d$. Let $A=aa^T$ be the matrix formed by the outer product of $a$ with itself. Suppose $b\notin C(A)$, the column space of $A$. Consider maximizing the ...
- 1,171
1
vote
0
answers
35
views
Rearranging a Lie algebra adjoint action
I've been stuck on this problem for quite a while, and I can't seem to find any similar questions, though if my terminology is wrong and that's why I failed to find one then my apologies.
Let $A, B \...
- 11
0
votes
0
answers
44
views
Orthogonal projection on a lower triangular non square block matrix $A \in \mathbb R^{m=4k,n=7k}$ such that $A_{i,j}\in \{0,1\}$
If i have a very large matrix matrix $$A \in \mathbb R^{m=4k,n=7k}$$ such that $$A_{i,j}\in \{0,1\}$$ and $A$ is a lower block matrix with diagonal block $$B_t\in \mathbb R^{4,7}$$ and block left of ...
- 92
0
votes
0
answers
24
views
Analysis of a parametric quadratic game
I am solving a game theory problem for N players. At each step, each player solves a projection-based gradient descent $\operatorname{proj}_{X}\left(x_i^{(k)}-\eta F\left(x_{i}^{(k)}\right)\right)$ ...
- 139
0
votes
0
answers
83
views
How to solve this convex QP?
Given a symmetric positive semidefinite matrix $\bf \Sigma$ and a real-valued vector $\bf r$,
$$ \begin{array}{ll} \underset {{\bf w}} {\text{minimize}} & {\bf w}^\top {\bf \Sigma} \, {\bf w} \\ \...
- 101
0
votes
1
answer
66
views
Minimizing $x^T A x$ subject to $B x \leq b$
Given $$ A = \begin{bmatrix} 4 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 2 & -3 \\ 5 & 2 & 1 \end{bmatrix}, \qquad b = \...
0
votes
0
answers
21
views
Unclear points in derivation of Lagrange duality for a quadratic optimization problem
Problem0:
$\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+\mathbf{p}^T\mathbf{u}$
$\,$ subject to $\,$ $\mathbf{a}^T\mathbf{u} \ge c$
Problem1:
$\displaystyle \...
- 165
0
votes
1
answer
38
views
Seeking Clarification on Obtaining Explicit Solution for Quadratic Programming Equation
I recently encountered a quadratic programming equation and would appreciate assistance in understanding and obtaining the explicit solution. The equation is given by:
$$ u^* = \text{argmin}_{u \in \...
- 13
0
votes
1
answer
103
views
A theorem due to Schoenberg
I am reading the book "Additional Exercises for Convex Optimization" [ Stephen Boyd & Lieven Vandenberghe 2016 ] where I have difficulties in understanding the content of an exercise.
...
- 431
0
votes
0
answers
65
views
Optimization Problem - Similar to Quadratic
I’m quite new to the forum and to optimisation, so my apologies if the question is trivial or in the wrong section. I've rewittren the question to clarify my doubt (I was previously writing from an ...
- 1
-1
votes
1
answer
87
views
When does a quadratic inequality have a solution? [closed]
Consider the following quadratic inequality:
$$x^T Q x + c^T x \leq b$$
for $x\in \Re^{d}$. When does this system have a solution?
Without loss of generality assume that $Q$ is symmetric.
Looking for ...
- 2,537
1
vote
0
answers
222
views
Is there a closed form to this quadratic program?
Problem :
I am currently trying to solve some optimization problem to get some information about a matrix. In the following, when we have a matrix $A\in\mathbb R^{m\times n}$, $0\leq A$ means that $0\...
- 5,977
2
votes
2
answers
82
views
Find the max and min of $(a \mathbf{x} + c)(b \mathbf{x} + d)$, where $\mathbf{x}$ is a vector with linear constraints.
Suppose there is a $n$-dimensional column vector $\mathbf{x}$, and an objective function $f(\mathbf{x}) = (a \mathbf{x} + c)(b \mathbf{x} + d)$, where $a$ and $b$ are $n$-dimensional row vector; $c$ ...
- 45
2
votes
1
answer
72
views
Proving that a set of quadratic constraints have no solution
I want to prove that a given set of quadratic and linear inequalities has no solution. The set size is of 13 equations, or, including the positiveness constrain, 21 equations.
I already used a python ...
- 23
0
votes
1
answer
39
views
How to handle the equality constraint that cannot be satisfied?
Given an optimization problem
$$
\text{min} \space x^T M x \\
\text{s.t.} \space Ax = b
$$
where an analytical solution called weighted general inverse exists.
However, we now know that Ax = b some ...
0
votes
0
answers
57
views
Quadratic programming with the non-negativity constraint
Let us assume that $B$ is a symmetric positive semi-definite matrix in $\mathbb{R}^{m\times m}$. What is the optimum solution for the following constrained quadratic programming problem:
$$min_{X>=...
- 662
1
vote
1
answer
113
views
Quadratic programming: maximizing the euclidean norm
The setting is the following, I have a full-dimensional polytope $\mathcal{F}: A \cdot x \leq \vec{b}$ that has been transformed such that it contains the origin: $\vec{0} \in \mathcal{F}$. I need to ...
- 133
1
vote
0
answers
210
views
Proof for the equivalence of the convex optimization problem in Kernel Fisher LDA paper.
All, I am trying to understand the convex optimization move made from eqns. 3 -> eqns. 4 in the Kernel Fisher LDA paper. The authors mention that the proof of equivalence is straightforward, and ...
- 61
0
votes
0
answers
35
views
Linear vs Quadratic integer programming on the example spread vs variance
I consider the following two instances of the same problem, computing the spread as the difference of the highest and lowest occurrence of something in a set. Further, I compute the variance of the ...
- 255
1
vote
0
answers
120
views
Dual of Dual problem of a simple convex Quadratic problem
I am trying to verify the
the dual of the dual is the primal? using a simple convex QP:
\begin{align}
\min_x& \frac{1}{2} x^\top H x + h^\top x\\
\text{s.t.} &~Ax\leq b \\
&~ A_e x = b_e
\...
- 153
1
vote
1
answer
137
views
KKT Conditions for SVM Problem
I am reading about SVMs and want to confirm that I understand the optimality conditions. Details below:
Consider the $n$ points $x_1, x_2, \dots, x_n$, each with $ d$ dimensions, and consider $ n$ ...
- 43