# Questions tagged [quadratic-programming]

Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.

408 questions
34 views

### Why is positive definiteness required for a global minimum to exist?

When we optimize $$\min x'Ax$$ why does matrix $A$ need to be positive definite in order to have a global minimum?
33 views

27 views

### Why would sequential quadratic programming fail to find global minimum?

I have a data set. A matrix $X$, $1300 \times 20$ and output vector $\mathbf{y} \in \Bbb R^{20}$ $$\mathbf{y} = \begin{bmatrix} 100\\100\\\vdots\\100\end{bmatrix}$$ I am trying to run OLS on this ...
49 views

### Best approximation of an arbitrary matrix by a distance matrix

A distance matrix $D$ is a $n\times n$ matrix obtained by computing the pair-wise distances $D_{ij} = \text{dist}(x_i, x_j)$ between a collection of points $\{x_1,\ldots, x_n\}$ in some metric space. ...
34 views

14 views

54 views

### Is there only one unique minimizer for this scalar complex quadratic form?

Consider $c,b \in \mathbb{C}$ and $f: \mathbb{C} \mapsto \mathbb{R}$, $$f(c) = bc' + b'c + cc'$$ is there only one extrema of $f$ corresponds to $$c^* = -b$$? where, $'$ means complex conjugate. ...
55 views

### Local optimality of non-convex quadratic minimization with linear constraints

We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave. Also, there ...
41 views

### Quadratic program reformulation maximum to minimum

I am newbie in optimization problem, I have the following optimization problem: $$\max \quad \frac{1}{2}x^THx - q^THx$$ $$\text{s.t.} \;\;l\leq x \leq u$$ where $H, q$ are known constants, and H is ...
52 views

### Quadratic optimization problem with quadratic constraint

Given $A = A^T \in \mathbb{R}^{n \times n}, X = \begin{bmatrix}x & \eta\end{bmatrix} \text{with} \ x, \eta \in \mathbb{R}^n$ and $||x|| = ||\eta|| = 1$ (vectors in $\mathbb{R}^n$ are treated as ...
52 views

### Karmarkar's canonical form for convex quadratic programs??

I'm working through this paper A Simple Polynomial-Time Algorithm for Convex Quadratic Programming which gives an interior point algorithm for convex quadratic programming. I've reached the end of the ...
21 views

### confusion in proof of lemma for LCP

I'm looking at the proof of lemma 2 on page 6 of https://cowles.yale.edu/sites/default/files/files/pub/d05/d0549.pdf Which claims that the LCP $$Mx+q \geq 0 \\ x \geq 0 \\ x^{T}(Mx+q) = 0$$ has a ...
56 views

### minimum of $\frac{1}{2}x^tQx-c^tx$ subject to $Ax=b$ is local $\iff$ is global

$$\min \frac{1}{2}x^tQx-c^tx\\ Ax=b$$ where $Q\in \mathbb{R}^{n\times n}$ is symmetric, $c\in \mathbb{R}^n$, $A\in \mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$. Prove that if ${x}^*$ is a local ...
229 views

153 views

### Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
21 views

### How to find uppper bound for the hyper parameters in linear model?

I have loss function of the following form: $$argmin_w= ||Y-w^TX||_2^2 + \lambda||w||_1 + \gamma \sum_{g=1}^G||w_g||_1$$ where $w_g$ is group of coefficents. Given $Y$ and $X$, I would like to find ...
74 views

### Minimise $||Ax - b||_2$ given $x \geq 0$ and $\textbf{1}^Tx = 1$

$$\min_x ||Ax - b||_2\; \;\text{given }x \geq 0\;\;\text{and}\;\;\textbf{1}^Tx = 1$$ I am trying to do the above optimization, I was using common Quadratic programming libraries but their speed is ...
56 views

### Silly Quadratic programming

Suppose that I want to minimize the function $x^2$ subject to the contraint $$ax\leq b,$$ for some $b> 0$. I solved the problem if the contraint is an equality but I'm not sure how to go about ...
34 views

### binary quadratic mixed integer nonlinear programming to inequalities

I have this unconstrained z=x.y where x,y are 0-1 integers. How to reformulate that into set of mixed integer linear inequalities with exactly the same feasible region?
76 views

### Non-positive-definite quadratic program minimum simplification

I was finding the minimum of a simple quadratic program with equality constraints: $$m = \min_x x^TQx\qquad\mathrm{s.t.}\quad Ax=b.$$ Using a formulation with Lagrange multipliers from Wikipedia I ...
29 views

### Constraint breaking in constrained least squares

In a constrained least squares problem $\boldsymbol{y} = \boldsymbol{X}\boldsymbol{\beta},\ \boldsymbol{\beta} = \{\beta_1, \ldots, \beta_n\}$ solved with quadratic programming, suppose that I have ...
187 views

### How to map quadratic programming formulation to dual soft margin SVM

I am trying to use quadratic programming for SVM and I am confused about how to map SVM formulation to quadratic programming formulation given in CVXOPT (Python package). This is what CVXOPT gives us ...