Questions tagged [qcqp]

A quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic.

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

Find solution of optimisation problem $\min_{x} \; x^TAx$ with constraint $\Vert x \Vert^2 \leq 1$

I have to find the solution of the following problem : $A \in R^{n\times n}$ is a symetric positive define matrix $$ \begin{cases} \min_{x} & x^TAx \newline s.c & \Vert x \Vert^2 \leq 1 \end{...
Ippotis TheKing's user avatar
1 vote
2 answers
97 views

Proof regarding center of an optimal Euclidean ball containing distinct points

Suppose we are given $k$ distinct points $a_i \in \mathbb{R}^n$ for $i = 1, 2, \dots, k$, and our objective is to determine the Euclidean ball with the smallest radius that contains all these points ($...
hunterlineage's user avatar
1 vote
0 answers
39 views

Dual of quadratically-constrained quadratic program (QCQP) with second order cone constraints

How to derive the dual of a quadratically-constrained quadratic program (QCQP) with second order cone constraint? Here is the optimization problem I want to handle: $$ \begin{array}{rl}\min_{\mathbf{x}...
Kaiming Zhang's user avatar
0 votes
0 answers
20 views

How to derive the dual for Parabolic Relaxation for QCQPs

I'm reading this paper (EQ 11/15/16) on a way to relax QCQPs. They state the dual of their program, but I can't quite figure out how they got there. We're minimizing over variables: $X$ (PSD $n\times ...
Blake's user avatar
  • 66
0 votes
0 answers
21 views

Quadratic Constrained Optimization: why do I get different optimality conditions after I make a change of variable?

Suppose that I am trying to solve the following $n$-dimensional quadratic optimization problem with linear constraints ($\bf{A}$ is an $n \times n$ invertible matrix): $\underset{\mathbf{y}\in\mathbb{...
bbecon's user avatar
  • 147
0 votes
2 answers
225 views

Why is this expression the Lagrangian dual problem of this QCQP?

$\newcommand{\bx}{\mathbf{x}}$ $\newcommand{\bC}{\mathbf{C}}$ $\newcommand{\bA}{\mathbf{A}}$ $\newcommand{\bl}{\boldsymbol{\lambda}}$ $\newcommand{\bb}{\mathbf{b}}$ $\newcommand{\bQ}{\mathbf{Q}}$ ...
gtg's user avatar
  • 121
4 votes
2 answers
121 views

Box-constrained QCQP

Let ${\bf A} \in \mathbb{R}^{n \times n}$ be a symmetric positive semidefinite (PSD) matrix, let ${\bf a} \in \mathbb{R}^n$ and let ${\bf B} \in \mathbb{R}^{n \times n}$ be a symmetric indefinite ...
Claudio Moneo's user avatar
3 votes
1 answer
145 views

A Lagrange optimisation that I don’t understand. $f(x, y, z) = x^2 + y^2$ is constrained by $5x^2 + 6xy + 5y^2 = 1$

The function $f(x, y, z) = x^2 + y^2$ is constrained by $5x^2 + 6xy + 5y^2 = 1$. Using Lagrange, maximise and minimise this function. My original Lagrange equation was $$L = x^2 + y^2 + \lambda(1 - ...
jxhn's user avatar
  • 43
0 votes
2 answers
95 views

Solving a weird QCQP using a Lagrange multiplier

Minimize $f(x,y,z)=\dfrac12 \left(x^2+y^2+z^2\right)$ in the set $C = \left\{ (x,y,z) \in \mathbb{R^{3}} \mid xy+xz+yz=1 \right\}$. I'm stuck on this question. I've shown that it is a non-bounded ...
UItraviolet's user avatar
1 vote
0 answers
234 views

Solving Lagrange multiplier problem $\max x'Qx$ subject to $\|x\|=1$

Given a symmetric positive definite matrix $Q$, $$ \max_{\| x \| = 1} x^t Q x \tag{P} $$ Solving the problem I made the following: First I see that $\|x\| = 1$ is equivalent to $\|x\|^2=1$, so I ...
Pablo Diego Acosta's user avatar
2 votes
0 answers
68 views

Maximum singular value via nonconvex QCQP

Finding the extremal singular triplet $(σ, u, v)$ of a generic real $m×n$ matrix $A$ can be formalized as a nonconvex quadratically-constrained quadratic program (QCQP): $$σ = \max_{u,v}\quad u^⊤ A v ...
Hyperplane's user avatar
  • 11.5k
3 votes
0 answers
133 views

Minimizing a strictly convex quadratic function subject to a single nonconvex quadratic constraint

For $A\succ 0, B\succeq 0, \rho,\phi>0$, and a given $y$, I am trying the find a cheap yet numerically stable method for solving a sequence of the following problem (it is a penalty method and $\...
Sam's user avatar
  • 384
1 vote
0 answers
48 views

Question about optimization formulation for finding all eigenvectors of a symmetric matrix

I am looking at the following optimization formulation for finding all the eigenvectors of a symmetric matrix $\mathbf{A} \in \Bbb R^{n\times n}$. $$\min_{\mathbf{\Phi} \in \Bbb R^{n \times n}}\;\...
Amit Boyarski's user avatar
0 votes
2 answers
137 views

Maximization of convex quadratic function for diagonal matrices over Euclidean ball

Let's say $\epsilon \in \mathbb{R}^d$. I am trying to solve the following optimization problems: \begin{equation} \underset{\|\epsilon\| _{\infty} \le \rho}{\operatorname{arg max}} \ \epsilon^T b + \...
Arman's user avatar
  • 103
0 votes
0 answers
140 views

Maximizing/minimizing a quadratic form over an ellipsoid

The goal is to solve the following maximization/minimization problem: \begin{align*} &\max_y/\min_y y^TQy\\&\text{s.t.}(y-x)^\top V(y-x)\le\beta^2\end{align*} where the optimization variable $...
OwnCandy's user avatar
2 votes
0 answers
172 views

Rewritting QCQP as SOCP

I have a convex function with convex constraints. $$f(p) = \min_\limits{\| b_{0} - A_{0} x \|_{2} \le p} \| x \|_{2} = \min_\limits{\| b_{0} - A_{0} x \|_{2} = p} \| x \|_{2}$$ I was researching a lot ...
nezudem's user avatar
  • 101
1 vote
0 answers
146 views

Minimizing norm on convex set

I have faced a problem of programming the computation of next function for each p: $$f(p) = \min_\limits{\| b_{0} - A_{0} x \| = p} \| x \|$$ For now I work with Euclidean norm (or Frobenius for ...
nezudem's user avatar
  • 101
4 votes
1 answer
74 views

Lagrange multiplier for QCQP with $1$ equality constraint

I want to find the maximum of $f(x,y) = x^2 - y^2$ under the constraint $\frac12 x^2 + y^2 - 1 = 0$. I defined Lagrange function: $$ L= x^2 - y^2 + \lambda \left( \frac12 x^2 + y^2 - 1 \right) $$ Then ...
user avatar
1 vote
0 answers
120 views

Objective function and constraints are matrix form in an optimization problem, can Lagrange multipliers method be applied to solve?

I would like to solve the following optimization problem: given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
lyh458's user avatar
  • 35
1 vote
1 answer
240 views

Least-squares QCQP problem with quadratic equality constraint equals to zero

Is there an efficient method to solve the QCQP problem: \begin{array}{ll} \text{minimize} & x^T Q x - f^Tx\\ \text{subject to} & x^TVx = 0\end{array} where $Q$ is symmetric positive definite ...
Andrea993's user avatar
  • 121
0 votes
0 answers
54 views

Optimize a non-positive-definite quadratic form

Given vectors $a, b \in \mathbb{R}^d$, consider the following optimization problem in $x,y\in \mathbb{R}^d$. $$ \underset{x, y \in \mathbb{R}^d}{\text{maximize}} \quad x^\top y + a^\top x+b^\top y \...
Henry Davii's user avatar
1 vote
1 answer
66 views

Solving an optimization problem in QCP form

I am reading a paper in which authors said quadratic-constrained optimization is used for the following problem: \begin{align} &\underset{\mathbf{P},\,\,\epsilon}{\min}\:\epsilon\\ &\mathrm{s....
zstr's user avatar
  • 43
2 votes
2 answers
134 views

Is there an analytical solution for the following optimization problem?

We need to solve the following least square problem $$\min_x (Y-Ax)^T(Y-Ax)$$ $$s.t. x^TA^TAx=1$$ in a closed form, where $Y \in \mathbb{R}^{n\times 1}$ and $A \in \mathbb{R}^{n\times n}$ are given. ...
user1034188's user avatar
2 votes
0 answers
62 views

nonconvex QCQP formulation

I am trying to solve a QCLP problem of the type \begin{equation*} \begin{aligned} & \underset{x,y}{\text{max}} & & \sum_xx_iU_i + \sum_yy_iVi \\ & \text{subject to} & & \frac{\...
Jacob's user avatar
  • 21
0 votes
1 answer
198 views

Problem of solving a large scale Quadratic Problem with Quadratic Inquality Constraint (QCQP)

I am trying to solve following large-scale quadratic fractional (QF) problem: \begin{equation} \begin{aligned} \min_{x\in\Re^{n\times1}} &\frac{x^\top H x + f^\top x + C_e}{x^\top R x}\\ \text{s.t....
Stephen Ge's user avatar
2 votes
1 answer
140 views

Optimizing the sum of quadratic forms linked by orthogonality constraints

I am looking to find a qualitative solution to the optimization problem: $$\text{min}_{\{\mathbf{u}_i\}_i}\quad\sum_i \mathbf{u}_i^T\mathbf{M}_i\mathbf{u}_i \\ \text{s.t.}\quad \mathbf{u}_i^T\mathbf{u}...
mrs's user avatar
  • 29
2 votes
3 answers
283 views

Minimizing the norm subject to a quadratic form

I am stuck with the following minimization problem $$\min_{x \in \mathbb{R}^n} \underbrace{\|x\|_2^2}_{=: f (x)} \quad \text{subject to} \quad \underbrace{x'Qx - 1}_{=: h (x)} = 0$$ where $Q$ is a ...
david_rios's user avatar
0 votes
2 answers
135 views

Finding maximum/minimum using Lagrange multiplier [closed]

$$\begin{array}{ll} \text{extremize} & xy+2yz+3zx\\ \text{subject to} & x^2+y^2+z^2=1\end{array}$$ How to find the maximum/minimum using Lagrange multipliers? Context: This is not a homework ...
Claire S.'s user avatar
3 votes
0 answers
110 views

Equality-constrained QCQP with non-negativity constraints

Given symmetric matrix $N \in \Bbb R^{n \times n}$, $$\begin{array}{ll} \underset{X \in \Bbb R^{n \times k}}{\text{minimize}} & \mbox{tr} \left( X^T N X \right)\\ \text{subject to} & \left\...
Nathan's user avatar
  • 86
0 votes
0 answers
480 views

Solution to QCQP problem and potential solvers in Python

I am working to solve a given linear system of the form $$\mathbf{A} \: \mathbf{x} = \mathbf{b}$$ where $\mathbf{x} = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix}^T$ with ...
Zero's user avatar
  • 464
1 vote
2 answers
78 views

Elementary issue with constrained optimization

I am trying to solve $$\begin{array}{ll} \text{extremize} & f(x,y) := x^2+3y\\ \text{subject to} & \dfrac{x^2}{4} + \dfrac{y^2}{9} -1 = 0\end{array}$$ I cannot understand why I am able to find ...
Mr Frog's user avatar
  • 237
1 vote
0 answers
65 views

Numerically stable method to find Lagrange multipliers

Given real symmetric matrix $H$, I am trying to numerically find all critical points of the function $$\begin{aligned} f : \mathbb{R}^{3n} &\to \mathbb{R}\\ x &\mapsto x^T H x \end{aligned}$$ ...
catalogue_number's user avatar
0 votes
0 answers
252 views

Reducing convex QCQP to SDP or something better

I am trying to solve the following QCQP $$\begin{array}{ll} \underset{x}{\text{minimize}} & x^T P_0 x + q_0^Tx + r_0\\ \text{subject to} & x^T P_1 x + r_1< 0\end{array}$$ where symmetric ...
Marcel's user avatar
  • 159
5 votes
1 answer
256 views

Minimize $x^*(A+A^*)x$ such that $x^*A^*Ax=1$ and $x^*x=1$

Given $A\in\mathbb{C}^{n\times n}$, such that it has singular values larger than $1$ and smaller than $1$, \begin{array}{ll} \underset{x\in\mathbb{C^n}}{\text{minimize}} & x^*(A+A^*)x.\\ \text{...
Lee's user avatar
  • 1,910
0 votes
0 answers
184 views

How to minimize the Frobenius norm subject to quadratic inequality constraints?

I want to solve the following optimization problem. Given, two $m \times n$ matrices, $A$ and $B$, $$\begin{array}{ll} \underset{B}{\text{minimize}} & \| A - B \|_F^2\\ \text{subject to} & \...
wit's user avatar
  • 109
0 votes
0 answers
251 views

Solving a non-convex quadratically constrained quadratic program (QCQP)

I am trying to solve following optimization problem: \begin{equation} \begin{aligned} \min_{x\in\Re^{n}} & ~x^\top H x + f^\top x + \sqrt{x^\top R x}\\ \text{s.t.} & ~Ax<b \end{aligned}, \...
Stephen Ge's user avatar
3 votes
1 answer
949 views

Maximize quadratic function over unit sphere

In lecture, we proved that, given a symmetric matrix $A$, the $$\max_{\|x\|_2 = 1} x^T A x$$ is the largest eigenvalue $\lambda_{\max}$ of matrix $A$: we diagonalize the matrix $A$ and show that for ...
samabu's user avatar
  • 713
0 votes
0 answers
59 views

Quadratically constrained quadratic programming

I tried to find something before but it seems all the answers do not include my kind of problem. Basically I want to minimize $\vec{a}^TM\vec{a}+\vec{a}^T\vec{b}$, $M$ is symmetric, positive definite ...
Saladino's user avatar
  • 165
2 votes
1 answer
731 views

Maximizing quadratic function over unit Euclidean ball

I am considering the following maximization problem $$\begin{array}{ll} \text{maximize} & \| A x - b \|_2^2\\ \text{subject to} & \| x \|_2 \leq 1\end{array}$$ For easiness, let's assume $A\in\...
Jiaji Huang's user avatar
1 vote
3 answers
236 views

Why is this QCQP non-convex?

Why is the following QCQP non-convex? $$\begin{array}{ll} \underset{x,y \in \Bbb R}{\text{minimize}} & (x+2)^2 + (y+2)^2\\ \text{subject to} & x y \ge 4\\ & x \le 4\\ & y \ge 2\end{...
dena's user avatar
  • 101
0 votes
0 answers
56 views

Find stationary points of QCQP

I'm given the following: $$\begin{align} \min &\qquad x^TQx\\ \mathrm{s.t}&\qquad x^TAx <= 1 \end{align}$$ where $A$ is a positive definite. I'm not sure if and or how this would change ...
mathcomp guy's user avatar
0 votes
0 answers
142 views

How to solve a QCQP where constraints are balls?

I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$ \begin{equation} \begin{aligned} & \underset{\theta}{\text{minimize}} & & \...
Manuel Madeira's user avatar
2 votes
1 answer
214 views

Equality-constrained QCQP — what to do next?

I am studying the following problem. I want to obtain all the local minima of $$ \min_{x\in D} x^Tx \quad \quad \quad \quad \quad \quad (P.1) $$ where $x\in\mathbb{R}^n$ and $D = \{x: x^TA_ix = 1, \...
FeedbackLooper's user avatar
1 vote
0 answers
110 views

Trace minimization with row norm constraint

For a symmetric and negative semidefinite matrix $Q\in\mathbb{R}^{n \times n}$, how can one solve the following optimization problem in tall matrix $X \in \mathbb{R}^{n \times r}$ $$\begin{array}{ll} \...
w382903's user avatar
  • 185
0 votes
1 answer
221 views

Trace minimization with column norm constraint

For a symmetric and negative semidefinite matrix $Q\in\mathbb{R}^{n \times n}$, how can one solve the following QCQP in tall matrix $X\in\mathbb{R}^{n \times r}$ $$\begin{array}{ll} \text{minimize} &...
w382903's user avatar
  • 185
10 votes
2 answers
449 views

Eigenvalue bound for quadratic maximization with linear constraint

This builds on my earlier questions here and here. Let $B$ be a symmetric positive definite matrix in $\mathbb{R}^{k\times k}$ and consider the problem $$\begin{array}{ll} \text{maximize} & x^\...
sven svenson's user avatar
  • 1,415
5 votes
2 answers
249 views

What is the range of $\vec{z}^{ \mathrm{ T } }A\vec{z} $?

Let A be a 3 by 3 matrix $$\begin{pmatrix} 1 & -2 & -1\\ -2 & 1 & 1 \\ -1 & 1 & 4 \end{pmatrix}$$ Then we have a real-number vector $\vec{ z }= \left( \begin{array}{c} ...
ohisamadaigaku's user avatar
4 votes
3 answers
1k views

Minimizing $x^2+y^2+z^2$ subject to $xy -z + 1 = 0$ via Lagrange multipliers

$$\begin{array}{ll} \text{minimize} & f(x,y,z) := x^2 + y^2 + z^2\\ \text{subject to} & g(x,y,z) := xy - z + 1 = 0\end{array}$$ I tried the Lagrange multipliers method and the system resulted ...
Ron's user avatar
  • 41
0 votes
1 answer
76 views

Trouble understanding QCQP

Using a graphical method, indicate the feasible region and solve the minimization problem. $$\begin{array}{ll} \text{minimize} & f := x_1^2 + x_2 + 4\\ \text{subject to} & c_1 := -x_1^2-(x_2+4)...
mdanie17's user avatar
0 votes
0 answers
74 views

Maximize $x^2 + y^2$ subject to $1 \leq 2 x^2 + 4 y^2 \leq 4$

$$\begin{array}{ll} \text{maximize} & x^2 + y^2\\ \text{subject to} & 1 \leq 2 x^2 + 4 y^2 \leq 4\end{array}$$ I don't know how to apply the KKT conditions here, maybe there is other method ...
Juan Sebastian's user avatar