Questions tagged [socp]

Second-order cone programming (SOCP).

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Comparisons of Solving Speed of QP & SOCP

For two same scale optimization problem, quadratic programming (QP) and second-order cone programming (SOCP), which one is faster to solve? As far as I know, the computational complexity of QP and ...
4
votes
1answer
55 views

Is there a second-order conic relaxation method for the bilinear term $z=xy$? [closed]

I hope to find a second-order conic (SOC) relaxation for $z = xy$, but it seems very hard.
1
vote
1answer
40 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 & ...
2
votes
1answer
43 views

Convexity of the logarithmic barrier function of SOCP

The logarithmic barrier function for second-order cone programming (SOCP) is usually $$F(x) = \log \left( x_n^2 - x_1^2-\cdots - x_{n-1}^2 \right)$$ How to prove its convexity? The Hessian is too ...
1
vote
0answers
33 views

What methods can solve SOCP problems?

What methods can solve SOCP problems? I need at least few different. By: https://en.wikipedia.org/wiki/Second-order_cone_programming it seems that the problem "reduces" to simpler problems, but I'...
0
votes
1answer
50 views

Why is this problem (multiuser transmit beamforming problem) an SOCP?

I am reading this article, in which the authors state that the problem \begin{equation*} \begin{aligned} & \min_{\mathbf w_1 \cdots \mathbf w_K} \sum_{k = 1}^K ||\mathbf w_k||_2^2\\ & \text{s....
0
votes
1answer
130 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-...
0
votes
1answer
41 views

Cone reformulation

Consider: Where $v$ and $Y-X\beta$ are columns of the same length, say $n$. I would like to understand how to go from the first display to the second.
0
votes
0answers
91 views

Dual of a convex SOCP

I'm reading up on convex optimization this summer and wanted to check my understanding of an example problem. $$\begin{array}{ll} \text{minimize} & \| x \|_2\\ \text{subject to} & \...
0
votes
0answers
29 views

Can this problem be represented as a second-order cone program?

$LOU_{min} = \underset{(m_1,\dots,m_n)\in\mathbb{R}^n}{\text{min}} \sum_{i=1}^N - u_i\left(m_i\right)$ $ 0.1 \leq m_i - b_i < p_i \qquad \forall i \in \{1,\dots,n\}$ $p_i - m_i \leq rmax_i \...
0
votes
0answers
70 views

Formulate as Second-order Cone Programming $minimize \frac{\|Ax-b\|^2_1}{1-\|x\|_\infty}$

I have this as problem and do not know how to solve it: Formulate the following problem as SOCP: $minimize \frac{\|Ax-b\|^2_1}{1-\|x\|_\infty}$ Anyone can help me or give me guidelines.
0
votes
1answer
63 views

What is the geometric representation of a mixed integer second order cone program?

Just as the title suggests, what is the geometric representation of a MISOCP? I know a SOCP can be geometrically (or visually) described as a cone... what about a mixed integer second order cone ...
1
vote
1answer
917 views

Dual of a Second Order Cone Program (SOCP)

I was reading on second order cone programs https://www.di.ens.fr/~aspremon/PDF/MVA/Duality.pdf page 33 and have trouble trying to derive its dual. While I am able to formulate the lagrangian easily, ...
1
vote
0answers
48 views

How to convert $z^2 = \theta y^2$ to second order cone constraint?

I have difficulties converting a constraint to a SOC constraint. Here is the full problem: \begin{align} \text{minimize} &\quad \alpha \nonumber\\ \text{subject to} &\quad \sum_{...
0
votes
0answers
43 views

SOCP Complementary Slackness Condition Confusion

So I know that for an SOCP, the complementary slackness condition together with the cone constraints are: $$ \mathbf{s}^{T}\mathbf{x} = 0$$ $$ s \underset{K}{\geq} 0 $$ $$ x \underset{K}{\geq} 0 $$ ...
1
vote
0answers
38 views

Conic Linear Program for Finding a center in the plane minimizing maximum distance from center to points

I struggle solving a task related to Conic Linear Optimization. This is the task: "Consider the set of points D = $\{a_1, ..., a_n\}$ $\subset$ $\mathbb{R}^2$. Formulate as a conic problem the ...
0
votes
0answers
44 views

Trust regions cause optimization problem to blow up

I’ve seen many papers (for example, this one on sequential convex programming) where non-convex problems are solved with convex optimization methods by first linearizing the problem at iteration $k$ ...
2
votes
2answers
100 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
1answer
522 views

Reformulating a Euclidean distance minimization problem into a semidefinite program

The following minimization problem is a Euclidean distance form of a single-facility location problem $$\min \quad \sum_j \sqrt {(x-a_j)^2+(y-b_j)^2}$$ where $(x,y)$ and $(a_j,b_j)$ are the ...
1
vote
0answers
54 views

How to rewrite this problem in an equivalent SOCP form?

Suppose I have problem like this: \begin{equation*} \min_x\left\{f^Tx:\sum^n_{i=1}\left\lvert x_i-x^0_i\right\rvert^{3/2} \le t\right\}, \end{equation*} How can I recast it into SOCP? I have some ...
2
votes
0answers
1k views

QCQP as a SDP or SOCP?

I have a QCQP as shown below: \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x}^{T}\cdot\mathbf{P}\cdot\mathbf{x}\\ & \text{subject to} & ...
-1
votes
1answer
178 views

minimizing sum of reciprocal via socp

Given $x_1$, $x_2$,..., $x_n$, with $x_i>0 \forall i \in[1,n]$ I would like to minimize via SOCP the following cost function $$J = ||\sum_{i=1}^n{\frac{\alpha_i}{x_i}}-K||$$, with $K>0$ and $\...
2
votes
1answer
1k views

Can a convex QCQP with an additional linear constraint be converted into a SOCP?

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} &...
0
votes
0answers
45 views

Eliminating variables from an SOCP

Given an SOCP problem $$ \begin{array}{ll} \text{minimize}&w^Tx\\ \text{subject to} &\|A_i x + b_i\|_2 \le c_i^T x + d_i ~~~~~~~ 1 \le i < N\\ \end{array} $$ where $x$ is partitioned into ...
2
votes
1answer
663 views

SOCP with a norm constraint

Is it possible to convert this optimization problem into a SOCP: \begin{eqnarray} \min && c^T x \\ s.t. && \|A_ix + b_i \|_2 \le c_i^T x + d_i \\ && \| Dx \|_2 = g \end{...
1
vote
0answers
505 views

SOCP or SDP optimization problem

I am studying an optimization problem \begin{equation} \mathbf{w}^* = \text{argmax} \sum_{d=1}^D \log \bigg( \frac{|\mathbf{f}_d^H\mathbf{w}|^2+c_1}{|\mathbf{f}_d^H\mathbf{w}|^2+c_2} \bigg)\\ \\ \...
1
vote
1answer
157 views

SOCP formulation: wrong inequality direction in constraints

The problem is constrained by a set of inequalities in the form of $$ \| A_i\mathbf{x}\|\geq \mathbf{y_i^Tx} $$ where x is a n-vector of unknowns, $A_i$ are matrices and $y_i$ vectors. Is it possible ...