0
$\begingroup$

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and Idnani (1981):

A Numerically Stable Dual Method for Solving Strictly Convex Quadratic Programs

and I was wondering what they do with equality constraints. In the introduction they say that $x$ may also be subject to equality constraints $\hat{C}^Tx-\hat{b}=0$ but they will ignore these to simplify the presentation. Sadly though I cant find a reference to these later in the paper.

What to do with these type of constraints? Should I split them up into two sets of inequality constraints like this?

$$\hat{C}^Tx\leq\hat{b},\\-\hat{C}^Tx\leq-\hat{b}.$$

Does this method work for the Goldfarb/Idnani (QP) case? Does it work for the Lobo/Vandenberghe/Boyd (SOCP) case? Does it matter that the solution is not in the interior of the set of feasible points when equality constraints are in place? If this does not work, how to deal with these constraints?

$\endgroup$
3
  • 2
    $\begingroup$ I'm not being flippant here: why concern yourself with picking apart an algorithm described in an academic paper from 1981, or even an effectively obsolete piece of software from 1995? Why not focus on the software and underlying algorithms that are actually used in practice on a regular basis? (Make no mistake, Goldfarb is a giant in the business, I'm just saying that I doubt the longevity of this particular contribution.) $\endgroup$ Jan 23, 2015 at 14:18
  • 1
    $\begingroup$ @MichaelGrant Well, you are probably right. The fact is, I want to explore SOCP in more detail and I am looking for open source software projects (non-commercial) on this topic. Even worse, I want to understand the methods used at least concept-wise. If you could point me to the algorithms actually used in practice (from your profile page I am quite sure you know all about them) I would be more than happy to look at them instead! Unfortunately, all R packages with SOCP solvers use this exact 1995 code! $\endgroup$
    – vanguard2k
    Jan 23, 2015 at 15:34
  • 1
    $\begingroup$ That is unfortunate! My personal recommendation is to look at ECOS. You'll find at the GitHub link some references to a paper and a thesis that describe the design of the algorithm, and other references that will help in your study. Full disclosure, I've contributed to that project, but I am not one of the primary developers. $\endgroup$ Jan 23, 2015 at 15:37

1 Answer 1

0
$\begingroup$

In general an equality constraint can be handled by using it to eliminate one of the variables (using ordinary linear algebra) before any of the clever optimization algorithms is let loose on the problem.

This works well for a general optimization algorithm, but if one wants to allow your method to be specialized to a particular sparse shape of the goal functions and/or constraints by providing optimized solvers for subproblems, one may have to handle equality constraints more explicitly during the algorithm proper.

$\endgroup$

You must log in to answer this question.

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