3
$\begingroup$

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...?

My question is simply: 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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JDS Mar 17 '15 at 15:26
  • $\begingroup$ 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 =) $\endgroup$ – JDS Mar 17 '15 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Mar 17 '15 at 15:32
  • 1
    $\begingroup$ 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.) $\endgroup$ – Michael Grant Mar 17 '15 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Mar 17 '15 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.