# Tagged Questions

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.

79 views

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 ...
192 views

### How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$f(x) = x^TQx + c^Tx$$ with constrains $$Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
29 views

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 ...
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, ...
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 ...
25 views

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} + ...
46 views

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: $... 0answers 97 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)... 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 ... 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^... 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 ... 0answers 41 views ### Effective convexity criterion for the finite point set in$\mathbb{R}^3$I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let$M = \{A_{1}, \ldots, A_{n}\}$be the ... 0answers 77 views ### Least squares with three quadratic constraints (Ellipse fitting based on algebraic distance) I would like to fit an ellipse to a given set of scattered data in$\mathcal{R}^2$. The fitting problem is in form least squares, minimizing the sum of squared algebraic distances \... 0answers 44 views ### Reproducing Kernel Function Interpolation My problem is as follows: I am attempting to use a reproducing kernel and quadratic programming to optimize/interpolate a smooth function from constraints. I am using all local extrema to calculate ... 0answers 149 views ### Constrained Quadratic Optimization(Reproducing Kernel) I am attempting to use a constrained quadratic optimization to find the coefficients of a reproducing kernel. The problem is as follows:$y(t)=\sum_{i=0}^J\alpha_iK(t, t_i)Q(\alpha)= \alpha^tK\...
58 views

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 ...
178 views

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 $... 0answers 38 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$Bare positive ... 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.... 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 ||... 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? 0answers 70 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'... 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? 0answers 77 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 ... 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{... 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\... 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 ... 0answers 113 views ### Modeling a lower-bound constraint on a euclidean distance in quadratic programming I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either ... 0answers 16 views ### Optimizing a set of rules to better predict the outcome of events I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ... 0answers 42 views ### Reduce degree of a high degree unconstrained binary term to quadratic unconstrained binary term I'm working on a optimization project, in this project I have to convert higher order unconstrained binary polynomial to quadratic unconstrained binary polynomial. Can anyone give me a hint of how to ... 0answers 59 views ### Existence criterion for solution in quadratic programming I have the problem$$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}with D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}, A,Q\in \mathbb{R}^{n\times n} and b,c \in \... 0answers 192 views ### Determining initial values for optimization problem I am trying to solve an optimization problem with a quadratic objective function and non-linear constraints, using SQP (Sequential Quadratic Programming). I am attempting at doing the implementation ... 0answers 47 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 ... 0answers 22 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} ... 0answers 76 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 ... 0answers 166 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}\} \\\ subject~to~&\mathbb{x}^Hx\... 0answers 221 views ### Quadratic programming with simplex constraints I have this quadratic function x'Ax which is not convex. I want to maximize this function subject to the constraints that the solution x lies in a simplex such that \sum_{i=1}^{n}x_i=1. That means ... 0answers 139 views ### Algorithm and solver for large, dense, positive-semidefinite integer QP I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n \... 0answers 36 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 ... 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} &... 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$$ whereW,C\in\mathbb{R}^{...
10 views

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 ...
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 ...
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 ...
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{...
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 ...
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 ...
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 ...
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 + ...