# Constrained optimization

Now we will move to studying constrained optimizaton problems i.e., the full problem
$$
\begin{align} \
\min \quad &f(x)\\
\text{s.t.} \quad & g_j(x) \geq 0\text{ for all }j=1,\ldots,J\\
& h_k(x) = 0\text{ for all }k=1,\ldots,K\\
&a_i\leq x_i\leq b_i\text{ for all } i=1,\ldots,n\\
&x\in \mathbb R^n,
\end{align}
$$
where for all $i=1,\ldots,n$ it holds that $a_i,b_i\in \mathbb R$ or they may also be $-\infty$ of $\infty$.

For example, we can have an optimization problem
$$
\begin{align} \
\min \quad &x_1^2+x_2^2\\
\text{s.t.} \quad & x_1+x_2-1\geq 0\\
&-1\leq x_1\leq 1, x_2\leq 3.\\
\end{align}
$$

In order to optimize that problem, we can define the following python function:


```python
import numpy as np
def f_constrained(x):
    return np.linalg.norm(x)**2,[x[0]+x[1]-1],[]
```

Now, we can call the function:


```python
(f_val,ieq,eq) = f_constrained([1,0])
print "Value of f is "+str(f_val)
if len(ieq)>0:
    print "The values of inequality constraints are:"
    for ieq_j in ieq:
        print str(ieq_j)+", "
if len(eq)>0:
    print "The values of the equality constraints are:"
    for eq_k in eq:
        print str(eq_k)+", "
```

    Value of f is 1.0
    The values of inequality constraints are:
    0, 


Is this solution feasible?


```python
if all([ieq_j>=0 for ieq_j in ieq]) and all([eq_k==0 for eq_k in eq]):
    print "Solution is feasible"
else:
    print "Solution is infeasible"
```

    Solution is feasible


# Indirect and direct methods for constrained optimization

There are two categories of methods for constrained optimization: Indirect and direct methods. The main difference is that
1. Indirect methods convert the constrained optimization problem into a single or a sequence of unconstrained optimization problems, that are then solved. Often, the intermediate solutions do not need to be feasbiel, the sequence of solutions converges to a solution that is optimal (and, thus, feasible).
2. Direct methods deal with the constrained optimization problem directly. In this case, the intermediate solutions are feasible.

# Indirect methods

## Penalty function methods

**IDEA:** Include constraints into the objective function with the help of penalty functions that penalize constraint violations.

Let, $\alpha(x):\mathbb R^n\to\mathbb R$ be a function so that 
* $\alpha(x)=$ for all feasible $x$
* $\alpha(x)>0$ for all infeasible $x$.

Define optimization problems
$$
\begin{align} \
\min \qquad &f(x)+r\alpha(x)\\
\text{s.t.} \qquad &x\in \mathbb R^n
\end{align}
$$
for $r>0$ and $x_r$ be the optimal solutions of these problems.

In this case, the optimal solutions $x_r$ converge to the optimal solution of the constrained problem, when $r\to\infty$, if such solution exists.

For example, good ideas for penalty functions are
* $h_k(x)^2$ for equality constraints,
* $\left(\min\{0,g_j(x)\}\right)^2$ for inequality constraints.


```python
def alpha(x,f):
    (_,ieq,eq) = f(x)
    return sum([min([0,ieq_j])**2 for ieq_j in ieq])+sum([eq_k**2 for eq_k in eq])
```


```python
alpha([1,0],f_constrained)
```




    0




```python
def penalized_function(x,f,r):
    return f(x)[0] + r*alpha(x,f)
```


```python
penalized_function([-1,0],f_constrained,10000)
```




    40001.0




```python
from scipy.optimize import minimize
res = minimize(lambda x:penalized_function(x,f_constrained,100000),
               [0,0],method='Nelder-Mead', 
         options={'disp': True})
print res.x
```

    Optimization terminated successfully.
             Current function value: 0.499998
             Iterations: 57
             Function evaluations: 96
    [ 0.49994305  0.50005243]



```python
(f_val,ieq,eq) = f_constrained(res.x)
print "Value of f is "+str(f_val)
if len(ieq)>0:
    print "The values of inequality constraints are:"
    for ieq_j in ieq:
        print str(ieq_j)+", "
if len(eq)>0:
    print "The values of the equality constraints are:"
    for eq_k in eq:
        print str(eq_k)+", "

if all([ieq_j>=0 for ieq_j in ieq]) and all([eq_k==0 for eq_k in eq]):
    print "Solution is feasible"
else:
    print "Solution is infeasible"
```

    Value of f is 0.49999548939
    The values of inequality constraints are:
    -4.51660156242e-06, 
    Solution is infeasible


### How to set the penalty term $r$?

The penalty term should
* be large enough in order for the solutions be close enough to the feasible region, but
* not be too large to
  * cause numerical problems, or
  * cause premature convergence to non-optimal solutions because of relative tolerances.

Usually, the penalty term is either
* set as big as possible without causing problems (hard to know), or
* updated iteratively.


# Barrier function methods

**IDEA:** Prevent leaving the feasible region so that the value of the objective is $\infty$ outside the feasible set.

This method is only applicable to problems with inequality constraints and for which the set 
$$\{x\in \mathbb R^n: g_j(x)>0\text{ for all }j=1,\ldots,J\}$$
is non-empty.

Let $\beta:\{x\in \mathbb R^n: g_j(x)>0\text{ for all }j=1,\ldots,J\}\to \mathbb R$ be a function so that $\beta(x)\to \infty$, when $x\to\partial\{x\in \mathbb R^n: g_j(x)>0\text{ for all }j=1,\ldots,J\}$, where $\partial A$ is the boundary of the set $A$. Now, define optimization problem 
$$
\begin{align}
\min \qquad & f(x) + r\beta(x)\\
\text{s.t. } \qquad & x\in \{x\in \mathbb R^n: g_j(x)>0\text{ for all }j=1,\ldots,J\}.
\end{align}
$$
and let $x_r$ be the optimal solution of this problem (which we assume to exist for all $r>0$).

In this case, $x_r$ converges to the optimal solution of the problem (if it exists), when $r\to 0^+$ (i.e., $r$ converges to zero from the right).

A good idea for barrier algorithm is $\frac1{g_j(x)}$.


```python
def beta(x,f):
    _,ieq,_ = f(x)
    try:
        value=sum([1/max([0,ieq_j]) for ieq_j in ieq])
    except ZeroDivisionError:
        value = float("inf")
    return value
```


```python
def function_with_barrier(x,f,r):
    return f(x)[0]+r*beta(x,f)
```


```python
from scipy.optimize import minimize
res = minimize(lambda x:function_with_barrier(x,f_constrained,0.00000000000001),
               [1,1],method='Nelder-Mead', options={'disp': True})
print res.x
```

    Optimization terminated successfully.
             Current function value: 0.500000
             Iterations: 78
             Function evaluations: 136
    [ 0.49998927  0.50001085]



```python
(f_val,ieq,eq) = f_constrained(res.x)
print "Value of f is "+str(f_val)
if len(ieq)>0:
    print "The values of inequality constraints are:"
    for ieq_j in ieq:
        print str(ieq_j)+", "
if len(eq)>0:
    print "The values of the equality constraints are:"
    for eq_k in eq:
        print str(eq_k)+", "
if all([ieq_j>=0 for ieq_j in ieq]) and all([eq_k==0 for eq_k in eq]):
    print "Solution is feasible"
else:
    print "Solution is infeasible"
```

    Value of f is 0.500000122097
    The values of inequality constraints are:
    1.21864303093e-07, 
    Solution is feasible


## Other notes about using penalty and barrier function methods

* It is worthwile to consider whether feasibility can be compromized. If the constraints do not have any tolerances, then barrier function method should be considered.
* Also barrier methods parameter can be set iteratively
* Penalty and barrier functions should be chosen so that they are differentiable (thus $x^2$ above)
* In both methods, the minimum is attained at the limit.
* Different penalty and barrier parameters can be used for differnt constraints, even for same problem.

45256d4d304a6853e389d2698bef91a04485aac0
ipynb
Jupyter Notebook
Lecture 6, Indirect methods for constrained optimization.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2019-04-26T12:46:14.000Z
2021-11-23T03:38:59.000Z
Lecture 6, Indirect methods for constrained optimization.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
Lecture 6, Indirect methods for constrained optimization.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2016-01-08T16:28:11.000Z
2021-04-10T05:18:10.000Z
Qwen/Qwen-72B
1. YES
2. YES