Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quadratic-programming]

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

0
votes
0answers
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?
0
votes
1answer
33 views

Solving weighted least squares with non-negative constraints

I have the optimization problem $$ \begin{align} \min_{\mathbf{P} \geq 0} \|\mathbf{A\odot(X-PQ^\top)}\|^2 + \frac{\|\mathbf{P}\|^2}{2} \end{align} $$ $\odot$ is the Hadamard product, $\mathbf{A,X,P,...
1
vote
2answers
57 views

Explanation of a convex quadratic program

I want to find the minimum of the following optimization problem but don't even understand the problem in the first place. $$\min\limits_{AX=b}\frac{1}{2}X^{T}QX+C^TX+\alpha$$ where $Q, A \in M_{n \...
0
votes
0answers
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 ...
1
vote
1answer
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. ...
0
votes
0answers
34 views

Minimum of sum of six squares over a polytope

$$\begin{array}{ll} \text{minimize} & x_1^2 + x_2^2 + \cdots + x_6^2\\ \text{subject to} & x_1 + x_2 + \cdots + x_6 = K\\ & x_1 + x_2 \ge k_1\\ & x_1 + x_2 + x_3 + x_4 \ge k_2\\ & ...
2
votes
0answers
42 views

Minimum of $\langle Ax,x \rangle - 2 \langle b,x \rangle$.

In exercise 5 of section 0 of Fundamentals of convex analysis by Hiriart-Urrut, Lemaréchal, we're supposed to prove that if a self-adjoint linear operator $A:\mathbb{R}^n \rightarrow \mathbb{R}^n$ is ...
0
votes
0answers
56 views

How to solve this constrained maximization problem?

Does anyone have an idea of how to tackle the following maximization problem? Maximize the function $ f(x,y,z) = x - y - \alpha z^2 $, $ \alpha > 0 $, under the following constraints: C1:...
0
votes
1answer
22 views

Total Unimodularity in Integer QP

I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the ...
0
votes
0answers
12 views

Quadratic programming terms

Help me to understand the terms of this quadratic programming problem? $Z$ and $U$, $x$ and $α$ are fixed. We have to minimize $w$. I would like to put it into terms of cvxopt to solve it.
0
votes
0answers
38 views

Are step sizes in quadratic programming solvers analytically exact?

In this paper (DOI link), Goldfarb and Idnani describe an algorithm for solving a certain subset of quadratic programs. This algorithm (or a very similar one) is implemented in the quadprogpp package ...
0
votes
0answers
29 views

Quadratic programming: Approximate Solution

Let $A$ be a $p \times p$, positive definite and symmetric matrix and $t \in \mathbb{R}^p$, such that $t_i>0$ for at least one $i \in \{1,\dots,p\}$. Let $x^*$ be the unique minimizer of $$min \{x'...
0
votes
2answers
14 views

Does this special case of convex quadratic programming have a partially-unique solution?

I know that a strictly convex quadratic programming problem has a unique solution, but I'm curious about the following situation: If $Q$ is positive definite, does the following problem: $$\min\...
0
votes
0answers
13 views

How Sequential Quadratic Programming versus Quadratic programming and Iterative QP are related?

What is the difference between Sequential Quadratic Programming (SQP) versus Quadratic Programming (QP)? Is it the same as Iterative Quadratic Programming (IQP)? For example, BFGS, DFP are types of QP/...
0
votes
1answer
28 views

Methods for solving nonlinear constraints quadratic programming

Are there any other methods to solve nonlinear constraints quadratic programming? I have known that some effective numerical methods, i.e, SQP and Gauss pseudospectral method and some heuristic ...
1
vote
1answer
27 views

quadratic programming /symmetric matrix

I have a quadratic program with $ F: \mathbb{R^n} \rightarrow \mathbb{R}, F(x)=x^TQx$ I want to find a symmetric matrix M for Q, such that $F(x)=x^TMx$ holds for all x. I can write Q as sum of ...
0
votes
2answers
86 views

Determining the coefficients of $y = a x^2 + b x + c$ so that the graph contains three given points

Determine coefficients of the equation for a second order polynomial in the format: $y = a x^2 + b x + c$ Here are the $x$-$y$ coordinates of three points: $(0.8143,0.3500)$ $(0.2435,0.1966)$ $(0....
0
votes
1answer
51 views

Unconstrained convex quadratic integer programing

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I have a minimization problem of the form $$ \min_{n\in N} \sum_i A_i n_i +\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2 $$ ...
0
votes
1answer
44 views

Approximate function by stacking building blocks

I need some help with a 'generalised Lego problem': Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
0
votes
1answer
38 views

Linearly constrained quadratic program

I have the following quadratic program $$\min_x x^TAx \qquad \text{s.t} \quad Ax \in [a,b]^m$$ where matrix $A$ is positive semidefinite, and is similar both the objective function and in the ...
0
votes
0answers
20 views

Is there a time polynomial algorithm to solve a box-constrained quadratic convex program?

I am working on the following quadratic convex problem $min_{x}x^{T}Qx+f^{T}x$ subject to $a\leq x\leq b$ where $x,a,b,f\in\mathbb{R}^{n}$ and $Q$ is positive definite. Is there any algorithm that ...
0
votes
1answer
49 views

Measuring infeasibility in convex optimization, relations with dual problem

A question regarding convex optimization and (maybe) duality. I have a problem in the form \begin{align} x^* = \mathrm{arg} \min_x f(x) \quad \text{s.t.} \quad A x \leq b, C x = d, \end{align} where $...
1
vote
0answers
43 views

Derive LCP from KKT conditions of a QP

I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program $$ \begin{aligned} \min \quad& \frac{1}{2}u^TQu - c^Tu\\ \text{...
0
votes
1answer
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. ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
2answers
229 views

How to minimize $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \Vert = 1$?

Given $n\times 3$ matrix $A$ and unit vector $\hat{b}\in R^3$, is there a closed-form solution for $x\in R^3$ that minimizes the Euclidean norm $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \...
0
votes
0answers
11 views

Two dimensional sorting: finding $\max_\sigma \langle M^\sigma,C\rangle$ for permutation function $\sigma$

Suppose that we have a non-negative matrices $C,M\in \mathbb{R}^{m\times m}_{\ge0}$. Also suppose $\sigma:[m] \rightarrow [m]$ is a permutation of $\{1,2,...,m\}$. We want to find the permutation that ...
0
votes
0answers
77 views

Large scale mixed integer (quadratic) programming

Here we have this optimization problem: Given positive semi-definite matrix $A \in \mathbb{R}^{n \times n }$, and matrix $B \in \mathbb{R}^{n \times m} \text{ and vectors } d \in \mathbb{R}^n,e \in ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
30 views

different block size in Block Matrix

I am following a book and having trouble understanding. so from Section 6.6.2 page 496, i have A = NxN matrix b = Nx1 vector c = Nx1 vector from Section 14.3.2 ...
1
vote
1answer
31 views

How to Reformulate an Image Constraint in the Dual of a Quadratic Program with Nonconvex Constraints?

I have the following nonconvex optimization problem, for which I want to formulate the dual: $\mathcal{P}:\underset{x}{\text{min}} \quad x^\top A x + b^\top x \\ \quad \ \ \text{s.t.} \quad x\in\{0,1\...
2
votes
0answers
33 views

On approximation of maximization of quadratic function over a convex set

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$. Let $L = \left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1 \right\rbrace$ be it's sub-level set and suppose that $L$ is not empty as well as ...
0
votes
0answers
44 views

If the relative value of the most negative eigenvalue is small, can we view the quadratic program as convex?

Consider symmetric matrix $A \in \mathbb{R}^{n \times n}$ with $n-1$ negative eigenvalues and a positive one such that $\lambda_1 > \lambda_2> \dots > \lambda_n$, where $\lambda_n$ is the ...
0
votes
0answers
32 views

Quadratic Matrix programming

I would like to find a numerical solution to the following quadratic matrix programming problem. Square matrix A has thousands of rows, so I need a algorithm which works fast. I looked into Python but ...
1
vote
1answer
144 views

What is the fastest algorithm to solve an equality-constrained convex quadratic program?

I am trying to solve the following convex problem $$\begin{array}{ll} \text{minimize} & x^T Q x + px\\ \text{subject to} & Ax + b = 0\end{array}$$ which arises in the active set method for ...
2
votes
1answer
141 views

Is the optimal solution of a convex problem continuous with respect to parameters?

Given the convex problem $$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i=1}^{N} f(x_i)\\ \text{subject to} & Ax = B\\ & 0\leq x_{\min} \leq x_i \leq x_{\max}\end{array}$$ ...
0
votes
0answers
49 views

Support Vector Machines: question about the underlying math

I'm new to Support Vector Machines and I've been trying to get into the underlying math (instead of just using Scikit Learn or something like that). I understand the math behind it up to the point ...
1
vote
1answer
84 views

Solving inequality-constrained least-norm problem non-iteratively

I am looking into the following constrained quadratic program in $x \in \mathcal{R}^4$ $$\begin{array}{ll} \text{minimize} & \| x \|_2^2\\ \text{subject to} & A x = b\\ & x_{\min} \le x_i ...