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
17 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
15 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
30 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 ...
0
votes
0answers
12 views

Sequential Quadratic Programming

I am new to optimization techniques. I have lograthmic function which I need to maximize. I need to ask if sequential quadratic programming can be used to solve logrithmic function taken as objective ...
2
votes
0answers
14 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
16 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
29 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
134 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
16 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
44 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
31 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
132 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
33 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
31 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
35 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
17 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
81 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
130 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
17 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
17 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$. ...
0
votes
0answers
21 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
53 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
6 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
45 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
25 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
54 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
30 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
168 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
20 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 ...
1
vote
2answers
143 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
30 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
65 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
48 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: ...
1
vote
1answer
49 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: ...
0
votes
0answers
64 views

a question about relationship between KKT matrix equation and optimal solution of quadratic problem.

I have a question regarding how the KKT matrix plays in solving for optimization problem: Is it correct that the optimal solution for quadratic optimization problem with positive definite hessian ...
0
votes
0answers
72 views

Are box constraints problematic when using KKT conditions to solve quadratic programming problems?

I've dealt with quadratic programming before, but I've never seen something of this sort: $$\min \frac12 \|v\|^2 + \sum_ip_i$$ $$\text{s.t. }f(v,p)\ge0 $$ $$0\le p_i\le a$$ for some constant a ...
1
vote
1answer
218 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
17 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} $ ...
0
votes
0answers
31 views

Implementing SVM: Help converting equation into form of another

I'm currently programming a simple linear SVM (Support Vector Machine). For the optimization involved, I need to find a way to convert the equation $\sum\limits_{i=1}^L a_i ...
1
vote
2answers
65 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 ...
0
votes
0answers
24 views

How to check if steepest gradient method will converge?

So I have this function $ f(x,y) = x^4 - 2x^2 +x + 4y^2 $ and I want to know if the steepest gradient method will converge if I pick an arbitrary point and apply said method. My initial thought ...
0
votes
1answer
43 views

How can I find the minimum and maximum?

Lets have the following equation: $f(x,y,y) = cos(x)^2+\frac{1}{1+x^3}+y^3+z$ I would like to find the minimum and maximum where $-2<x<2$ $-1<y<1$ $-2<z<1$ How can I do that, I ...
0
votes
0answers
42 views

Finding an optimal set of weights for combining correlated classifiers

In order to combine classifiers that are correlated with one another, I would need to solve the following optimization problem: Find a vector $\mathbf{w}$ that minimizes $\mathbf{w}^T M \mathbf{w}$ ...
1
vote
0answers
52 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 ...
0
votes
1answer
60 views

Minimization problem convex set

I'm trying to minimize the function: $$f(w)=w^T\mu+k\sqrt{w^T\Sigma w}$$ where $w$ is a vector in $W=\{x \in \mathbb{R}^n|x_1+...+x_n=1 , x_i \geq 0 \forall i\}$. The vector $\mu \in \mathbb{R}^n$, ...
0
votes
0answers
219 views

Minimum Curvature Path - implementation

I need to implement an algorithm which solves the Minimum Curvature Path problem. I found an interesting solution in Race driver model by Braghin, Cheli, Melzi and Sabbioni. Here is an image of the ...
2
votes
1answer
164 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 ...
3
votes
2answers
82 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 ...
0
votes
1answer
62 views

How to re-parametrize for quadratic minimization?

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...