How does SOCP work? Also, how can they get away with a linear approximation?

[ers...@md.metrocast.net]

I am trying to implement the algorithm published here which uses Second Order Conic Programming (SOCP) via SeDuMi to find an optimal design. Most published algorithms on this topic use either SOCP or Semi Definite Programming (SDP). The paper referenced above says, "The presence of of the denominator polynomial in IIR filters make their design more challenging than that of FIR filters because it results in a highly nonlinear objective function that requires highly sophisticated optimization methods." I am wondering why SOCP and SDP are almost always used. What is the basic idea to how SOCP works, and what makes it more effective than many alternative optimization algorithms? Another thing that puzzles me is that the objective function, in the paper referenced above, is a linear approximation of the problem they really need to solve. As I understand it, a linear approximation is needed to make the problem suitable for SOCP. Wouldn't use of a linear approximation mess up everything when the algorithm still has to wonder through several hills and valleys before it gets to the global minimum?

[Erling D. Andersen]

The history goes like this. In 1984 Karmarkar developed a new method for LP that had polynomial complexity. A variant of Karmarkars idea notably the primal-dual interior-point algorithm also worked extremely well in practice for LP.

Now when you try generalize the primal-dual algorithm it can really only be generalized to problems of the form

   min c'x

   st Ax=b

       x \in K

where K is a symmetric cone.  Symmetric cones includes the linear, quadratic and semi-definite cone cases. There is some papers by Todd and Nesterov showing this. That is why codes such as SeDuMi and MOSEK can handle this type of problems

because for this class of problems we have superior algorithms. 

If you want to know more about the algorithm for SOCP you can check out

   http://www.mendeley.com/download/public/11467401/4702721365/90ef5290d1f3c913bd1a085ca47de0b710e452db/dl.pdf

which also provides a lot references.

[Rennie T]

Hi. Have you implement this algorithm successfully? I have trying to implement it for several months. But I still cannot get a similar result. There are some questions puzzle me:
· What is value of gama_pb, gama_sb, i.e the constant limiting p-norm of passband and stopband constrain?
· For fixed group delay method, is there any possibility that initial solution obtained from Model Reduction cannot satisfy the constrain for stopband? If it is possible, why the model did not include a slack variable for stopband constrain?
·For constrain which limit the 2-norm of delta, I cannot understand why we can relax this constrain because I think if we relax it, then the linear approximation may lead to a bit large error.
And could you please send me your code? I'm really appreciate if you don’t mind sharing them with me!

[Johan Löfberg]

Have you tried contacting the authors of the paper? That is always the most obvious start....

[Erling D. Andersen]

If you use MOSEK and logging is turned on then it prints our a solution summary. That is very useful for checking whether the optimizer solved the formulated problem.

Maybe you could paste the log output into a reply.

If that is the case, then the formulation must be wrong. 

[Rennie T]

Thanks for your kind suggestion. I have sent email but have not received reply. BTW, thanks for creating YALMIP! It's really a cool tool for optimization. I was excited when I found it.

[Rennie T]

I use yalmip to solve it. I think the solver had successfully solved each iteration for the iterative algorithm proposed by that paper. If the solver I choose is mosek, then the log of first iteration is as following:
MOSEK Version 7.1.0.44 (Build date: 2016-1-8 13:36:44)
Copyright (c) 1998-2016 MOSEK ApS, Denmark. WWW: http://mosek.com
Platform: Windows/32-X86

Computer
Platform : Windows/32-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 30
Cones : 924
Scalar variables : 3843
Matrix variables : 0
Integer variables : 0

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries : 0 time : 0.00
Eliminator - elim's : 0
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 28
Optimizer - Cones : 924
Optimizer - Scalar variables : 3841 conic : 2795
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 402 after factor : 406
Factor - dense dim. : 0 flops : 2.68e+006
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.0e+003 1.6e+000 1.2e+001 0.00e+000 6.919754462e+002 0.000000000e+000 1.0e+000 0.05
1 5.6e+002 8.9e-001 6.4e+000 -7.80e-001 6.999708771e+002 1.409798784e+002 5.4e-001 0.08
2 4.6e+002 7.4e-001 5.3e+000 1.25e+000 -5.386091937e+002 -8.648006325e+002 4.5e-001 0.09
3 3.6e+002 5.8e-001 4.1e+000 9.89e-001 -6.817516996e+002 -9.157505744e+002 3.5e-001 0.09
4 2.2e+002 3.5e-001 2.5e+000 1.28e+000 -7.682617431e+002 -8.880227276e+002 2.1e-001 0.09
5 2.0e+002 3.2e-001 2.3e+000 1.34e+000 -7.881795555e+002 -8.971351123e+002 1.9e-001 0.09
6 1.7e+002 2.7e-001 1.9e+000 1.05e+000 -8.703390131e+002 -9.657691563e+002 1.6e-001 0.11
7 5.1e+001 8.1e-002 5.8e-001 8.72e-001 -9.654507013e+002 -9.965767149e+002 4.9e-002 0.11
8 1.7e+001 2.7e-002 1.9e-001 1.28e+000 -7.660213995e+002 -7.750173648e+002 1.6e-002 0.11
9 4.2e+000 6.7e-003 4.8e-002 1.24e+000 -7.344340534e+002 -7.363791509e+002 4.1e-003 0.11
10 2.1e+000 3.4e-003 2.4e-002 1.22e+000 -7.390552948e+002 -7.399461556e+002 2.0e-003 0.13
11 1.7e+000 2.8e-003 2.0e-002 1.13e+000 -7.402439851e+002 -7.410077074e+002 1.7e-003 0.13
12 3.8e-001 6.1e-004 4.4e-003 1.10e+000 -7.430420882e+002 -7.432014346e+002 3.7e-004 0.13
13 2.4e-001 3.9e-004 2.8e-003 9.43e-001 -7.436390931e+002 -7.437444006e+002 2.4e-004 0.13
14 1.8e-001 3.0e-004 2.1e-003 7.90e-001 -7.440322802e+002 -7.441183901e+002 1.8e-004 0.14
15 9.3e-002 1.5e-004 1.1e-003 1.06e+000 -7.447586750e+002 -7.447994689e+002 9.1e-005 0.14
16 4.6e-002 7.3e-005 5.3e-004 8.19e-001 -7.453304881e+002 -7.453528447e+002 4.5e-005 0.14
17 1.1e-002 1.8e-005 1.3e-004 1.02e+000 -7.457948354e+002 -7.458002661e+002 1.1e-005 0.14
18 3.2e-003 5.1e-006 3.7e-005 9.90e-001 -7.459143599e+002 -7.459159153e+002 3.1e-006 0.16
19 6.4e-004 1.0e-006 7.4e-006 9.94e-001 -7.459593250e+002 -7.459596386e+002 6.2e-007 0.16
20 1.1e-004 1.8e-007 1.3e-006 9.98e-001 -7.459696081e+002 -7.459696637e+002 1.1e-007 0.16
21 2.3e-005 3.6e-008 2.3e-007 9.99e-001 -7.459715091e+002 -7.459715188e+002 2.2e-008 0.16
22 4.3e-006 4.1e-009 2.7e-007 1.00e+000 -7.459719586e+002 -7.459719465e+002 2.5e-009 0.17
23 4.3e-006 4.1e-009 2.7e-007 1.00e+000 -7.459719586e+002 -7.459719465e+002 2.5e-009 0.17
Interior-point optimizer terminated. Time: 0.17.

Optimizer terminated. Time: 0.34

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : NEAR_OPTIMAL
Primal. obj: -7.4597195865e+002 Viol. con: 2e-003 var: 0e+000 cones: 0e+000
Dual. obj: -7.4597194653e+002 Viol. con: 0e+000 var: 6e-009 cones: 0e+000
Optimizer summary
Optimizer - time: 0.34
Interior-point - iterations : 23 time: 0.17
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Clean primal-dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Primal-dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Mosek error: MSK_RES_TRM_STALL ()

sol =

yalmiptime: 1.7708
solvertime: 0.4162
info: 'Successfully solved (MOSEK)'
problem: 0
solveroutput: [1x1 struct]
solverinput: [1x1 struct]

Do you find anything wrong?

[Johan Löfberg]

Looks ok.

[Rennie T]

Thank you anyway!