Skip to main content

Questions tagged [quadratic-programming]

Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.

Filter by
Sorted by
Tagged with
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.$$
user3750444's user avatar
-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 ...
mirhan ürkmez's user avatar
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 ...
zvi's user avatar
  • 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 ...
user10478's user avatar
  • 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 ...
Faraz Masroor's user avatar
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}...
Royi's user avatar
  • 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-...
user avatar
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-...
mercury0114's user avatar
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 ...
Amirhossein Rezaei's user avatar
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} \...
Shengzhi Lai's user avatar
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 ...
oweydd's user avatar
  • 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 ...
Shengzhi Lai's user avatar
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+...
DBruwel's user avatar
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=...
Chechy Levas's user avatar
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 ...
Mark's user avatar
  • 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: \...
Taiwaninja's user avatar
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 \...
Euler_Salter's user avatar
  • 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 ...
JJMae's user avatar
  • 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 $\...
Lucca's user avatar
  • 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 \\ \ \ \ \ \ \...
Sean W's user avatar
  • 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(...
Boyan Hristov's user avatar
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}...
Hepdrey's user avatar
  • 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 ...
zenzu's user avatar
  • 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 ...
Brian Lai's user avatar
  • 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}$, ...
C. Brendel's user avatar
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}...
zzgsam's user avatar
  • 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 \...
Danny Blozrov's user avatar
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 ...
Bruno's user avatar
  • 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 ...
Nathan Legoman's user avatar
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 ...
Nap D. Lover's user avatar
  • 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 \...
Nick Hafner's user avatar
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 ...
D. Sikilai's user avatar
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)$ ...
zzgsam's user avatar
  • 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} \\ \...
Sumit's user avatar
  • 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 = \...
Adithya Ram's user avatar
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 \...
DSPinfinity's user avatar
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 \...
thi's user avatar
  • 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. ...
Pipnap's user avatar
  • 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 ...
Lucca's user avatar
  • 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 ...
AspiringMat's user avatar
  • 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\...
P. Quinton's user avatar
  • 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$ ...
Augustin Pan's user avatar
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 ...
Bipolo's user avatar
  • 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 ...
shupeng lai's user avatar
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>=...
Math-Data's user avatar
  • 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 ...
Patrickens's user avatar
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 ...
mskb's user avatar
  • 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 ...
baxbear's user avatar
  • 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 \...
Stephen Ge's user avatar
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$ ...
user35083's user avatar

1
2 3 4 5
16