Questions tagged [quadratic-programming]
Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.
0
votes
0answers
25 views
Active set method for a simple problem
In my computetional methods course we recently had an algorithm for solving
$(P)$ : $\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^THx + c^Tx $
subject to $a_i \leq x_i \leq b_i$ for $i \in \...
0
votes
0answers
25 views
Dual of linear program with several quadratic constraints
Let $ \mathcal{P}$ be a convex problem with linear objective and quadratic constraints,
$$ \eqalign{
\mathcal{P}: & \min_{x,t} -t \\
& \text{s.t.} \\
{\color{blue}{\mu_k}}: & a^H_k x +...
1
vote
1answer
22 views
How can I ensure that the quadratic constraints I am creating are convex?
Essentially, how can I check if functions like this are convex, and how can I know before I write a quadratic constraint that it will be convex? So essentially, how can I write feasible convex ...
0
votes
1answer
39 views
Finding minimum of penalty-approximated quadratic problem
Find the minimum of the following quadratic function
$$ f_{\alpha}(x) := \frac{1}{2} x^T H x + c^T x + \frac{\alpha}{2}(b^Tx)^2 $$
where matrix $H$ is symmetric and positive definite, and $\...
0
votes
2answers
34 views
Minimizing univariate quadratic via gradient descent — choosing the step size
I'm learning gradient descent method and I saw different (and opposite) things on my referrals.
I have the following function
$$f(x) = 2x^2 - 5x$$
and I have to calculate some iterations of ...
4
votes
2answers
116 views
How to solve this inequality-constrained least-squares problem?
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 ...
1
vote
1answer
33 views
Proving that the solution of ${\rm arg\,min}\,\|W-HH^T\|_F^2$ is the same as the solution of ${\rm arg\,max}\langle W,HH^T\rangle$
Assume a binary matrix $A\in\{0,1\}^{N\times K}$, where $K\leq N$, and there is one and only one non-zero element in each row of $A$, i.e., $A1^{K\times 1}=1^{N\times 1}$. We obtain a matrix $W=AA^T$. ...
1
vote
2answers
61 views
Solve KKT conditions of the following problem
I'm having problems solving the following
$\min f(X) = −3x^2 +y^2 +2z^2 +2(x+y+z) $
subject to $c(X):=x^2+y^2+z^2−1=0$
Now, I get the KKT:
$-6x +2 -2\lambda x = 0 $
$2y +2 -2\lambda y = 0 $
$4z +...
0
votes
0answers
7 views
Quadratic problem with non-negativity constraints: substantiate the hardness of analytical solution
I have a quadratic program
$$
\underset{V\mathbf{x}=\mathbf{d}, \mathbf{x} \geq \mathbf{0} }{\min} f_{\mu}(\mathbf x)= \sum_{i=1}^{n} \text{Var}\left(R_{i}\right)-\sum_{i=1}^{n}\mu\text{E}(R_i),
$$
...
2
votes
0answers
76 views
Simplification of a Quadratically constrained, Quadratic objective (to apply Semidefinite relaxation)
I came up with the following optimization problem:
$$\arg\max_{G_i} \quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$
subject to:
$$\|G_i\|_2^2=1 \quad \forall i$$
$$\|G_i-G_{o_i}\|_2^2\leq c \quad \forall i$$
...
2
votes
4answers
85 views
How to maximize $p_1p_2$ subject to constraints?
Given $x_2 \geq x_1 \geq 0$, solve the following optimization problem in $p_1$ and $p_2$.
$$\max p_1p_2$$
subject to:
$$p_1 x_1 + p_2 (x_2 - x_1) = 1 $$
$$0\leq p_2 \leq p_1$$
0
votes
1answer
52 views
Multiple constraints on quadratic programming? - How to solve?
Assume that you are using quadprog command in MATLAB/Octave and you want to minimize this objective function:
$$\Phi_{min} = \frac{1}{2}X^TQX + c^TX$$
With ...
0
votes
0answers
40 views
Why is positive definiteness required for a global minimum to exist?
When we optimize
$$\min x'Ax$$
why does matrix $A$ need to be positive definite in order to have a global minimum?
0
votes
1answer
53 views
Solving weighted least squares with non-negative constraints
I have the optimization problem
$$
\begin{align}
\min_{\mathbf{P} \geq 0} \|\mathbf{A\odot(X-PQ^\top)}\|^2 + \frac{\|\mathbf{P}\|^2}{2}
\end{align}
$$
$\odot$ is the Hadamard product, $\mathbf{A,X,P,...
1
vote
2answers
73 views
Explanation of a convex quadratic program
I want to find the minimum of the following optimization problem but don't even understand the problem in the first place.
$$\min\limits_{AX=b}\frac{1}{2}X^{T}QX+C^TX+\alpha$$
where $Q, A \in M_{n \...
0
votes
0answers
28 views
Why would sequential quadratic programming fail to find global minimum?
I have a data set. A matrix $X$, $1300 \times 20$ and output vector $\mathbf{y} \in \Bbb R^{20}$ $$\mathbf{y} = \begin{bmatrix} 100\\100\\\vdots\\100\end{bmatrix}$$
I am trying to run OLS on this ...
1
vote
2answers
58 views
Best approximation of an arbitrary matrix by a distance matrix
A distance matrix $D$ is a $n\times n$ matrix obtained by computing the pair-wise distances $D_{ij} = \text{dist}(x_i, x_j)$ between a collection of points $\{x_1,\ldots, x_n\}$ in some metric space. ...
0
votes
0answers
34 views
Minimum of sum of six squares over a polytope
$$\begin{array}{ll} \text{minimize} & x_1^2 + x_2^2 + \cdots + x_6^2\\ \text{subject to} & x_1 + x_2 + \cdots + x_6 = K\\ & x_1 + x_2 \ge k_1\\ & x_1 + x_2 + x_3 + x_4 \ge k_2\\ & ...
0
votes
0answers
10 views
On higher degree quadratic conditions as convex constraint in convex programming?
We know $x^2+y^2+z^2<a$ is a quadratic condition if $a>0$ and can be used as convex constraint in convex programming.
Is $x^{2n}+y^{2m}+z^{2\ell}<a$ also convex condition if $a>0$ and can ...
2
votes
0answers
42 views
Minimum of $\langle Ax,x \rangle - 2 \langle b,x \rangle$.
In exercise 5 of section 0 of Fundamentals of convex analysis by Hiriart-Urrut, Lemaréchal, we're supposed to prove that if a self-adjoint linear operator $A:\mathbb{R}^n \rightarrow \mathbb{R}^n$ is ...
0
votes
0answers
63 views
How to solve this constrained maximization problem?
Does anyone have an idea of how to tackle the following maximization problem?
Maximize the function $ f(x,y,z) = x - y - \alpha z^2 $, $ \alpha > 0 $, under the following constraints:
C1:...
0
votes
1answer
41 views
Total Unimodularity in Integer QP
I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the ...
0
votes
0answers
18 views
Quadratic programming terms
Help me to understand the terms of this quadratic programming problem?
$$
P{\left(U,Z,W\right)} =
\sum_{p=1}^{k}
\sum_{i=1}^{n}
\sum_{j=1}^{m}
U_{ip}
W_{pj}
(
X_{ij} - Z_{pj}
)^{2}
+{1 \over{2}}a
\...
0
votes
0answers
39 views
Are step sizes in quadratic programming solvers analytically exact?
In this paper (DOI link), Goldfarb and Idnani describe an algorithm for solving a certain subset of quadratic programs. This algorithm (or a very similar one) is implemented in the quadprogpp package ...
0
votes
0answers
30 views
Quadratic programming: Approximate Solution
Let $A$ be a $p \times p$, positive definite and symmetric matrix and $t \in \mathbb{R}^p$, such that $t_i>0$ for at least one $i \in \{1,\dots,p\}$. Let $x^*$ be the unique minimizer of
$$min \{x'...
0
votes
2answers
19 views
Does this special case of convex quadratic programming have a partially-unique solution?
I know that a strictly convex quadratic programming problem has a unique solution, but I'm curious about the following situation:
If $Q$ is positive definite, does the following problem:
$$\min\...
0
votes
0answers
17 views
How Sequential Quadratic Programming versus Quadratic programming and Iterative QP are related?
What is the difference between Sequential Quadratic Programming (SQP) versus Quadratic Programming (QP)? Is it the same as Iterative Quadratic Programming (IQP)? For example, BFGS, DFP are types of QP/...
0
votes
1answer
45 views
Methods for solving nonlinear constraints quadratic programming
Are there any other methods to solve nonlinear constraints quadratic programming? I have known that some effective numerical methods, i.e, SQP and Gauss pseudospectral method and some heuristic ...
1
vote
1answer
38 views
quadratic programming /symmetric matrix
I have a quadratic program with $ F: \mathbb{R^n} \rightarrow \mathbb{R}, F(x)=x^TQx$ I want to find a symmetric matrix M for Q, such that $F(x)=x^TMx$ holds for all x.
I can write Q as sum of ...
0
votes
2answers
95 views
Determining the coefficients of $y = a x^2 + b x + c$ so that the graph contains three given points
Determine coefficients of the equation for a second order polynomial in the format: $y = a x^2 + b x + c$
Here are the $x$-$y$ coordinates of three points:
$(0.8143,0.3500)$
$(0.2435,0.1966)$
$(0....
0
votes
1answer
55 views
Unconstrained convex quadratic integer programing
Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I have a minimization problem of the form
$$
\min_{n\in N} \sum_i A_i n_i +\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2
$$
...
0
votes
1answer
44 views
Approximate function by stacking building blocks
I need some help with a 'generalised Lego problem':
Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
0
votes
1answer
46 views
Linearly constrained quadratic program
I have the following quadratic program
$$\min_x x^TAx \qquad \text{s.t} \quad Ax \in [a,b]^m$$
where matrix $A$ is positive semidefinite, and is similar both the objective function and in the ...
0
votes
0answers
28 views
Is there a time polynomial algorithm to solve a box-constrained quadratic convex program?
I am working on the following quadratic convex problem
$min_{x}x^{T}Qx+f^{T}x$
subject to
$a\leq x\leq b$
where $x,a,b,f\in\mathbb{R}^{n}$ and $Q$ is positive definite. Is there any
algorithm that ...
0
votes
1answer
55 views
Measuring infeasibility in convex optimization, relations with dual problem
A question regarding convex optimization and (maybe) duality.
I have a problem in the form
\begin{align}
x^* = \mathrm{arg} \min_x f(x) \quad \text{s.t.} \quad A x \leq b, C x = d,
\end{align}
where $...
1
vote
0answers
80 views
Derive LCP from KKT conditions of a QP
I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program
$$
\begin{aligned}
\min \quad& \frac{1}{2}u^TQu - c^Tu\\
\text{...
0
votes
1answer
76 views
Is there only one unique minimizer for this scalar complex quadratic form?
Consider $c,b \in \mathbb{C}$ and $f: \mathbb{C} \mapsto \mathbb{R}$,
$$f(c) = bc' + b'c + cc'$$
is there only one extrema of $f$ corresponds to $$c^* = -b$$?
where, $'$ means complex conjugate.
...
0
votes
1answer
70 views
Local optimality of non-convex quadratic minimization with linear constraints
We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave.
Also, there ...
0
votes
0answers
44 views
Quadratic program reformulation maximum to minimum
I am newbie in optimization problem, I have the following optimization problem:
$$\max \quad \frac{1}{2}x^THx - q^THx$$
$$\text{s.t.} \;\;l\leq x \leq u$$
where $H, q$ are known constants, and H is ...
1
vote
2answers
55 views
Quadratic optimization problem with quadratic constraint
Given $A = A^T \in \mathbb{R}^{n \times n}, X = \begin{bmatrix}x & \eta\end{bmatrix} \text{with} \ x, \eta \in \mathbb{R}^n$ and $||x|| = ||\eta|| = 1$ (vectors in $\mathbb{R}^n$ are treated as ...
1
vote
0answers
59 views
Karmarkar's canonical form for convex quadratic programs??
I'm working through this paper A Simple Polynomial-Time Algorithm for Convex Quadratic Programming which gives an interior point algorithm for convex quadratic programming. I've reached the end of the ...
0
votes
1answer
21 views
confusion in proof of lemma for LCP
I'm looking at the proof of lemma 2 on page 6 of https://cowles.yale.edu/sites/default/files/files/pub/d05/d0549.pdf
Which claims that the LCP
$$
Mx+q \geq 0 \\
x \geq 0 \\
x^{T}(Mx+q) = 0
$$
has a ...
0
votes
1answer
61 views
minimum of $\frac{1}{2}x^tQx-c^tx$ subject to $Ax=b$ is local $\iff$ is global
$$\min \frac{1}{2}x^tQx-c^tx\\ Ax=b$$ where $Q\in \mathbb{R}^{n\times
n}$ is symmetric, $c\in \mathbb{R}^n$, $A\in \mathbb{R}^{m\times n}$
and $b\in\mathbb{R}^m$. Prove that if ${x}^*$ is a local
...
3
votes
2answers
239 views
How to minimize $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \Vert = 1$?
Given $n\times 3$ matrix $A$ and unit vector $\hat{b}\in R^3$, is there a closed-form solution for $x\in R^3$ that minimizes the Euclidean norm $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \...
0
votes
0answers
16 views
Two dimensional sorting: finding $\max_\sigma \langle M^\sigma,C\rangle$ for permutation function $\sigma$
Suppose that we have a non-negative matrices $C,M\in \mathbb{R}^{m\times m}_{\ge0}$. Also suppose $\sigma:[m] \rightarrow [m]$ is a permutation of $\{1,2,...,m\}$. We want to find the permutation that ...
0
votes
0answers
104 views
Large scale mixed integer (quadratic) programming
Here we have this optimization problem:
Given positive semi-definite matrix $A \in \mathbb{R}^{n \times n }$, and matrix $B \in \mathbb{R}^{n \times m} \text{ and vectors } d \in \mathbb{R}^n,e \in ...
6
votes
2answers
159 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 ...
0
votes
1answer
21 views
How to find uppper bound for the hyper parameters in linear model?
I have loss function of the following form:
$$argmin_w= ||Y-w^TX||_2^2 + \lambda||w||_1 + \gamma \sum_{g=1}^G||w_g||_1$$
where $w_g$ is group of coefficents.
Given $Y$ and $X$, I would like to find ...
0
votes
2answers
101 views
Minimise $||Ax - b||_2$ given $x \geq 0$ and $\textbf{1}^Tx = 1$
$$
\min_x ||Ax - b||_2\; \;\text{given }x \geq 0\;\;\text{and}\;\;\textbf{1}^Tx = 1
$$
I am trying to do the above optimization, I was using common Quadratic programming libraries but their speed is ...
0
votes
1answer
59 views
Silly Quadratic programming
Suppose that I want to minimize the function $x^2$ subject to the contraint
$$
ax\leq b,
$$
for some $b> 0$. I solved the problem if the contraint is an equality but I'm not sure how to go about ...
