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
12 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} ...
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
29 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
14 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 ...
0
votes
0answers
31 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 ...
0
votes
0answers
19 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
8 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
35 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
25 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
18 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
66 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 ...
5
votes
2answers
66 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 ...
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 ...
1
vote
2answers
4k 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
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 ...
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 ...
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
0answers
23 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) ; ...
0
votes
1answer
57 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[ ...
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
38 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
28 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
21 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
17 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) = ...
0
votes
1answer
31 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 = ...
0
votes
1answer
63 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
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
21 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 ...
0
votes
1answer
35 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 ...
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 ...
2
votes
0answers
23 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
12 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: ...
0
votes
1answer
29 views

Beyond quadratic in binary integer programming

If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. ...
0
votes
2answers
72 views

Converting standard constrained optimization problem into an unconstrained one

This question strikes me as if it must be a theorem or something, but I cannot find a good result. I was fiddling with Lagrange multipliers and their use when it comes to converting constrained ...
0
votes
2answers
40 views

Showing if $H$ is positive semi-definite there are either no minimizers or infinitely many

Suppose I have some $f(x) = g^{T}x + \frac{1}{2}x^{T}Hx$ where $g \in \mathbb{R}^{n}$ and $H$ is symmetric, positive semi-definite. This is the standard form for a quadratic minimization function. ...
1
vote
0answers
35 views

How to prove that this is a Quadratic Optimization Problem?

Show that the following problem is a Quadratic Optimization Problem. $$ \begin{array}{ll} \max & \sum\limits_{i=1}^n \left( \mu_i(z_i + x_i) - a_i \lvert x_i \rvert - b_i x_i^2 \right) \\ ...
1
vote
0answers
74 views

Linear reformulation or approximation of a quadratic inequality set

Based on the useful comments I reformulated my problem - hopefully it's more clear now. Let $A,B \in \mathbb{R}^{d \times d}$ be symmetric positive-semidefinite matrices, $x \in \mathbb{R}^d$ and ...
0
votes
0answers
53 views

Quadratic programming over nonnegative orthant?

I'm trying to solve a quadratic optimization over nonnegative orthant as below. \begin{equation} \begin{aligned} \mbox{maximize} \quad & -\frac{1}{2} \lambda^{T} [\frac{\Sigma_{i}}{\alpha_{i}} + ...
0
votes
0answers
25 views

convex symmetric quadratic programming

Good morning, I have trouble understanding the concept of self-duality in quadratic programming. I am reading a paper right now where we first show that the dual of a convex symmetric quadratic ...
2
votes
1answer
62 views

Maximize sum of N variables squared subject to constraint

I have the following problem. Maximize ${\sum_{x=0}^N \beta_{1,x}v_x + \beta_{2,x}v_x^2}$ subject to $\sum_{x=0}^N v_x = X$ wrt $v_x$. I am thinking about both Lagrange multipliers and quadratic ...
1
vote
0answers
36 views

Projection onto the positive subset of a hyperplane

I am wondering if there is a closed form solution for the projection of a point $x_0$ onto the subset of a hyperplane $Ax=b$ in the positive orthnat, that is $x\geq0$?
1
vote
0answers
58 views

Quadratic Programming “big M” method

How does the optimization problem $$\min_{x,\eta} \frac{1}{2} x^TGx+x^Tc+M\eta$$ $$ s.t. Ax+\eta-b \geq0$$ $$\eta\geq0$$ look in standard form? What would the KKT look like? The problem is, that ...
0
votes
0answers
32 views

Quadratic optimization problem with quadratic equality constraint

I am trying to solve the following optimization problem: $$ \min_{x \in \mathbf{R}^2} \, x^T A x + b^Tx \quad \text{subject to $x^T J x = 1$} $$ where $A$ is a positive semi-definite $2 \times 2$ ...
1
vote
0answers
84 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
0
votes
0answers
73 views

Computational complexity of the following quadratic program (QP)

Let $A^TA$ be a $n \times n$ matrix. I have the following quadratic program to solve: \begin{array}{rl} \min \limits_{x} & x^T A^T A x \\ \mbox{subject to} & \sum_{i=1}^{r} x_i =1, ...
0
votes
0answers
49 views

How to do linear quadratic dynamic programming with non homogeneous quadratic equation

I am not well versed on matrix algebra and linear quadratic programming. I am wondering if it is possible to make a non-homogeneous equation into a homogeneous one. I need to make the following ...