# How to formulate constrained optimization problems

For a constrained optimization problem, there can be different formulations.

For example, consider the problem with the following formulation:

$$\min_{x \in X \subseteq \mathbb{R}^n} \, f(x),$$ subject to $g(x) \leq 0, h(x)=0$.

1. One can move part of those (in)equality constraints into the set $X$, or shrink $X$ by moving part of it to the (in)equality constraints.
2. One can also exchange between the equality constraints and the inequality constraints. For example, $h(x)=0$ can be replaced by $h(x)\leq 0, -h(x) \leq 0$.

I was wondering if there are some guidelines on how to formulate a constrained optimization problem into different forms for various purposes, such as to better reveal its structure, to make it easier to solve, to make it become less ill-posed in some sense, ...

Thanks and regards!

-
From my understanding, this question does not have a definitve answer. I consider the proper (re-)formulation of a constrained optimization problem as part of the "art of optimization". I would also love to see some guidelines... (and I also lack a good reference). – Dirk Apr 5 '11 at 9:25

Typically you'll use the set $X$ to represent black-box constraints, e.g., constraints for which you don't have an analytical representation. They could consist in the output of a computer code that returns True if the constraints are satisfied and False otherwise. In general, if you have analytical descriptions of the constraints, it is to your advantage to use them. There is research on mixed black-box optimization, where the problem has a mixture of black-box constraints and explicit constraints, but you wouldn't get the most out of your problem in terms of efficiency if you misclassified constraints as black-box constraints.

As to the transformation of and equality into two inequalities, it will cause most algorithms for smooth optimization to break down (assuming $h$ is smooth). It's easy to see why: most methods will aim to satisfy the KKT conditions (first-order optimality). However the KKT conditions are necessary for optimality IF a constraint qualification is satisfied. A constraint qualification is a certificate that the analytical expression of the feasible set is, in some sense, not redundant in the description of its geometry.

Consider for instance the constraints $x^3 \leq 1$ and $x^3 \geq 1$. We clearly see some redundancy here. Why not just say $x^3 = 1$? Why not just say $x=1$???

The redundancy manifests itself in the constraint qualification. The most widely used constraint qualification condition is the linear independence constraint qualification condition (LICQ). It requires that the gradients of all constraints that are satisfied as an equality at a solution be linearly independent. This concerns of course all equality constraints but also all inequalities that are "active" (i.e. $g_i(x) = 0$ in your notation). Since $h$ was an equality constraints, we'll necessarily have $h(x) = 0$ at a solution, but the gradients of the functions $h$ and $-h$ cannot be linearly independent. Try solving a problem with $x^3 \leq 1$ and $x^3 \geq 1$ on one of the NEOS solvers and you'll observe trouble: http://neos-server.org/neos

You'll run into the same kind of trouble if one of the active constraint gradients vanishes at a solution. Consider for instance the constraint $x^2 = 0$. When problems are automatically generated by some procedure, it's very hard to check for such redundancy, but when you model a problem by hand from scratch, it's important to look out for it.

Coming back to the first topic, there is a (theoretical) advantage to describing any feasible set as just $X \subseteq \mathbb{R}^n$. It is that the first-order optimality conditions are simply that $-\nabla f(x)$ must lie in the normal cone to $X$ at $x$. And this doesn't depend on any constraint qualification because this is a statement that only concerns the geometry of the feasible set, not its analytical description.

For more information, take a look at the book by Bazaraa, Sherali and Shetty, or "Numerical Optimization" by Nocedal and Wright (Springer).

-

There is actually a ready, well developed theory exactly for your optimization problem

minimize $f(x)$ under $g(x)\leq0,h(x)=0$,

It generalizes the technique of Lagrange Multipliers for the problem without inequalities $g\leq0$, which you should understand beforehand, if you haven't already.

-

A jet plane is to reach a certain point in space in minimum time from take off. Assuming that the total energy (kinetic energy + potential energy + fuel) is constant, the jet burns fuel at its maximum constant rate and it has zero velocity at take off, formulate the corresponding optimization problem.

-
This does not appear to be an answer to the question. – Daniel R Mar 7 '14 at 11:41