This is for questions on Quadratic Programming (QP). A QP problem is the problem of minimising or maximising a quadratic objective function subject to affine constraints.
0
votes
0answers
14 views
Binding inequality constraints in linear programming with quadratic constraints
I am trying to maximize the following objective function:
$a_{1}b_{1}x_{1}+a_{2}b_{2}x_{2}+a_{3}b_{3}x_{3}+a_{4}b_{4}x_{4}$
The quadratic constraint is given by
$b_{1}^2 x_{1}^2 + b_{2}^2 x_{2}^2 + ...
0
votes
1answer
61 views
A light solution of a quadratic programming problem
I have a simple and light quadratic programming problem that I need to solve, as following:
\begin{align}
& \underset{x}{\arg\min}
& & \dfrac{1}{2}x^T x-z^T x\\
& \text{subject ...
2
votes
0answers
25 views
Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem
I have a simple QCQP problem to solve:
$\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
5
votes
2answers
57 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,..x,N}, x_i \in R^3$, the associated sinc-distance matrix $S \in R^{n\times ...
0
votes
1answer
18 views
Why in quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear
I found in wikipedia that...
Quadratic programming is particularly simple when there are only
equality constraints; specifically, the problem is linear
font: Quadratic Programming
What I ...
0
votes
1answer
20 views
General form to standard form regarding ellipse?
I've tried 2 hours to do this so I hope someone can help me:
$$11400000=-0.64x^2+2560x-y^2+6000y$$
It says that it have to equal an ellipse with center at the point $(2000,3000)$ and a horizontal ...
0
votes
0answers
20 views
Nonlinear Optimization
I have a nonlinear optimization problem, but constraints are ODE.
Cost function is $J= x1+x1*x2+x1^2$
while constraints are,
$\underline{x_i} < x < \bar{x_i}$ (for i=1,2,3) ;
...
1
vote
1answer
27 views
Quadratic programing problem and MATLAB
I have a little problem with quadratic programing problem:
${\bf v}^T \Sigma {\bf v} \rightarrow min $,
and constrains are
$ {\bf v}^T \mu = \mu_*, {\bf v}^T {\bf 1 }= 1, 0 \leq {\bf v}. $
Where ...
0
votes
1answer
49 views
Solve $\min_{\mathbf{x}} \sum_i \min\left[ (\mathbf{c}_i^T\mathbf{x}-a_i)^2, (\mathbf{d}_i^T\mathbf{x}-b_i)^2 \right]$
I am wondering if there is an efficient (perhaps closed form) way to solve the following piecewise quadratic minimisation problem:
$$
\min_{\mathbf{x}}
\sum_{i=1}^n \min\left[ ...
1
vote
1answer
27 views
Minimizing a quadratic function of 2 variables in quadratic region
Let $f$ be a real valued quadratic function of 2 real variables:
$$f(x,y) = ax^2 + by^2 + cxy + dx + ey + f$$
How to minimize it? Subject to constraints:
$$ 0\leq x \leq 1, \quad 0\leq y \leq 1 $$
...
0
votes
0answers
37 views
Solution of quadratic optimization with linear constraints
Hi， I want to solve a quadratic optimization problem defined as
$\min \|\bf{a^T}\bf{x}\|^2_2$
$s.t. \|\bf{x}\|_1=1$
$\ \ \ \ \ \ \ \ x_i\ge0,\ i=0,1,...,n-1$
$\ \ \ \ \ \ \ \ \bf{b}^T\bf{x}-C\le0$
...
0
votes
1answer
23 views
Quadratic Equality Constrained Quadratic Program and Convexity
There are a few questions on this topic already. However, none of them really answer my question.
The most relevant are these:
Quadratic optimisation with quadratic equality constraints
Quadratic ...
1
vote
1answer
48 views
Positive-Semi-Definite form of Variance?
first thing: I'm an informatics student and know some algebra. However, this seems to be a bit over my head, so please be gentle with me. ;)
I have multiple sets of real variables. Let these sets be ...
0
votes
1answer
21 views
Optimization problem: Find shortest distance between two vectors
$$\min (u-v)^T(u-v)$$
$$s.t. \space Ru=p, \space Sv=q$$
where $u$ and $v$ are in $R^4$ and $R$ and $S$ are $3x4$ matrices.
When I expanded the expression I got this:
$$u^Tu - 2u^Tv +v^Tv$$
Is this ...
0
votes
1answer
62 views
Math for optimal asset allocation given constraints (linear/quadratic programming?)
Say we have a set of mutual funds, with various characteristics. I'd like to run some maths and give back the ideal mixture of these funds to meet the users constraints, and I'm unsure of whether ...
0
votes
1answer
31 views
Minimizing a quadratic function with constraints on some variables
Consider a problem with strictly convex quadratic objective with some of the unconstrained variables.
minimize: $x_1^TP_{11}x_1 + 2x_1^TP_{12}x_2 + x_2^TP_{22}x_2$
subject to: $f_i(x_1) \leq0, i = ...
0
votes
1answer
16 views
Convex or Quasiconvex Relaxed Binary Quadratic Optimization Problem
Let's say I have a quadratic problem with nonnegative triangular matrix Q and binary decision variables x.
$$min_{x} f(x) = ...
0
votes
0answers
43 views
Quadratic optimization: Why does the formula have “$\frac{1}{2}”$ in front?
$$\frac{1}{2}x^THx+c^Tx + c_0$$
I have just formulated a problem as a quadratic optimization problem in two variables. My solution differs from the solution manual in the aspect that they have, only ...
0
votes
0answers
21 views
(Convex) reformulation of a nonlinear program
Consider the following program:
\begin{eqnarray*}
\min_{\mathrm x}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\big(x_i(Sx)_i-x_j(Sx)_j\big)^2}}\\
\mathrm{subject\; to}\quad \sum_{i=1}^{n}{x_i}=1 \\
x_i\geq 0
...
0
votes
1answer
34 views
Linear programming with quadratic constraints
I have a given set of variables:
$x_1,y_1,x_2,y_2,x_3,y_3$
The objective function is to minimize the sum of these with quadratic equality constraints:
$y_1(x_1+x_2+x_3)$=0
$y_2(x_2+x_3)$=0
...
0
votes
0answers
22 views
Minimize/reformulate sum of products as convex problem
Is it possible to optimize this objective function as such or transform it into an convex formulation?
The unknown continuous variables $x_i \in [-1, 1]$ are nodes in a graph and for each edge ...
2
votes
0answers
20 views
Transformation into quadratic program
I am struggling with the following optimization problem:
\begin{equation*}
\begin{aligned}
& \underset{x_{1}, \ ..., \ x_{5} \in \mathrm{R}}{\text{minimize}}
& & \begin{pmatrix}
x_{1} + ...
0
votes
0answers
9 views
Nonlinear Programming
I have the following non-linear programmig problem that I have arrived
at after various manipulations. I have to find the set of values for
$x$ and $y$ that satisfy the following:
$$
x^{n}+y^{m}=C
$$
...
2
votes
0answers
45 views
Reformulate absolute value as quadratic problem
I'm looking for standard approach to reformulate this objective function.
The aim is to find values of $x_i$ that are close to either $y_i$ or $-y_i$ ($y_i$s are known) in a least-squares sense:
...
0
votes
1answer
29 views
Beyond quadratic in binary integer programming
If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. ...
0
votes
2answers
48 views
Converting standard constrained optimization problem into an unconstrained one
This question strikes me as if it must be a theorem or something, but I cannot find a good result. I was fiddling with Lagrange multipliers and their use when it comes to converting constrained ...
0
votes
2answers
34 views
Showing if $H$ is positive semi-definite there are either no minimizers or infinitely many
Suppose I have some $f(x) = g^{T}x + \frac{1}{2}x^{T}Hx$ where $g \in \mathbb{R}^{n}$ and $H$ is symmetric, positive semi-definite. This is the standard form for a quadratic minimization function.
...
1
vote
0answers
35 views
How to prove that this is a Quadratic Optimization Problem?
Show that the following problem is a
Quadratic Optimization Problem.
$$
\begin{array}{ll}
\max & \sum\limits_{i=1}^n
\left( \mu_i(z_i + x_i) - a_i \lvert x_i \rvert - b_i x_i^2 \right) \\
...
1
vote
0answers
72 views
Linear reformulation or approximation of a quadratic inequality set
Based on the useful comments I reformulated my problem - hopefully it's more clear now.
Let $A,B \in \mathbb{R}^{d \times d}$ be symmetric positive-semidefinite matrices, $x \in \mathbb{R}^d$ and ...
0
votes
0answers
47 views
Quadratic programming over nonnegative orthant?
I'm trying to solve a quadratic optimization over nonnegative orthant as below.
\begin{equation}
\begin{aligned}
\mbox{maximize} \quad & -\frac{1}{2} \lambda^{T} [\frac{\Sigma_{i}}{\alpha_{i}} + ...
0
votes
0answers
24 views
convex symmetric quadratic programming
Good morning,
I have trouble understanding the concept of self-duality in quadratic programming. I am reading a paper right now where we first show that the dual of a convex symmetric quadratic ...
1
vote
1answer
58 views
Maximize sum of N variables squared subject to constraint
I have the following problem.
Maximize ${\sum_{x=0}^N \beta_{1,x}v_x + \beta_{2,x}v_x^2}$ subject to $\sum_{x=0}^N v_x = X$ wrt $v_x$.
I am thinking about both Lagrange multipliers and quadratic ...
1
vote
0answers
35 views
Projection onto the positive subset of a hyperplane
I am wondering if there is a closed form solution for the projection of a point $x_0$ onto the subset of a hyperplane $Ax=b$ in the positive orthnat, that is $x\geq0$?
1
vote
0answers
50 views
Quadratic Programming “big M” method
How does the optimization problem
$$\min_{x,\eta} \frac{1}{2} x^TGx+x^Tc+M\eta$$
$$ s.t. Ax+\eta-b \geq0$$
$$\eta\geq0$$
look in standard form? What would the KKT look like?
The problem is, that ...
0
votes
0answers
30 views
Quadratic optimization problem with quadratic equality constraint
I am trying to solve the following optimization problem:
$$
\min_{x \in \mathbf{R}^2} \, x^T A x + b^Tx \quad \text{subject to $x^T J x = 1$}
$$
where $A$ is a positive semi-definite $2 \times 2$ ...
1
vote
0answers
73 views
Relaxation of non-convex QCQP with one quadratic and one linear constraint
According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
0
votes
0answers
42 views
How to do linear quadratic dynamic programming with non homogeneous quadratic equation
I am not well versed on matrix algebra and linear quadratic programming. I am wondering if it is possible to make a non-homogeneous equation into a homogeneous one. I need to make the following ...
0
votes
0answers
72 views
Computational complexity of the following quadratic program (QP)
Let $A^TA$ be a $n \times n$ matrix.
I have the following quadratic program to solve:
\begin{array}{rl}
\min \limits_{x} & x^T A^T A x \\
\mbox{subject to} & \sum_{i=1}^{r} x_i =1, ...
0
votes
2answers
44 views
Rewrite matrix equation as a quadratic programming problem
Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form:
...
0
votes
0answers
20 views
Existence of lagrange multipliers with polyhedral constraints
I am working with a paper (Exact regularization of polyhedral norms, Schöpfer 2012) which states as a well-known fact that, if $f$ is a polyhedral norm, then for some $\mu^* > 0$
\begin{equation}
...
2
votes
1answer
119 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 \Gamma
...
1
vote
0answers
42 views
Complexity of solving quadratic programming (QP) using ADMM
I am trying to analysis the time complexity of quadratic programming problem, using alternating direction method of multipliers.
Anyone could give me a help?
0
votes
0answers
46 views
Approximate inverse (or fast optimization) of non-linear least squares problem
Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define
$${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$
where $[.]_+ = ...
0
votes
1answer
65 views
Can a Convex QCQP Problem with an additional linear constraint be converted to a SOCP?
I have a quadratically constrained quadratic programming problem that I massaged into the form
$$
\begin{aligned}
& \underset{x}{\text{minimize}}
& & x^T Q x \\
& \text{subject to}
...
2
votes
0answers
23 views
Quadratic programming
For a research project I am interested in minimizing $x^TQx$ under the constraints $Qx \le b$, where $Q$ is a positive definite matrix and $b$ is a vector of negative elements. I have solved this ...
1
vote
1answer
30 views
quadratic programming problem with positive constrains
Is there a non-iterative solution to the following quadratic programming problem with constrains? Is there any problem to think the variable as some square of another variable to get ride of the ...
0
votes
0answers
55 views
How to obtain the optimal lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found.?
I am using a blackbox solver to solve the following nonconvex QCQP to global optimality.
$$ \min_x x^TQ_0x + c^T x \\
s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\
Ax=b \\
l\leq x\leq u
$$
where $Q_0$ is ...
1
vote
0answers
72 views
Quadratic optimization problem (inner products) with stochastic constraints
Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
0
votes
1answer
103 views
SDP relaxation of a non-convex quadratically constrained quadratic program.
I am very new to SDP and SDP solvers. I have a semi definite program of the following form
$$\min_{x,X}\ Q\bullet X+c^Tx$$
$$\text{s.t. } Q^k \bullet X + (c^k)^T x =b^k , \ k=1,2, \dots,m \\
\quad ...
0
votes
0answers
51 views
When is a quadratically constrained quadratic program (indefinite objective matrix) unbounded?
I have a nonconvex QCQP of the form
$$x^TQ_0x + c^T x$$ such that $x^TQ_1x+c_1^Tx=b_1$, $Ax=b$, and $l\leq x\leq m$
where $Q_0$ is indefinite diagonal matrix and $Q_1$ is positive semidefinite ...
