Questions tagged [quadratic-programming]
Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.
680
questions
-2
votes
0
answers
28
views
How to find two vectors with a linear constrain to maxmize the angle between them? [closed]
I want to find two vectors in a linear constrained region. How can I find two vectors in the region that have the maximal angles? It can be written as:
$$\begin{aligned}
\min & \frac{w_1^Tw_2}{\|...
- 2,541
2
votes
1
answer
38
views
Decision variable limit condition in constrained linear and quadratic programing
We are given a quadratic (or linear) program as$$\min \limits _xx^TPx+q^Tx\qquad \text{s.t.}\quad a_i^tx\leq b_i,\quad \forall i\in \{1,\ldots ,N\}.$$In the above problem, we do not have any limit on ...
- 58
1
vote
0
answers
75
views
Why linear programming is called 'programming' instead of 'optimization'?
In numerical optimization (a mathematics branch), a standard optimization problem is formulated as
min f(x), subject to c(x) = 0 or c(x) >= 0.
But when these ...
- 71
2
votes
0
answers
27
views
Showing existence of a solution to a quadratic system of equations implies existence of a solution to another
Given a system of quadratic equations:
$$\forall i\>\>\>x^{\dagger}M_ix = y_i$$
I want to show that if there exists a solution $x\in \mathbb{C}^n$, there must also exist a solution $\hat{x}$ ...
- 290
0
votes
0
answers
73
views
Quadratic optimization problem where the variable is a binary matrix.
I have the following optimization problem that I want to solve (note that the $X$ variable consists of a binary matrix subject to a single constraint).
First, some definitions:
My $X$ variable:
$$
X = ...
- 148
0
votes
0
answers
45
views
What is the fastest way to solve a large-scale quadratic programming problem with inequality constraint?
I am trying to solve problem as follows:
\begin{equation}
\begin{split}
&\mathop{min} \limits_{\textbf{x}_1...\textbf{x}_k} \ \frac{1}{2}\textbf{x}_1^T\textbf{Q}_1\textbf{x}_1+\textbf{q}_1^T\...
- 21
1
vote
1
answer
33
views
Second Order Cone Program with Quadratic Objective Function
The standard form for a Second Order Cone Program (SOCP) is
\begin{equation}
\begin{array}{c}
\min _{x} f^{T} x \\
\left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m
\end{array}
\...
- 13
1
vote
0
answers
37
views
Rewriting quadratic optimization problem with negative definite matrix
Consider the following problem:
Minimize $x(1-x) + y(1-y) + z(1-z)$ subject to:
$$ a. 0\leq x, y, z \leq 1$$
$$ b. x+y+z = 1$$
If I plug in this problem in a standard quadratic optimizer, which ...
- 71
2
votes
1
answer
39
views
Explicit Solution of Quadratic Opt. Problem
I have the following optimization problem I am unsure whether I've got it correct:
$$
\text{min } x^Tx \\
\text{so that } a + c^Tx <= 0
$$
I have introduced a slack variable $s$ to make it ...
- 157
1
vote
0
answers
44
views
Objective function and constraints are matrix form in an optimization problem, can Lagrange multipliers method be applied to solve?
I would like to solve the following optimization problem:
given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
- 35
0
votes
0
answers
37
views
Frobenius inner product, Frobenius norm objective function with quadratic equality constraints.
I would like to solve the following optimization problem:
given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
- 35
1
vote
1
answer
66
views
Quadratic Minimization Problem with positivity constraint
Let $A \in\mathbb{R}^{m\times n}$, $b,c\in\mathbb{R}^m$, $x\in \mathbb{R}^n$. Consider the following minimization problem:
$$
\min_{x\succeq 0} f(x):= \frac{1}{2}\|Ax-c\|^2 + b^\top Ax.
$$
For the ...
- 293
2
votes
2
answers
98
views
Simple Quadratic Minimization Problem
Let $A \in\mathbb{R}^{m\times n}$, $b,c\in\mathbb{R}^m$, $x\in \mathbb{R}^n$. Consider the following minimization problem:
$$
\min_{x} f(x):= \frac{1}{2}\|Ax-c\|^2 + b^\top Ax.
$$
Since the function ...
- 293
0
votes
0
answers
41
views
Recast maximization as minimization
I hope you can help me.
I would like to know which are the conditions to transform a maximization problem into a minimization one.
I have the following problem
$
Q: \max_{x,y} ~ f(y) / g(x) ~~ s.t. ~ (...
- 694
1
vote
0
answers
32
views
How is the Wilson-Han-Powell SQP algorithm applied?
Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$.
Now, the WHP-SQP algorithm goes ...
- 363
0
votes
0
answers
29
views
Parametrically enlarge one ellipsoid to fit another one
I'm trying to figure out the smallest enlargement factor which I need to apply to one ellipsoid $E_1$ in order to fit another one $E_2$. Precisely, let $E(c, S) := \{x | (x-c)^T S (x-c) \leq 1\}$ be ...
2
votes
1
answer
43
views
Unconstrained minimizer as a linear combination
I'm given the following function:
$$f : R^n \rightarrow R$$
$$f(x)=\frac{||Ax-b||^2}{c^Tx+d}$$ where x $\in R^n$ and $dom(f) = \{x|c^Tx+d > 0\}$
Also it's given that $rank(A)=n$ and vector b is ...
- 147
0
votes
0
answers
24
views
Solutions of Two Similar Quadratic Programs
I am solving a very large number of quadratic programs with the same objective function, and very similar constraints. Given a positive definite matrix $\Sigma$ and constraints $A,B,a,b$, let
$$ x = \...
- 1,876
0
votes
0
answers
14
views
Closed form solution of linear least square with penalty term and inequality constraint
I want to find a closed form solution of the following problem
$$ \min_B \|V^T B- E \|^2 + \lambda \| B\|^2$$
$$s.t. V + B \geq 0, $$
where $B \in \mathbb{R}^{k \times n }$, $E \in \mathbb{S}^n$, and $...
- 710
0
votes
0
answers
21
views
Solution to quadratic problem in least square optimization
$
\begin{array}{rrclcl}
\displaystyle \min_{\dot{\boldsymbol{x}}} & (\boldsymbol{G}_a^T\dot{\boldsymbol{x}}-\dot{\boldsymbol{\theta}}_a)^T(\boldsymbol{G}_a^T\dot{\boldsymbol{x}}-\dot{\boldsymbol{\...
- 1
1
vote
1
answer
97
views
Norm $\|x\|$ defined as the sum of largest $r$ absolute values, how to write $\min \|A x-b\|_{2}^{2}+\|x\|$ as QP?
This is a question from Boyd Convex Optimization, Additional Exercise 5.31
In this problem, $r$ is an integer between 1 and $n$, and $\|x\|$ denotes the norm
$$
\|x\|=\max _{1 \leq i_{1}<\cdots<...
- 25
0
votes
0
answers
23
views
Projection mapping as quadratic programming problem.
I am studying Variational inequalities in Hilbert space. To define this, let $C$ be a closed, convex subset of a Hilbert space $H$. The Variational inequality problem is to find $x \in C$ such that $\...
- 11
0
votes
1
answer
69
views
Solving a constrained optimization problem using Lagrange Multiplier
I am trying to solve a relatively simple single variable constrained quadratic programming but having hard time. The problem is as follows:
$$
\min_x ax^2-b(1+x)
$$
subject to
$$
0\leq x \leq1
$$
$$
b(...
0
votes
1
answer
99
views
How to solve non-negativity-constrained quadratic programs?
$$\min_{x_1,x_2,x_3 \geq 0} \quad 2x^2_1+3x^2_2+4x^2_3+2x_1x_2 -2x_1x_3 -8x_1-4x_2-2x_3 $$
I tried to re range the problem to matrix form and got
$$ \min_{x \geq 0_3} \quad x^T Ax + 2b^Tx$$
where
$$...
- 17
0
votes
0
answers
37
views
The dual function of non-convex QP
I am trying to find the dual function of the follwoing non-convex QP
\begin{equation*}
\min \frac{1}{2}x^T Q x \\
Ax = b, 0\leq x \leq e
\end{equation*}
The Lagrangian function is given by
\begin{...
- 31
1
vote
0
answers
37
views
Minimizing $b^Tb$ subject to $Ax=b, x\geq 0, x\leq 1$
I have the following quadratic program: Minimize $b^Tb$ subject to $Ax=b$ where $A$ is a $n\times m$ matrix ($n\leq m$) of rank $n-1$. I also want $0\leq x\leq 1$.
For my choice of $A$, I can prove ...
- 1,756
1
vote
1
answer
39
views
Hessian of quadratic objective function
I have the quadratic function
$$f(\boldsymbol{x}) = \frac{3}{2} \left (x_{1}^{2}+x_{2}^{2} \right) + (1+a) x_{1} x_{2} - \left(x_{1} + x_{2} \right) + b$$
where $a, b \in \Bbb R$ are unknown ...
- 177
1
vote
1
answer
51
views
Solving Quadratic Optimization problems without using Lagrange Multipliers
I am having trouble understanding min/max problems in Linear Algebra. I am normally used to solving these types of problems using some form of calculus. The question I am stuck on is minimizing:
$$b^{...
- 75
0
votes
0
answers
20
views
Constrained Least Squares - Analytical solution
Given a matrix $A \in \mathbb{R}^{d \times d}$, and a pair of vectors $b,x_0 \in \mathbb{R}^d$, and some positive scalar $\alpha > 0$, is there an analytical solution to the following optimization ...
- 583
0
votes
1
answer
50
views
Minimizer of a convex quadratic function
Suppose that there is a positive definite matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, and a vector $\mathbf{b} \in \mathbb{R}^{n}$, then minimization of quadratic functions with linear terms can ...
- 600
0
votes
1
answer
110
views
How can I form this second-order conic constraint?
I am trying to show that if we have a real symmetric matrix $Q$ with one negative eigenvalue within a quadratic constraint:
$x^\top Qx+a^\top x +b \leq 0$
That this constraint can be formulated as a ...
- 381
0
votes
0
answers
18
views
Affine Scaling Interior Point algorithm for linear programming.
Can someone explain, or provide sources for, why the affine scaling interior point method (by Dikin) projects the gradient of the objective function onto the null space of the constraint matrix to ...
- 1
1
vote
0
answers
77
views
Model Predictive Control with Linear Programming VS Quadratic Programming
Model Predrictive Control is often used with Quadratic Programming. But I have tried Model Predictive Control with Linear Programming and it works very well.
Let's begin with the discrete SISO state ...
- 2,560
1
vote
0
answers
71
views
Minimizing $\|A−XB\|^2_F$
Find a closed form solution for $$\underset{X}{\operatorname{argmin}} \|A−XB\|^2_F$$ where $\| \cdot \|_F$ denotes the Frobenius norm.
I have found this thread. Not sure if it helps here though. Any ...
- 11
1
vote
1
answer
63
views
Indefinite generalized Tikhonov regularization
Suppose we want to choose $x$ to minimise the following (generalized) Tikhonov regularized least squares objective:
$$(Ax-b)^\top (Ax-b) + \lambda [(x-c)^\top W (x-c)],$$
where $W$ is symmetric, but ...
- 671
1
vote
0
answers
7
views
Show that $\vec{a}_j$ is linear independent with respect to $\{\vec{a}_i:i\in W_k\}$.
Suppose that $\quad \vec{a}^T\vec{d}>0\quad$ for a $j\in I-W_k\quad$ and $\quad \vec{d}\neq 0$ is the optimum solution of the system $$\text{min}_{\vec{d}} (\frac{1}{2}d^TGd+d^T\vec{g}_k)$$ $$\vec{...
- 1,454
1
vote
0
answers
55
views
How to solve a linear optimization problem with two arrays variables?
I have two sets of $n$ 3 dimensional vectors independent from eachother ;
$$A = (f_1, f_2, ..., f_n)$$
$$C = (m_1, m_2, ..., m_n)$$
I am looking for the set of $n$ real factors, $X = (X_1, X_2, ..., ...
- 21
1
vote
1
answer
32
views
Solving an optimization problem in QCP form
I am reading a paper in which authors said quadratic-constrained optimization is used for the following problem:
\begin{align}
&\underset{\mathbf{P},\,\,\epsilon}{\min}\:\epsilon\\
&\mathrm{s....
- 43
0
votes
0
answers
33
views
How is Mathematica minimizing correlation exactly with linear constraints?
I made a random data matrix as
data = Table[Random[], {i, 5}, {j, 5}];
In my case it was
$$ \left(
\begin{array}{ccccc}
0.951203 & 0.546669 & 0.86928 &...
- 23.5k
3
votes
0
answers
143
views
Closed form solution for a quadratic program in matrix form with inequality constraint
Is there a closed form solution for the following quadratic program with inequality constraint? Let $P \in \mathbb{S}^n_{++}$ be a symmetric positive definite matrix, and $B$, $F \in \mathbb{R}^{k \...
- 710
1
vote
0
answers
53
views
Show that the function $f(\vec{x})=\frac{1}{2}\vec{x}^TG\vec{x}+\vec{x}\vec{c}$ is convex if and only if $G$ is semidefinited positive. [duplicate]
Show that the function $f(\vec{x})=\frac{1}{2}\vec{x}^TG\vec{x}+\vec{x}\vec{c}$ is convex if and only if $G$ is semidefinited positive.
My approach:
$\Rightarrow]$
I want to show that $\vec{x}^TG\vec{...
- 1,454
1
vote
0
answers
86
views
How to solve this non-convex quadratic program?
Consider the following quadratic program
$$\begin{array}{ll} \underset{x,y}{\text{minimize}} & a x^2 - b x y - c y\\ \text{subject to} & x \geq 1\\ & y \geq 5\end{array}$$
where $a$, $b$ ...
- 352
0
votes
0
answers
44
views
Convert a formula to a quadratic formula.
I've just started to learn Quantum annealing and I have found that I have to convert my problem into its quadratic form. I have to use something named QUBO.
To start with, I have tried to find a ...
- 296
2
votes
1
answer
129
views
For a given function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, find the direction of least change
As written in the title, I have a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ and I want to find the direction of least change. However, I encountered an inconsistency between two different ...
- 161
1
vote
0
answers
56
views
Linear Objective with quadratic constraint
Suppose $H$ is a symmetric positive definite matrix, and $h$ a vector. I want to solve the following optimization problem with linear objective and quadratic equality constraint:
$$\underset{v^THv = 1}...
- 710
0
votes
1
answer
85
views
Prove the existence and uniqueness of a global minimum for a quadratic function $q(x)$ with positive definite Hessian
How do I prove the existence and uniqueness of a global minimum for a quadratic function $q(x)$ with positive definite Hessian?
1
vote
1
answer
57
views
Is $q(x) = \frac{1}{2} x^T H x - g^T x$ strongly convex?
Let $$q(x) := \frac{1}{2} x^T H x - g^T x$$ where matrix $H$ is symmetric positive definite and $g \in \mathbb{R}^n$. Clearly, the function is strictly convex, but why is it strongly convex?
1
vote
0
answers
46
views
Showing no stationary point of the function $f(x)=\frac12\langle Ax,x\rangle+\langle b,x\rangle+c$ is a point of local extremum
Not recalling the theorem about the sufficient conditions for local extrema, show that no stationary point of the function $f:\Bbb R^2\to\Bbb R$ $$f(x)=\frac12\langle Ax,x\rangle+\langle b,x\rangle+c$$...
- 4,357
0
votes
2
answers
296
views
How to find the minimum value of $f(x)=x^TAx+b^Tx+c$?
A scalar valued function is defined as $f(x)=x^TAx+b^Tx+c$ , where $A$ is a symmetric positive definite matrix with dimension $n\times n$ ; $b$ and $x$ are vectors of dimension $n\times 1$. Show that ...
- 8,750
0
votes
1
answer
90
views
Dual problem of a quadratic problem
the primal problem is:
minimize: $\frac{1}{2}y\cdot Py+e\cdot z $ over $(y,z)\in \mathbb{R}^{k}\times\mathbb{R}^{l}$ subject to $Dy+Ez=w$
where $P\in\mathbb{R}^{k\times k}$ is positive definite, $w\...
- 337