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
0 votes
0 answers
37 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,177
1 vote
0 answers
33 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
42 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
23 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
  • 97
0 votes
0 answers
74 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
64 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
19 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
24 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 \...
Thinesh's user avatar
0 votes
1 answer
94 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
  • 319
0 votes
0 answers
61 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
80 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,288
1 vote
0 answers
163 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,934
2 votes
2 answers
79 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
66 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
32 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
44 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
84 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
205 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
21 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
  • 233
1 vote
0 answers
102 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
34 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
0 votes
0 answers
11 views

Discrete Fast Radon Transform Transpose for Optimization Algorithm

The radon transform of an image $f(x,y)$ can be written as: \begin{equation} p(\alpha,s)=\int_{-\infty}^{\infty}f(x(z),y(z))dz \\ = \int_{-\infty}^{\infty}f(z\sin\alpha+s\cos \alpha , -z\cos \alpha + ...
Matthew James's user avatar
0 votes
0 answers
20 views

How to derive the dual for Parabolic Relaxation for QCQPs

I'm reading this paper (EQ 11/15/16) on a way to relax QCQPs. They state the dual of their program, but I can't quite figure out how they got there. We're minimizing over variables: $X$ (PSD $n\times ...
Blake's user avatar
  • 66
1 vote
1 answer
84 views

Generating random quadratic and linear programming optimization problems

I have coded two solvers (interior-point and active set algorithms) of quadratic problems of the form: $$ \min_x \quad f(x) = \frac{1}{2} x' H x + g' x $$ $$ s.t. \ \ A' x = b $$ $$ \qquad \quad \ \ ...
Bergson's user avatar
  • 1,637
0 votes
0 answers
39 views

Optimization Method with Circumference Level Curves and Affine Constraints

Hello fellow mathematicians, I am a computer engineering PhD student specializing in control engineering, seeking your insights on an optimization method I've been working on. My approach revolves ...
Lucian Ribeiro's user avatar
1 vote
2 answers
171 views

How to use the Karush–Kuhn–Tucker conditions properly?

I want to learn how to use the Karush-Kuhn-Tucker (KKT) conditions to solve a quadratic programming problem with both equality and in-equality constraints. The problem in question is set in finance ...
Przemo's user avatar
  • 11.2k
0 votes
0 answers
21 views

Quadratic Constrained Optimization: why do I get different optimality conditions after I make a change of variable?

Suppose that I am trying to solve the following $n$-dimensional quadratic optimization problem with linear constraints ($\bf{A}$ is an $n \times n$ invertible matrix): $\underset{\mathbf{y}\in\mathbb{...
bbecon's user avatar
  • 147
3 votes
0 answers
80 views

Does the value function of a quadratic program stay convex when adding constraints?

I am interested in the value function of a quadratic program of the form $$ v(y)=\min_x \frac{1}{2} x^\top Q(y) x, $$ subject to a linear equality constraint $$ E(y)x=d(y), $$ and a linear inequality ...
user_lambda's user avatar
  • 1,367
2 votes
0 answers
42 views

Point in polytope that is farthest from the origin

Given the tall matrix ${\bf A} \in {\Bbb R}^{n \times m}$ (where $n > m$) and the vector ${\bf b} \in {\Bbb R}^n$, $$ \max_{{\bf x} \in {\Bbb R}^m} \, \left\| {\bf x} \right\|_2 \quad \text{subject ...
093r's user avatar
  • 21
0 votes
0 answers
32 views

Upper bound on the distance between quadratic minimizers.

Consider the quadratic program: $$\psi \in \underset{\xi \in (\mathcal{X} - a)}{\operatorname{arg min}} - \xi'S + \frac{1}{2}\xi' W \xi \, , $$ where $\mathcal{X}$ is a convex subset of $\mathbb{R}^d$,...
Debora Ozassa's user avatar
1 vote
1 answer
104 views

Matrix and the method of Lagrange multipliers

In a book on linear algebra, I saw a brief description of the Lagrange multiplier. The $x$ that minimizes $P(x)=\frac{1}{2}x^TAx-x^Tb$ is the solution of $Ax=b$. If $P(x)=x_1^2-x_1x_2+x_2^2-b_1x_1-...
ististyle's user avatar
  • 460
0 votes
0 answers
42 views

Expanded form of an unconstrained minimization problem

Consider the following problem: \begin{equation*} \begin{aligned} & \underset{x \in\mathbb{R}}{\text{minimize}} & & f(x) = \frac{1}{2}x^TAx - bx \\ \end{aligned} \end{equation*} where $b \...
themathfan's user avatar
0 votes
0 answers
48 views

Advice on optimizing an objective with many potential cases to track

I am analysing a game based on an extension of the Monty Hall problem and have come across an optimization problem that is just not clicking. I do not currently understand fully whether I should be ...
Joe McKeown's user avatar
1 vote
0 answers
64 views

Proof of the Frank-Wolfe theorem

Does anybody know where I might find a proof for the Frank-Wolfe Theorem (stated below)? Frank-Wolfe Theorem: If a quadratic function $f$ is bounded below on a nonempty polyhedron (the intersection ...
user316720's user avatar
2 votes
1 answer
51 views

Binary program that maximizes ratio of quadratic forms

I'd like to solve the following optimization problem. Given $\mathbf a, \mathbf b \in (0, \infty)^n$, find $\mathbf x \in \{0, 1\}^n$ which maximizes $$ f (\mathbf x) = \frac{\left( \sum\limits_{i=1}^...
Jon Warneke's user avatar
  • 4,917
0 votes
0 answers
14 views

Optimizing Quadratic Likelihood

I'm trying to implement a parameter estimation method that includes finding some polynomial $$b(z) = z^M + b_1z^{M-1} + \dots + b_M$$ To find these polynomial coefficients, one has to solve: $$\hat{\...
Marco Marinho's user avatar
0 votes
0 answers
73 views

What can be said about $AA^+$ for symmetric real matrices?

Defining $A^+$ as the pseudoinverse of matrix $A$, what can be said about $AA^+$ if $A$ is a real matrix? What if $A$ is also symmetric? The reason I am asking this is that I want to see why the ...
HappyFace's user avatar
  • 128
6 votes
1 answer
200 views

Sufficient conditions for a quadratic program with linear inequality constraints to have unique solution

Consider a quadratic program $$\min_{x} x^TQx + b^tx$$ such that $Ax\leq c$ pointwise. This is a quadratic program with linear inequality constraints. Under what conditions for the data (matrix $Q$, ...
Jürgen Sukumaran's user avatar
0 votes
0 answers
20 views

Eigendecomposition in unconstrained QP

Can someone please help me to understand the following statement? Let $Q \in \mathbb{R}^{d \times d}$ be a positive definite matrix with eigenvalues $\lambda_{\max} = \lambda_{1} \geq \dots \geq \...
Finn's user avatar
  • 23
2 votes
1 answer
119 views

Minimize $f(x,y) = x^2 - cxy + y^2$ using co-ordinate descent $\big{(}$for $c \in [0,2) \big)$

In a course I am taking on programming and algorithms for data scientists, I came across the following example of using co-ordinate descent to find a local minimum of a function. However, it is ...
FD_bfa's user avatar
  • 3,803
3 votes
1 answer
73 views

Which probability mass function has the largest Euclidean norm?

Fix $n > 1$ and let $[n] := \{ 1, 2, \dots, n \}$. Which probability mass function (PMF) over $[n]$ has the largest $2$-norm? Doodling for the cases $n \in \{2,3\}$ does suggest that the maximal $...
Rodrigo de Azevedo's user avatar
1 vote
2 answers
172 views

Convexity of general quadratic function [closed]

Let $f(x) := x^T A x + b^T x + c$. If we only know $A \in \mathbb{R}^{n \times n}$, why does convexity of $f$ require that $A + A^T$ be positive semidefinite (PSD) and why does strong convexity ...
79999's user avatar
  • 137
1 vote
0 answers
64 views

NP-hardness of maximizing convex quadratic over linear inequality constraints

I have the following problem: \begin{align} \max_{x} \quad & \| x - \hat{x} \|_2^2 \\ \text{s.t.} \quad & x^\top a_i \leq b_i, \quad \forall i \in \{ 1,\ldots,N \}, \end{align} where $x \in \...
durdi's user avatar
  • 753
1 vote
1 answer
68 views

Constrained non-convex QP

Consider the optimization problem: $$ \begin{aligned} \text{maximize}&\sum_{k=1}^9\left(x_k+\frac{k}{9}\right)^2\\ \text{subject to}&\begin{cases}\bar{x}\succeq \bar{0}\\\sum_{k=1}^9x_k=1.\end{...
Irving Lee's user avatar
1 vote
1 answer
95 views

Is it possible to express inequality constraints as equality constraints?

For quadratic programming, the objective function is: $$\text{min } \frac{1}{2}x^TQx + c^Tx$$ Subject to: $$Ax \leq b$$ These QP-solvers that can only handle inequality constraints are the most ...
euraad's user avatar
  • 2,914
0 votes
0 answers
38 views

How to describe Support Vector Machine formula onto the Quadratic Programming objective function?

Assume that we have two lines. Green and blue line. $$w^Tx - b = 1$$ $$w^Tx - b = -1$$ Our goal is to find $w$ and $b$ here. The first we can do, is to find the distance between these two lines. We ...
euraad's user avatar
  • 2,914
2 votes
0 answers
18 views

Estimating/Tuning a Coefficient from an 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
1 vote
0 answers
100 views

Quadratic optimization with FFT

I'm trying to solve the following bounded quadratic optimization problem. \begin{equation} \min_{x} \frac{1}{2}x^TAx+b^Tx \end{equation} \begin{equation} \textrm{s.t. }\\ x \geq 0 \end{equation} Where ...
Matthew James's user avatar
2 votes
1 answer
203 views

Express as either LP, QP, QCQP or SOCP

I have a problem which needs to be expressed as either LP, QP, QCQP or SOCP. \begin{array}{ll} \text{minimise}_{x,y,t} & a||\mathbf{x}||_2^2 + b||\mathbf{y}||_2^2 \\ \text{subject to}& ||\...
Craig Wilder's user avatar
2 votes
1 answer
350 views

Why is Hildreth's QP algorithm so simple?

I have Hildreth's quadratic programming (QP) algorithm and I find it very simple. Too simple so it becomes very much suspect. Why are this algorithm so simple, but other QP algorithms are complex and ...
euraad's user avatar
  • 2,914

1
2 3 4 5
16