0
$\begingroup$

I have a nonlinear objective function with a nonlinear set of inequality constraints and I am trying to reformulate the problem using the Lagrangian function. My goal is to transform a constrained problem to non-constrained then apply an optimization method like simulated annealing to solve my new formulation of the problem. Is that even the right approach?

$\endgroup$
2
  • 2
    $\begingroup$ It's difficult to say without seeing the constraints and the objective, you should know that once you reformulate the problem using the Lagrangian you will not have a simple minimization problem but instead a saddle point problem. $\endgroup$ Commented Apr 26, 2019 at 6:53
  • $\begingroup$ If you want to convert a constrained optimization problem into unconstrained optimization, you should look into barrier methods and penalty methods instead. $\endgroup$
    – user856
    Commented Apr 26, 2019 at 7:07

1 Answer 1

2
$\begingroup$

$\newcommand{\minimize}{\operatorname*{Minimize}}$You can use the penalty method or the augmented Lagrangian method. Suppose you have a problem of the form

\begin{aligned} \mathbb{P}:\minimize_{g(x) \leq 0} f(x). \end{aligned}

You can solve the sequence of

\begin{aligned} \mathbb{P}_\lambda:\minimize_{x\in\mathbb{R}^n} f(x) + c \left[g(x)\right]_+^2, \end{aligned}

where $\left[z\right]_+$ is defined as

\begin{aligned} \left[z\right]_+ = \begin{cases} 0, &\text{if } z < 0 \\ z, &\text{if } z \geq 0 \end{cases} \end{aligned}

In doing so, you will solve $\mathbb{P}_{\lambda_k}$, increase $\lambda_k$ (e.g., $\lambda_{k+1} = 10 \lambda_k$) and solve the next problem, $\mathbb{P}_{\lambda_k}$, using the previous solution as an initial guess.

Let us denote the set of minimizers of $\mathbb{P}_{\lambda_k}$ by $X_k^\star$ and let $X^\star$ be the set of minimizers of $\mathbb{P}$. Then, it can be shown that

$$ \limsup_k X_k^\star \subseteq X^{\star}, $$

in other words, every cluster point, $x^\star$, of a sequence $(x_k^\star)_k$ with $x_k^\star \in X_k^\star$, is a minimizer of $\mathbb{P}$.

Although in theory you need to take $\lambda$ to infinity in order to recover a solution of the original problem, in practice you can stop the procedure once $[g(x_k^\star)]_+$ drops below a desired tolerance.

Note that there exist penalty functions other than $c \left[g(x)\right]_+^2$ (for example, $c \left[g(x)\right]_+$). You can read more about the penalty method in the book of Nocedal and Wright.

The augmented Lagrangian method is similar, but it uses a different unconstrained formulation.

$\endgroup$
3
  • $\begingroup$ I actually tried to use interior penalty function where the penalty term is r*(1/g(x)) and from what I understand, the penalty function penalize any point where we get near the constraint boundry. But this seems not to work for me, because the solution I obtain violates the constraints. I understand that we need to chose an intial point inside the active region, which I did by chosing the correct optimum point as intial point $\endgroup$
    – amidher
    Commented Apr 27, 2019 at 6:23
  • $\begingroup$ @amidher Thank you for accepting my answer. The penalty method does not require that you start from an interior point. In fact, you can relax all constraints and convert your problem into an unconstrained problem. I have developed a software called OpEn (Optimization Engine) in which I do that exactly; you can find an example of using the penalty method here. In theory, with this method as well as with interior point methods, you shouldn't get an infeasible solution. $\endgroup$ Commented Apr 27, 2019 at 18:31
  • $\begingroup$ @amidher This is provided that your problem is feasible and bounded. Additionally, unless you use a global optimization method, there is no guarantee that you will converge to a global optimum. Determining a feasible point can be equally difficult. Another reason for not getting a meaningful solution is that you problem might be too ill conditioned. $\endgroup$ Commented Apr 27, 2019 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .