Questions tagged [quadratic-programming]

A quadratic program (QP) is an optimization problem in which the objective function is quadratic and the feasible region is a convex polytope.

Filter by
Sorted by
Tagged with
1
vote
1answer
107 views

Does the Perron vector maximize $x^TAx$ in the simplex?

Let $\mathbf{A}$ be any $n\times n$ symmetric positive matrix ($A_{ij}>0$). It is easy to show that the solution to the following optimization problem \begin{align} \max_{\mathbf{x}}~~\mathbf{x^...
5
votes
2answers
108 views

Symmetric linear least-squares solution

Given tall matrices $A$ and $Y$ and the following overdetermined linear system in square matrix $X$ $$AX=Y$$ is there an explicit formula for the least-squares solution if $X$ is constrained to be ...
0
votes
1answer
83 views

KKT conditions for min-cost flow QP [closed]

I'm working on a convex quadratic separable min-cost flow problem with the following structure: $P = \{\min \frac{1}{2}x^tQx + qx : Ex = b, 0 \leq x \leq u\}$ But I'm stuck on deriving the KKT ...
1
vote
0answers
56 views

Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
1
vote
0answers
72 views

Finding a point on a convex set

Given a compact bounded convex set $\mathcal C\subseteq\mathbb R^n$ given by $t$ hyperplane inequalities I want to find a point $u\in\mathcal C$ such that for all $v\in\mathcal C$ a convex relation $...
0
votes
0answers
41 views

When does nuclear norm mininimization give rank $1$ solution when we have at most one solution?

We have a quadratic system of equations $$A(X\otimes Y)=b$$ where $A\in\mathbb Z^{m\times n^2}$ and $b\in\mathbb Z^m$ are known and $X,Y\in\mathbb Z^{n}$ are unknown. $A$ and $b$ have at most $b$ bit ...
0
votes
0answers
70 views

Does positivstellensatz and SOS proof system help here?

I have a system of $m$ homogeneous degree $2$ polynomial equations in $\mathbb Z[x_1,\dots,x_n]$ where $m=poly(n)$. Take $$f_1(x_1,\dots,x_n)=0$$ $$\dots$$ $$f_m(x_1,\dots,x_n)=0$$ to be the system. ...
1
vote
0answers
16 views

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

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
121 views

A “nice” (but non-definite) quadratic programme

For integers $n\geq k>0$, let $f$ be the following quadratic form: $$f(x_1,\ldots,x_n)=\sum_{i=1}^n\sum_{j=0}^{k-1}x_ix_{i+j\bmod n}.$$ Is it true that the minimum of $f$ over the unit simplex is ...
0
votes
0answers
46 views

Convex Relaxation in Affine Subspace

I was reading an article about solving a correspondence problem. There, the original non-convex problem is formulated like that: $$ min_X E(x) = x^t W x \\ s.t. \ X \in \Pi_n $$ Where $\Pi_n$ is a ...
2
votes
2answers
90 views

Correlation between the first and a random position of an ergodic bit sequence

Edit: Since the geometric approach did not work, I try now another approach: phrasing the problem as a quadratic programme. Probabilistic version. Let $x=(x_1,x_2, \ldots) $ be an ergodic random ...
2
votes
1answer
53 views

Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
2
votes
1answer
123 views

Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently? $$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
1
vote
1answer
197 views

Maximizing quadratic form subject to inequality constraints [closed]

Given a $n \times n$ symmetric matrix $\rm S$, solve the optimization problem in $n \times k$ (where $n \geq k$) matrix $\rm X$ $$\begin{array}{ll} \text{maximize} & \mbox{tr} \left( \mathrm X^\...
3
votes
0answers
183 views

Solve Huber's M-Estimation using quadratic programming

The Huber's M-estimate is to solve the problem $$\underset{\mathbf x}{\rm{minimize}} \rho(\mathbf b-\mathbf A\mathbf x) + \alpha|\mathbf x|$$ where $$ \rho(t) = \left\{\begin{array}{c}\frac{t^2}{2\...
1
vote
1answer
77 views

Norm of solution of quadratic program

In a quadratic program (QP), do linear equality constraints always reduce the norm of the minimizer? Specifically, let $P \succ 0$, $A \in \mathsf{M}_{m\times n}$ and $q\in\mathbb{R}^n$. Define $$x^* ...
4
votes
1answer
200 views

Least square solution to $AXB+CXD=E$

I am trying to find the least-squares solution $X$ of the following matrix equation $$AXB+CXD=E$$ Of course, I know that this equation can be written in the form $$(B^T \otimes A+D^T \otimes C) \...
2
votes
0answers
81 views

Are there scenarios under which feasibility bilinear programming is easy?

Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
1
vote
0answers
78 views

On convex quadratic programming clarification

We know convex quadratic programming is in $P$. Is it also in $P$ if the function of interest is only convex in the domain of interest?
3
votes
1answer
457 views

Is this result on an unconstrained inverse quadratic programming problem new or known already?

Is this problem and solution actually new, or has someone done this earlier? The details can be found in the preprint: arxiv:1701.01477. Let us consider a direct quadratic programming problem: $$ \...
5
votes
2answers
369 views

Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$

Look at the expression $$ f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1. $$ The numbers $x_1,x_2,x_3$ are non-negative, and I assume that $x_1+x_2+x_3=3$. This is a sum of squares and "...
2
votes
0answers
123 views

Optimization of quadratic form with band matrices

Let $A_1$ be the $N \times N$-matrix for which $a_{i,j} = 1$ for $i=j$ and 0 otherwise. Let $A_2$ be the matrix for which $a_{i,j}=1$ for $|i-j| \leq 1$ and 0 otherwise. Similarly define $A_3$ (which ...
3
votes
1answer
94 views

Convex Decomposition of matrix

For a matrix $\mathbf{X} \in \mathbb{R}^{n\times l}$, we have the following problem of representing vectors in $\mathbf{X}$ as a convex combination of other vectors excluding the vector itself: $\min\...
1
vote
1answer
144 views

Least squares problem with constrained solution [closed]

If $a_{m\times 1}$ and $Q_{m\times n}$ ($m<n $) are known, and we know every element of $b$ is between $[-1\ \ 1]$, how to determine $b$ to minimize $\|a+Qb\|_2$?
2
votes
3answers
565 views

Quadratic Programming With Piecewise Linear Term

The problem I have can be defined as: $$ \min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x} $$ s.t. linear equality constraints: $$ \mathbf{Ax=b} $$ and linear inequality ...
1
vote
1answer
150 views

Quadratically constrained quadratic programming/optimization involving piece-wise function

I have a quadratically constrained quadratic programming/optimization problem involving kind-of piece-wise quadratic functions $f_n (x_m)=a_{n,m} (x_m-\theta_n)^2$, if $|x_m-\theta_n|<c$; $c^2a_{n....
1
vote
0answers
40 views

Which algorithm is most efficient for a specific QP problem

I have a QP problem of the following kind: $\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$ s.t. $l\leq \alpha \leq u$ The matrix $M$ is symmetric and positive definite and of ...
1
vote
0answers
99 views

Hessian matrix positive definiteness (concavity test) [closed]

I have a rather simple scenario based optimization problem: Maximize $$ Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c $$ subject to $Q_1{...
2
votes
1answer
141 views

A graph assignment problem

Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $...
2
votes
0answers
95 views

A (non-convex) minimization quadratic programming problem with d constraints

Minimize $0<\omega_{dd}<2$ subject to $$\sum_{j=1}^{d}(\omega_{dj} - \omega_{ij})^{2} \geq 4, i=0,1,...,d-1,$$ where $-2<\omega_{ij}<2$ is known for $0 \leq i \leq d-1$ and $1 \leq j \leq ...
1
vote
0answers
112 views

Optimization question: maximize quadratic objective with semidefinite constraints

I recently encountered the following optimization problem: $\max \|AX\|_F^2$ subject to: $X\succeq0$ and $Xb_i\leq c_i$ for a collection of $T$ conditions: $i=1,\ldots,T$. Matrices $A$ and $X$ are ...
1
vote
0answers
73 views

Frobenius nearest non-negative Gram matrix of balanced row-sums

Let $W \in \mathbb{R}^{n \times n}$ be any non-negative real symmetric matrix. For $k \leq n$, let $\mathcal{F} := \{X \in \mathbb{R}^{n \times k} \ | \ X \geq 0, X \mathbf{1} = \alpha \mathbf{1}, \...
2
votes
0answers
139 views

How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
4
votes
0answers
157 views

Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$ Subject to $ A \mathbf{...
3
votes
0answers
447 views

Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. \...
0
votes
2answers
112 views

Inner Product of Given Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in A,\,\sup\...
3
votes
1answer
542 views

General method for under and over determined systems?

Suppose I have a system: $$ Ax = b $$ where $A$ is a $m$ by $n$ matrix which is less than full rank (neither full column nor row rank). In my particular case $m<n$. I'd like a combination of a ...
4
votes
0answers
218 views

Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: \begin{equation} A = \left[\begin{array}{c|c} \...
4
votes
2answers
187 views

combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
1
vote
1answer
821 views

Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]

I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form: [ C C ] [ C C ] However, the quadratic solver ...
31
votes
4answers
3k views

Why are optimization problems often called “programs”?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...