# Do primal-dual methods need to start with strictly a feasible point?

I'm learning about Primal-Dual interior point algorithms from Boyd & Vandenberghe Convex Optimization, ch.11.7. Now the text mentions:

In a primal-dual interior-point method, the primal and dual iterates are not necessarily feasible.

However, when describing the algorithm more, it is stated:

Now consider the Newton step for solving the nonlinear equations rt(x, λ, ν) = 0, for fixed t (without first eliminating λ, as in §11.3.4), at a point (x, λ, ν) that satisifes f(x) ≺ 0, λ ≻ 0.

The text then describes the Newton step, and later on a modified backtracking line search to ensure that $$\lambda$$ stays positive / dual feasible. It reads to me like from this quote onwards we need our iterates to be strictly feasible...?

Do I need an initial strictly feasible $$x, \lambda$$ with which to start my primal dual method? This seems to contradict the first quote.

For my particular problem it would be much more convenient to start with a not-necessarily feasible point. Also, my model of the inequality constraint functions changes at every iteration ideally (I am doing sequential convex optimization).

Hence I want an iterative method such that after every iteration I don't need to solve a phase I/II problem to get a feasible starting point (let alone strictly feasible?). Computation time is a major concern. Is the primal dual algorithm a good choice for me? Cheers.

• Listed Commented Apr 18, 2021 at 15:48

Make no mistake, the book Convex Optimization is a fantastic resource for learning about convex optimization. I am very biased; Prof. Boyd was my Ph.D. advisor, and we still work together. I also know Prof. Vandenberghe personally and respect him greatly as well. But I've also taught courses in convex optimization using the book. I stand by my opinion!

That said, that book does not attempt to teach you how to build a state-of-the-art convex optimization algorithm. Instead, it's just giving you the basics, and in the process it makes some common simplifying assumptions, like strict primal and dual feasibility. Whereas the book teaches you about barrier methods, most state-of-the-art algorithms today employ what is called a symmetric primal dual method. There are very good reasons to do this, including the ability to start from an infeasible point, and even the ability to handle problems that are not strictly feasible in the first place. And yet, the computations involved in barrier methods are actually extremely similar to the ones employed in symmetric primal-dual methods. So the book does a reasonably good job as an introduction to the way things are actually done.

You are not going to get an answer here on Math.SE on how to implement your own custom solver that can handle infeasible starting points. That's simply beyond the scope of the forum. I recommend Google searches for infeasible interior-point methods, symmetric primal dual methods, and homogeneous self-dual embedding. This last term refers to a technique that allows some of the best solvers out there (e.g., MOSEK, Gurobi [i think], ECOS, CVXOPT, SeDuMi, SDPT3) to handle infeasible and unbounded problems. Be prepared for some thick reading material.

Perhaps you should reconsider whether or not it is wise to even try to implement your own algorithm. There are a lot of good convex optimization engines out there, why would you try and reinvent the wheel? Yes, I know you want to do sequential convex optimization. But that just means you have a lot of things to worry about besides whether or not your internal convex optimization loop is as fast as it could be. Get something working first before you spend time reinventing the wheel.

If you must build your own solver: again, do what ever works first. If the numerical results you get out of it are good, then think about what it takes to speed things up; at least you know the effort will be worth it. If the numerical results don't look good, then its speed is irrelevant---unless you like getting bad results faster.

• Excellent answer! I'm actually fairly comfortable with the software implementation side, my concern is the math theory - for using any primal-dual method. My problem is convex with quadratic inequalities. If I seed the algorithm described in the book with say $x = ones(n,1)$, $\lambda = ones(m,1)$, $\nu = ones(p,1)$ which is not necessarily feasible, is the PD algorithm guaranteed to "work" in the sense that an infeasible newton start method would?
– JDS
Commented Mar 17, 2015 at 15:26
• Technically I could just run CVX in an inner loop over and over again as I update my quadratic inequality constraint functions... but my simulations might end up taking too long. Plus in this research I want to experiment with updating the inequality function models as I iterate (rather than fully solve, then update model, then solve again). As Prof. Boyd says, there's a lot of room for "self expression" in these type of methods =)
– JDS
Commented Mar 17, 2015 at 15:30
• Regarding your first question, I do not believe the algorithms in the book will be guaranteed to work if you happen to feed them an infeasible starting point. They might, but again, I can't guarantee it. There is a reason there is a lot of research on infeasible-start methods. Commented Mar 17, 2015 at 15:32
• And regarding your idea to update the inequalities at every iteration, that is where you're veering off into unexplored territory. You certainly cannot guarantee that starting at an infeasible point and updating the inequalities at every iteration is going to give you a converging algorithm. A safer option, but one still without guarantees, would be to solve the subproblems to a fixed, but low precision. Don't fix the number of iterations though. (Obviously use a higher precision when you get close to the result.) Commented Mar 17, 2015 at 15:36
• Not really. That's an unsymmetric method. If you have quadratic inequality constraints, your best bet is to transform them to second-order cone constraints and implement symmetric KKT equations for those. I think you should limit your view to papers whose code you can see and is actively used. There is plenty of material that qualifies, from the implementers of, say, SeDuMi, ECOS, CVXOPT, etc. Commented Mar 17, 2015 at 16:38

In a so-called "infeasible interior-point method", we start with a primal-dual solution that is strictly feasible with respect to the inequality constraints $$x>0$$ and $$z>0$$ but may be infeasible with respect to the primal and dual linear equality constraints $$Ax=b$$ and $$A^{T}y+z=c$$. Nonnegativity is maintained throughout the iterations and feasibility with respect to the primal and dual equality constraints is typically attained after a few iterations.