The question is about finding convexity of any optimisation problem involving equality constraints. I will start with my belief first so if there are already some issues there, they can be addressed right away.
Belief: A problem is convex iff
1. Functions defining inequality constraints i.e. g_i(x)
You're right: a local minimum is characterized by the (necessary) KKT conditions and (sufficient) second-order conditions: https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Second-order_sufficient_conditions
They require that the Hessian be SPD on the nullspace of the Jacobian of the active constraints, that is exactly what happens in your example. Since your constraint is an equality and is linear, the Jacobian of the active constraints is the vector (1, 1) and its nullspace is the feasible set itself.
So your conclusion is correct: the Hessian should be SPD on the set {(x, y) | x+y = 0}.
In practice, this condition is not super easy to check, so if one wants to solve a subproblem that involves a Hessian that is not SPD, one usually regularizes the Hessian to make it (S)PD. Everywhere.
First of all we should define when an optimization problem is convex. Following T,R. Rockafellar, see his magnificent book " convex analysis", one could proceed as follows. First of all, define the notion of a convex function. It is wise to consider functions from , say R^n to R extended, that means, R, where +infinity and -infinity are adjoined. Then, given an objective function F and a constraint set C, define the minimization problem to be convex , when the following function is convex:
G defined by G(x)=F(x) whenever x is an element of C and G(x) = +infinity whenever x is not in C. The notion of Hessian is secondary, a tool, because not every function is everywhere twice differentiable. Rockafellar is a must read, when you are interested in this kind of issues. And, he has a lot of excellent students and colleagues. I only mention one : Jonathan Borwein, who is unfortunately not under the living anymore.
If your problem has equality constraints only, i.e. the feasible set is an affine subspace, this read might be helpful:
https://www.sciencedirect.com/science/article/pii/002437959290289M
Charlie Vanaret
Thank you very much for this sophisticated answer. I could already sense it but really needed this sophisticated description and approval to be confident. Highly appreciated!
I don't fully grasp your last line though! How do we regularize the hessian? Is it the same as reducing the obj. function by eliminating the extra variables using the linear equality constraints?
J. W. Nieuwenhuis
Thank you for the more fundamental description. For my example problem, this description indeed makes it quite intuitive to think that the problem is indeed a convex minimization problem.
However, I am really looking for tools that can help me automate the analysis especially when the number of variables are large. Thanks for the book recommendation, I do have online access to it so, I will check it out :-)
Also, just googled about Jonathan Borwein! He was an impressive personality!
Ralf Gollmer
Thank you very much for the recommendation. It definitely seems something that I was looking for :-)
Gaurav Malik this would be a reduced Hessian :)
Regularization is simply a convexification of the problem: you would usually add a multiple of the identity to the Hessian, check that its eigenvalues are all positive (easy to check for small problems, for large problems you can use the factorization step of linear solvers such as MA57 or Pardiso) and repeat if it's not the case.
Example 5.3 (Second-order conditions for constrained case) in this book, might be helpful for checking positive definiteness of Hessians in a give direction:
Book Engineering Design Optimization
Also, did you really meant to write "if and only if"? It is true that those conditions are sufficient, but they are too restrictive. There are convex problems that don't satisfy all 3.
Joaquim R. R. A. Martins
Thank you very much for providing the link of your book. It really appreciate that I can download it for free!
For the 2nd comment, I indeed meant to write "if and only if" and would really appreciate if you can throw some more light on it as I am myself not fully convinced of the "iff" but can't seem to find literature that suggests something else.
Hi, the iff is valid under additional doffetentabiliy conditipns - but of course a function may ne convex without being differentiable at all Just think of |x| at x=0.
So you would have to specify more closely what ^ iff^ condition you are looking for.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling