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

1
vote
1answer
20 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
17 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
28 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
35 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
26 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
16 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
21 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
5 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
33 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
29 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
33 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
55 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
35 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
44 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
54 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
34 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
24 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 ...
0
votes
0answers
39 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
17 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
45 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
22 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
21 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
43 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
143 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
19 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
61 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
34 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
326 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
73 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 = ...
1
vote
1answer
33 views

Quadratic Problen with 2 constraints

Could someone help me to solve the following: $\min x^Tx$ s.t. $x^T a=1$ $x^T b=0$ where $x$,$a$ and $b$ are $(N\times1)$ vectors and $1$ and $0$ scalars. Thank you!
0
votes
0answers
46 views

Determining initial values for optimization problem

I am trying to solve an optimization problem with a quadratic objective function and non-linear constraints, using SQP (Sequential Quadratic Programming). I am attempting at doing the implementation ...
0
votes
0answers
25 views

First and second derivatives of barrier term in a quadratic programming problem

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
1answer
222 views

Are “constrained linear least squares” and “quadratic programming” the same thing?

A Quadratic Programming problem is to minimize: $f(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $A\mathbf{x} \leq \mathbf b$; $C\mathbf{x} = \mathbf d$; ...
3
votes
2answers
174 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
0
votes
0answers
24 views

Restating optimization problem for quadratic programming

I'm working on implementing an author disambiguation algorithm as described in Torvik et al's paper. I've got most steps done, but am completely stumped on implementing a quadratic optimization step. ...
0
votes
0answers
19 views

Backwards quadratic programming to infer Q matrix

Consider the standard QP problem: $\arg\min \frac{1}{2}x^TQx +c^Tx$ Say I know the optimal $x$ for a large number of solutions to this problem with various (known) $c$, and identical (unknown) $Q$. ...
1
vote
0answers
27 views

Hinge point in quadratic program (bilateral constraint)

My question itself is possibly quite simple and I guess that if someone can answer me they probably does not need a wall of text that is my background to the problem, but I figured I should provide as ...
1
vote
1answer
57 views

A particular quadratic minimization problem

Given $n^2$ constants $a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}$ and $n^2$ non-negative variables $x_{11},x_{12},\ldots,x_{1n},x_{21},\ldots,x_{nn}$. Find the minimum value of $$\sum_{i=1}^n ...
0
votes
0answers
8 views

Perturbation of Polyhedral Projection

I am interested in understanding the behavior of the Euclidean projection $\pi_K(x)$ as the polyhedral set $K$ varies. I know there are different approaches to this, but for what I am doing it would ...
0
votes
0answers
76 views

enforcing big M constraints in quadprog

I have a QP with LC type problem. I have several sets of variables x1, x2 ... ,y where x is continuous and y is binary. However I don't enforce this, it is simply bound 0 <= y <= 1 Now I use big ...
0
votes
0answers
55 views

Writing down the KKT optimality conditions

Consider the problem Minimize $(1/2)\times{x}^{T}\times Q\times x+{P}^{T}\times x$ Subject to $(1/2)\times {x}^{T}\times P\times x+{d}^{T}\times x≤r$ Where Q and P are n×n matrices, P is ...
0
votes
1answer
69 views

Homogeneous non-negative least-squares

I would like to least-squares-"solve" a set of linear equations ($\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2$). In my case, $\mathbf{b=0}$, e.g. the system is homogeneous. I also ...
0
votes
0answers
31 views

How to find maximum of $w_1^Ta + w_2^Tb + w_3^Tc$

I have a question that is not homework, but I have gotten nowhere on yet. Define: $w_1^T := [x_1,\ldots,x_n]$, $w_2^T := [x_1^2,\ldots,x_n^2]$ and $w_3^T := [x_1^3,\ldots,x_n^3]$. How do I maximise ...
0
votes
1answer
297 views

How do you minimize “hinge-loss”?

A lot of material on the web regarding Loss functions talk about "minimizing the Hinge Loss". However, nobody actually explains it, or at least gives some example. The best material I found is here ...
0
votes
0answers
21 views

Optimization with intervals

I am trying to solve a specific problem, and I was able to summarize it in the following optimization problem. I have a portfolio comprised of two assets. Asset 1 has return $r_1$, standard deviation ...
2
votes
2answers
233 views

Quadratic Equality Constraints via SDP

I want to know if it is possible to solve a QCQP problem with quadratic equality constraints in SDP. I know it is possible to convert a QCQP to an SDP by using the Shur complement. The following ...
1
vote
1answer
34 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
0
votes
1answer
80 views

Linear programming with non-convex quadratic constraint

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard? $\min c^Tx$ s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in ...
0
votes
1answer
55 views

Is a given point P outside a given bounding box, in Ax < b form

Given a point $x$ and a bounding box $B$ - let's say we have the unit normals $N_i$ of the sides (pointing inwards) and one point on each side $P_i$ - we can check if $x$ is inside $B$ as follows: ...