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

3
votes
2answers
91 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 ...
2
votes
1answer
28 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
1answer
218 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
966 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 ...
0
votes
0answers
14 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
14 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
12 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
48 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
5 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
21 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
22 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 ...
2
votes
1answer
94 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 ...
0
votes
1answer
44 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 ...
1
vote
1answer
151 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 ...
0
votes
1answer
86 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
18 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
45 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
27 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
53 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
41 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
44 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
2answers
2k views

Using Matlab quadprog to solve markowitz model

I have the markowitz model shown below and I need to use the quadprog function to solve it (i.e get the values for w_i values). However I am a bit new to mat lab and not sure which definition of ...
0
votes
0answers
50 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
56 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
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
46 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
22 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 ...
2
votes
1answer
165 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} ...
0
votes
1answer
41 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
32 views

Total unimodularity in quadratic programming.

I have a quadratic integer problem of the following form: \begin{align} minimize & \quad \tfrac{1}{2} x^T Q x + c^T x \\ subject \ to & \quad M x = 1 \\ & \quad x_i \in \{0, 1\} ...
0
votes
0answers
39 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
49 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
183 views

Minimum Curvature Path - implementation

I need to implement an algorithm which solves the Minimum Curvature Path problem. I found an interesting solution in this paper http://i.imgur.com/2EeGQKp.png. First, I decided to implement an ...
2
votes
1answer
142 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
56 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
80 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 ...
4
votes
1answer
168 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
1answer
280 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 ...
0
votes
1answer
55 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 ...
0
votes
0answers
124 views

Optimization problem given a known solution space

Here is my problem. I have to find four points in 3D (x1,y1,z1; x2,y2,z2; x3,y3,z3; x4,y4,z4) that satisfy some given quadratic constraints. In addition, I have a solution space in the form of a set ...
1
vote
0answers
72 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 ...
0
votes
2answers
494 views

How to solve this quadratically constrained quadratic programming problem?

Could you please shed some lights on this? (Not a homework problem) I am looking for solutions to solve the following problem: $$\text{max } || X b || \text{ s.t. } || b - b_0 || < a, || b || = ...
0
votes
0answers
74 views

Is this a quadratic programming problem?

I have $N$ unknown 2D points ${\bf x} = (x,y)$ and I want to minimize: $f({\bf x}) = \sum_{i=0}^{N-1}{(||x_{i+1} - x_i||_2 - c_i)^2}$ where c are $N-1$ known scalars. What is the simplest form that ...
3
votes
2answers
307 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} ...
1
vote
0answers
86 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}\} \\\ ...
0
votes
2answers
124 views

Optimize quadratic problem under collinearity boundary condition

Summary Given the optimization problem $$ \min_{d\in\mathbb{R}^{n\times 2}} \text{trace}\big( d^T Q d+Cd\big) $$ for some $n\times n$-matrix $Q$ and another matrix $C\in\mathbb{R}^{2\times n}$, I'd ...
0
votes
1answer
146 views

Convex optimization problem to quadratic programming problem

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a ...