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

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) ; ...
1
vote
1answer
25 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
47 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
26 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
36 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
17 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
48 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
62 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
28 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
15 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
0answers
42 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
19 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
27 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
18 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 ...
1
vote
0answers
19 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
9 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
44 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
28 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
42 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
32 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
34 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
69 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
46 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
24 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 ...
1
vote
1answer
52 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 ...
0
votes
0answers
31 views

Can variance be replaced by absolute value in this objective function?

Initially I modeled my objective function as follows: argmin var(f(x),g(x))+var(c(x),d(x)) where f,g,c,d are linear functions in order to be able to use mixed integer linear solvers, I modeled the ...
1
vote
0answers
34 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$?
0
votes
0answers
39 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
28 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
63 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
33 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
70 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
2answers
41 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} ...
2
votes
1answer
102 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 ...
0
votes
0answers
39 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
45 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
59 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
21 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
28 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
51 views

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

I am using a blackbox solver to solve the following nonconvex 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
68 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 ...
0
votes
1answer
96 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
0answers
49 views

When is a quadratically constrained quadratic program (indefinite objective matrix) unbounded?

I have a nonconvex QCQP of the form $$x^TQ_0x + c^T x$$ such that $x^TQ_1x+c_1^Tx=b_1$, $Ax=b$, and $l\leq x\leq m$ where $Q_0$ is indefinite diagonal matrix and $Q_1$ is positive semidefinite ...
0
votes
1answer
39 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$ ...
0
votes
0answers
20 views

How to deal with a barrier function when constrained variables reach their bounds?

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
0answers
163 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} & ...
0
votes
0answers
172 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
1
vote
1answer
115 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 ...