Questions tagged [qclp]

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

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

Optimizing Trace$(Q^TZ)$ subject to $Q^TQ=I$

Let $Z \in \mathbb{R}^{m \times n}$ be a tall matrix ($m > n$). Solve the following optimization problem in $Q \in \mathbb{R}^{m \times n}$ $$\begin{array}{ll} \text{maximize} & \mbox{Tr} \...
1
vote
1answer
53 views

Constrained convex optimization [duplicate]

Solve Maximize $f(x)=c^Tx$ subject to $x^TQx \leq 1$ where $Q$ is a positive definite matrix. what is the solution if the objective function is to be minimized ?
0
votes
3answers
57 views

Minimize with Lagrange multiplier

$$\begin{array}{ll} \text{minimize} & f(x,y,z) := x+2y+z\\ \text{subject to} & g(x,y,z) := x^2+y^2+z^2-1=0\end{array}$$ I get the following $\nabla f=(1,2,1)$ and $\nabla g=(2x,2y,2z)$. Now, ...
1
vote
1answer
47 views

Minimize $x + z$ subject to $x^2 + y^2 = 1$ and $y^2+z^2 = 4$

I'm trying to solve this problem by KKT's condition: $$\begin{align*} \text{min} & \quad x + z \\ \text{s.t} & \quad x^2 + y^2 = 1 \\ & \quad y^2+z^2 = 4 \end{align*}$$ One ...
1
vote
2answers
53 views

Minimise $2x+y$ subject to $x^2+y^2=1$ using KKT

I'm doing this exercise in preparing for the final exam in optimization: $$\begin{align*} \text{min} &\quad 2x+y \\ \text{s.t} & \quad x^2+y^2=1 \end{align*}$$ Could you please verify if I ...
2
votes
2answers
154 views

Maximisation of a piecewise affine function over an ellipsoid

Given vectors $\mathrm a, \bar{\mathrm x} \in \mathbb R^n$ and matrix $\mathrm P \in \mathbb S^n_{++}$, how to deal with the absolute value in the objective function of this optimization problem in $\...
1
vote
1answer
49 views

Change of variables in QCLP

Is there any change of variables that makes the following optimization problem easier to solve? \begin{align} \max_{x\in\mathbb{R}^n,t\in\mathbb{R}}\quad & c^\top x,\\ \mbox{s.t.}\quad\quad & ...
0
votes
0answers
90 views

Constrained optimization problem exam question

Consider the following constrained optimization problem: $$\min_{x} f = x_1 \\ \text{such that} \quad g_1=x_1^2+x_2^2-9 \leq0 \\ \qquad \qquad \ \ \quad \ g_2=-x_1^2-x_2^2+4 \leq0 \\ \qquad \ \ \ ...
1
vote
0answers
89 views

“Convert” quadratic constraint to quadratic objective

I have a large sparse quadratic optimization problem with a single quadratic constraint: $$\begin{array}{ll} \text{maximize} & c'x\\ \text{subject to} & l \leq Ax \leq u\\ & x'Qx + b'x \...
1
vote
1answer
53 views

Finding maximum of $y-z$ given quadratic constraint

Problem According to my friend, this is a problem that seems to be solvable by observation. Try to find the maximum of $(y-z)$ given following two constraints $$ \begin{aligned} x+y+z=3\\ x^2+y^2+z^...
1
vote
4answers
82 views

Difficulty finding Lagrange multiplier because of $\leq$

Let $f: \mathbb R^3 \to \mathbb R$ be defined by $$f(x,y,z)=x-y+z$$ and $$E:=\{(x,y,z)\in \mathbb R^{3} \mid x^2+2y^2+2z^2\leq1\}$$ Find the extrema of $f$ on $E$. Path: I have already proven that ...
1
vote
1answer
66 views

Find a minimum and a maximum of expression $E(x,y,z)=x-2y+z$

Find minimum and maximum of $E(x,y,z)=x-2y+z$ where $2x^2+y^2+z^2=3$. For finding the maximum of the expression I first thought using the inequality of Cauchy-Buniakowski-Schwarz: $$\boxed{(ax+by+cz)^...
3
votes
2answers
51 views

Lagrange multiplier when decisions variables are not in the same set

Find the maximum of $2x+y$ over the constraint set $$S = \left\{ (x,y) \in \mathbb R^2 : 2x^2 + y^2 \leq 1, \; x \leq 0 \right\}$$ I want to use Lagrange multipliers to find the optimal solution. ...
0
votes
1answer
48 views

Optimization of linear objective with quadratic integer constraint

Is there any way to solve an linear optimization problem with quadratic integer constraint? E.g. $\max a^Tx$, $x=\langle x_1,x_2,\cdots,x_n \rangle$ s.t. $x_ix_j<b_{ij}$, $\forall x_i,x_j \in x$ ...
2
votes
1answer
179 views

Optimality condition for convex QCLP

I am trying to get the optimality condition for the following problem $$\begin{array}{ll} \text{minimize} & c^T y\\ \text{subject to} & Ay = 0\\ & y^T B y \le 1\end{array}$$ where $B$ is ...
2
votes
1answer
306 views

Optimization of linear objective with non-convex quadratic constraint

Is there any technique to deal with a problem where we have a linear objective function and one or many quadratic non-convex function(s) like the problem below? $$\begin{array}{ll} \text{minimize} &...
1
vote
1answer
194 views

Boolean quadratically constrained linear program (QCLP)

1) I have the following problem that I would like to first solve optimally but I have not been able to express it in a way that can be accepted by Matlab optimization functions. $$\begin{array}{ll} ...
1
vote
1answer
749 views

Solving linear program with 1 quadratic constraint complexity

Consider the following linear program, $$\min y \\ xc_1 \leq c_2 + yz,\\ x = x_1 + \dots + x_n,\\ z \leq x_1 + x_2, \\ z \leq x_2 + x_3, \\ \vdots\\ z \leq x_{n-1} + x_n, \\ x,x_1, \dots, x_n,y,z \...
6
votes
4answers
97 views

If $a,b$ are positive integers and $x^2+y^2\leq 1$ then find the maximum of $ax+by$ without differentiation.

If $x^2+y^2\leq 1$ then maximum of $ax+by$ Here what I have done so far. Let $ax+by=k$ . Thus $by=k-ax$. So we can have that $$b^2x^2+(k-ax)^2 \leq b^2$$ $$b^2x^2+k^2-2akx +a^2x^2-b^2\leq 0 $$ By ...
2
votes
2answers
110 views

How to prove the maximum of n-dimensional linear function $a^Tx$ is $||a||_2$ for $||x||_2 \le 1$

I can get it when $x \in \mathbb R$, but I cannot understand why $$\sup\{a^Tx \mid \|x\|_2 \le 1 \} = \| a \|_2$$ when $x \in \mathbb R^n$. To my understanding, this problem can be transformed into ...
2
votes
3answers
330 views

Determining the minimum of a linear function subject to a quadratic inequality constraint

What is the minimum value of $x+4z$, a function defined on $\mathbb{R^3}$, subject to the constraint $x^2 + y^2 +z^2 \leq 2$? I know how to solve this if the constraint is an equality, but what shall ...
0
votes
1answer
132 views

Maximize $\mbox{tr} (AX)$ subject to $\mbox{tr} (BX'CX) = 1$

Suppose $A,B,C$ are given square matrices and $X$ is a matrix variable. Is there a nice way to express the following? $$\begin{array}{ll} \text{maximize} & \mbox{tr} (AX)\\ \text{subject to} &...
0
votes
0answers
438 views

Python solver for a linear objective function with quadratic constraints

I need to optimize a problem of the following form within Python $ minimize$ $\qquad abs(\Delta w) \;\epsilon^T$ $s.t.$ $\qquad(w+\Delta w)C(w+\Delta w)^T \; \le 9500 (some\; finite\; number) \\\\[...
1
vote
2answers
247 views

How to solve this convex optimization problem (with absolute and linear objective function)?

I have the following problem: \begin{align*} \sup_y&\quad \big | \langle u,y \rangle\big |\\ \mbox{s.t.}&\quad \frac{1}{2}\langle y,y \rangle\ + \langle b,y \rangle\ \geq \gamma. \end{align*...
2
votes
2answers
808 views

Linear objective function with quadratic constraints

The context is ordinary multivariate regression with $k$ (>1) regressors, i.e. $Y = X\beta + \epsilon$, where $Y \in \mathbb{R}^{n \times 1}$ vector of predicted variable, $X \in \mathbb{R}^{n \times (...
3
votes
1answer
142 views

Indefinite quadratic constraint

I'm trying to solve an optimization problem with a linear objective function and mostly linear constraints. However, I do have several constraints of the form $$\sum_{i=1}^m x_i\phi_i - \left(\sum_{...
1
vote
1answer
87 views

How to maximize $\langle X, Y \rangle$ over $X$ under constraint s.t $\mbox{Tr} (X^TAX)=1$?

Maximize $\langle X, Y \rangle$ over $X$ subject to the constraint $\mbox{Tr} (X^TAX) = 1$. Here $A$ is positive semi-definite and also all matrices have real entries and $Y$ is a known matrix given ...
0
votes
4answers
123 views

Maximize $\langle \mathrm A , \mathrm X \rangle$ subject to $\| \mathrm X \|_F = 1$

Given $\mathrm A \in \mathbb R^{m \times n}$, $$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \| \mathrm X \|_F = 1\end{array}$$ I can ...
0
votes
2answers
968 views

Minimize linear objective subject to unit norm constraint

I have a linear function with unit norm constraint that I need to minimize. $$\begin{array}{ll} \underset{w}{\text{minimize}} & w^\top x\\ \text{subject to} & \|w\| = 1 \end{array}$$ Is ...
2
votes
1answer
2k views

Maximizing a linear function over an ellipsoid

Let $A \in \mathbb{R}^{n\times n}$ be a positive definite matrix, $x \in \mathbb{R}^n$ and $c \in \mathbb{R} \setminus \{0\}$. I got to determine the maximum $$\max\{c^Ty:y\in \mathcal{E} (A,x)\}$$ ...
2
votes
2answers
869 views

Linear programming with quadratic constraints

I have a given set of variables: $x_1,y_1,x_2,y_2,x_3,y_3$ The objective function is to minimize the sum of these with quadratic equality constraints: $y_1(x_1+x_2+x_3)$=0 $y_2(x_2+x_3)$=0 $y_3(...
1
vote
1answer
417 views

Linear programming with non-convex quadratic constraint

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard? $\min c^Tx$ s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in \mathbb{R}_+^n,Q\in\...
9
votes
2answers
2k views

Linear programming with one quadratic equality constraint

I have a problem that can be formulated as a linear program with one quadratic equality constraint: where variable $x$ is an $n$-dimensional vector and $H$ is a positive semidefinite $n \times n$ ...
3
votes
1answer
2k views

How to solve a quadratically constrained linear program (QCLP)?

Can anybody suggest some techniques to solve a quadratically constrained linear program (QCLP)? Any references on standard techniques would be helpful.