Convex Optimization Note

Convex Function

Definition

$\forall 0\le t\le 1,\forall x_1,x_2\in X,f(t{x}_1+(1-t)x_2)\le tf(x_1)+(1-t)f(x_2)$

If $f$ is differentiable on $(a,b)$, then

• $\forall a<x<y<b,f^{\prime }(x_2)\le f^{\prime }(x_2)\iff f$ is convex
• $\forall a<x<b,f^{\prime \prime }(x)>0\iff f$ is convex

Link to original

Convex Set

Definition

A set of points is convex if it contains every line segment between two points in the set. $\forall x,y\in X,\forall t\in [0,1],(1-t)x+ty\in X$

Link to original

Feasible Region

Definition

The set of all possible points on an optimization problem that satisfy the problem’s constraints.

Link to original

Convex Optimization

Definition

$\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

An optimization problem in which the objective function is a Convex Function and the feasible set is a Convex Set.

Facts

Every local minimum is a global minimum

The convex feasible set condition is equivalent to the following conditions

• the inequality constraint function $g$ is a Convex Function
• the equality constraint function $h$ is an affine function

Link to original

Gradient Descent

Definition

An iterative optimization algorithm for finding a local minimum of a differentiable function

${\mathbf{x}}_{n+1}=x_n-\gamma \nabla f(x_n)$ where $\gamma$ is a learning rate

Examples

Solution of a linear system

Solve $A\mathbf{x}=\mathbf{b}$ with an MSE loss

The cost function is $f(\mathbf{x})=(A\mathbf{x}-\mathbf{b}{)}^{⊺}(A\mathbf{x}-\mathbf{b})$ and its gradient is $\nabla f(x)=-2(\mathbf{b}-A\mathbf{x}{)}^{⊺}$

Then, solution is ${\mathbf{x}}_{n+1}={\mathbf{x}}_n+2\gamma A^{⊺}(\mathbf{b}-A{\mathbf{x}}_n)$

Link to original

Newton's Method

Definition

An iterative algorithm for finding the roots of a differentiable function, which are solution to the equation $f(x)=0$

Algorithm

Find the next point such that the Taylor series of the given point is 0 Taylor first approximation: $f(x)\simeq f(x_n)+f^{\prime }(x_n)(x-x_n)$ The point such that the Taylor series is 0: $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

multivariate version: ${\mathbf{x}}_{n+1}=f({\mathbf{x}}_n)-\nabla f({\mathbf{x}}_n{)}^{-1}f({\mathbf{x}}_n)$

In convex optimization,

Find the minimum point^[its derivative is 0] of Taylor quadratic approximation. Taylor quadratic approximation: $f(x)\simeq f(x_n)+f^{\prime }(x_n)(x-x_n)+\frac{f^{\prime \prime }(x_n)}{2}(x-x_n{)}^2$ The derivative of the quadratic approximation: $f^{\prime }(x_n)+f^{\prime \prime }(x_n)(x-x_n)$ The minimum point of the quadratic approximation^[the point such that the derivative of the quadratic approximation is 0]: $x_{n+1}=x_n-\frac{f^{\prime }(x_n)}{f^{\prime \prime }(x_n)}$ multivariate version: ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-{\nabla }^{2}f({\mathbf{x}}_n{)}^{-1}\nabla f({\mathbf{x}}_n)$

Examples

Solution of a linear system

Solve $A\mathbf{x}=\mathbf{b}$ with an MSE loss

The cost function is $f(\mathbf{x})=(A\mathbf{x}-\mathbf{b}{)}^{⊺}(A\mathbf{x}-\mathbf{b})$ and its gradient and hessian are $\nabla f(x)=-2(\mathbf{b}-A\mathbf{x}{)}^{⊺}$, ${\nabla }^{2}f(x)=2A^{⊺}A$

Then, solution is ${\mathbf{x}}_{n+1}={\mathbf{x}}_n+(A^{⊺}A{)}^{-1}{A}^{⊺}(\mathbf{b}-A{\mathbf{x}}_n)$ If $(A^{⊺}A)$ is invertible, ${\mathbf{x}}_{n+1}=(A^{⊺}A{)}^{-1}{A}^{⊺}\mathbf{b}$ is a Least Square solution.

Link to original

Quasi-Newton Method

Definition

Secant equation

Methods

• Broyden’s Method
• Symmetric Rank-One Method
• Broyden–Fletcher–Goldfarb–Shanno Algorithm
• Davidon–Fletcher–Powell Formula
• Broyden Family Method

Facts

DFP and BFGS is dual problem

Link to original

Broyden's Method

Definition

Solve $f(x)=0$ using Newton’s Method with approximation of Jacobian Matrix

Algorithm

The essence of Broyden’s method is to approximate Jacobian Matrix of Newton’s Method using the average rate of change

Replace derivative $f^{\prime }(x_n)\simeq \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$ or gradient with an approximation ${\nabla }^{2}f({\mathbf{x}}_n)\simeq J_n$ Then, $J_n\cdot ({\mathbf{x}}_n-{\mathbf{x}}_{n-1})\simeq f({\mathbf{x}}_n)-f({\mathbf{x}}_{n-1})$

Define ${\mathbf{f}}_n:=f({\mathbf{x}}_n)$ $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$

Then, ${\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n\simeq \Delta {\mathbf{f}}_n$

We want to find $A$ satisfying the following expression $J_n=J_{n-1}+A$ $\Rightarrow \Delta {\mathbf{f}}_n=(J_{n-1}+A)\Delta {\mathbf{x}}_n=J_{n-1}\Delta {\mathbf{x}}_n+A\Delta {\mathbf{x}}_n\Rightarrow \Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n=A\Delta {\mathbf{x}}_n$ by above approximation

To ensure stability of update, take a minimum modification $J_{n-1}$ In other words, solve the minimization problem using method of Lagrange multipliers $\min ||A|{|}_F=||J_n-J_{n-1}|{|}_F$ subject to $\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n=A\Delta {\mathbf{x}}_n$

Then, the solution is $A=\frac{\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n}{||\Delta {\mathbf{x}}_n||}\Delta {\mathbf{x}}_n^{⊺}$ and $J_n$ is calculated by $J_{n-1}$ $J_n=J_{n-1}+\frac{\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n}{||\Delta {\mathbf{x}}_n||}\Delta {\mathbf{x}}_n^{⊺}$

Now updating formula become ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-J_n^{-1}\mathbf{f}({\mathbf{x}}_n)$

Where $J_n^{-1}$ can be easily calculated by Sherman–Morrison Formula

$J_n^{-1}=J_{n-1}^{-1}+\frac{\Delta {\mathbf{x}}_n-J_{n-1}^{-1}\Delta {\mathbf{f}}_n}{\Delta {\mathbf{x}}_n^{\mathrm{T}}{J}_{n-1}^{-1}\Delta {\mathbf{f}}_n}\Delta {\mathbf{x}}_n^{\mathrm{T}}{J}_{n-1}^{-1}$ and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-J_n^{-1}\mathbf{f}({\mathbf{x}}_n)$

Link to original

Symmetric Rank-One Method

Symmetric Rank-One Method

The Quasi-Newton Method method with a symmetric condition

Algorithm

Define $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$ $H_n=J_n^{-1}\simeq {\nabla }^{2}f(x{)}^{-1}$

Then, $\Delta {\mathbf{f}}_n={\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n$ $\Delta {\mathbf{x}}_n={\mathbf{H}}_{\mathbf{n}}\Delta {\mathbf{f}}_n$

To assure the symmetry of the approximation of hessian matrix, let the perturbation matrix be $\mathbf{u}{\mathbf{u}}^{⊺}$ $H_n=H_{n-1}+\mathbf{u}{\mathbf{u}}^{⊺}$

Then, $\Delta {\mathbf{x}}_n=H_n\Delta {\mathbf{f}}_n\Rightarrow \Delta {\mathbf{x}}_n=H_{n-1}\Delta {\mathbf{f}}_n+\mathbf{u}{\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n\Rightarrow \mathbf{u}{\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$

Now we can express $\mathbf{u}=\frac{(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)}{{\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n}$ and $\mathbf{u}{\mathbf{u}}^{⊺}=\frac{(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{({\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n{)}^2}$

Since $\mathbf{u}{\mathbf{u}}^{⊺}$ satisfying $\mathbf{u}{\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$ is unique(because $\mathbf{u}({\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n)=⟨{\mathbf{u}}^{⊺},\Delta {\mathbf{f}}_n⟩\mathbf{u}$ is the scaling of $\mathbf{u}$), we can get $({\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n{)}^2$ by multiplying $\Delta {\mathbf{f}}_n^{⊺}$ to the both side $({\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n{)}^2=\Delta {\mathbf{f}}_n^{⊺}\mathbf{u}{\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n=\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)$

by substituting $({\mathbf{u}}^{⊺}\Delta {\mathbf{f}}_n{)}^2$ to original expression, $\mathbf{u}{\mathbf{u}}^{⊺}=\frac{(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)}$

Therefore, $H_n=H_{n-1}+\frac{(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}\Delta {\mathbf{f}}_n}$ Since the denominator is a scalar and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-H_n\mathbf{f}({\mathbf{x}}_n)$

Link to original

Broyden–Fletcher–Goldfarb–Shanno Algorithm

Definition

The quasi-Newton method with symmetric and positive-definite condition Update inverse of hessian directly

Algorithm

Define $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$ $H_n=J_n^{-1}\simeq {\nabla }^{2}f(x{)}^{-1}$

Then, $\Delta {\mathbf{f}}_n={\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n$ $\Delta {\mathbf{x}}_n={\mathbf{H}}_{\mathbf{n}}\Delta {\mathbf{f}}_n$

We want to find $A$ satisfying the following expression with the symmetric and positive-definite condition $H_n=H_{n-1}+A$ $\Rightarrow \Delta {\mathbf{x}}_n=(H_{n-1}+A)\Delta {\mathbf{f}}_n=H_{n-1}\Delta {\mathbf{f}}_n+A\Delta {\mathbf{f}}_n\Rightarrow A\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$ by the definition

So, Solve the minimization problem with the symmetric and positive-definite conditions using method of Lagrange multipliers $\min ||A|{|}_w^2=||MA{M}^{⊺}|{|}_F^2$ subject to $A=A^{⊺}$ and $A\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$ where $W=M^{⊺}M:=J_k$

Then, the solution is $A=\frac{(W^{-1}\Delta {\mathbf{f}}_n)(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}+(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}(W^{-1}\Delta {\mathbf{f}}_n)}-\frac{\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{(\Delta {\mathbf{f}}_n^{⊺}(W^{-1}\Delta {\mathbf{f}}_n){)}^2}$ where $W^{-1}\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n$ by the definition $=\frac{\Delta {\mathbf{x}}_n(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}+(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}-\frac{\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{(\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n{)}^2}$ $=\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)H_{n-1}\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$

Therefore, updating formula is $H_n=H_{n-1}+\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)H_{n-1}\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$

And by the Sherman–Morrison Formula, $J_n=J_{n-1}+\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}-\frac{J_{n-1}\Delta {\mathbf{x}}_n(J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}}{\Delta {\mathbf{x}}_n^{⊺}{J}_{n-1}\Delta {\mathbf{x}}_n}$ and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-H_n\mathbf{f}({\mathbf{x}}_n)$

Link to original

Davidon–Fletcher–Powell Formula

Definition

The quasi-Newton method with symmetric and positive-definite condition Update hessian and find inverse using Sherman–Morrison Formula

Algorithm

Define $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$ $H_n=J_n^{-1}\simeq {\nabla }^{2}f(x{)}^{-1}$

Then, $\Delta {\mathbf{f}}_n={\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n$ $\Delta {\mathbf{x}}_n={\mathbf{H}}_{\mathbf{n}}\Delta {\mathbf{f}}_n$

We want to find $A$ satisfying the following expression with the symmetric and positive-definite condition $J_n=J_{n-1}+A$ $\Rightarrow \Delta {\mathbf{f}}_n=(J_{n-1}+A)\Delta {\mathbf{x}}_n=J_{n-1}\Delta {\mathbf{x}}_n+A\Delta {\mathbf{x}}_n\Rightarrow A\Delta {\mathbf{x}}_n=\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n$ by the definition

So, solve the minimization problem with the symmetric and positive-definite conditions using method of Lagrange multipliers $\min ||A|{|}_w^2=||MA{M}^{⊺}|{|}_F^2$ subject to $A=A^{⊺}$ and $A\Delta {\mathbf{x}}_n=\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n$ where $W=M^{⊺}M:=H_k$

Then, the solution is $A=\frac{(W^{-1}\Delta {\mathbf{x}}_n)(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}+(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n)(W^{-1}\Delta {\mathbf{x}}_n{)}^{⊺}}{\Delta {\mathbf{x}}_n^{⊺}(W^{-1}\Delta {\mathbf{x}}_n)}-\frac{\Delta {\mathbf{x}}_n^{⊺}(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n)(W^{-1}\Delta {\mathbf{x}}_n)(W^{-1}\Delta {\mathbf{x}}_n{)}^{⊺}}{(\Delta {\mathbf{x}}_n^{⊺}(W^{-1}\Delta {\mathbf{x}}_n){)}^2}$ where $W^{-1}\Delta {\mathbf{x}}_n=\Delta {\mathbf{f}}_n$ by the definition $=\frac{\Delta {\mathbf{f}}_n(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}+(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n)\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{x}}_n^{⊺}\Delta {\mathbf{f}}_n}-\frac{\Delta {\mathbf{x}}_n^{⊺}(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n)\Delta {\mathbf{f}}_n\Delta {\mathbf{f}}_n^{⊺}}{(\Delta {\mathbf{x}}_n^{⊺}\Delta {\mathbf{f}}_n{)}^2}$ $=\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)J_{n-1}\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$ Therefore, updating formula is $J_n=J_{n-1}+\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)J_{n-1}\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$

And by the Sherman–Morrison Formula, $H_n=H_{n-1}+\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{x}}_n^{⊺}\Delta {\mathbf{f}}_n}-\frac{H_{n-1}\Delta {\mathbf{f}}_n(H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}{H}_{n-1}\Delta {\mathbf{f}}_n}$ and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-H_n\mathbf{f}({\mathbf{x}}_n)$

Link to original

Broyden Family Method

Definition

Broyden family update is obtained from combining the BFGS and the DFP method

Algorithm

$B_n=(1-{\alpha }_{n-1})J_{n-1}^{BFGS}+{\alpha }_{n-1}{J}_{n-1}^{DFP}$ where $\alpha \in [0,1]$

Facts

If the $\alpha$ of Broyden Family is a $\frac{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n-\Delta {\mathbf{x}}_n^{⊺}{J}_{k-1}\Delta {\mathbf{x}}_n}$, then the update is equal to Symmetric Rank-One Method $B_n=B_{n-1}+\frac{(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n)(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}}{(\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}\Delta {\mathbf{x}}_n}$

Link to original

Method of Lagrange Multipliers

Definition

$\mathcal{L}(x,\lambda ):=f(x)+\lambda g(x)$

The method of Lagrange multipliers is a method for finding the local maxima and minima of a function subject to equality constraints

Solution

Given general problem $\underset{x}{\min }f(x)\text{subject to}g(x)=0$

In order to find the maximum or minimum of a function $f(x)$ subject to the equality constraint $g(x)=0$, find the stationary point of $\mathcal{L}(x,\lambda )$ considered as a function of $x$ and the Lagrange multiplier $\lambda$. In other words, all partial derivatives should be zero. ${\nabla }_x\mathcal{L}(x,\lambda )=0,{\nabla }_{\lambda }\mathcal{L}(x,\lambda )=0⟺{\nabla }_{x}f(x)=\lambda {\nabla }_{x}g(x),g(x)=0$ The solution of the constrained optimization problem is always a Saddle Point of the Lagrangian function $\mathcal{L}(x,\lambda )$.

Facts

The gradient of constraint ${\nabla }_{x}g(x)$ and the gradient of the function ${\nabla }_{x}f(x)$ should be in same or directions.

Proof ${\nabla }_{x}f(x)+\lambda {\nabla }_{x}g(x)=0⟹{\nabla }_{x}f(x)=-\lambda {\nabla }_{x}g(x)$

If ${\nabla }_{x}f(x)$ and ${\nabla }_{x}g(x)$ don’t have same or directions, then there is the direction decreasing $f(x)$ subject to $g(x)=0$

If ${\nabla }_{x}f(x)$ and ${\nabla }_{x}g(x)$ have the same or opposite direction, then there is no direction decreasing $f(x)$ subject to $g(x)=0$

Link to original

Infeasible Start Newton's Method

Definition

Algorithm

Solve the minimization problem with the equality condition $\min f(\mathbf{x})$ subject to $A\mathbf{x}=\mathbf{b}$

Use a Newton’s Method to find the optimal point ${\mathbf{x}}^{\ast }$ satisfying above conditions

The quadratic Taylor approximation of $f(\mathbf{x}+(\Delta \mathbf{x}))$ at the point $\mathbf{x}$ is $f(\mathbf{x}+(\Delta \mathbf{x}))\simeq f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})$

The minimization problem is $\min f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})$ subject to $A((\Delta \mathbf{x})+\mathbf{x})=\mathbf{b}$

The Lagrangian function is $\mathcal{L}(\mathbf{x},\mathbf{w})=f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})+{\mathbf{w}}^{⊺}(A(\Delta \mathbf{x})+A\mathbf{x}-\mathbf{b})$ where $\mathbf{w}$ is a Lagrangian multiplier

The optimality condition is ${\nabla }_{(\Delta \mathbf{x})}\mathcal{L}(\mathbf{x},(\Delta \mathbf{w}))={\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})+\nabla f(\mathbf{x})+{\mathbf{w}}^{⊺}A=0,A(\Delta \mathbf{x})=-(A\mathbf{x}-\mathbf{b})$

In a matrix form, $\left[\begin{array}{cc}{\nabla }^{2}f(\mathbf{x})& A^{⊺}\\ A& 0\end{array}\right]\left[\begin{array}{c}(\Delta \mathbf{x})\\ \mathbf{w}\end{array}\right]=-\left[\begin{array}{c}\nabla f(\mathbf{x})\\ A\mathbf{x}-\mathbf{b}\end{array}\right]$

we solve this linear equation to find the Newton direction $(\Delta \mathbf{x})$

Link to original

Backtracking Line Search

Definition

The method to determine the amount to move along a given search direction (learning rate).

Algorithm

We want to find a learning rate minimizing the cost function $\underset{t>0}{\mathrm{argmin}}f(x+t\Delta x)$

Exact line search

The optimal $t$ can be obtained by using grid search in the interval $[0,1]$ However, it causes substantial computational costs.

Backtracking line search

Identify a value of $\alpha$ that provides a reasonable amount of improvement in the objective function, rather than to find the actual minimizing value $t$

The backtracking line search starts with a large $t$ and iteratively shrinks it until the value is enough to provide a decrease in the objective function.

Calculate the gradient of objective function with respect to learning rate $t$ at the point $t=0$ ${\nabla }_{t}f(x+t\Delta x)\simeq f(x)+\nabla f(x)t\Delta x$

and define a parameter $\alpha \in (0,\frac{1}{2})$ which modify the slope of $f(x)+\nabla f(x)t\Delta x$

Now, the line $f(x)+\alpha \nabla f(x)t\Delta x$ is used to check whether the decrease in the objective function is enough

Start from large $t$ usually $1$, and iteratively shrinks it by multiplying $\beta \in (0,1)$ to $t$ until the value is lower than the line

If the condition $f(x+t\Delta x)<f(x)+\alpha \nabla f(x)t\Delta x$ is satisfied, then use $t$ as a learning rate

Link to original

Duality

Definition

Optimization problems may be viewed from either the primal problem or the dual problem.

Properties

Consider the following optimization problem

The original problem is called a Primal problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$ Let a $\mathcal{D}$ be the domain of the problem and the $\mathcal{X}\in \mathcal{D}$ be its feasible set

The Lagrangian function corresponding to the primal problem is called a Lagrangian primal function $\mathcal{L}(x,\mu ,\lambda )=f(x)+\mu g(x)+\lambda h(x)$ where the variable $x$ is called a Primal variable, and $\mu ,\lambda$ are called Dual variables

Since $\forall x\in \mathcal{X}\Rightarrow g(x)\le 0\wedge h(x)=0$ by the constraints, the Lagrangian primal function is always lower than or equal to the $f(x)$ for all $x$ in the feasible set $L(x,\lambda ,\mu )=f(x)+\mu g(x)+\lambda h(x)\le f(x),\forall x\in \mathcal{X}$

Let a primal optimal value $f(x^{\ast })$ be the feasible optimal value of the primal problem $f(x^{\ast })=\underset{x\in \mathcal{X}}{\min }f(x)$

Let a Lagrange dual function $q(\mu ,\lambda )$ be the minimum of the Lagrangian primal function for all $x$ in the domain $q(\mu ,\lambda ):=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )=\underset{x\in \mathcal{D}}{\min }\left(f(x)+\lambda h(x)+\mu g(x)\right),\forall \mu >0,\forall \lambda$

We say another optimization problem for the Lagrange dual function $q(\mu ,\lambda )$ a Dual problem $\max q(\mu ,\lambda )$ subject to $\mu \ge 0$

Since the Lagrange dual function minimize the Lagrangian primal function $\forall x\in \mathcal{D}$, it is always lower than or equal to the primal optimal value that minimizes that $\forall x\in \mathcal{X}$ $q(\mu ,\lambda )=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )\le \underset{x\in \mathcal{X}}{\min }\mathcal{L}(x,\mu ,\lambda )=\mathcal{L}(x^{\ast },\mu ,\lambda )=f(x^{\ast })+\lambda h(x^{\ast })+\mu g(x^{\ast })\le f(x^{\ast })\forall \mu >0,\forall \lambda$

Let a dual optimal value be the maximum of the dual problem $q(\mu ,\lambda )$ $q({\mu }^{\ast },{\lambda }^{\ast }):=\underset{\mu ,\lambda }{\max }q(\mu ,\lambda )=\underset{\mu ,\lambda }{\max }(\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda ))\forall \mu >0,\forall \lambda$

Then, by the above inequality, $q({\mu }^{\ast },{\lambda }^{\ast })$ become the lower bound of $f(x^{\ast })$ $q(\mu ,\lambda )\le q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })$ This property is called a Weak Duality $q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })$

and the difference between the dual optimal value and the primal optimal value is called a Duality Gap $f(x^{\ast })-q({\mu }^{\ast },{\lambda }^{\ast })$

If the dual optimal value and the primal optimal value are the same, then this property is called a Strong Duality $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$

Solution for the Problem Satisfying Strong Duality

Find the Lagrange dual function $q(\mu ,\lambda ):=\underset{x\in \mathcal{D}}{\min }\mathcal{L}(x,\mu ,\lambda )$ by using the gradient condition ${\nabla }_x\mathcal{L}(x,\mu ,\lambda )=0$ find the dual optimal variables ${\mu }^{\ast },{\lambda }^{\ast }$ from the dual problem $\underset{\mu ,\lambda }{\max }q(\mu ,\lambda )$ by using the gradient condition ${\nabla }_{\mu ,\lambda }q(\mu ,\lambda )=0$ obtain the primal optimal variable $x^{\ast }$ using the dual optimal variables ${\mu }^{\ast },{\lambda }^{\ast }$

Visual Explanation of Duality

Consider an optimization problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0$

Let a set $\mathcal{G}$ where $\mathcal{G}=\{(g(x),f(x))|x\in \mathcal{D}\}$

And let $p^{\ast }$ be the primal optimal solution $p^{\ast }=\inf (\{t|(u,t)\in \mathcal{G},u\le 0\})$

By definition of Lagrange dual function, $g(\lambda )=\underset{x\in \mathcal{D}}{\inf }(f(x)+\lambda g(x))=\underset{x\in \mathcal{D}}{\inf }(t+\lambda u)=\inf (\{(\lambda ,1{)}^{⊺}(u,t)|(u,t)\in \mathcal{G}\})$ where $\lambda \ge 0$

Consider $u-t$ plane Where the feasible region is of $\mathcal{G}\cap u\le 0$

The optimal value $p^{\ast }$ is given by the tangent horizontal line that indicates the minimum value when $u\le 0$

Since $\lambda \ge 0$, the line always has negative slope. So, for a given $\lambda$, the line $t=-\lambda u+g(\lambda )$ provides the lower bound of the objective function $t=f(x)$

The figure shows the hyperplanes for different values $\lambda$ We see that ${\lambda }^{\ast }$ gives the best lower bound $d^{\ast }$, also see that Strong Duality does not hold because $p^{\ast }\ne d^{\ast }$

Optimality Property

$\exists \bar{x},\exists \bar{\lambda },\exists \bar{\mu },q(\bar{\mu },\bar{\lambda })=f(\bar{x})\Rightarrow q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })\wedge f(\bar{x})=f(x^{\ast })$ If we have feasible solutions to the primal and dual problems such that their respective objective functions are equal, then these solutions are optimal to their respective problems

Proof Let a prime variable be $\bar{x}$ and dual variables be $\bar{\lambda },\bar{\mu }$ satisfying $q(\mu ,\lambda )=f(x)$

Since the primal optimal $x^{\ast }$ minimize $f(x^{\ast })$, the value $f(\bar{x})$ with the prime variable $\bar{x}$ always greater than or equal to the $f(x^{\ast })$ $q(\mu ,\lambda )\le q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })\le f(\bar{x})$

And by the assumption, the first term and the last term of the inequality become the same. $q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })=f(\bar{x})$

Then, by the equality $q(\bar{\mu },\bar{\lambda })=q({\mu }^{\ast },{\lambda }^{\ast })$, the dual variable $\bar{\lambda },\bar{\mu }$ are the dual optimal, and by the equality $f(x^{\ast })=f(\bar{x})$, the primal variable $\bar{x}$ is the primal optimal And the two are the same.

Therefore, values $\bar{x},\bar{\lambda },\bar{\mu }$ are optimal.

Facts

If the primal is a minimization problem, then the dual is a maximization problem, and vice versa

The solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal, and vice versa

For the minimization primal problem, the dual optimal is a lower bound of the primal optimal

Link to original

Duality Gap

Definition

$p^{\ast }-d^{\ast }\iff f(x^{\ast })-q({\mu }^{\ast },{\lambda }^{\ast })$

The difference between the primal and dual solutions

Link to original

Weak Duality

Definition

For a minimization problem, $q(d^{\ast })\le f(p^{\ast })\iff q({\mu }^{\ast },{\lambda }^{\ast })\le f(x^{\ast })$ The solution to the primal problem is always greater than or equal to the solution to the dual problem

The Duality Gap of an optimization problem is always greater than or equal to zero

Link to original

Strong Duality

Definition

$f(p^{\ast })=q(d^{\ast })\iff f(x^{\ast })=q({\mu }^{\ast },{\lambda }^{\ast })$

The primal optimal objective and the dual optimal objective are equal. The Duality Gap of an optimization problem is zero.

Facts

If a strong duality holds, the dual optimal $\iff$ primal optimal

Link to original

Slater's Condition

Definition

For a convex problem, there exists a point $x$ such that $h(x)=0$ and $g(x)<0$

Link to original

Karush-Kun-Tucker Conditions

Definition

By allowing inequality constraints, generalizes the method of Lagrange multiplier, which allows only equality constraints.

Given general problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

The KKT conditions are

• Stationarity: $\nabla \mathcal{L}(x,\mu ,\lambda )=\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$
• Primal feasibility: $h(x)=0,g(x)\le 0$
• Dual feasibility: $\mu \ge 0$
• Complementary slackness: $\mu g(x)=0$

Facts

The gradient of inequality constraint ${\nabla }_{x}g(x)$ and the gradient of the function ${\nabla }_{x}f(x)$ should be in opposite directions.

If ${\nabla }_{x}f(x)$ and ${\nabla }_{x}g(x)$ don’t have opposite directions, then there is the area(direction) decreasing both $f(x)$ and $g(x)$

For a problem with Strong Duality, $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal $\Rightarrow$ $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT conditions

For a convex optimization, $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT condition $\Rightarrow$ Strong Duality holds

Proof Since $f(x),h(x),g(x)$ are all convex function, the Lagrangian primal function $\mathcal{L}(x,\mu ,\lambda )=f(x)+\lambda h(x)+\mu g(x)$ is also convex

Let $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ be the values satisfy KKT conditions. By the stationarity condition, $\nabla \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })+\lambda \nabla h(x^{\ast })+\mu \nabla g(x^{\ast })=0$ So, $x^{\ast }$ is a local minimum of $\mathcal{L}(x,\mu ,\lambda )$ and by the convexity, it is also global minimum Therefore, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })=q({\mu }^{\ast },{\lambda }^{\ast })$^[Lagrange dual function]

Also, by the complementary slackness and primal feasibility conditions, ${\mu }^{\ast }g(x^{\ast })=0,h(x^{\ast })=0$ So, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+\lambda h(x^{\ast })+\mu g(x^{\ast })=f(x^{\ast })$ Therefore, the dual optimal value and the primal optimal value is the same. In other words, satisfy the Strong Duality condition $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$

$\therefore x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal

For a problem with Slater’s Condition (ensure Strong Duality and convexity), and $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT condition $\iff$ $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal

Proof Let $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ be the primal and dual solutions

Since ${\mu }^{\ast },{\lambda }^{\ast }$ are the dual optimal, the dual optimal value $q({\mu }^{\ast },{\lambda }^{\ast })$ can be expressed as an expression in regard to $x$ $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})$ where $\bar{x}:=\underset{x}{\mathrm{argmin}}\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)$

Since $x^{\ast }$ is a feasible value, the $q({\mu }^{\ast },{\lambda }^{\ast })$ with $x^{\ast }$, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ is always greater than or equal to the $q({\mu }^{\ast },{\lambda }^{\ast })$ with $\bar{x}$ $f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})\le f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ and by the constraints of Lagrangian primal function, $h(x)=0\Rightarrow {\lambda }^{\ast }h(x^{\ast })=0$ and $g(x)\le 0\wedge \mu \ge 0\Rightarrow {\mu }^{\ast }g(x^{\ast })\le 0$ So, $f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })\le f(x^{\ast })$

In summary $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})\le \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })\le f(x^{\ast })$

Since Slater’s Condition ensures Strong Duality $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$, the inequality become the equality $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=f(x^{\ast })$ Therefore, $f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=f(x^{\ast })\Rightarrow {\mu }^{\ast }g(x^{\ast })=0$, so the complementary slackness condition is satisfied Also, $\underset{x}{\min }\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })\Rightarrow x=\underset{x}{\mathrm{argmin}}\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })\Rightarrow \nabla \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })+\lambda \nabla h(x^{\ast })+\mu \nabla g(x^{\ast })=0$, so the stationary condition is satisfied Finally, since $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are the primal and dual solutions, the constraints of Lagrangian primal and dual function, satisfy the primal and dual feasibility condition

Link to original

Barrier Method

Definition

An interior point optimization technique used to solve constrained optimization problems. It involves adding a barrier or penalty term to the objective function that penalizes solutions for being outside the feasible region.

Algorithm

Consider the optimization problem with an inequality constraint

$\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

The KKT Conditions of the problem are the following

• $\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$^[Stationarity]
• $h(x)=0,g(x)\le 0$^[Primal feasibility]
• $\mu \ge 0$^[Dual feasibility]
• $\mu g(x)=0$^[Complementary slackness]

Interior point methods solve the problem whose complementary slackness condition is relaxed $\mu g(x)=-t$ where $t>0$ $\Rightarrow \mu =-\frac{t}{g(x)}$

the stationary condition become $\nabla f(x)+\lambda \nabla h(x)-t\frac{\nabla g(x)}{g(x)}=0\iff \nabla f(x)+\lambda \nabla h(x)-t\ln (-g(x))=0$ where $-t\ln (-g(x))$ is called a logarithmic barrier function

As $t$ large, the logarithmic barrier function functions like an indicator function.

Now, by the definition of log function, $g(x)$ should be negative or zero, so the primal feasibility condition holds. Also, by the relaxed complementary slackness conditions, $\mu$ is positive or zero, so the dual feasibility conditions holds

Now the conditions have to be satisfied are the following

• $\nabla f(x)+\lambda \nabla h(x)-t\nabla \ln (-g(x))=0$
• $h(x)=0$
• $-g(x)>0$
• $t>0$

and the problem with inequality become the problem with equality $\underset{x}{\min }f(x)-t\ln (-g(x))$ subject to $h(x)=0$

It can be solved using Newton’s Method

Newton’s Method’s approximation becomes unstable if $t$ is too small and the current point is far from optimal. So, we initially choose large $t$ and iteratively shrink it.

Analytic Central Point of Feasible Region

If $t$ is very large, then the optimization problem become the following. $\underset{x}{\min }-t\ln (-g(x))$ subject to $h(x)=0$

Since $\ln$ is a monotonic increasing function, the problem can be transformed as $\underset{x}{\min }g(x)$ subject to $h(x)=0$

So, it finds the analytic central point of feasible region (gravity of the feasible region)

Phase 1 method

In the iteration, we have to find the initial points satisfying constraints $t_0,x_{0,}{\lambda }_0$ satisfying $t_0>0,g(x_0)<0$

To ensure the $g(x_0)<0$ condition, transform the optimization problem only at the initial stage. $\underset{x}{\min }f(x)-t_0\ln (s-g(x))$ subject to $h(x)=0,s=0$

Now the problem can be solved using Infeasible Start Newton’s Method

Link to original

Primal-Dual Interior-Point Method

Definition

An interior point optimization technique used to solve constrained optimization problems. Converging and accuracy are faster than Barrier Method

Algorithm

Consider the optimization problem with an inequality constraint

$\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

The KKT Conditions of the problem are the following

• $\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$^[Stationarity]
• $h(x)=0,g(x)\le 0$^[Primal feasibility]
• $\mu \ge 0$^[Dual feasibility]
• $\mu g(x)=0$^[Complementary slackness]

Interior point methods solve the problem whose complementary slackness condition is relaxed $\mu g(x)=-t$ where $t>0$

Instead of substituting $\mu$ in the stationary condition with $-\frac{t}{g(x)}$ like the Barrier Method, Primal-dual interior method directly solve the problem with Newton’s Method

Now, the conditions have to be satisfied are the following

• $\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$
• $\mu g(x)+t=0$
• $h(x)=0$
• $t>0$

and the problem with inequality become the problem with equality $\underset{x}{\min }f(x)$ subject to $\mu g(x)+t=0,h(x)=0$

It can be solved using Newton’s Method

Link to original