Questions tagged [second-order-cone-programming]

Second-order cone programming (SOCP).

Filter by
Sorted by
Tagged with
2 votes
1 answer
24 views

Convex constraint for the minimum of a vector

I am solving a second-order cone programming (SOCP) problem. I had to add a constraint that checks if at least one element of the decision variable vector is lower or equal to 0, i.e., I have to add ...
CaG's user avatar
  • 87
0 votes
0 answers
30 views

Reformulation of Convex Constraints

I am trying to reformulate the constraints $$ \alpha^\intercal L \beta + \|L^\intercal \alpha\|_{2}^{2} \leq \rho, $$ where $\alpha\in\mathbb{R}^{n},\beta\in\mathbb{R}^{m}$ and $\rho\in\mathbb{R}$ are ...
Josh Pilipovsky's user avatar
1 vote
2 answers
95 views

Proof regarding center of an optimal Euclidean ball containing distinct points

Suppose we are given $k$ distinct points $a_i \in \mathbb{R}^n$ for $i = 1, 2, \dots, k$, and our objective is to determine the Euclidean ball with the smallest radius that contains all these points ($...
hunterlineage's user avatar
0 votes
1 answer
64 views

Minimum volume sphere bounding all points as a linear programming problem

I want to find the smallest sphere which encapsulate a set of points $x_i \in \mathbb{R}^d$. I can formulate is as $$ \arg \min_{a \in \mathbb{R}^d, r} r \quad\quad \text{s.t.} \quad || x_i - a|| \leq ...
Mark's user avatar
  • 121
1 vote
0 answers
39 views

Dual of quadratically-constrained quadratic program (QCQP) with second order cone constraints

How to derive the dual of a quadratically-constrained quadratic program (QCQP) with second order cone constraint? Here is the optimization problem I want to handle: $$ \begin{array}{rl}\min_{\mathbf{x}...
Kaiming Zhang's user avatar
0 votes
0 answers
50 views

Taylor approximation of exponential constraints

I'm currently tackling an optimization problem that involves an exponential constraint, and I'm trying to apply the following technique to transform it into second-order cones. However, I'm struggling ...
Juan's user avatar
  • 35
0 votes
1 answer
55 views

Is this an example of an SOCP optimization problem?

I'm reading a paper that (vaguely) states that the following problem is an SOCP: \begin{equation*} \begin{aligned} \max& \hspace{0.4cm} f(x_{0},x_{1},\cdots,x_{2n}) \\ \text{subject to}& \...
Dan's user avatar
  • 486
0 votes
0 answers
36 views

How to transforming constraint into Second-Order Cone (SOC) form?

$\sum_{i=1}^n [2(\hat α_k[n]+\hat β_k[n])(α_k[n]+β_k[n])-(\hat α_k[n]+\hat β_k[n])^2-(α_k[n]-β_k[n])^2] \ge 4Nr, \forall k \quad (25)$ $||α_k[1]-β_k[1],...,α_k[N]-β_k[N],\frac {A_k-1}{2}|| \le \frac{...
KxXy_AiLIVe3's user avatar
2 votes
0 answers
85 views

How can I find the geometric median of n points in 2D Euclidean space using high school level calculus and optimization of total distance?

I am a high school student trying to work on a math project. I have plotted the coordinates of all households in a Kenyan village and am trying to locate the geometric median of the set of points to ...
will's user avatar
  • 21
0 votes
1 answer
147 views

Proving convexity of a second-order cone from basic definition of convexity

I am trying to prove that the second-order cone defined as $C = \{(x,t): || x ||_2 \leq t, t\geq 0\}$ is a cone and is convex. I want to use the definition of convexity. Here is what I have so far: ...
hunterlineage's user avatar
1 vote
0 answers
84 views

Is SOCP harder than GP?

As an electrical engineer, I have been studying convex optimization for a while. During my study, I see that most textbooks claim that both second-order cone programs (SOCP) and geometric programs (GP)...
Tuong Nguyen Minh's user avatar
1 vote
0 answers
156 views

Reducing an SDP to an SOCP

Consider a linear estimation setting where we have measurements of the following form. $$ {\bf y} = {\bf H} {\bf x} + {\bf v} $$ where ${\bf y}, {\bf v} \in \mathbb{R}^m$, ${\bf x} \in \mathbb{R}^n$ ...
serpentine's user avatar
3 votes
3 answers
268 views

Find the shortest distance of the curve $\frac{(x-3)^2}{4}+\frac{(y-1)^2}{9}=1$ from the origin

https://math.stackexchange.com/a/185627 Referring to the methods mentioned in this answer, after trying the first method I got a term that looked like this: $$\sqrt{14 + 5\sin^2{\theta} + 6\sin{\theta}...
Grandmaster10's user avatar
0 votes
0 answers
78 views

Second-order-cone programming - Lagrange multiplier and dual cone

In standard nonlinear optimization when we are interested to minimize a given cost function the presence of an inequality constraint g(x)<0 is treated by adding it to the cost function to form the ...
venom's user avatar
  • 233
2 votes
1 answer
208 views

Express as either LP, QP, QCQP or SOCP

I have a problem which needs to be expressed as either LP, QP, QCQP or SOCP. \begin{array}{ll} \text{minimise}_{x,y,t} & a||\mathbf{x}||_2^2 + b||\mathbf{y}||_2^2 \\ \text{subject to}& ||\...
Craig Wilder's user avatar
2 votes
1 answer
107 views

How to convert a quadratic constraint into a conic section constraint (SOCP)?

Given an quadratic optimization program Minimize $\sqrt{X_{1}^2 + 2X_{2}^2 + X_1X_2 - 2X_2 +1} - X_2$ such that. $X_1^2 - 4X_2\leq 3$ I need to rewrite it into an SOCP. And my thought is to ...
Victor Xie's user avatar
0 votes
0 answers
52 views

Sensitivity analysis of SOCP (parametric programming)

Recently I am studying a problem which boils down as follows: $$\epsilon_1 = \underset{\epsilon}{\mathop{\arg \min}}\; \epsilon^{\top}\epsilon$$ $$s.t.\quad \mathbb{a}^{\top}\epsilon + R\|\mathbb{b} + ...
TJ Chang's user avatar
1 vote
1 answer
106 views

How to minimize sum of reciprocals under multiple linear constraints?

Given $A\in(\mathbb{R}_{>0})^{n\times m}$, $b\in(\mathbb{R}_{>0})^{m} $ and $c\in(\mathbb{R}_{>0})^{n}$, $$ \begin{array}{ll} \underset{x \in (\Bbb R_{>0})^n}{\text{minimize}} & f(x) :=...
Logan Shi's user avatar
1 vote
1 answer
107 views

Maximize system of non-linear equations

How to maximize $$Y = \sum_{i=0}^n \frac{a_ix_i}{b_ix_i+c_i}$$ Given the following constraints: $\sum_{i=0}^n x_i = X$ (X is a constant) $x_0, x_1, ..., x_n >= 0$ In the above, $a, b, c$ are ...
iulian's user avatar
  • 113
2 votes
0 answers
172 views

Rewritting QCQP as SOCP

I have a convex function with convex constraints. $$f(p) = \min_\limits{\| b_{0} - A_{0} x \|_{2} \le p} \| x \|_{2} = \min_\limits{\| b_{0} - A_{0} x \|_{2} = p} \| x \|_{2}$$ I was researching a lot ...
nezudem's user avatar
  • 101
1 vote
1 answer
58 views

Integer allocation problem alternative to MI-SOCP?

Can the following problem be solved without needing to use a MI-SOCP solver? I think I can code it as just a simple parallel branch-and-bound search but I'm not sure if the performance will be close ...
Ant's user avatar
  • 13
0 votes
0 answers
64 views

Prove that the constraint cannot be written as a second-order cone constraint

I am to prove that the constraint $x_1x_2=x_3x_4$ (where $x=(x_1, x_2, x_3, x_4)\in \mathbb{R}^n$ and $x_k\geq 0$ for $k=1,2,3,4$) cannot be written as a second-order cone constraint. In other words, ...
FabrizzioMuzz's user avatar
1 vote
1 answer
162 views

Second Order Cone Program with Quadratic Objective Function

The standard form for a Second Order Cone Program (SOCP) is \begin{equation} \begin{array}{c} \min _{x} f^{T} x \\ \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m \end{array} \...
Lea Suttion's user avatar
1 vote
1 answer
78 views

How to transform two non-convex problems to convex problems?

I came cross two non-convex problems, and I wanted to transform them to standard form of convex problems. However, I don't know how to do it. If anyone can provide ideas or give answers, I would like ...
xiuhua's user avatar
  • 441
0 votes
1 answer
221 views

How can I form this second-order conic constraint?

I am trying to show that if we have a real symmetric matrix $Q$ with one negative eigenvalue within a quadratic constraint: $x^\top Qx+a^\top x +b \leq 0$ That this constraint can be formulated as a ...
L. Johnson's user avatar
0 votes
1 answer
141 views

Conic representation of convex hull of unit ball and point

Let $S = \mathrm{conv}(B \cup p)$ where $B = \{x \in \mathbb{R}^2 | x^Tx \leq 1 \}$ and $p = (-2,0)$ Can this set be represented in conic form $Ax \preceq_{\mathcal{K}} b$ where $\mathcal{K}$ is $\...
James's user avatar
  • 31
0 votes
0 answers
677 views

Comparison between SOCP and SDP in terms of computational complexity

Dears If I have an optimization problem with n variables and m constraints that can be solved using the SOCP and SDP, how can I compare the performance of both algorithms using the Big-O notation? I ...
engfrompalestine's user avatar
0 votes
1 answer
148 views

How to convert $\min x^{1.5}$ into a SOCP problem?

I want to optimize: $\min x^{1.5}$ (with some other constraints and variables, but they are not related to this question) using Second Order Cone Programming. Therefore, I wonder how I can do it? ...
ch271828n's user avatar
  • 241
0 votes
1 answer
120 views

SOCP formulation from a convex constraint

Suppose I have the constraint set $$\{x: a_1\|x-b_1\|_2-a_2\|x-b_2\|_2\leq t\}$$ where $a_1,a_2\geq 0$. I know that the function $$f(x)=a_1\|x-b_1\|_2-a_2\|x-b_2\|_2$$ is convex (it is given that $f$ ...
Cherryblossoms's user avatar
0 votes
1 answer
104 views

Is this problem convex?

I'm trying to solve the following max-flow type problem using convex optimization. I have $n$ nodes which each have an input currency $u_i$ and output currency $v_i$. My decision variables are $x_i$ ...
nickponline's user avatar
2 votes
0 answers
175 views

How to Cast a Quadratic Constraint as Convex if Q is a (PSD) Variable?

Background I am working on a stochastic optimal control problem and $x$ represents the state of the dynamic system. The optimal state must be found, but, due to the stochastic nature of the problem, ...
Boris Benedikter's user avatar
2 votes
0 answers
117 views

What does this: $\{a\}\doteq\emptyset$ mean to you? Is this notation acceptable in any sense?

I'm kind of embarassed for asking this question, but... The problem: I'm having a hard time trying to establish a consistent notation for the spectral decomposition of the elements of a second-order ...
Koto's user avatar
  • 909
0 votes
0 answers
347 views

Second Order Cone Program with Quadratic Objective

The standard form for a Second Order Cone Program (SOCP) \begin{equation} \begin{array}{c} \min _{x} f^{T} x \\ \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m \end{array} \end{...
Apprentice's user avatar
0 votes
0 answers
44 views

Quadratic Objective with Second Order Cone Constraint [duplicate]

is there any way to solve the following problem with a quadratic objective and a second-order cone constraint in closed form? $$\min_{x\in\mathbb{R}^d} (x-x_0)^TA(x-x_0) \\\text{subject to } \sqrt{x^T\...
Apprentice's user avatar
0 votes
0 answers
153 views

How to transform L2-norm constraint into SOCP

I was wondering if you could help with the idea of how the following problem can be converted into a standard SOCP. $\underset{\{\mathbf{W}_{1}\}}{\text{min}} \ \| \mathbf{w}_{1} \| ^{2}_{2}\\ \text{s....
A. Mohammad's user avatar
2 votes
1 answer
188 views

Converting problem with norm bound to SOCP problem

I am currently researching some robust control problems, and I ended up with the following optimization problem: \begin{align} \max_{x,w} ~&~ f(x,w) \\ {\rm s.t.} ~&~ g(x,w) \le 0 \\ ~&~ \|...
Miel Sharf's user avatar
1 vote
1 answer
556 views

Maximizing a harmonic mean via SOCP

$$ \begin{array}{ll} \underset {x} {\text{maximize}} & \left(\sum\limits_{i=1}^m \dfrac{1}{a_i^T x + b_i}\right)^{-1} \\ \text{subject to} & Ax > b \end{array} $$ where $a_i^T$ is the $i$-...
user13's user avatar
  • 1,653
0 votes
0 answers
17 views

Transform the following function into its second order cone form

I would like to transform the following function into its second order cone form but I do not know how to do that $$f_\sigma(s)=\frac{\|s\|_2^2}{\|s\|_2^2+\sigma}$$ Thans a lot if you can help me !
Romain's user avatar
  • 1
0 votes
1 answer
84 views

How to reformulate ${\left\| {Ax + b} \right\|^2} \le c + {b^T}b - r$ as an SOCP constraint?

I am running into a constrain that looks quite similar but not really in the standard form of an SOCP. That is: $${\left\| {Ax + b} \right\|^2} \le c + {b^T}b - r$$ Standard form of SOCP: $$\left\| {...
Tuong Nguyen Minh's user avatar
1 vote
0 answers
399 views

Why is a QP a SOCP?

I have seen that QP can be rewritten as a SOCP from several resources online. Why is this the case? More precisely, using relaxation, QP can be written as $$ \min_{x,t} c^Tx + t \quad \text{ subject ...
user808843's user avatar
2 votes
0 answers
55 views

Optimization of a problem with quadratic objective and quadratic constraints and alternative formulations

Suppose we have $A \in \mathbb{R}^{m \times n}$, we want to minimize \begin{align} \min&\quad\|Ax\|_2^2 \\ \text{s.t.}&\quad x^\top C_1x = 1, \\ &\quad x^\top C_2 x = 1, \\ &\quad Dx &...
user4864665's user avatar
0 votes
1 answer
70 views

Why can $\frac{{{x^2}}}{{\sqrt y }} \le t$ be prepresent as the the following equivalent second order cone constraint?

I am quite new to the field of convex optimization and in a research paper that I have read, some author represent this constraint $\frac{{{x^2}}}{{\sqrt y }} \le t$ as equivalent SOC constraint like ...
Tuong Nguyen Minh's user avatar
0 votes
1 answer
67 views

Direction of Steepest Descent within a Polyhedral Cone

Let $\mathbf c \in \mathbb{R}^n$ where $\mathbf c \neq \mathbf 0$ and $\mathbf A \in \mathbb{R}^{m \times n}$. What is the most efficient way to solve the following optimization problem? Even better, ...
Garrett's user avatar
  • 1,491
3 votes
1 answer
78 views

What are mathematicians talking about when using the term programming?

What are mathematicians talking about when using the terms linear programming (LP), quadratic programming (QP), semidefinite programming (SDP), cone programming (CP), dynamic programming (DP), etc? It'...
pmixer's user avatar
  • 61
6 votes
1 answer
250 views

Probability that random variable is inside cone

Suppose $x\in\mathbb{R}^n$ is a random variable with mean $\mu$ and covariance $ \Sigma$. Consider a stochastic convex optimization problem, i.e. an optimization problem with chance constraints, ...
Josh Pilipovsky's user avatar
0 votes
0 answers
887 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 $...
Dan Berkenstock's user avatar
1 vote
1 answer
345 views

Rewriting sum of norms as a SOC constraint

I'm trying to compute the complexity of the following convex problem: \begin{align} \underset{y}{\mathop{\text{minimize} }} \quad & v^Ty \\ \text{s}\text{.t}\text{.} \quad\quad\quad\,\,& ...
aph2004's user avatar
  • 13
1 vote
2 answers
472 views

Trouble visualizing a second-order cone constraint

I have this problem from Boyd's optimization textbook: A standard form for the SOCP model is $$\text{minimize } f^Tx \\\text{subject to: }‖A_ix+b_i‖_2 ≤ c_i^Tx + d_i, i= 1,\dots,m$$ where we see ...
Frank's user avatar
  • 880
3 votes
0 answers
350 views

Convert QCQP into SOCP [closed]

I have to solve the following optimization problem How can I convert this quadratically-constrained quadratic program (QCQP) into a second-order cone program (SOCP)? Is this QCQP convex?
Changhee Han's user avatar
0 votes
1 answer
204 views

Dual of a rotated conic programming

I'm new to convex analysis and got stuck when formulating a dual problem for a rotated conic programming problem. The problem is as follows. $\min \ \ 2x_1+2x_2+x_3-3x_4$ $s.t. \ \ x_1 \leq 7$ $ ...
Taichi's user avatar
  • 3