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

4
votes
2answers
46 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 ...
4
votes
1answer
380 views

How to use lagrange multipliers here?

I have a simple QP as below: $\min L(x,y) = (x-5.1)^2+y^2$ such that $(x-3)^2+y^2\geq1$ $(x-5.3)^2+y^2\geq1$ $(x-7)^2+y^2\geq1$ Intuitively, I think the optimal solution of the problem is ...
4
votes
2answers
452 views

Analog of Simplex Method for Quadratic Programming

It happened so I need to work with an algorithm for solving QP problems. The main issue here is that I can't find any references to this algorithms (at least no references in sources in english). ...
4
votes
1answer
174 views

solution to $\min \|A-BXC \|$

I have the following problem. Let $A$, $B$ $C$ be real-valued matrices of size $m \times q$, $m \times n$, $p\times q$ respectively. I would like to find matrix $X$ of size $n\times p$ and maximum ...
4
votes
0answers
38 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 ...
3
votes
2answers
156 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 ...
3
votes
2answers
83 views

$ k x^2 +4x = n $, Algorithm or any other method needed

I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$ $ k x^2 +4 x = n $ constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$ I ...
3
votes
2answers
279 views

Quadratic equation to calculate a temperature from resistance

I'm trying to implement an electronic temperature sensor that gives a resistance value. The sensor is a Honeywell TD4. In the datasheet, they give a table of values : -40ºC => 1584Ω ±12Ω -30ºC => ...
3
votes
2answers
365 views

A standard quadratic minimization problem

Consider the "Complex" Quadratic minimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1 \end{align} ...
3
votes
1answer
42 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 ...
3
votes
1answer
233 views

Optimization problem with ratio objective

I need to solve the following optimization problem $$ \text{maximize} \quad \frac{(a^T x)^2}{x^TBx+c^T|x|} \quad \text{subject to} \quad \|x\|_1=1 \quad (\text{or alternatively} \quad c^T|x|=1), $$ ...
3
votes
2answers
1k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
2
votes
1answer
160 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$; ...
2
votes
1answer
78 views

Find my mistake: Solving quadratic programm by “brute force” triangularization

Do you know the feeling when you have proven something totally incredible? In fact, it is so incredible you do not believe it yourself. So you start looking for your mistake, for the one, small ...
2
votes
2answers
217 views

Finding the closest vector subject to an absolute constraint

I'm trying to solve the following problem: $$\min_b \|d-b\| \\ \text{s.t. } |Ab|^2 \leq y $$ or equivalently $$\min_b \|d-b\| \\ \text{s.t. } |Ab| \leq c = \sqrt{y} $$ Both $d$ and $b$ are vectors. I ...
2
votes
1answer
25 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.} \\ ...
2
votes
1answer
1k views

How to convert quadratic programming problem to matrix form

I am new to this topic and am looking at an example I can't figure out. Can someone please help explain how this example creates the matrices used in the solver? Thanks! This is the PROBLEM ...
2
votes
0answers
33 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 ...
2
votes
0answers
21 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
37 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)= ...
2
votes
1answer
178 views

Shortest Path and Minimum Curvature Path - implementation

Let's say we are given a race track, which may be described as a closed curve of given width (it may differ along the curve). My task is to implement an algorithm which finds two kinds of trajectories ...
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
1answer
178 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
2
votes
1answer
100 views

Software to optimize a quadratic program with quadratic constraints

I'm working in eight dimensions and want to minimize $x^TAx$ under the constraints $x^TBx \geq c$. Unfortunately, A is not positive semidefinite. Worse, I am almost positive that my domain is not ...
1
vote
4answers
100 views

Solution to a system of quadratics

I am learning about a Bell State, and am trying to show that they are entangled. I believe that the required proof is to show that the system $$\alpha_0^2+\alpha_1^2=1$$ $$\beta_0^2+\beta_1^2=1$$ ...
1
vote
1answer
785 views

Example of a quadratic programming problem with no optimal solution on vertices?

Is there a way to write a quadratic programming problem with two variables bounded, nonempty feasible region linear constraints and yet have none of the vertices of the region optimize the ...
1
vote
1answer
32 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 ...
1
vote
1answer
474 views

Markowitz portfolio optimization

Say that there are 5 assets with given mean values, standard deviations and correlations. Is it possible to find the expected return of a risk-seeking portfolio (maximum expected return) by using ...
1
vote
1answer
141 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
1answer
251 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 ...
1
vote
1answer
56 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 ...
1
vote
2answers
203 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
2answers
71 views

Trace of quadratic function with 2 PSD matrices - convex?

If A & B are positive semi-definite, is this always convex: $$ trace(XAX^TB) $$ There was a similar question asked here: Trace of a quadratic function, Convexity and here: Confusion related to ...
1
vote
1answer
124 views

Issues with quadratic programming

I am trying to do a quadratic programming. I have an affinity matrix A, and I have to maximize certain function x'Ax. This is basically related to feature matching i.e matching points to labels This ...
1
vote
1answer
845 views

Linear least squares with non-negativity constraint

I am interested in the linear least squares problem: $$\min_x \|Ax-b\|^2$$ Without constraint, the problem can be directly solved. With an additional linear equality constraint, the problem can be ...
1
vote
1answer
2k views

Matlab Trust-region-reflective algorithm warning

I am very new to matlab and trying to solve portfolio optimization problem (minimizing the variance) using quadprog: ...
1
vote
0answers
11 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
0answers
12 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 ...
1
vote
0answers
22 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
18 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 ...
1
vote
1answer
32 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!
1
vote
1answer
52 views

Solving multiple $L_1$ penalties with quadratic programming

Starting from a simple $L_1$ penalization: \begin{equation} min_x \frac{1}{2}||y-x||^2_2 + \lambda||Dx||_1 \end{equation} We can solve this with quadratic programming via the dual problem: ...
1
vote
1answer
265 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
1
vote
0answers
18 views

Uniqueness of the solution to a quadratic opt problem

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
1
vote
0answers
53 views

Linear Complementarity Problem - multiple solutions, which one will it find?

If I have a inequality constrained system: w = Mz + q <= 0, z<=0, z^T w = 0 that for some given properties M and ...
1
vote
0answers
92 views

Nearest point to a convex polytope

I am looking for fast, memory-efficient computational algorithms to solve the following problem: Minimize: $||x - x*||_2^2$, subject to constraints $A x = a, B x <= b, l <= x <= u$, where ...
1
vote
0answers
109 views

Minimize a complex quadratic subject to two convex quadratic constraints

I have the following the optimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\} \\\ ...
1
vote
0answers
126 views

Quadratic programming with simplex constraints

I have this quadratic function $x'Ax$ which is not convex. I want to maximize this function subject to the constraints that the solution x lies in a simplex such that $\sum_{i=1}^{n}x_i=1$. That means ...
1
vote
0answers
119 views

Algorithm and solver for large, dense, positive-semidefinite integer QP

I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n ...
0
votes
2answers
46 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$$ ...