Optimization with Inequality Constraints

Constrained Optimization with Inequality Constraints

Set-Up and Assumptions

$$\max\limits_{\substack{\mathbf x\\ \mathrm{subject\, to} \\ \\g_1(\mathbf x)\le c_1\\[-6pt] \vdots \\[1.5pt] g_k(\mathbf x)\le c_k }} f(\mathbf x)$$

$\max$ : maximize
$f$ : the objective function
$\mathbf x=(x_1,\ldots,x_n)$ : vector of $n$ choice variables
$g_i$ : constraint function (there are $k$ of them)
$c_i$ : constraint bound constant (there are $k$ of them)
We assume $f$ is concave and continuously differentiable and each $g_i$ is convex and continuously differentiable.
There is a value of $\mathbf x$ such that $g_j(\mathbf x)< c_j$ for all $j=1,...,k$.

Constrained Optimization with Inequality Constraints

Useful facts

Any minimization problem can be converted in a maximization problem (and vice-versa) by setting the objective function in the maximization problem as the negative of the objective function in the minimization problem: $$\max\limits_{\substack{\mathbf x\\ \mathrm{subject\, to} \\ \\g_1(\mathbf x)\le c_1\\[-6pt] \vdots \\[1.5pt] g_k(\mathbf x)\le c_k }} f(\mathbf x) = -\min\limits_{\substack{\mathbf x\\ \mathrm{subject\, to} \\ \\g_1(\mathbf x)\le c_1\\[-6pt] \vdots \\[1.5pt] g_k(\mathbf x)\le c_k }} -f(\mathbf x)$$
Any constraint involving the greater or equal than inequality $\geq$ can (and should!) be converted into a constraint involving the less or equal than inequality $\leq$. $$ g(x)\geq c \Leftrightarrow -g(x)\leq -c$$
Any constraint involving an equality can (but in practice we do not do that!) be converted into two constraints involving the less than equal inequality $$ g(x)= c \Leftrightarrow -g(x)\leq -c \text{ and } g(x)\leq c$$

Optimization with Inequality Constraints

$$\max\limits_{\substack{\mathbf x\\ \mathrm{subject\, to} \\ \\g_1(\mathbf x)\le c_1\\[-6pt] \vdots \\[1.5pt] g_k(\mathbf x)\le c_k }} f(\mathbf x)$$

When a constraint holds as an equality, $g_j(\mathbf x)= c_j$, we say it is binding.
When a constraint holds as a strict inequality, $g_j(\mathbf x)<c_j$, we say it is slack.

Optimization with Inequality Constraints

Conditions For A Solution

Given maximization problem define the Lagrangian,

$$ \mathcal{L}(\mathbf x, \boldsymbol \lambda)=f(\mathbf x)-\sum_{j=1}^{k}\lambda_{j}\cdot(g_{j}(\mathbf x)-c_{j})$$

Notice that the Lagrangian is a function of the choice variables $\mathbf x$ and also of the Lagrangian multipliers $\boldsymbol \lambda$

If $(\mathbf x^\ast, \boldsymbol \lambda^\ast)$ solves the following conditions, it solves the maximization problem.

$\nabla_{\mathbf x} \mathcal{L}(\mathbf x^\ast, \boldsymbol \lambda^\ast) =0$ where $\nabla_{\mathbf x} \mathcal{L}$ is the gradient of $\mathcal{L}$ with respect the variables $\mathbf x$. Notice that this condition is identical as in the case of the equality constraints.
For every constraint $j$, $\lambda^{\ast}_{j}\cdot(g_{j}(\mathbf x^{\ast})-c_{j})=0$. Notice that when $\lambda_{j}^{\ast}>0$ this means that $g_{j}(\mathbf x^{\ast})=c_{j}$ and so, the constraint holds as an equality (it is binding).
For every constraint $j$, $\lambda_{j}^{\ast}\geq 0$. Notice this is different than the recipe for equality constraints since in that case, the Lagrange multipliers could take negative values.
Every constraint $j$ is respected, $g_{j}(\mathbf x^{\ast})\leq c_{j}$.

Optimization with Inequality Constraints

Recipe #2

Write down the maximization (or minimization) problem. Do not forget to write all constraints in the form $g_j(x)\le c_j$!
Write the corresponding Lagrangian.
List all possible cases for the Lagrange multipliers ($\lambda_{j}>0$ or $\lambda_{j}=0$) in a table.
Consider a particular case. In this case let $\boldsymbol \lambda^{+}$ denote the list/vector of Lagrangian multipliers that are positive and let $\boldsymbol\lambda^{0}$ denote the list/vector of Lagrangian multipliers that are zero.
For the case in question, replace by zero all the multipliers $\boldsymbol\lambda^{0}$ in the Lagrangian and apply basic recipe #1 with the variables being $\mathbf x$ and $\boldsymbol\lambda^{+}$:

Solve $\nabla_{\mathbf x,\boldsymbol\lambda^{+}} \mathcal{L}=0$ for $\mathbf x$ and $\boldsymbol\lambda^{+}$. If there is no solution, consider other cases.
Does this solution satisfy (3) in the previous page, that is, is it true that $\boldsymbol \lambda^{+}>0$ as we assumed?
Does this solution satisfy (4) in the previous page, that is, is it true that $g_j(x)\leq c_j$ for every $j$ such that we are assuming $\lambda_j=0$?
If the answers to the two previous questions are yes then we found a solution. If no, consider other cases.

Click here to learn the steps of Recipe #2.