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
41 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
73 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 ...
0
votes
1answer
74 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
60 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
47 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{...
0
votes
0answers
65 views

Determine whether the Lagrange multiplier $\mu$ is a continuous function of $\xi$ in the following optimization problem.

Consider the Euclidean projection of a vector $\xi\in\mathbb{R}^n$ onto a non-convex (in general) non-empty set $\mathcal{X}$ defined by $$\mathcal{X}=\{x\in\mathbb{R}^n\,|\,x^{\rm T}Ax-2b^{\rm T}x\...
2
votes
0answers
54 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
31 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
68 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 ...
0
votes
1answer
86 views

How to derive the closed-form solution for this optimization problem?

$$\begin{array}{ll} \text{maximize} & \mbox{tr} (A^T B A)\\ \text{subject to} & A^T A = I\end{array}$$ where the maximization is over $A$. I know that the solution is eigenvectors of $B$, ...
0
votes
1answer
51 views

What is the sub-topic that deals with this kind of optimization problems?

I am encountering a deluge of optimization problems of the following kind $$\begin{array}{ll} \text{minimize} & \mbox{tr}(WKLKW)\\ \text{subject to} & WKHKW=I\end{array}$$ where the ...
2
votes
3answers
163 views

Why does the Lagrange multiplier $\lambda$ change when the equality constraint is scaled?

Consider the problem $$\begin{array}{ll} \text{maximize} & x^2+y^2 \\ \text{subject to} & \dfrac{x^2}{25} + \dfrac{y^2}{9} = 1\end{array}$$ Solving this using the Lagrange multiplier method,...
0
votes
1answer
47 views

Lagrange dual of quadratic optimization problem with quadratic equality constraints

What is the Lagrange dual of the following optimization problem in $w \in \mathbb{R}^2$? $$\begin{array}{ll} \text{minimize} & w^T Q \, w\\ \text{subject to} & w_1^2 = 1\\ & w_2^2 = 1\end{...
2
votes
0answers
58 views

Maximizing $x^T A^T B \, x$ over the unit Euclidean sphere

Is there an algorithm to solve the QCQP $$\begin{array}{ll} \text{maximize} & x^T A^T B \, x\\ \text{subject to} & \|x\|_2 = 1\end{array}$$ when $A^T B$ is not necessarily symmetric? When $A^...
-1
votes
1answer
60 views

Prove that maximum value is the largest eigenvalue

Given a symmetric positive definite matrix $A \in \mathbb{R}^{n \times n}$ and a full rank matrix $B \in \mathbb{R}^{n \times n}$. Prove that the maximum value the following optimization problem is ...
0
votes
0answers
73 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:...
1
vote
2answers
71 views

Maximum value of $f(x,y)=x^2+2y^2$ subject to constraint : $y-x^2+1=0$?

If $f(y)=2y^2+y+1,$ $f'(y)=4y+1=0\Rightarrow y=-\frac14,\; x=\pm\frac{\sqrt3}2$ $f''(y)=4>0,$ so I can't obtain a point of maxima. What does this mean? Do I necessarily need to use Lagrange's ...
0
votes
0answers
33 views

Minimizing mixed-norm subject to a nonconvex quartic constraint for small n and m

How can one solve this mixed-norm minimization problem subject to a quartic constraint for small N and M (ex: M=12 and N=4): $\textbf{c} = [c_{1},...,c_{N}]^T$ $min\biggl (\|\textbf{c}\|_{1} + \beta\|...
1
vote
1answer
290 views

Norm constrained least square minimization with an additional single linear equality constraint: A quadratically constrained quadratic program (QCQP)

Given is the following QCQP problem: \begin{align} &&\min_{\mathbf{x} \in \mathbb{C}^n} &\|A \mathbf{x} - \mathbf{b}\|^2,\tag{1}\label{1}\\ \text{ subject to:}&&&\\ &&\|...
0
votes
1answer
316 views

Linearisation of product of two continuous variable.

I have a quadratic constraint which I want to linearise. $x_1x_2=0$ where $0\leqslant x_1,x_2\leqslant1$. What is the best way to do this?
0
votes
1answer
137 views

Convert Quadratic to Conic Constraint

Per Wikipedia, a quadratic constraint of the below form $$x^TA^TAx+b^Tx+c\leq0\tag{1}$$ can be written as the following equivalent conic formulation $$\left \|[(1+b^Tx+c)/2,~Ax ]\right \|_2\leq(1-...
4
votes
1answer
128 views

Least squares problem with a quadratic constraint

I have to minimize $e_1^2+e_2^2+e_3^2$ subject to $\mathbf{e}^\top \mathbf{A} \mathbf{e} + \mathbf{e}^\top \mathbf{b} +c =0$ with $\mathbf{e} = [e_1, e_2, e_3]^\top$ I know that matrix $\mathbf{A}...
1
vote
0answers
45 views

Can I get a closed form of this optimization problem?

$$\begin{array}{ll} & \underset{w \in \mathbb R^n}{\text{minimize}} & & \quad w^{H} w \\ & \text{subject to} & & w^{H} A w \geq 1 \\ & & & w^{H} B w \geq 1 \...
1
vote
2answers
58 views

Why is $\max_{c^TBc=1}c^T a a^Tc =a^TB^{-1}a$?

I'm having some trouble in understanding the last step in this sequence of equalities: $$\max_{c}\frac{c^Taa^Tc}{c^TBc}=\max_{c^TBc=1}c^T a a^Tc =a^TB^{-1}a$$ I would think that the maximum would ...
0
votes
1answer
92 views

Minimize $ {x}^{T} Q y $ subject to $ \left\| x \right\|^{2} + \left\| y \right\|^{2} = 1 $

Let $ Q $ be an $ n \times n $ diagonal matrix with positive diagonal entries $\lambda_{1}<\cdots<\lambda_{n}$. Find local minimizer(s) for the function $f : \mathbb{R}^{n} \times \mathbb{R}^{...
2
votes
3answers
59 views

Why are the solutions of the $3\times 3$ system like that?

Consider the problem:$$ \min \quad -x_1^2-4x_1x_2-x_2^2\\ \text{s.t.} \quad x_1^2 + x_2^2 = 1$$ The KKT system is given by\begin{align*} x_1 (-1 + v) + 2 x_2 &= 0 \tag{1} ,\\ x_2 (-1 + v) + 2 x_1 &...
3
votes
1answer
294 views

Minimize $ \mbox{tr} ( X^T A X ) + \lambda \mbox{tr} ( X^T B ) $ subject to $ X^T X = I $ - Linear Matrix Function with Norm Equality Constraint

We have the following optimization problem in tall matrix $X \in\mathbb R^{n \times k}$ $$\begin{array}{ll} \text{minimize} & \mbox{tr}(X^T A X) + \lambda \,\mbox{tr}(X^T B)\\ \text{subject to} &...
0
votes
0answers
118 views

Mixed Binary Quadratic Programming Quadratically Constrained

I would like to find an algorithm to find the optimal (or a close approximation) of the minimum of $f(X,Y)$: $$ f(X,Y)=\sum^N_{i=1}{x_it_i}+\sum^N_{i=1}{x_iy_ir_i}\\ \begin{align} s.t &&x_i \...
0
votes
0answers
218 views

Implement QCQP in CVXOPT

I'm struggling to formulate a simple QCQP in the correct format to solve with CVXOPT. I'm trying to implement max-margin Inverse Reinforcement Learning from the paper Apprenticeship Learning via ...
4
votes
1answer
414 views

Convert a non-convex QCQP into a convex counterpart

Problem We consider a possibly non-convex QCQP, with nonnegative variable $x\in \mathbb{R}^n$, \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{...
1
vote
3answers
112 views

Maximizing a bivariate quadratic form with Lagrange's method

Maximize the generic bivariate quadratic form constrained to the unit circle. $$\begin{array}{ll} \text{maximize} & f(x_1, x_2) := ax_1^2 + 2bx_1 x_2 + cx_2^2\\ \text{subject to} & g(x_1, ...
3
votes
0answers
321 views

Semidefinite relaxation for QCQP with nonconvex “homogeneous” constraints

Suppose we wish to solve the quadratically constrained quadratic program (QCQP) in $x \in \mathbb R^n$ $$\begin{array}{rl} \text{minimize} & \frac{1}{2}x^\top Lx\\ \text{subject to} & Ax=b\\ &...
2
votes
0answers
371 views

Conversion of convex QCQP to standard form SDP

I have the following QCQP: $$ \underset{\mathbf{x}}{minimize} \quad \mathbf{x}^{T} H \mathbf{x} + \mathbf{p}^{T} \mathbf{x}$$ $$ subject \; to \quad \mathbf{x}^{T}Q_{i}\mathbf{x} + \mathbf{q}_{i}^{T}...
1
vote
0answers
159 views

Least squares minimization subject to generalized orthogonality constraint?

I'd like to solve the following minimization problem: $$ \min_{\Phi^T D \Phi = I_k} \frac{1}{2}\|\Phi - Y\|_F^2, $$ where $\Phi \in \mathbb{R}^{n \times k}$, $D \in \mathbb{R}^{n \times n}$ is a (...
1
vote
0answers
64 views

Does this optimization problem have a closed form solution?

Consider the following optimization problem $$\min \qquad \omega^H \omega \\ \text{s. t.} \quad \omega^H A \omega \geq a, \\ \quad \quad \omega^H B \omega \geq b $$ where $A$ and $B$ are ...
5
votes
1answer
391 views

Minimizing Quadratic Form with Norm and Positive Orthant Constraints

Let $ M $ be a positive semi definite matrix. I want to solve $$ \arg \min_{x} {x}^{T} M x \quad \mathrm{s.t.} \quad \left\| x \right\| = 1, \ x \succeq 0 $$ where $ x \succeq 0 $ means each ...
2
votes
3answers
142 views

What are the maximum and minimum values of $4x + y^2$ subject to $2x^2 + y^2 = 4$?

$$ 2x^2 + y^2 = 4 $$ $$ Y = \sqrt{4-2x^2} $$ $$4x + y = 2x^2 + \sqrt{4-2x^2}$$ Find the derivative of $$ 2x^2 + \sqrt{4-2x^2} $$ set as = 0 $$X^2 = 64/33$$ $$ F(64/33) = 34\sqrt{33}/33 $$ How to ...
1
vote
0answers
113 views

Minimizing quadratic objective subject to a quadratic equality constraint

I have the following optimization problem in $X \in \mathbb R^{r \times n}$ $$\begin{array}{ll} \text{minimize} & \| A - B X \|_F + \beta \, \mbox{Tr}(X^TCX)\\ \text{subject to} & X^T X = I_n\...
0
votes
1answer
108 views

How to handle equality constraints in this problem?

Here is the problem setup \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \mathbf{b}^{T}_{}\mathbf{A}^{}_{}\mathbf{b}^{}_{} \\ s.t \hspace{5mm} \mathbf{b} \in \mathbb{R}^{N} \\ \hspace{9mm}...
0
votes
0answers
317 views

Maximimization problem with quadratic equality constraint

Given this optimization problem, $Max \quad Q(x)$ $s.t., \quad x \in X$ $\quad \sum_{i=1}^{n} x_i^2 = k$ where $x_i$ are integers, $x \in X$ is a set of linear inequalities, k is a parameter, ...
1
vote
0answers
110 views

Trace maximization with semi-orthogonal constraint

I am trying to solve the following optimization problem in $W \in \mathbb{R}^{D \times d}$ $$\begin{array}{ll} \text{maximize} & \displaystyle\sum_{k=1}^K\text{Tr}(W^\top A_k WB_k)\\ \text{...
3
votes
0answers
81 views

Minimize $x^T A y$, subject to $ x^Ty\geq 0$, where $A=\Phi^T\Phi$ is symmtric and semi-positive definite.

I try to solve it by KKT conditions. The Lagrangian is $L=x^TAy-\lambda x^Ty$. Its KKT conditions are given by $$ \begin{align} Ay-\lambda y=&0\quad (1)\\ A^Tx-\lambda x=&0\quad (2)\\ \...
2
votes
6answers
112 views

Find largest possible value of $x^2+y^2$ given that $x^2+y^2=2x-2y+2$

Let $x, y \in \mathbb R$ such that $x^2+y^2=2x-2y+2$. Find the largest possible value of $x^2+y^2$. My attempt: $x^2+y^2=2x-2y+2$ $(x^2-2x)+(y^2+1)=2$ $(x-1)^2+(y+1)^2=4$ I have no idea how to ...
1
vote
4answers
343 views

Find all local maxima and minima of $x^2+y^2$ subject to the constraint $x^2+2y=6$. Does $x^2+y^2$ have a global max/min on the same constraint?

This is my method for the local max/min. Does this answer sound sensible? (Not sure how to go about checking for global max/min though...) Method $G(x,y)=x^2+2y-6$. Rewrite in terms of $y$, so $y=((-...
2
votes
2answers
95 views

In which interval lies the minimum? [closed]

Let $a_1,a_2,a_3,a_4$ be real numbers such that $a_1+a_2+a_3+a_4 =0 $ and $a_1^2+a_2^2+a_3^2+a_4^2=1$. Then in what interval does the smallest possible value of the following expression lies? $$(...
2
votes
0answers
607 views

Convex QCQP in CVXOPT

So I have the following simple QCQP: $$ \underset{\mathbf{x}}{minimize} \quad \mathbf{x}^{T} Q_{0}\mathbf{x} + \mathbf{q}_{0}^{T}\mathbf{x} + c_{0} $$ $$ subject \; to \quad \mathbf{x}^{T} Q_{i}\...
1
vote
0answers
349 views

How to solve this QCQP efficiently?

I'd like to solve the following quadratically constrained quadratic program (QCQP) \begin{equation}\label{bijective} \begin{split} \min_{x} \quad &x^{T}Ax\\ \mathrm{s.t.}\quad &...
1
vote
1answer
49 views

Constrained optimisation for quadratic form with linear term

I need to maximise a quadratic form in 3D with the constraint that the solution vector, $\mathbf{x}$, lies on the unit sphere. I know that for a simple quadratic form: $$ \mathbf{x}^T\mathbf{A}\...
11
votes
3answers
869 views

Solve Least Squares Minimization from Over Determined System with Orthonormal Constraint

I would like to find the rectangular matrix $X \in \mathbb{R}^{n \times k}$ that solves the following minimization problem: $$ \mathop{\text{minimize }}_{X \in \mathbb{R}^{n \times k}} \left\| A X - ...