All Questions
Tagged with qclp optimization
49 questions
1
vote
2
answers
121
views
Analytical solution for equality-constrained QCLP
I'm looking for a way to derive a closed form expression for $\omega$, which is the solution of the following maximization problem:
$$\max_{w} \omega^{T}\mu$$
$$\textrm{st.}\hspace{0.5cm} \omega^{T}\...
- 123
1
vote
2
answers
260
views
Linear program plus sphere constraint
I have the following optimization problem:
\begin{align}
\min_{x} \quad & x^\top \hat{x} \\
\text{s.t.} \quad & x^\top a_i \leq 0, \quad \forall i \in \{ 1,\ldots,N \} \\
& \|x\|_2 = 1,
\...
- 783
0
votes
0
answers
90
views
Dual formulation of a QCLP
I'm working on a quadratic constrained linear program (QCLP) which I'm trying to obtain its dual formulation. I would like this formulation to be linear, or at least convex. Here are my results so far....
- 1
1
vote
0
answers
109
views
Solving a QCLP with both equality and inequality quadratic constraints
I have the following quadratically-constrained linear program (QCLP)
$$ \begin{array}{ll} \underset {x} {\text{minimize}} & -c^T x \\ \text{subject to} & x^T Q x \leq a^2 \\ & x^T L x = 1 \...
2
votes
1
answer
76
views
Gradient of Lagrangian can not be set to 0
I am trying to solve the following constrained optimization problem:
$$ \begin{array}{rl} \underset{V \in \Bbb R^{D \times d}}{\operatorname{minimize}} & \operatorname{trace} \left( W V^\top \...
- 21
1
vote
3
answers
114
views
How to deal with the constraint $a \leq \|x\|_2 \leq b$ in an optimization problem?
How to solve the following optimization problem?
$$\begin{array}{c l} \underset {x} {\text{minimize}} & c^{\top} x\\ \text{subject to}~& a \leq \|x\|_2 \leq b
\end{array} $$
Can we convert it ...
- 697
2
votes
1
answer
122
views
Maximizing linear objective subject to quadratic equality constraint
I've been trying to get through some practice questions on the Karush-Kuhn-Tucker (KKT) theorem but I can't seem to answer the following.
Given $f, g : \mathbb{R}^2 \to \mathbb{R}$ defined by $f(x) :=...
- 21
0
votes
1
answer
342
views
Explicit solution of an QCLP
Give an explicit solution of the following QCLP $$\begin{split} & c^\top x \to \min\limits_{x \in \mathbb{R}^n }\\ \text{s.t. } & x^\top A x \leq 1\end{split}$$ where $A \in \mathbb{S}^n_{++}$ ...
1
vote
1
answer
91
views
Sketch the graph of $ f (x_1, \: x_2) = x_2 $ over $ x_1 ^ 2 + x_2 ^ 2 \leq 2 $ and find the maximum value of $ f $.
Sketch the graph of $ f (x_1, \: x_2) = x_2 $ over $ x_1 ^ 2 + x_2 ^ 2 \leq 2 $ and find the maximum value of $ f $.
The graph would be what's inside the cylinder, I think. My affirmation is that the ...
- 880
0
votes
1
answer
727
views
Maximize $f(x,y) = x+y$ subject to $x^2+xy+y^2+y=1$
I'm stuck trying to find the maximum value and at which point it occurs of the function
$$f(x,y) = x + y,$$
subject to the constraint $x^2 +xy +y^2 + y = 1$.
my working so far is
$f_x = \lambda g_x \...
- 3
1
vote
2
answers
141
views
How can I solve this maximization problem with inequality constraint on the Frobenius norm?
$$
\max_{C\in \mathbb{S}^n} x^TCx\\
s.t. \|C\|_{tr}^2\leq b
$$
where $\|C\|_{tr}^2=tr(C^TC)=tr(CC)$, $C$ is a symmetric matrix.
- 11
1
vote
1
answer
390
views
Solve with KKT min $x_1-4x_2+x_3$
Given min $x_1-4x_2+x_3$
s.t $x_1+2x_2+2x_3=-2$
$||x||^2\leq1$
(i)Given a KKT point of the problem above,must it be an optimal solution?
(ii) Find the optimal solution of the problem using KKT ...
- 1,898
0
votes
1
answer
282
views
Linear objective with quadratic equality constraint
I've been given a problem:
min $f(x) = c^Tx$
s.t.
$\sum_{i}x_i = 0$
$\sum_{i}x^2_i$ = 1
I've created the Lagrangian function
$L(x,\lambda) = c^Tx - \lambda_1\sum_{i}x_i - \lambda_2\left(\left(\sum_{i}...
- 478
0
votes
0
answers
330
views
Solve Mean-Variance Problem by Expected Return Maximization
One period market with n securities with return R~ $N(\mu,\Sigma)$. An expected return on each security is $\mu_1,\dots,\mu_n$
Investor has 1 unit of wealth and invests into n assets, with weights $...
- 128
1
vote
1
answer
221
views
Maximize $a^T x$ with constraint on $2$-norm of $x$
In a textbook i'm reading, a maximization statement is given to maximize $a^Tx$ where the 2-norm of $x$ is smaller or equal than $c$, where $a$ and $x$ are vectors and $c$ is a scalar. The answer is ...
- 371
1
vote
2
answers
2k
views
Linear program with quadratic (L2 norm) constraint
I would like to solve an optimization problem of the type
$$ \min_x x^T c, \quad s.t. \|x\|_2 \leq k \; \land \; a \leq x_i \leq b \; \forall i$$
efficiently (note the quadratic norm constraint), ...
- 148
0
votes
2
answers
1k
views
Lagrange Multiplier Find Maximum and Minimum
Use Lagrange multiplier to find maximum and minimum of $f(x,y) = 3x-4y$ subject to $x^2+3y^2=129$.
So I start by getting the partial with respect to both f(x, y) and $x^2+3y^2=129$
Ultimately, I get ...
- 173
2
votes
1
answer
189
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} \left(...
- 306
3
votes
1
answer
728
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 ?
- 29
0
votes
3
answers
98
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, ...
user732574
1
vote
1
answer
167
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 ...
- 17.9k
1
vote
2
answers
259
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 ...
- 17.9k
2
votes
2
answers
441
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 $\...
- 332
1
vote
1
answer
143
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 & ...
- 25
0
votes
0
answers
208
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 \ \ \ \ \ ...
- 459
2
votes
0
answers
277
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 \...
- 23
1
vote
1
answer
94
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^...
- 666
1
vote
1
answer
83
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,313
3
votes
2
answers
85
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. ...
- 319
0
votes
1
answer
66
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
1
answer
279
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 ...
- 83
2
votes
1
answer
713
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
1
answer
306
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}
...
- 778
1
vote
1
answer
2k
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 \...
- 741
6
votes
4
answers
116
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 ...
- 6,058
2
votes
3
answers
857
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 ...
user426277
0
votes
1
answer
349
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} &...
- 5,703
0
votes
0
answers
589
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
1
vote
2
answers
608
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*...
- 8,485
3
votes
2
answers
2k
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 (...
- 49
3
votes
1
answer
311
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_{...
- 31
1
vote
1
answer
121
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 ...
- 301
0
votes
4
answers
196
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 think ...
2
votes
2
answers
3k
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 ...
- 143
7
votes
1
answer
4k
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\}$. Determine the maximum $$ \max_{y \in \mathbb{R}^n} \left\{ c^T y : y \in \...
- 1,242
3
votes
3
answers
2k
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(...
- 71
1
vote
2
answers
614
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\...
- 11
11
votes
2
answers
4k
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$ ...
- 111
3
votes
1
answer
3k
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.
- 31