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
0
votes
0answers
39 views

QCQP maximization problem

I'm trying to maximize the following simple quadratic form with quadratic constraints too. $$\arg\max_{\boldsymbol{\delta}} \boldsymbol{\delta}^\text{H} \boldsymbol{A}^\text{H} \boldsymbol{A} \, \...
1
vote
3answers
62 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 ...
0
votes
2answers
88 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 ...
3
votes
0answers
58 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\...
0
votes
0answers
76 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 ...
1
vote
2answers
70 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 ...
1
vote
0answers
44 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}$$ ...
0
votes
0answers
51 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 ...
4
votes
1answer
201 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{...
0
votes
0answers
66 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} & \...
0
votes
0answers
31 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}, \...
2
votes
1answer
178 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 ...
0
votes
0answers
39 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 ...
1
vote
1answer
154 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\...
0
votes
0answers
54 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 ...
0
votes
0answers
61 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}} & & \...
2
votes
1answer
133 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, \...
1
vote
0answers
70 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} \...
0
votes
1answer
69 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} &...
10
votes
2answers
339 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^\...
5
votes
2answers
212 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} ...
4
votes
3answers
543 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 ...
0
votes
1answer
60 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)...
0
votes
0answers
67 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 ...
2
votes
1answer
203 views

Eigenvector problem with ellipsoids (maximizing quadratic form)

Let $B$ be a symmetric, positive definite matrix and consider the problem $$\begin{array}{ll} \text{maximize} & x^\top B x\\ \text{subject to} & \|x\| = 1\\ & b^\top x = 0\end{array}$$ for ...
0
votes
2answers
67 views

How can I minimize a quadratic over a $2$-norm ball in Matlab?

On Matlab, how can I solve $$\begin{array}{ll} \text{minimize} & x^tQx + b^tx + c\\ \text{subject to} & \|x\|_2 \leq C\end{array}$$ where $C > 0$? I read about function ...
0
votes
0answers
16 views

What is the normal cone of the constraints of a quadratically constrained quadratic programming(QCQP)?

$$\begin{array}{ll} \text{minimize} & f_0(x)\\ \text{subject to} & f_i(x) \leq 0\end{array}$$ where $$f_i (x) := (A_ix+b_i)^T(A_ix+b_i)-c_i^Tx-d_i$$ How can I calculate the normal cone of ...
4
votes
2answers
181 views

Projection of an interior point of an ellipsoid onto itself

Consider $$E := \{ x \in \Bbb R^n \mid x^T D x = 1 \}$$ an ellipsoid constructed by the diagonal matrix $D = \mbox{diag}(d_1, d_2, \dots, d_n)$ with $d_i > 0,\ \forall i \in [n]$. Suppose that $z$ ...
3
votes
2answers
705 views

Maximizing quadratic form subject to quadratic constraint

How can I find the maximum and minimum value of the following quadratic form $$Q(x) = x_1^2+3x_2^2+10x_1x_3+25x_3^2$$ subject to the equality constraint $\|x\|_2 = 3$? The norm is the Euclidian one....
2
votes
5answers
396 views

Maximize $\mathrm{tr}(Q^TCQ)$ subject to $Q^TQ=I$

Let $C \in \mathbb{R}^{d \times d}$ be symmetric, and $$Q = \begin{bmatrix} \vert & \vert & & \vert \\ q_1 & q_2 & \dots & q_K \\ \vert & \vert &...
0
votes
0answers
89 views

Minimizing quadratic form with quadratic and linear constraints

I am trying to solve the following optimization problem $$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \left(\mathbf{x}-m\mathbf{1}\right)^T \...
0
votes
1answer
137 views

Converting a quadratically constrained optimization problem into a standard semidefinite program

I have a constrained matrix optimization problem as follows \begin{align} \max\limits_{X,Y} \;\; &tr\Big( X^T B X \Lambda \Big) + tr\Big( BY\Big) + tr\Big( X^T C \Lambda \Big) \\ \text{subject ...
2
votes
3answers
80 views

Find max/min of the following function

Find the minimum e max distance (in $R^2$) ) between the point $Q = ( 3/ 2 , − 3/ 2 )$ and the set $$B = \{(x, y) ∈ R^2 : yx = 1, x ≥ 0, y ≥ 0\}$$ In other words I have to find max /min points of the ...
0
votes
0answers
35 views

Lagrange multipliers on matrix function, where matrix doesn't have to be symmetric

Let $x \in \mathbb{R}^{n \times1 }, A \in \mathbb{R}^{n \times n}$. We are looking for maximal and minimal value of $f(x) = x^TAx$ with constraint $g(x)=x^Tx$. We get that $\nabla g= 2x, \nabla f = Ax ...
0
votes
1answer
642 views

Maximum and minimum on unit circle

How would I do $f(x, y) = 5x^2 + 6y^2$ on circle $x^2+y^2 = 1$? I understand that we first solve for the critical points getting $f(0, 0) = 0$ which is the global minimum. But after that how do we ...
1
vote
3answers
98 views

Maximize $x^2+2y^2$ subject to $y-x^2+1=0$

Maximize $x^2+2y^2$ subject to $y-x^2+1=0$ I tried using Lagrange multiplier method. We have: $$L(x,y)=x^2+2y^2+\lambda(y-x^2+1)$$ So we have: $$L_x=2x(1-\lambda)=0$$ $$L_y=4y+\lambda=0$$ One ...
0
votes
0answers
346 views

How to convert Quadratically Constrained Quadratic Program (QCQP) with indefinite constraints into Second Order Cone Program (SOCP)?

In their paper, "Applications of Second Order Cone Programming," Boyd, Vandenberghe et al introduce the following procedure to convert a quadratic constraint into a second order cone constraint. For $...
1
vote
0answers
66 views

Least-squares constrained to the unit Euclidean sphere [duplicate]

Assume $A\in \mathbb{R}^{t\times n}$ and $b\in \mathbb{R}^t$. How to solve the following optimization problem in $x\in \mathbb{R}^n$? $$\begin{array}{ll} \text{minimize} & \|Ax-b\|_2^2\\ \text{...
1
vote
4answers
209 views

Find minimum value $E(x, y) = x^2 + y^2 -6x -10y$, where $x^2 + y^2 - 2y \le 0$

I am given the expression: $$E(x, y) = x^2 + y^2 -6x -10y$$ And I have to find the minimum value of $E(x, y)$ for $(x, y) \in D$ where: $$D = \{ (x,y) \in \mathbb{R}^2 \hspace{0.25cm} | \hspace{0....
2
votes
1answer
131 views

Find maximum of $C=2(x+y+z)-xy-yz-xz$

Let $x,y,z\ge 0$ such that $x^2+y^2+z^2=3$. Find the maximum of $$C=2(x+y+z)-xy-yz-xz.$$ I tried Schur and AM-GM inequality but I really have no idea about this problem. It is not homogeneous so it's ...
0
votes
2answers
56 views

Finding minimum value using Lagrange multipliers

I need to find the minimum of $f(x,y,z) = x^2 + y^2 + z^2$ subject to the constraints $(x-2)^2 + y^2 + z^2 = 1$ and $x + z = 3$. I've got the following equations set up (using Lagrange multipliers): ...
1
vote
1answer
125 views

Find the minima/maxima of the function with Lagrange multiplier

Find the minima and maxima of the function $f(x,y) = x^2 + y^2$ under the constraint $y = x^2 - 9/2$. Use Lagrange multiplier method. So we have the function $f(x,y) = x^2 + y^2$ and I rewrite the ...
1
vote
3answers
1k views

Maximum and minimum of $x^2+2y^2+3z^2$ subject to $x^2+y^2+z^2=100$

Find the maximum and minimum values of the function $f(x,y,z)=x^2+2y^2+3z^2$ subject to the constraint $x^2+y^2+z^2=100$. I know to find the critical points I need to solve the system of equations $...
0
votes
1answer
87 views

Finding the axes of an ellipse using Lagrange multipliers

From Demidovich: Find the axes of the ellipse $5x^2 + 8xy + 5y^2 = 9$ using Lagrange multipliers. I've tried to separate into two equations, $g(x,y)$ and $f(x,y)$, to apply $$\nabla f(x,y) = -\...
1
vote
0answers
67 views

Dominant eigenvector of convex combination of Hermitian matrices

Given Hermitian matrices ${\bf A}, {\bf B}, {\bf C} \in \mathbb{C}^{N \times N}$, we have the following optimization problem in vector ${\bf x} \in \mathbb{C}^N$ $$\begin{array}{ll} \text{maximize} &...
3
votes
0answers
159 views

Convert quadratically constrained quadratic program(QCQP) into second-order cone programming(SOCP) [closed]

I have to solve optimization problem enter image description here How can i convert this quadratically constrained quadratic program(QCQP) into SOCP? Is this QCQP a convex problem?
0
votes
1answer
96 views

Minimize $x y$ subject to $x^2 + y^2 \le 1$ by linear independence constraint qualification

I'm trying to solve this problem by KKT $$\begin{align*} \text{min} & \quad x y \\ \text{s.t} & \quad x^2 + y^2 \le 1 \end{align*}$$ One of the regularity conditions is linear independence ...
0
votes
1answer
219 views

Minimize $x y$ subject to $x^2 + y^2 \le 1$ by Mangasarian-Fromovitz constraint qualification

I'm trying to solve this problem by KKT $$\begin{align*} \text{min} & \quad x y \\ \text{s.t} & \quad x^2 + y^2 \le 1 \end{align*}$$ One of the regularity conditions is Mangasarian-...
2
votes
1answer
205 views

Smallest value of $x^2+5y^2+8z^2$ given $xy+yz+xz=-1$.

The question is: Find the smallest value of $x^2+5y^2+8z^2$ given $xy+yz+xz=-1$. Here's what I've tried so far. Dividing by $xyz$, I get $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=\frac{1}{-xyz}$. ...
2
votes
3answers
75 views

Find the minimum value of $f(x,y) = x + y^2$ given the constraint $2x^2 + y^2 = 1$

Find the minimum value of $x + y^2$ subject to the condition $2x^2 + y^2 = 1$. 1) I find $\nabla f$ and $\nabla g$ to get $$\nabla f(x,y) = (1, 2y) \\ \nabla g(x,y) = (4x, 2y)$$ Then I set up the ...