3
$\begingroup$

Suppose I want to optimize some function of continuous variables and the objective is nonlinear; in this context, gradient-based methods are quite popular. To my knowledge, soft constraints can be added with a Lagrangian Multiplier, which would essentially add a penalty proportionate to the degree that the constraint was violated.

Suppose one constraint was that $x \ge 0$. In the context of a minimization problem, we could presumably add $e^{-(x-n)}$ to the objective (or $-e^{-(x-n)}$ in the context of a maximization problem) where $n$ could be dialed up to create some arbitrarily painful penalty.

Is this considered a fairly standard practice in industry or are there different, preferred ways to enforce constraints in non-linear optimization?

Edit:

$e^{-m(x-n)}$ is the appropriate definition, where m defines the steepness of the curve and n defines the "elbow".

Elbow plot

$\endgroup$
1

2 Answers 2

2
$\begingroup$

Let's assume that you want to minimize $f:\mathbb{R}^n \rightarrow \mathbb{R}$ subject to $g(x)\ge 0$ ($g:\mathbb{R}^n \rightarrow \mathbb{R}^m$) with no particular assumptions on $f$ and $g.$ Heuristics aside, the three most common approaches would be the following.

Penalty Method

Minimize $f(x) + h(g(x))$ (unconstrained) where $h:\mathbb{R}^m \rightarrow \mathbb{R}^+$ is positive when $g(x) \not\ge 0$ and 0 when $g(x) \ge 0.$ You want the penalty term large enough to "discourage" accepting an infeasible solution in order to artificially reduce the value of $f(x).$ This approach does not require knowing a feasible solution.

Barrier Method

Similar to the penalty method, you minimize $f(x) + h(g(x))$ with $h$ a penalty function. In this case, though, you want $h(z)=0$ for $z \ge (\epsilon, \dots, \epsilon)$ (for some positive $\epsilon$), and $h(z)\rightarrow \infty$ as $z\downarrow 0.$ In other words, the penalty is 0 for most feasible solutions but blows up as you get close to violating any of the constraints. You need to know a strictly feasible (zero penalty) starting solution for the barrier method, and you may not find the true optimum if it lies too close to the boundary of the feasible region. $h$ is called a "barrier function", because it serves as a barrier to keep you from escaping the feasible region.

Lagrangian Relaxation

In the LR approach, you solve two nested problems: $$\max_{\lambda \ge 0} \min_x (f(x) - \lambda^\prime g(x)).$$ The inner problem resembles the penalty method, where the penalty function is a weighted sum of the constraint violations. This is an iterative scheme. You pick penalty weights $\lambda$ and solve the inner (minimization) problem. You then tweak the weights and try again. The outer (maximization) problem encourages selection of weights that penalize constraint violations without encouraging overachievement of constraints ($g_i(x) > 0$) too much ... hopefully.

Depending on what the properties of $f$ and $g$ are (convexity, smoothness, steepness) you may not be guaranteed a global optimum with any of these methods.

$\endgroup$
6
  • $\begingroup$ Are all three of these methods differentiable? I suspect the penalty method is not but I’m not certain. $\endgroup$
    – jbuddy_13
    Commented Mar 1 at 0:19
  • 1
    $\begingroup$ I'm not sure what you mean by a method being differentiable, but if you are asking whether gradients can be used when $f,$ $g$ and (where relevant) $h$ are all smooth, the answer is yes for all three methods. $\endgroup$
    – prubin
    Commented Mar 1 at 16:41
  • $\begingroup$ Are we guaranteed a feasible global optimum in the first case (Penalty Method)? I am pretty sure that even with convexity, if $h$ is not chosen well, the penalty method can yield an infeasible solution. A counter example is $f(x) = x(x+2)$ subject to $x>0$. If we choose $h = -x$ for $x>0$ and $0 $ for $x<0$, then we get $f(x)+h(g(x)) = x^2 + 2x - x = x(x+1)$ which has argmin $x = -1/2$, infeasible. If this is correct, then how do we chose $h$ to ensure feasibility? $\endgroup$ Commented Apr 2 at 18:26
  • $\begingroup$ @travelingbones Your penalty function is 0 for infeasible solutions and negative (rewarding) for feasible solutions, which is the reverse of what I wrote. $\endgroup$
    – prubin
    Commented Apr 3 at 2:43
  • $\begingroup$ @prubin, thanks for the reply. Indeed, my comment had a typo, but I think the problem/question remains. In the exapmle, our constraint is $g(x) = x \geq 0$ so (no fixing the typo) we let $h(x) = -x >0$ when $g(x) = x < 0$ and $h(x) = 0$ if $ g(x) = x \leq 0. $ Then the new objective function is $f+h\circ g = x**2+2𝑥−𝑥=𝑥(𝑥+1)$ which has argmin 𝑥=−1/2, infeasible. So the question is how do we choose appropriate $h$ to ensure feasibility? $\endgroup$ Commented Apr 3 at 18:03
0
$\begingroup$

You use penalty methods when the constraints considered for penalization are complex and cannot be handled directly. More precisely, if the projection map on your constraints has a closed form, there is no need to penalize them, as you can use projected gradient descent. In the case of minimizing $f(x)$ subject to $x \ge 0$, after calculating the term $x_k - \alpha_k\nabla f(x_k)$, project it onto the set $\{x \; | \; x \ge 0\}$. The resulting projection is then your $x_{k+1}$. Note that penalty methods usually provide an approximate solution, which may not even be feasible. To address this issue, people consider "Exact" penalty terms. The price to pay is that your obtained objective function is no longer differentiable across the entire space. For example, Lasso is the result of the exact penalty method. If you are interested in delving into the mathematics of these techniques, you can read a draft of the paper I am writing: https://arxiv.org/abs/2206.04020

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.