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.
Best Answer
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.