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.

learn more… | top users | synonyms

0
votes
0answers
73 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
45 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} ...
3
votes
1answer
155 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
48 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
50 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
91 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
24 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
61 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
76 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
120 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
54 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 ...
0
votes
1answer
45 views

minimising quadratic function subject to integer solutions

I would appreciate if one could help me to solve this problem. I have a bivariate quadratic function: $$ f(a_1,a_2)=(1-u_1^2)a_1^2 +(1-u_2^2)a_2^2 -2u_1u_2a_1a_2 $$ where $u_1^2+u_2^2=1$ and $a_1$ ...
2
votes
0answers
165 views

Lagrange multiplier expression

I would like to solve the following optimization problem using the gradient ascend method: \begin{array}{ll} \text{maximize}_{\theta} & \theta^TQ_1\theta + b_1\\ \text{subject to} & ...
1
vote
1answer
148 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
0
votes
2answers
198 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
0
votes
1answer
83 views

How to determine the optimal step size in a quadratic function optimization

I have the following optimization problem: $$\underset{\alpha\in\mathbb{R}}{\text{min}}:\;\;f(\textbf{x}+\alpha\textbf{d})$$ $$\text{subject to}:\;\;0\leq\alpha\leq \alpha_{max},$$ where ...
1
vote
1answer
270 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
1
vote
1answer
56 views

Quadratic programming with constrained number of free variables

I started with a (positive-definite) quadratic programming problem subject only to a single equality constraint. i.e. $$ f(x)=x^{T}Qx+c^{T}x $$ $$ s.t. x_1+x_2+x_3+...+x_n=y $$ I now have to find ...
0
votes
0answers
38 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
0
votes
1answer
69 views

SVM and quadratic programming

I wonder if the SVM optimization problem minimize $||w||^2$ with the contraints $y_i(w^\intercal x_i+b)\ge 1$ could be formulated as a typical quadratic programming problem: $0.5\cdot z^\intercal ...
2
votes
0answers
47 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
0
votes
1answer
180 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
1
vote
0answers
116 views

Why use two slack variables in the support vector regression formulation?

I am learning support vector regression but cannot fully understand the rational of the slack variable tricks in its formulation. The original optimization problem for SVR is as follows: ...
1
vote
4answers
87 views

Optimization of a quadratic function with qudratic constraints

I'm a Graduate student of Electrical Engineering. I have some basic knowledge on Convex Optimization. For my research, I cam across the following optimization program. With $\mu > 0$, find $\arg ...
0
votes
0answers
31 views

Portfolio Optimization Problem: Variance Co-variance matrix

I have a set of daily returns and using these daily returns I calculated the average annual return for each asset and also by using the daily returns I calculated the var-cov matrix. To get optimize ...
0
votes
0answers
50 views

Finding a solution on Matlab for a quadratic programming-type problem with more restrictions

I have some existence results using one modified version of the Farkas Lemma for which I need to solve the following problem. This problem has its application on economics but I will refer here merely ...
1
vote
1answer
63 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
0
votes
1answer
119 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
1
vote
0answers
55 views

Two quadratic programming problems always same answer?

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Is there an intuitive proof? Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T ...
1
vote
1answer
129 views

How do you calculate the coordinates a quadratic curve follows?

I'm a programmer, and terrible at maths. Usually, I try Google or my math-addict co-worker for problems like this, but Google searches show nothing and my co-worker is on vacation for a few weeks. I ...
4
votes
0answers
77 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $\min_{x} (x'Ax)$ subject to $x'Bx = x'Cx = 1$. Where A is symmetric and B and C are diagonal. Does anyone have a suggestion for an ...
1
vote
0answers
59 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
1
vote
0answers
112 views

Modeling a lower-bound constraint on a euclidean distance in quadratic programming

I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either ...
1
vote
1answer
38 views

How to convert non-PSD matrix to PSD matrix?

I have a mixed-integer optimization problem with the following constraint matrix $Q_1$: \begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & 0 ...
1
vote
0answers
15 views

Optimizing a set of rules to better predict the outcome of events

I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ...
0
votes
1answer
211 views

Quadratic equation formula for a,b,c from 3 points

I can solve for a, b, c given three points for a parabola for example (1,1)(2,4)(3,9) but i need to create a program which returns a,b,c in the form: ...
2
votes
1answer
42 views

What is the solution for this quadratic program?

Given scalars $p_1\geq p_2\geq \cdots \geq p_r > 0$, can we find a solution for following problem? \begin{align} \text{minimize} & & & \sum_{j=1}^{r} p_j (1-t_j)^2 \\ \text{s.t.} \\ ...
0
votes
1answer
58 views

Quadratic Program reformulation

I have the quadratic program $$\max\quad \mu^Tx+r_fx_0-\gamma \sum\limits_{i=1}^n |x_i-y_i|-\frac{\lambda}{2}x^TVx$$ $$\text{s.t. }\quad \mathbb{1}^Tx+x_0=1$$ where $\mu$, $r_f$, $\gamma$, $\lambda$, ...
4
votes
2answers
185 views

Duality in quadratically constrained quadratic program

I have been given the primal quadratic program with a single quadratic constraint as given below: $$ \text{min} ~~~~~~~~~~~~~~~~~~~~~~~~~ \frac{1}{2}x^{T}Qx $$ \begin{align*} \text{subject ...
0
votes
1answer
58 views

quadratic constraints

Is it possible to reformulate the following quadratic constraints to conic constraints so that I use an SOCP solver $$ ( x_1^2 + x_2^2 ) - ( y_1^2 + y_2^2 ) \leqslant c $$ ...
4
votes
0answers
184 views

How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$ f(x) = x^TQx + c^Tx$$ with constrains $$ Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
1
vote
2answers
69 views

Quadratic programming for special equation issues

My problem is how to find $\tau_1$ and $\tau_2$ s.t maximize the objective function is $$E=M-\alpha V$$ subject to $$-0.0062\le\tau_1\le0.499$$ $$-0.479\le\tau_2\le0.0262$$ $$\tau_1+\tau_2\le0.02$$ ...
2
votes
0answers
41 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
1
vote
0answers
41 views

Reduce degree of a high degree unconstrained binary term to quadratic unconstrained binary term

I'm working on a optimization project, in this project I have to convert higher order unconstrained binary polynomial to quadratic unconstrained binary polynomial. Can anyone give me a hint of how to ...
2
votes
0answers
77 views

Least squares with three quadratic constraints (Ellipse fitting based on algebraic distance)

I would like to fit an ellipse to a given set of scattered data in $\mathcal{R}^2$. The fitting problem is in form least squares, minimizing the sum of squared algebraic distances \begin{equation} ...
3
votes
1answer
83 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in ...
2
votes
0answers
44 views

Reproducing Kernel Function Interpolation

My problem is as follows: I am attempting to use a reproducing kernel and quadratic programming to optimize/interpolate a smooth function from constraints. I am using all local extrema to calculate ...
2
votes
0answers
139 views

Constrained Quadratic Optimization(Reproducing Kernel)

I am attempting to use a constrained quadratic optimization to find the coefficients of a reproducing kernel. The problem is as follows: $y(t)=\sum_{i=0}^J\alpha_iK(t, t_i)$ $Q(\alpha)= ...