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
5 views

How to deal with a barrier function when constrained variables reach their bounds?

I am implementing an algorithm of Dang and Xu's, ``Non-convex Quadratic Programming Problem with Box Constraints'' and I'm hoping that somebody could verify what I'm doing. Their algorithm minimizes ...
2
votes
0answers
26 views

Second-order Quadratic Constraint

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^T\theta\\ \text{subject to} & ...
0
votes
0answers
124 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
1
vote
1answer
59 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
51 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
29 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
31 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
29 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
13 views

Quadratic program with complementarity/modular constraints is NP?

Is the following program NP/NP-hard? Any neat way to prove it, or a helpful reference? $\min x^TMx$, subject to $\|x\|_1=1,e^Tx=0$ Here $M$ is a real, symmetric and semidefinite positive matrix, ...
0
votes
0answers
18 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
46 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
34 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
58 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:}} ...
0
votes
0answers
37 views

Using Gurobi QP to solve SVM problem

I am trying to use Gurobi to solve the QP problem in primal form of soft margin SVM. The quadprog function seems to return the correct answer while Gurobi cannot solve the problem. Gurobi keeps ...
1
vote
0answers
40 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: ...
0
votes
0answers
8 views

How to test if a set of underdetermined equations have solution in a particular region?

For a underdetermined system $A\cdot x = b$ where $A$ is a $m \times n$ matrix with $m<n$, how to test if it has a solution within a specific region $\{ x | lb<x_i<ub \}$? Basically I have ...
0
votes
0answers
24 views

Reformulate as quadratic programming

I am trying to approximate L0 constrained quad-prog problem as L1 but not making any progress. The objective is to minimize $x A x'$, s.t. $\sum x <=n$ , where $0<=x<=1$ and A is positive ...
1
vote
4answers
66 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
21 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
30 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
33 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
37 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
40 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
43 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
32 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
20 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
40 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
20 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
13 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
46 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
31 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
40 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
72 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
37 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
78 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
57 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
35 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
31 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 ...
1
vote
0answers
55 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} ...
0
votes
0answers
19 views

Is there a software package to solve large (128 x 128) non-positive-definite quadratic programming problems?

I am trying to solve a quadratic program of the form maximize $\sum_{i=1}^n\sum_{j=1}^nA_{i,j}w_iw_j$ subject to $\forall i:w_i\ge 0$ and $\sum_{i=1}^nw_i=1$ for a 128$\times$128 matrix $A$. ...
3
votes
1answer
55 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
26 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 ...
0
votes
0answers
27 views

Quadratic programming over a simplex

I have to solve the following problem: $$\left\{\begin{array}{l}\hat\theta = \arg \min_{\theta} \theta^TQ\theta + \theta^Tl\\ \text{s.t.}\\ \sum_{i=1}^n \theta_i = M\\ \theta_i \in [0, M] ~ \forall i ...
2
votes
0answers
67 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)= ...
1
vote
1answer
151 views

How to solve this optimization problem with equality constraints?

I want to find $\delta_j$ in the following optimization problem. My variables are $\gamma_i$ and $\delta_j$ (all other symbols are known parameters). Assume $i\in\{1,\ldots,9\}$ and ...
1
vote
0answers
24 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
0
votes
2answers
79 views

Exposition of solving the quadratic programming problem for SVMs

I'm looking to find a mathematically rigorous exposition on how to solve the quadratic programming problem $$\min ||x||^2 \textrm{ subject to } Ax\leq b$$ where $x\in\mathbb{R}^n$, ...
0
votes
1answer
40 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
1
vote
1answer
614 views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where ...
0
votes
0answers
230 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...