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

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: $...
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
83 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
41 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
36 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) \\ \text{s....
1
vote
0answers
77 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
64 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
26 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
65 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
71 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 I'...
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$ ...
2
votes
0answers
102 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 B)...
0
votes
0answers
56 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 ...
0
votes
0answers
74 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, \sum_{i=...
0
votes
2answers
46 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
0
votes
0answers
20 views

Existence of lagrange multipliers with polyhedral constraints

I am working with a paper (Exact regularization of polyhedral norms, Schöpfer 2012) which states as a well-known fact that, if $f$ is a polyhedral norm, then for some $\mu^* > 0$ \begin{equation} \...
3
votes
1answer
183 views

binary quadratic optimization problem

I am trying to solve the following binary quadratic program. $$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ...
1
vote
0answers
51 views

Complexity of solving quadratic programming (QP) using ADMM

I am trying to analysis the time complexity of quadratic programming problem, using alternating direction method of multipliers. Anyone could give me a help?
0
votes
0answers
51 views

Approximate inverse (or fast optimization) of non-linear least squares problem

Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define $${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$ where $[.]_+ = ...
0
votes
1answer
101 views

Can a Convex QCQP Problem with an additional linear constraint be converted to a SOCP?

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} &...
2
votes
0answers
24 views

Quadratic programming

For a research project I am interested in minimizing $x^TQx$ under the constraints $Qx \le b$, where $Q$ is a positive definite matrix and $b$ is a vector of negative elements. I have solved this ...
1
vote
1answer
32 views

quadratic programming problem with positive constrains

Is there a non-iterative solution to the following quadratic programming problem with constrains? Is there any problem to think the variable as some square of another variable to get ride of the ...
0
votes
0answers
66 views

How to obtain the optimal Lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found?

I am using a black-box solver to solve the following non-convex QCQP to global optimality. $$ \min_x x^TQ_0x + c^T x \\ s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\ Ax=b \\ l\leq x\leq u $$ where $Q_0$ is ...
1
vote
0answers
78 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
1
vote
1answer
133 views

SDP relaxation of a non-convex quadratically constrained quadratic program.

I am very new to SDP and SDP solvers. I have a semi definite program of the following form $$\min_{x,X}\ Q\bullet X+c^Tx$$ $$\text{s.t. } Q^k \bullet X + (c^k)^T x =b^k , \ k=1,2, \dots,m \\ \quad ...
0
votes
1answer
45 views

minimising quadratic function subject to integer solutions

I would appreciate if one could help me to solve this problem. I have a bivariate quadratic function: $$ f(a_1,a_2)=(1-u_1^2)a_1^2 +(1-u_2^2)a_2^2 -2u_1u_2a_1a_2 $$ where $u_1^2+u_2^2=1$ and $a_1$ ...
2
votes
0answers
165 views

Lagrange multiplier expression

I would like to solve the following optimization problem using the gradient ascend method: \begin{array}{ll} \text{maximize}_{\theta} & \theta^TQ_1\theta + b_1\\ \text{subject to} & \theta^...
1
vote
1answer
154 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
0
votes
2answers
207 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
0
votes
1answer
84 views

How to determine the optimal step size in a quadratic function optimization

I have the following optimization problem: $$\underset{\alpha\in\mathbb{R}}{\text{min}}:\;\;f(\textbf{x}+\alpha\textbf{d})$$ $$\text{subject to}:\;\;0\leq\alpha\leq \alpha_{max},$$ where $f(\...
1
vote
1answer
289 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
1
vote
1answer
56 views

Quadratic programming with constrained number of free variables

I started with a (positive-definite) quadratic programming problem subject only to a single equality constraint. i.e. $$ f(x)=x^{T}Qx+c^{T}x $$ $$ s.t. x_1+x_2+x_3+...+x_n=y $$ I now have to find ...
0
votes
0answers
38 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
0
votes
1answer
72 views

SVM and quadratic programming

I wonder if the SVM optimization problem minimize $||w||^2$ with the contraints $y_i(w^\intercal x_i+b)\ge 1$ could be formulated as a typical quadratic programming problem: $0.5\cdot z^\intercal Mz$...
2
votes
0answers
48 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
0
votes
1answer
185 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
1
vote
0answers
117 views

Why use two slack variables in the support vector regression formulation?

I am learning support vector regression but cannot fully understand the rational of the slack variable tricks in its formulation. The original optimization problem for SVR is as follows: $\mathrm{...
1
vote
2answers
471 views

Using Lagrange multipliers to find the shortest distance between two straight lines

A problem asks me to use the method of Lagrange multipliers to find the shortest distance between the straight lines $x=y = z$ and $x = -y, z=2$ (It also warns me that using this method is a bit ...
1
vote
4answers
88 views

Optimization of a quadratic function with qudratic constraints

I'm a Graduate student of Electrical Engineering. I have some basic knowledge on Convex Optimization. For my research, I cam across the following optimization program. With $\mu > 0$, find $\arg \...
0
votes
0answers
33 views

Portfolio Optimization Problem: Variance Co-variance matrix

I have a set of daily returns and using these daily returns I calculated the average annual return for each asset and also by using the daily returns I calculated the var-cov matrix. To get optimize ...
0
votes
0answers
52 views

Finding a solution on Matlab for a quadratic programming-type problem with more restrictions

I have some existence results using one modified version of the Farkas Lemma for which I need to solve the following problem. This problem has its application on economics but I will refer here merely ...
1
vote
1answer
64 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
0
votes
1answer
124 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
1
vote
0answers
55 views

Two quadratic programming problems always same answer?

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Is there an intuitive proof? Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T Q\...
1
vote
1answer
137 views

How do you calculate the coordinates a quadratic curve follows?

I'm a programmer, and terrible at maths. Usually, I try Google or my math-addict co-worker for problems like this, but Google searches show nothing and my co-worker is on vacation for a few weeks. I ...
4
votes
0answers
80 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $\min_{x} (x'Ax)$ subject to $x'Bx = x'Cx = 1$. Where A is symmetric and B and C are diagonal. Does anyone have a suggestion for an ...
1
vote
0answers
60 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...