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

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
1
vote
1answer
48 views

How to solve this quadratic matrix equation?

I have to solve the following equation where D is the unknown matrix: $$D^{T}D(DVD^{T}+I)^{-1}=A$$ I is the identity matrix, V and A are know constant matrices. Does anyone have any idea how to solve ...
0
votes
0answers
12 views

How to solve a LMI with inverse matrix and quadratic form

I have to solve the following LMI, where $\Sigma$ is a symmetric positive definite matrix. K,D and $\Sigma$ are unknown: $$\left[\begin{array}{cc} K\Sigma^{-1}K^{T}+DVD^{T}+I & KA^{T}\\ AK^{T} &...
0
votes
0answers
30 views

Minimizing trace with equality constraints

I would like to solve the following trace-minimization under equality constraints optimization problem: $$W^* =\arg\min \operatorname{Tr}[WCW^T] \text{ s.t. } A=B^TW^TWB$$ where $W,C\in\mathbb{R}^{...
-1
votes
0answers
13 views

reference request quadratic optimization problem

I have this problem and it seems similar to something people must have studied in quadratic optimization/non-convex optimization. $\min_{a,b \in [0,1]^n} a^TM b\\ \text{subject to. } a^TQb\geq \alpha$...
0
votes
0answers
10 views

Lagrangian Relaxation of quadratically constrained quadratic program

I have the following problem: $$ \min_{w,\theta\ge0}\frac{1}{2}\|w-w_t\|^2+(\theta-\theta_t)^2 \text{ s.t. } w^\top(\hat n\hat z-nz)+\theta w^\top(z-\hat z)+1 \le 0,\theta-1\le 0 $$ Notice that $w$ is ...
1
vote
0answers
39 views

Quadratic problem with two vectors linked by one quadratic constraint

I would like to find $$\min_{w,b} w_iA_{ij}w_{j} + b_iB_{ij}b_j + 2\alpha_iw_i + 2\beta_ib_i $$ Constrained to: $$ w_i > 0 $$ $$ \sum w_i = 1 $$ $$ b_i=w_i^2 $$ Where $A$ and $B$ are positive ...
2
votes
1answer
37 views

Minimizing the Frobenius norm with linear inequality constraints

How to solve the following system for $\mathbf{C}$ and $\mathbf{a}$: $\min\|\mathbf{X-XC} \,\mbox{diag} (\mathbf{a})\|_F^2$ subject to $\mathbf{c}_{ik}\geq 0$, $1^T \mathbf{c}_k = 1$ and $1-\delta\...
2
votes
0answers
29 views

Boolean Quadratic Programming

I am new to optimization and I am trying to understand concepts of semi-definite relaxation (SDR) through examples. It seems my understanding of this topic is not fully clear as I will show in details ...
1
vote
2answers
47 views

Optimizing a problem using Lagrange multipliers

$\newcommand{\norm}[1]{\|#1\|}$ I have the following problem: $$ \min_{w,\theta}\frac{1}{2}\norm{w-w_t}^2+\frac{1}{2}(\theta-\theta_t)^2 \text{ s.t. } w^\top(z(n-\theta)-\hat z(\hat n - \theta)) \ge 1 ...
1
vote
2answers
52 views

Given a set of vectors and a target vector, find the set of scaling factors that minimizes distance of sum of those vectors from target

I have a set of $n$ starting vectors $\vec i_n$ and a target vector $\vec t$. I have a set of scaling factors $a_n$ for which I can compute the sum $\vec s$: $$ \vec s = \sum_{i=1}^n {a_i \vec i_i} $$...
0
votes
0answers
20 views

How to calculate a projection matrix for nonnegative constrained least squares?

Suppose we have a data vector $\boldsymbol{z}$ in R^{p} and a training data matrix $\boldsymbol{X}$ in $R^{p \times N}$, where N (N>p) is the number of samples in the training data matrix. If we'd ...
2
votes
2answers
67 views

How do I solve the following equality-constrained quadratic program?

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$ subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$ Is there a closed form ...
0
votes
2answers
16 views

QP with simplex constraints. [closed]

I want to solve something: $\Vert \mathbf{x-Da}\Vert_2^2$ s.t. $\sum \mathbf{a}_i=1$ and $\mathbf{a}_i\geq 0$. How to convert such problems into equivelent Quadratic program so that I can use Matlab'...
0
votes
0answers
16 views

Converting a sum over squared norms to Quadratic Programming problem

I'm trying to minimize the following function which is a function of a set of vectors $\vec{x}_i \in \mathbb{R}^2$, and is parametrized by the fixed parameters $\alpha, \beta,\gamma_i,\vec{u}_i$ where ...
0
votes
1answer
17 views

Geometric interpretation of support vector values in primal space

The Linear Support Vector Machine classification ($y_{k} = -1\ \mathrm{or}\ +1$) with misclassification tolerance loss function in primal weight space looks like this: $$\min\limits_{w,b,\xi} J_{P}(w,...
0
votes
1answer
12 views

SVM / QP result for impossible to satisfy conditions

The theory behind Linear Support Vector Machines with tolerance of misclassifications states that we are trying to minimise in the primal weight space the following function: $$\min\limits_{w,b,\xi} ...
2
votes
1answer
30 views

Solving a quadratic convex optimization problem

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier. $$\begin{array}{ll} \text{minimize} &...
1
vote
1answer
15 views

Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in \mathbb{R}$,...
0
votes
0answers
33 views

Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as \begin{...
0
votes
0answers
21 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
0answers
10 views

Bipartite Matching with quadratic objective

I'm looking for the best way to formulate and solve the following bipartite matching problem: I have n nodes on the left hand side of the diagram, partitioned into ...
0
votes
1answer
43 views

Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
0
votes
0answers
13 views

Matrix inversion vs. iterative scheme in quadratic programming problem for high dimensions

According to this entry about quadratic programming problems with equality constraints the system will not be positive definite any longer for higher dimensions. For lower dimensions this system could ...
2
votes
0answers
26 views

How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
0
votes
0answers
21 views

Finding a suitable solver

I have a problem finding a solver that can solve a mathematical programming model with a quasi quadratic object function. I have tried some commercially available quadratic and non-linear solvers, but ...
0
votes
0answers
19 views

Binding inequality constraints in linear programming with quadratic constraints

I am trying to maximize the following objective function: $a_{1}b_{1}x_{1}+a_{2}b_{2}x_{2}+a_{3}b_{3}x_{3}+a_{4}b_{4}x_{4}$ The quadratic constraint is given by $b_{1}^2 x_{1}^2 + b_{2}^2 x_{2}^2 + ...
0
votes
1answer
67 views

A light solution of a quadratic programming problem

I have a simple and light quadratic programming problem that I need to solve, as following: \begin{align} & \underset{x}{\arg\min} & & \dfrac{1}{2}x^T x-z^T x\\ & \text{subject ...
2
votes
0answers
28 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
6
votes
3answers
79 views

Is a sinc-distance matrix positive semidefinite?

I've been trying to crack this problem for days but I can't find a way around it. Given a set of unique N points $X = {x_1,..x,N}, x_i \in R^3$, the associated sinc-distance matrix $S \in R^{n\times n}...
0
votes
1answer
20 views

Why in quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear

I found in wikipedia that... Quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear font: Quadratic Programming What I can'...
0
votes
1answer
22 views

General form to standard form regarding ellipse?

I've tried 2 hours to do this so I hope someone can help me: $$11400000=-0.64x^2+2560x-y^2+6000y$$ It says that it have to equal an ellipse with center at the point $(2000,3000)$ and a horizontal ...
0
votes
0answers
25 views

Nonlinear Optimization

I have a nonlinear optimization problem, but constraints are ODE. Cost function is $J= x1+x1*x2+x1^2$ while constraints are, $\underline{x_i} < x < \bar{x_i}$ (for i=1,2,3) ; $\frac{dx3}{dt}=...
1
vote
1answer
30 views

Quadratic programing problem and MATLAB

I have a little problem with quadratic programing problem: ${\bf v}^T \Sigma {\bf v} \rightarrow min $, and constrains are $ {\bf v}^T \mu = \mu_*, {\bf v}^T {\bf 1 }= 1, 0 \leq {\bf v}. $ Where ...
0
votes
1answer
58 views

Solve $\min_{\mathbf{x}} \sum_i \min\left[ (\mathbf{c}_i^T\mathbf{x}-a_i)^2, (\mathbf{d}_i^T\mathbf{x}-b_i)^2 \right]$

I am wondering if there is an efficient (perhaps closed form) way to solve the following piecewise quadratic minimisation problem: $$ \min_{\mathbf{x}} \sum_{i=1}^n \min\left[ (\mathbf{c}_i^T\mathbf{x}...
1
vote
1answer
27 views

Minimizing a quadratic function of 2 variables in quadratic region

Let $f$ be a real valued quadratic function of 2 real variables: $$f(x,y) = ax^2 + by^2 + cxy + dx + ey + f$$ How to minimize it? Subject to constraints: $$ 0\leq x \leq 1, \quad 0\leq y \leq 1 $$ ...
0
votes
0answers
39 views

Solution of quadratic optimization with linear constraints

Hi, I want to solve a quadratic optimization problem defined as $\min \|\bf{a^T}\bf{x}\|^2_2$ $s.t. \|\bf{x}\|_1=1$ $\ \ \ \ \ \ \ \ x_i\ge0,\ i=0,1,...,n-1$ $\ \ \ \ \ \ \ \ \bf{b}^T\bf{x}-C\le0$ ...
0
votes
1answer
30 views

Quadratic Equality Constrained Quadratic Program and Convexity

There are a few questions on this topic already. However, none of them really answer my question. The most relevant are these: Quadratic optimisation with quadratic equality constraints Quadratic ...
1
vote
1answer
50 views

Positive-Semi-Definite form of Variance?

first thing: I'm an informatics student and know some algebra. However, this seems to be a bit over my head, so please be gentle with me. ;) I have multiple sets of real variables. Let these sets be $...
0
votes
1answer
22 views

Optimization problem: Find shortest distance between two vectors

$$\min (u-v)^T(u-v)$$ $$s.t. \space Ru=p, \space Sv=q$$ where $u$ and $v$ are in $R^4$ and $R$ and $S$ are $3x4$ matrices. When I expanded the expression I got this: $$u^Tu - 2u^Tv +v^Tv$$ Is this ...
0
votes
1answer
64 views

Math for optimal asset allocation given constraints (linear/quadratic programming?)

Say we have a set of mutual funds, with various characteristics. I'd like to run some maths and give back the ideal mixture of these funds to meet the users constraints, and I'm unsure of whether ...
0
votes
1answer
32 views

Minimizing a quadratic function with constraints on some variables

Consider a problem with strictly convex quadratic objective with some of the unconstrained variables. minimize: $x_1^TP_{11}x_1 + 2x_1^TP_{12}x_2 + x_2^TP_{22}x_2$ subject to: $f_i(x_1) \leq0, i = 1,...
1
vote
1answer
20 views

Convex or Quasiconvex Relaxed Binary Quadratic Optimization Problem

Let's say I have a quadratic problem with nonnegative triangular matrix Q and binary decision variables x. $$min_{x} f(x) = x^\...
0
votes
0answers
43 views

Quadratic optimization: Why does the formula have “$\frac{1}{2}”$ in front?

$$\frac{1}{2}x^THx+c^Tx + c_0$$ I have just formulated a problem as a quadratic optimization problem in two variables. My solution differs from the solution manual in the aspect that they have, only ...
0
votes
0answers
22 views

(Convex) reformulation of a nonlinear program

Consider the following program: \begin{eqnarray*} \min_{\mathrm x}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\big(x_i(Sx)_i-x_j(Sx)_j\big)^2}}\\ \mathrm{subject\; to}\quad \sum_{i=1}^{n}{x_i}=1 \\ x_i\geq 0 \end{...
0
votes
1answer
39 views

Linear programming with quadratic constraints

I have a given set of variables: $x_1,y_1,x_2,y_2,x_3,y_3$ The objective function is to minimize the sum of these with quadratic equality constraints: $y_1(x_1+x_2+x_3)$=0 $y_2(x_2+x_3)$=0 $y_3(...
0
votes
0answers
22 views

Minimize/reformulate sum of products as convex problem

Is it possible to optimize this objective function as such or transform it into an convex formulation? The unknown continuous variables $x_i \in [-1, 1]$ are nodes in a graph and for each edge $(i,j)\...
2
votes
0answers
25 views

Transformation into quadratic program

I am struggling with the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x_{1}, \ ..., \ x_{5} \in \mathrm{R}}{\text{minimize}} & & \begin{pmatrix} x_{1} + ...
0
votes
0answers
13 views

Nonlinear Programming

I have the following non-linear programmig problem that I have arrived at after various manipulations. I have to find the set of values for $x$ and $y$ that satisfy the following: $$ x^{n}+y^{m}=C $$ ...
2
votes
0answers
46 views

Reformulate absolute value as quadratic problem

I'm looking for standard approach to reformulate this objective function. The aim is to find values of $x_i$ that are close to either $y_i$ or $-y_i$ ($y_i$s are known) in a least-squares sense: $...