1
$\begingroup$

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 that the variables $(A_ix+b_i,c^T_ix+d_i)$ should belong to a second-order cone of appropriate size.


I don't see why the variables are in a second-order cone. According to the text, a second-order cone is the set

$$C = \left\{ (x, t) \in \Bbb R^{n+1} : \| x \|_2 \leq t \right\}$$

is $t$ the same as $c_i^Tx + d_i$? Can someone tip me off to how this is a cone? It seems like a set of all hyperplanes less than or equal to a line for each i ?

$\endgroup$
2
  • $\begingroup$ Which book? Boyd & Vandenberghe's Convex Optimization? $\endgroup$ May 7, 2023 at 10:31
  • $\begingroup$ Just use different dummy variables in the description of $C$ and it will become clear. $\endgroup$
    – littleO
    May 7, 2023 at 10:34

3 Answers 3

1
$\begingroup$

The cone $C$ can be visualized as in https://docs.mosek.com/modeling-cookbook/cqo.html#quadratic-cones. In 3 dimensions it really is like an ice-cream cone.

And then instead of the pair $(t,x)$ you have the pair $(c^Tx+d,Ax+b)$, and the inequality they satisfy remains the same, so it is just some affine transformation of the cone $C$ (squeezing, stretching, shifting, rotating). See also https://docs.mosek.com/modeling-cookbook/cqo.html#second-order-cones

$\endgroup$
3
  • $\begingroup$ Thanks for your answer; I read the link. How can I get the intuition to what is going on in the transformation? $\endgroup$
    – Frank
    Jan 16, 2020 at 1:57
  • $\begingroup$ @Frank Well it's just arbitrary linear transformations. The important thing is that SOCP is a certain way of writing certain quadratic constraints and being able to recognize when to use it. Try not to overthink the general form but look at some concrete examples. $\endgroup$ Jan 16, 2020 at 17:35
  • $\begingroup$ Thanks. Things like this drive me crazy, if you happen to run across a good chapter of a text that is specifically about cones, please let me know. $\endgroup$
    – Frank
    Jan 17, 2020 at 1:56
1
$\begingroup$

I tried to code it: Code and record it: VideoLink

Hope this may helpful to you.

$\endgroup$
0
$\begingroup$

I was also trying to imagine what second order constraint looks like and what does $A$, $b$, $c$, and $d$ control in the $||Ax + b||_2 \leq c^Tx + d$ constraint.

So, let us try to imagine this in 2D plane. We can rewrite this constraint as

$||Ax-x_0||_2 \leq c^T(x - x_1)$

Now, let us take example when $A$ is indentity and $c$ is $(1, 0)$ and $x_1$ is $0$, then the constraint means all those points, whose norm from $x_0$ is equal to distance from the directrix at origin!

Which is nothing but a parabola! now if $c$ was say $(e,0)$ then we can write that as $e*(1,0)$ and then we have ellipse (or hyperbola) with e as an eccentricity.

So $c$ controls the direction of the directrix, $d$ controls it's position and $b$ controls the position of the focii.

Now to understand what $A$ does. We can also write the constraint as

$||Ax - x0||_2 \leq (c^TA^{*})Ax - x_1$, $A^*$ is pseudo inverse

$||x^\prime - x0||_2 \leq f^Tx^\prime - x_1$ which is same thing just in a distorted (affine) coordinate system.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .