1. Basic Optimization Theory

1.1. Formulation of an Optimization Problem

A constrained optimization problem consists of:

  • A function to minimize, often called an objective function or sometimes a cost function.

  • Optimization or design variables.

  • Constraints. In mathematical terms, this translates to

\[ \min_{x\in \mathbb{R}^n} f(x) \quad \text{subject to:} \quad c_i(x)\geq0, \; i \in \mathcal{I}.\]

In the equation above, the objective function is \(f\), the vector \(x\) is the optimization variable and \(c_i\) with \(i\in \mathcal{I}\) is a set of contraints. A point \(x\) satisfying the constraints is called a feasible point and the set of all feasible points is called the feasible set \(\Omega\)

\[ \Omega = \left\{x\in \mathbf{R}^n \quad \text{such that} \quad c_i(x)\geq 0, \; i\in \mathcal{I}\right\}.\]

The feasible set is where a minimum of \(f\) is sought. Optimization problems are often formulated with equality constraints and upper and lower bounds on the optimization variables in addition to inequality constraints. This can be beneficial for certain solution techniques, but such constraints can always be rewritten as inequality constraints for the sake of simplicity.

A simple example is to minimize the material costs for a single mooring line, subject to certain rules and regulations. The optimization variables could then be length \(l\) and diameter \(d\) of the mooring line. Upper and lower bounds on \(l\) and \(d\) can together with limitations on axial tension form the constraints. The objective function could be the amount of material in the mooring line, i.e. \(f(l,d) = ld^2\). In such an example the evaluation of the constraints involving line tension could typically involve running RIFLEX.

1.2. Gradient Based Methods for Nonlinear Problems

This subsection is to a large extent based on Nocedal and Wright (1999). There are two main classes of gradient based methods for nonlinear constrained problems:

  • Penalty, barrier and augmented Lagrangian methods

  • Sequential quadratic programming (SQP) methods
    The idea of penalty, barrier and augmented Lagrangian methods is to replace a constrained optimization problem with a sequence of unconstrained problems by introducing penalty and barrier parameters. Penalty methods are most suitable for problems with only equality constraints. A quadratic penalty function penalty function \(Q(x; \mu)\) is often defined as

\[ Q (x;\mu) = f(x) + \frac{1}{2\mu} \sum_{i\in\mathcal{E}} c_i^2(x),\]

where \(\mathcal{E}\) is the set of equality constraints and \(\mu>0\) is a penalty parameter. The second term of the equation above is the penalty term which increases if the constraints are violated. The unconstrained problem is solved for a decreasing sequence of penalty parameters until a solution to the constrained problem is found.

Barrier methods are similar to penalty methods, but more suited for problems with only inequality constraints. A typical logarithmic barrier function can be defined as

\[P(x; \mu) = f(x) -\mu\sum_{i\in\mathcal{I}} \log c_i(x),\]

where \(\mathcal{I}\) is the set of inequality constraints and \(\mu > 0\) is a barrier parameter. The second term is the barrier term which blows up when \(x\) approaches the boundary of the feasible set. As for penalty methods, the procedure is to solve the unconstrained problem for a decreasing sequence of barrier parameters \(\mu\).

Penalty and barrier methods need to be combined to handle general nonlinear problems need to be combined in order to handle both inequality and equality constraints. Some issues with penalty and barrier are:

  • Contours of the penalty or barrier function are usually elongated when \(\mu\rightarrow 0\) and makes it increasingly more difficult for unconstrained optimization routines to perform well.

  • A good choice for starting point is needed when the penalty/barrier parameter \(\mu\) is small.

  • The Hessian of the penalty or barrier function may become ill-conditioned for small \(\mu\).

Augmented Lagrangian methods overcome some of the issues above. For an equality constrained problem, the augmented Lagrangian function may be defined as

\[\mathcal{L_A} (x, \lambda; \mu) = f(x)- \sum_{i\in \mathcal{E}} \lambda_i c_i(x) + \frac{1}{2\mu} \sum_{i\in \mathcal{E}} c_i^2(x).\]

The idea is the same as for penalty and barrier methods, namely to solve and unconstrained problem instead of a constrained one, but details are omitted here. Augmented Lagrangian methods can also be formulated for general problems with both equality and inequality constraints.

The basic idea of sequential quadratic programming (SQP) methods is to formulate a quadratic subproblem in each iterate and apply the solution of the subproblem as a new search direction. If we consider the problem Equation (1), then a typical quadratic subproblem is

\[\min_p \frac{1}{2}p^TW_kp + \nabla f_k^T p,\label{eq:SQPsub}\]

subject to

\[\nabla c_i(x_k)^Tp + c_i(x_k)\geq 0,\quad i \in \mathcal{I},\]

where the constraints have been linearized. In the equation above, \(W_k = W (x_k, \lambda_k)\) is the Hessian of the Lagrangian of the problem, i.e.

\[ W (x,\lambda) = \nabla_{xx}^2 \mathcal{L}(x,\lambda) = \nabla_{xx}^2\left( f(x) - \sum_{i\in\mathcal{L}} \lambda_ic_i(x) \right).\]

Quadratic programming algorithms, such as active-set methods, are applied to solve Equation (6). See Nocedal and Wright (1999) for further details. Sequential quadratic programming methods are often efficient on both small and large scale problems.

1.3. References

J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.