How to Convert a Constrained Optimization Problem into an Unconstrained One

A constrained optimization problem asks you to minimize an objective only over points satisfying specified conditions. Whether you can turn it into an unconstrained problem depends on the type of constraints and on what “convert” means. For linear equality constraints, there is an exact method: describe the feasible set with free variables, then substitute that description into the objective. Penalty and barrier methods are useful too, but they have different guarantees.

Exact conversion for linear equality constraints

Consider the problem

$$\min_x f(x) \quad \text{subject to } Ax=b.$$

First find one feasible point $x_p$ such that $Ax_p=b$. Next, find a matrix $N$ whose columns form a basis for the null space of $A$, so $AN=0$. Every feasible point can then be written as

$$x=x_p+Nz.$$

Here, $z$ is a vector of free variables. The equality constraint is satisfied automatically because

$$A(x_p+Nz)=Ax_p+ANz=b.$$

Substitute this expression into the objective. The original constrained problem is now the unconstrained problem

$$\min_z f(x_p+Nz).$$

This is an equivalent reformulation: its feasible choices of $z$ correspond exactly to feasible choices of $x$ in the original problem. If the equality constraints have rank $r$ and there are $n$ variables, the reduced problem has $n-r$ free variables.

For a quadratic objective with symmetric $Q$,

$$f(x)=\frac12 x^TQx+c^Tx,$$

the reduced objective is also quadratic:

$$f(x_p+Nz)=\frac12 z^T(N^TQN)z + (N^T(Qx_p+c))^Tz + f(x_p).$$

The constant term $f(x_p)$ does not affect the minimizer, but it can be retained when you want the original objective value.

Worked example

Minimize $x_1^2+x_2^2$ subject to $x_1+x_2=1$. A feasible point is $(1/2,1/2)$, and a direction along the constraint line is $(1,-1)$. Thus all feasible points have the form

$$(x_1,x_2)=\left(\frac12+t,\frac12-t\right), \qquad t\in\mathbb{R}.$$

Substitute into the objective:

$$\begin{aligned} f(t)&=\left(\frac12+t\right)^2+\left(\frac12-t\right)^2\\ &=\frac12+2t^2. \end{aligned}$$

This is now an unconstrained one-variable problem. Its minimum occurs at $t=0$, giving $(x_1,x_2)=(1/2,1/2)$ and objective value $1/2$. The constraint has not been approximated; it is built into the parameterization.

Penalty functions: useful, but usually approximate

A common alternative is to add a penalty for constraint violation. For equality constraints, one choice is

$$\min_x f(x)+\frac{\rho}{2}\lVert Ax-b\rVert^2,$$

where $\rho>0$ controls the penalty strength. This is unconstrained, but for a finite $\rho$ its minimizer generally does not satisfy $Ax=b$ exactly. Increasing $\rho$ discourages violations; under appropriate conditions, solutions approach solutions of the constrained problem as $\rho$ grows. Very large penalties can also make numerical calculations poorly conditioned.

For example, minimize $x^2$ subject to $x=1$. The penalized objective is $x^2+\frac{\rho}{2}(x-1)^2$. Differentiating and setting the derivative to zero gives

$$2x+\rho(x-1)=0, \qquad x=\frac{\rho}{\rho+2}.$$

For every finite positive $\rho$, this minimizer is less than $1$, so it violates the original constraint. It approaches $1$ as $\rho$ increases, but the penalty formulation is not exactly equivalent at finite $\rho$.

Inequalities and the Lagrangian

Inequality constraints, such as $g_i(x)\leq 0$, need additional care. A logarithmic barrier, for example, adds terms such as $-\mu\log(-g_i(x))$ to the objective and keeps iterates inside the feasible region. Barrier methods generally solve a sequence of unconstrained problems as $\mu$ changes; a single finite barrier parameter does not usually give the exact constrained solution. An active-set method instead identifies which inequalities hold with equality at the solution and treats those as equalities, while checking that the remaining inequalities are satisfied.

The Lagrangian for equality constraints is

$$L(x,\lambda)=f(x)+\lambda^T(Ax-b).$$

It is central to deriving optimality conditions, but simply minimizing $L$ jointly over $x$ and $\lambda$ is not a valid general conversion: if $Ax\ne b$, changing the unrestricted multiplier can make the Lagrangian arbitrarily small. Instead, the solution is characterized using a saddle point or the Karush–Kuhn–Tucker (KKT) conditions, when the required assumptions hold.

Common mistakes

• Treating a penalty as exact. A finite quadratic penalty may leave a nonzero constraint residual.
• Optimizing over multipliers as ordinary variables. Lagrange multipliers enforce stationarity and feasibility through saddle-point or KKT conditions; they are not usually extra variables in a plain minimization.
• Assuming inequalities disappear by substitution. Parameterizing equalities does not remove inequalities that remain in the reduced variables.
• Using an infeasible starting point for a parameterization. The expression $x=x_p+Nz$ requires $Ax_p=b$. If no such $x_p$ exists, the equality constraints are infeasible.

For a quadratic program with linear equalities, null-space parameterization is the direct exact route when you want an unconstrained problem. For inequalities, choose a method suited to the goal—such as an active-set, barrier, or penalty method—and account for its assumptions and approximation behavior.