Class 02 - Q&A

[andrewrosemberg]

Please use this space to ask clarification questions, propose changes/corrections to the presented topics that should be accounted for in the final chapter, or point out interesting facts!

[andrewrosemberg]

Does the Armijo Rule work regardless of the conditions of the Hessian at the approximation (starting) point?

[klamike]

My linear programming visualizer http://lpviz.net actually includes an Armijo as part of the "Central Path" solver, which uses Newton's to solve for each point! Here is the relevant source code (sorry about the typescript)

Based on the code, you can see there is an "obvious" failure more where Armijo will decrease the step size so much, that x'≈x where x' <- α*δx (since α≈0). In that case the algorithm would basically stagnate. But that would only happen if the function is so nasty that you can't find a small enough α such that obj(x') < obj(x). Or, whatever heuristic rule is used to search for α (in my code, just halving it) cannot find it.

That said, I don't think I've ever actually seen those log messages, suggesting Newtons+Armijo is stable in that 2D barrier LP setting. But I'm sure it's possible, maybe with super big or super small regions, almost parallel constraints, etc. Feel free to try to trigger them and share your nasty LPs 😁

(Looking at the code now, the safetyBreaks is definitely redundant, I will fix that at some point 😅 )

[andrewrosemberg]

Does anyone have interesting examples where the Augmented Lagrangian Method works better than the Interior Point Method?

[jwestrenen3]

Although I am not completely sure, I can think of an example something like this:

Minimize: 𝑓(𝑥)=(𝑥−2)^2
subject to: x^2−1=0

Unconstrained minimum: 𝑥=2
Feasible solutions: x=±1
Constrained minimum: x∗=1

ALM Wins because it can start infeasible x0= 0. It also handles nonlinear equality constraints naturally. IPM requires feasible starting points and careful handling of equalities.

[andrewrosemberg]

@jwestrenen3 can you make a simulation of both methods and show the number of iterations that both take?

[jwestrenen3]

I created this simulation, which shows that you cannot start infeasibly with IPM. Is this what you are looking for?

[andrewrosemberg]

Does anyone have an illustrative example of the penalty method not converging?

[klamike]

Although the question was sort of answered in class, it may be interesting to have some further discussion on geometric interpretation of Tikhonov regularization in Newton's

In other words, how does the pink function change as you increase the regularization?

This video has some really nice graphics/explanations (of the non-regularized case). PS, the entire channel has really good content on basic optimization topics (KKT, LP, gradient descent, etc)

[andrewrosemberg]

More on the Tikhonov regularization: In primal-dual methods, why do we add positive values to some of the diagonal entries of the kkt matrix ("primal" rows) and negative values to other entries ("dual" rows)?

[andrewrosemberg]

I don't know if this definition stuck in the last lecture: Can anyone say what a merit function is? Mentioned in the context of root-finding.