3
$\begingroup$

Essentially, how can I check if functions like this are convex, and how can I know before I write a quadratic constraint that it will be convex? So essentially, how can I write feasible convex quadratic constraints so that I don't waste my time writing non-convex ones. Is there a certain form quadratic constraints look like in convex form? I am writing an optimization program that's mixed-integer and quadratic in constraints and objective function but am running into the issue of having a non-semidefinite matrix Q to be used in my solver. Some of the quadratic constraints I have are:

-x8*x10 + 1.4*x7*x9 <= 0

x7*x1 + x8*x4 <= 1470, "Rows Constraint"

x9*x2 <= 163.128, "Seats Per Row Constraint First-Class"

x10*x5 <= 163.128, "Seats Per Row Constraint Premium-Economy"

Which of the above are non-convex? Also, all x's are a positive number.

Thank you so much in advance! PS I am a master's of aerospace engineering student looking for help!

$\endgroup$
2
2
$\begingroup$

Convex constraints in standard form are given by $$g(\mathbf{x}) \le 0,$$ where $g(\cdot)$ is a convex function. Your constraints are already in the form given above, but your $g(\cdot)$ functions are not convex.

To check whether $g(\cdot)$ is convex, you need to check whether the Hessian -- the matrix of partial second derivatives -- is positive semidefinite. So, for example, the Hessian of your first constraint is $$\left[\matrix{0 & 0 & 1.4 & 0 \\ 0 & 0 & 0 & -1 \\ 1.4 & 0 & 0 & 0 \\0 & -1 & 0 & 0}\right],$$ which is not PSD (it has negative eigenvalues $\implies$ not PSD).

I gather that you are trying to find a way to "write" a nonconvex constraint as a convex one. But it's not a matter of just writing it in a specific way. A constraint is either convex or not; shifting things to one side of the inequality or the other, multiplying both sides by $-1$, etc. --- things like that are not going to convert a nonconvex constraint into a convex one.

$\endgroup$

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.