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
1answer
101 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
47 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
49 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
316 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
189 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
98 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
50 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
61 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
104 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
41 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
12 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
130 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
219 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....
1
vote
4answers
148 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
39 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
71 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
69 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
17 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
116 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
90 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
115 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
39 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
73 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
106 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
42 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
43 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
2answers
90 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
42 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
41 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} &...
2
votes
0answers
92 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
50 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
59 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
152 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
52 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 ...
2
votes
3answers
40 views

Maximum value of $8v_1 - 6v_2 - v_1^2 - v_2^2$ subject to $v_1^2+v_2^2\leq 1$

Given that $g:\mathbb{R}^2 \to \mathbb{R}$ defined by $$g(v_1,v_2) = 8v_1 - 6v_2 - v_1^2 - v_2^2$$ find the maximum value of $g$ subject to the constraint $v_1^2+v_2^2\leq 1.$ My attempt: Note ...
1
vote
5answers
135 views

If $x$ and $y$ are real number such that $x^2+2xy-y^2=6$, then find the minimum value of $(x^2+y^2)^2$

If $x$ and $y$ are real number such that $x^2+2xy-y^2=6$, then find the maximum value of $(x^2+y^2)^2$ My attempt is as follows: $$(x-y)^2\ge 0$$ $$x^2+y^2\ge 2xy$$ $$2(x^2+y^2)\ge x^2+y^2+2xy$$ \...
0
votes
0answers
54 views

QCQP Convex quadratic optimisation with quadratic constraint

I am trying to implement this QCQP optimisation problem in a more efficient way. The optimisation aims to smooth an existing 3D trajectory represented by "P" which contains "n" 3D coordinates. The "n"...
0
votes
0answers
50 views

Find maximum and minimum of a quadratic form on an $n$-dimensional sphere

Let $A = (a_{ij})$ be a symmetric matrix. Find the maximum and minimum of $$F: {\mathbb{R}}^n \to {\mathbb{R}}: f(x) = \sum_{i, j = 1}^{n}a_{ij}x_{i}x_{j}$$ on the sphere $$S = \left\{ x \in \mathbb{R}...
0
votes
1answer
116 views

Relationship between QCQP constraint bound and dual solution.

Assume that we have the following class of primal QCQP problems $$ \begin{array}{ll} \text{minimize}_\alpha & f(\alpha) \\ \text{subject to} & h(\alpha)\leq t, \end{array} $$ that are ...
0
votes
3answers
38 views

How would you approach this type of System of Equations? Could you give me a solid method to approach these?

$$ \left\{ \begin{array}{c} y+2\lambda x=0 \\ x+2z+2\lambda y=0 \\ 2y+2\lambda z=0 \\ x^2+y^2+z^2-1=0 \end{array} \right. $$ And yeah the problem is to find maximum and minimum for the function: ...
2
votes
0answers
12 views

Bound and branch method for NQCQP Problem and its difference to SDP-rank-$1$ decomposition

I'm trying to solve a problem of the form $$\begin{array}{ll} \text{maximize} & x^H Q_0 x\\ \text{subject to} & x^H Q_i x > b_i, \quad i \in [m]\end{array}$$ where matrices $Q_0, Q_1, \...
0
votes
0answers
71 views

Minimize quadratic over unit spherical surface with linear constraints

Is there a closed-form solution for this problem? $$\begin{array}{ll} \text{minimize} & {\color{red}x}^{T}A^{T}A{\color{red}x} \\ \text{subject to} & \left\Vert {\color{red}x}\right\Vert_2^2 =...
-2
votes
1answer
708 views

Find Minimum + Maximum of function with constraints [closed]

homework assignment ask to find Max/Min for $$U(x,y,z) = x^2 + 2y^2 + 3z^2$$ with these constraints: $x^2 + y^2 + z^2 = 1$ $x + 2y + 3z = 0$ Thank you. First i tried to isolate x from the second ...
1
vote
1answer
107 views

Trace minimization in a Rayleigh-quotient-like problem

Given an $n\times n$ real diagonal matrix $D$ and an $m\times m$ real diagonal matrix $W$ (where $n\geq m$) with $\text{tr}(W^2)=1$, consider the following optimization problem in $X \in \mathbb{R}^{n ...
1
vote
4answers
70 views

Maximising and minimising $f(x,y)$ on $x^2+y^2\leqslant 9$

Find the absolute minimum and maximum of $f(x,y):=x^2+y^2-8y+3$ on the disc $x^2+y^2\leqslant 9$. I know what the answer is and how to obtain it. What I do not understand is why we may assume that ...
1
vote
2answers
65 views

QCQP with bilinear constraints

I have the optimization problem in $u := \left(u_{1},u_{2}\right)$ $$\begin{array}{ll} \text{minimize} & \frac{1}{2}u^{\top}\Sigma u-au^{\top}\beta\\ \text{subject to} & u_{1}u_{2}\le0\end{...
2
votes
0answers
120 views

Solve KKT system for Quadratic Constrained Quadratic Program

I'm having trouble solving one of the possible cases that arise when solving the KKT conditions of the following problem: We have the following optimization problem in $ \mathrm x \in \mathbb R^n$, ...
0
votes
0answers
28 views

Finding maxima using Lagrange multipliers [duplicate]

Finding maxima of $x^2+y^2+z^2$ subject to conditions $\frac{x^2}{4}+\frac{y^2}{5}+\frac{z^2}{25} = 1 $ and $z=x+y$ Now I form $F(x,y,z, \lambda_1 , \lambda_2 )= x^2+y^2+z^2 + \lambda_1(\frac{x^2}{4}+...
0
votes
1answer
41 views

Why is this optimization problem nonconvex: ${\min}_{x \in \mathbb{C}^n} \ x^* A x \ $s.t.$|b^* x|^2 \geq 1$, $A \succeq 0$, and $b \in \mathbb{C}^n$?

Given problem, \begin{align} \text{minimize}_{x \in \mathbb{C}^n} \quad & x^* A x \\ \text{subject to }\quad & |b^* x|^2 \geq 1 \ ,\\ \end{align} where $A \in \mathbb{C}^{n \times n} \...
2
votes
1answer
116 views

Maximize trace over Stiefel manifold

This question is the same as the question in this post. The OP of that post changed what they were asking and reduced it to a special case, so I’m asking the question in full generality here. Given ...