Questions tagged [quadratic-programming]
Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.
782
questions
26
votes
4
answers
13k
views
How does the SVD solve the least squares problem?
How do I prove that the least-squares solution for $$\text{minimize} \quad \|Ax-b\|_2$$ is $A^{+} b$, where $A^{+}$ is the pseudoinverse of $A$?
- 639
20
votes
5
answers
989
views
Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$
Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$. What is the maximum of $x_1 x_2 + x_2 x_3 + \dots + x_n x_1$?
17
votes
2
answers
11k
views
Are "constrained linear least squares" and "quadratic programming" the same thing?
A Quadratic Programming problem is to minimize:
$f(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$
subject to $A\mathbf{x} \leq \mathbf b$; $C\mathbf{x} = \mathbf d$; ...
- 273
12
votes
2
answers
10k
views
Does gradient descent converge to a minimum-norm solution in least-squares problems?
Consider running gradient descent (GD) on the following optimization problem:
$$\arg\min_{\mathbf x \in \mathbb R^n} \| A\mathbf x-\mathbf b \|_2^2$$
where $\mathbf b$ lies in the column space of $A$...
- 3,145
11
votes
2
answers
4k
views
Linear programming with one quadratic equality constraint
I have a problem that can be formulated as a linear program with one quadratic equality constraint:
where variable $x$ is an $n$-dimensional vector and $H$ is a positive semidefinite $n \times n$ ...
- 111
10
votes
3
answers
20k
views
How do you minimize "hinge-loss"?
A lot of material on the web regarding Loss functions talk about "minimizing the Hinge Loss".
However, nobody actually explains it, or at least gives some example.
The best material I found is here ...
- 1,652
10
votes
2
answers
3k
views
Analog of Simplex Method for Quadratic Programming
It happened so I need to work with an algorithm for solving QP problems. The main issue here is that I can't find any references to this algorithms (at least no references in sources in english). ...
- 211
9
votes
1
answer
7k
views
Writing a convex quadratic program (QP) as a semidefinite program (SDP)
Given a convex quadratic program (QP)
$$\begin{array}{ll} \underset{x}{\text{minimize}} & \mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s\\ \text{subject to} & \mathrm A ...
8
votes
3
answers
5k
views
Least squares Problem with Non Negativity Constraints
Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem:
\begin{array}{rl}
\min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\
\mbox{s.t.} & x_k\ge 0, \forall ...
- 571
8
votes
2
answers
5k
views
Projection of a point onto a convex polyhedra
Let $x_0 \in \mathbb{R}^n$ and $A \in \mathbb{R}^{n \times n}$ be given. Define the set $S$ as
$$
S \triangleq \{x \in \mathbb{R}^n: A x \leq 1\}.
$$
I want to compute the projection of $x_0$ onto $S$...
- 2,859
8
votes
2
answers
7k
views
Converting from QP to SOCP
I want to convert the following problem into SOCP form:
$minimize \quad$ $x^TAx+a^Tx$:
$subject$ $to \quad$ $Bx \leq b$
The approach I am taking is introducing new variables, $u$ and $v$, such that:...
- 555
8
votes
2
answers
3k
views
What Numerical Methods Are Known to Solve $ {L}_{1} $ Regularized Quadratic Programming Problems?
What numerical methods are suitable to solve the following problem
$$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$
where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
- 29.3k
7
votes
1
answer
8k
views
Minimization of a convex quadratic form
I have a (non-strictly) convex quadratic form and I am wondering what the best (in terms of speed) method (iterative or not) to find a local minimum is. Since the objective function is convex, every ...
7
votes
1
answer
240
views
How to find the maximum of $\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}$ subject to $\boldsymbol{q}^T \boldsymbol{x}=1$?
I want to solve the following problem in $\boldsymbol{x} \in \mathbb R^{n}$
$$\begin{array}{ll} \text{maximize} & \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}\\ \text{subject to} & \...
- 321
7
votes
2
answers
9k
views
Quadratic function must be positive definite to have a unique minimum
Let $$V(x):=a+b^{T}x+\frac{1}{2}x^{T}Cx$$ for some $a \in \mathbb{R}$, $b \in \mathbb{R}^{n}$, $C \in \mathbb{R}^{nxn}$ that for $V$ to have a strict unique minimum it is imperative that $C>0$.
I ...
- 155
7
votes
3
answers
3k
views
Solving box-constrained least-squares
I have a linear least squares problem with linear constraints:
$$\min_x \| A x - b \|^2 \quad\text{subject to}\quad k_1 \leq x_i \leq k_2$$
Should quadratic programming be used here? If so, what would ...
- 71
7
votes
1
answer
897
views
Least-squares over the unit simplex
I am interested in the non-negative least squares problem subject to one equality constraint
$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} &...
- 215
6
votes
3
answers
615
views
Minimum of the given expression
For all real numbers $a$ and $b$ find the minimum of the following expression.
$$(a-b)^2 + (2-a-b)^2 + (2a-3b)^2$$
I tried expressing the entire expression in terms of a single function of $a$ and $...
- 948
6
votes
3
answers
1k
views
Is a sinc-distance matrix positive semidefinite?
I've been trying to crack this problem for days but I can't find a way around it. Given a set of unique $N$ points $X = \{x_1,\dots,x_N\}, x_i \in R^3$, the associated sinc-distance matrix $S \in R^{n\...
- 160
6
votes
5
answers
386
views
Linear Matrix Least Squares with Linear Equality Constraint - Minimize $ {\left\| A - B \right\|}_{F}^{2} $ Subject to $ B x = v $
$$\begin{array}{ll} \text{minimize} & \| A - B \|_F^2\\ \text{subject to} & B x = v\end{array}$$
where $B$ is an $m \times n$ matrix and $x$ is an $n$-vector where each element is $1/n$ (an ...
- 2,140
6
votes
4
answers
382
views
How can I solve "average" best rank-$1$ approximation?
Assume I want to minimise this
$$ \min_{x,y} \left\| A - x y^T \right\|_{\text{F}}^2$$
then I am finding best rank-$1$ approximation of $A$ in the squared-error sense and this can be done via the SVD, ...
- 397
6
votes
4
answers
2k
views
Quadratic optimisation with quadratic equality constraints
I would like to solve the following optimisation problem:
$$\text{minimize} \quad x'Ax \qquad \qquad \text{subject to} \quad x'Bx = x'Cx = 1$$
Where $A$ is symmetric and $B$ and $C$ are diagonal.
...
- 527
6
votes
1
answer
11k
views
Linear Least Squares with Linear Inequality Constraints
I'm trying to follow this older paper, page 19.
The goal is to solve:
$\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$
By combining the equations into a single LCP of the form:
$Mz + q = w$ s.t. $...
- 2,168
6
votes
1
answer
308
views
Solving many quadratic programs with the same objective matrix
If one wants to solve many linear systems with the same matrix,
$$\mathbf A\mathbf x_1 = \mathbf b_1, \quad \mathbf A\mathbf x_2 = \mathbf b_2, \quad \ldots, \quad \mathbf A\mathbf x_k = \mathbf b_k,$$...
user856
6
votes
1
answer
6k
views
How to convert quadratic programming problem to matrix form
I am new to this topic and am looking at an example I can't figure out. Can someone please help explain how this example creates the matrices used in the solver? Thanks!
This is the PROBLEM
...
- 63
6
votes
1
answer
275
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$, ...
- 7,766
5
votes
3
answers
2k
views
Need help setting up and solving dual problem
I need to solve the quadratic programming problem $$ \text{minimize}\,\, \sum_{j=1}^{n}(x_{j})^{2} \\ \text{subject to}\,\,\, \sum_{j=1}^{n}x_{j}=1,\\ 0 \leq x_{j}\leq u_{j}, \, \, j=1,\cdots , n $$
...
user100463
5
votes
1
answer
285
views
The best performing (theoretical complexity-wise) algorithm to solve this quadratic program
Find the best performing (complexity-wise) algorithm to solve the following quadratic program
$$\begin{array}{ll} \text{minimize} & \frac 12\|\mathrm x - \mathrm v\|_2^2\\ \text{subject to} & ...
- 1,720
5
votes
2
answers
834
views
Minimum volume covering ellipse
Given a convex polygon in the plane, consider the smallest-area ellipse that contains this polygon. This is the "minimal volume covering ellipsoid" or "minimal volume enclosing ellipsoid" (MVEE), and ...
- 487
5
votes
2
answers
434
views
Transform an optimisation problem into a linearly-constrained quadratic program?
I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
- 278
5
votes
1
answer
2k
views
How to use lagrange multipliers here?
I have a simple QP as below:
$\min L(x,y) = (x-5.1)^2+y^2$
such that
$(x-3)^2+y^2\geq1$
$(x-5.3)^2+y^2\geq1$
$(x-7)^2+y^2\geq1$
Intuitively, I think the optimal solution of the problem is $x^*=4....
- 441
5
votes
3
answers
1k
views
Find closest point, subject to linear inequality constraints
Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is,
$$\begin{array}{ll} \text{minimize} & ...
- 369
5
votes
1
answer
2k
views
How to write the dual of quadratic program with positive semidefinite matrix?
Consider the following quadratic program
$$\begin{align*}&\text{min } \frac{1}{2}b^TDb+d^Tb\\ &\text{s.t. } Ab\le b_0\end{align*}$$
where $D$ is a positive semidefinite matrix.
The ...
- 349
5
votes
1
answer
2k
views
Binary quadratic optimization problem
I am trying to solve the following binary quadratic program.
$$
\min_{\Delta} \Delta^T H \Delta + c^T\Delta \\
\text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \...
- 419
5
votes
1
answer
4k
views
Shortest Path and Minimum Curvature Path - implementation
Let's say we are given a race track, which may be described as a closed curve of given width (it may differ along the curve). My task is to implement an algorithm which finds two kinds of trajectories ...
- 153
5
votes
1
answer
4k
views
Computational complexity of solving a quadratic program with linear inequality constraints
I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
- 151
5
votes
0
answers
72
views
Arranging Points Uniformly on the Unit Sphere
What is $\min\limits_{{v_i\in R^m,\ \|v_i\|=1,}\atop{i\in\{1,2,\cdots,n\}}}\max\limits_{i,j}v_i^Tv_j$ where $\|\cdot\|$ denotes the Euclidean length? Basically, I would like to distribute a given ...
- 9,967
5
votes
2
answers
1k
views
QR factorization & Regularized Least Squares
Given regularized-least squares
$$\min_x ||Ax - b||^2+ \lambda||x||^2 $$
How do you use QR decomposition to find a solution?
I understand that QR decomposition leads to $Rx = Q^Tb$, but how do you ...
- 334
4
votes
1
answer
5k
views
Unconstrained quadratic programming problem with positive semidefinite matrix
I want to find $x\in\mathbb{R^n}$, where $x$ minimizes
$$f(x) = \frac{1}{2}x^TA x + b^Tx$$
There are no constraints. I do know that $A$ is symmetric positive semidefinite, and $f(x) \ge 0$ for all $...
- 1,120
4
votes
2
answers
2k
views
How to Solve Linear Least Squares with Matrix Inequality Constraint
I need to solve the following inequality-constrained least-squares problem in vector $x$
$$ \min_{Ax \geq 0} \frac{1}{2} \|Ax-b\|_2^2$$
where matrix $A$ and vector $b$ are given.
I am totally ...
- 641
4
votes
2
answers
3k
views
Maximize convex quadratic function on convex set (box constraints)
I am trying to maximize a (semi) convex quadratic function over a convex (box constraints) set, however I don't know if it is possible to solve (in not too long computation time).
The problem is
$$\...
- 291
4
votes
2
answers
2k
views
A standard quadratic minimization problem
Consider the "Complex" Quadratic minimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1
\end{align}
$\Re(...
- 8,947
4
votes
2
answers
4k
views
Linear Least Squares with Non Negativity Constraint
I am interested in the linear least squares problem:
$$\min_x \|Ax-b\|^2$$
Without constraint, the problem can be directly solved. With an additional linear equality constraint, the problem can be ...
- 1,963
4
votes
1
answer
227
views
Show that $(A^TA)^{-1} A^T$ minimizes $\mbox{Tr}(X^T X)$ over all matrices $X$ such that $XA = I$
How can I show that $(A^TA)^{-1} A^T$ minimizes $\mathbf{Tr}(X^TX)$ over all matrices $X$ such that $XA = I$?
[Note that $A$ is an $m \times n$ matrix.]
I've tried rearranging the trace, and ...
- 3,979
4
votes
2
answers
1k
views
indicator function in objective function with $L_2$ norm
I am trying to solve an optimization problem. The objective function is as follow
$arg\ min \lVert\mathbb{A}\mathbf{x} - \mathbf{b}\rVert^2 + other\ linear\ least\ squares\ terms + \mathcal{I}(\...
- 131
4
votes
2
answers
170
views
What does "programming" mean in mathematics?
In the past few years, I have came across some topics in Math and CS that have the word "programming" in them. For example, there are linear programming, quadratic programming and dynamic ...
- 252
4
votes
1
answer
113
views
Portfolio optimization
I prepare Markowitz optimization model for 4 different local companies with Excel functions and Solver. And I get confusing result for me, maybe somebody will explain it. So, from historic information ...
- 480
4
votes
2
answers
1k
views
Different behaviour of Newton's method for finding minimum of a function
Given the following function of two variables
$$f(x, y) = 2x^2 − 2xy + y^2 + 2x − 2y$$
I wanted to use Newton's method to find a minimum of this function. I started from $(x_1, y_1) = (0, 0)$ and ...
- 761
4
votes
1
answer
1k
views
Solving an equality-constrained convex quadratic program
There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier.
$$\begin{array}{ll} \text{minimize} &...
- 143
4
votes
1
answer
1k
views
How to solve quadratic optimization problem with two variables
I would like to solve the support vector regression problem.
The formula for the optimization is the following:
$$a_1^*, a_2^* = \max\sum_{i=1}^{n} (a_{1i}-a_{2i})y_{i} - eta\sum_{i=1}^{n}(a_{1i}+a_{...
- 155