Newton step for ${\min}_{x \in \mathbb{R}^n} \ \sum_{i=1}^n -\ln(1 + \eta_i x_i) \ $ s.t. $A x \leq b$; $-x \leq 0$ to be used in primal-dual

Question

I have a following problem on hand.

P1: \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & \sum_{i=1}^n -\ln(1 + \eta_i x_i) \equiv -e^T \ln(e + \eta \odot x) \\ \text{subject to }\quad & Ax \leq b\\ & -x \leq 0 , \end{align} where $A \in \mathbb{R}_{+}^{m \times n}$, $b \in \mathbb{R}_{++}^{m \times 1}$, $\eta \in \mathbb{R}_{+}^{n \times 1}$, and $e$ is all-ones vector.

Question:

Is my Newton step correct (please see below)?

(it is a part of the primal-dual interior point method).

Your suggestions/feedback will be highly appreciated.

---

Partial attempt

Reformulating the above problem P1 such that \begin{align} \text{minimize}_{x , y} \quad & e^T \ln(e + \eta \odot x) := f(x) \\ \text{subject to }\quad & Ax + y = b\\ & -y, -x \leq 0 . \end{align}

Now forming the Lagrangian ($u \geq 0$, $v \geq 0$, and $w \in \mathbb{R}^m$), \begin{align} L_a(x,y,u,v,w) := f(x) - u^T x - v^T y - w^T(Ax + y - b) . \end{align}

The perturbed KKT conditions can be summarized as following: \begin{align} \frac{\partial L_a}{\partial x} = 0 \Longrightarrow \nabla f(x) - u - A^T w &= 0 \\ \frac{\partial L_a}{\partial y} = 0 \Longrightarrow -v - w &= 0 \\ U x - \tau e &= 0 \\ V y - \tau e &= 0 \\ Ax + y - b &= 0 \\ -y, -x &\leq 0 \ , \end{align} where $U = {\rm Diag}(u)$ and $V = {\rm Diag}(v)$ are diagonal matrices.

Now the Newton step can be shown as

\begin{align} \left[ \begin{array}{ccccc} \nabla^2f(x) & 0 & -I & 0 & -A^T\\ 0 & 0 & 0 & -I & -I \\ U & 0 & X & 0 & 0 \\ 0 & V & 0 & Y & 0 \\ A & I & 0 & 0 & 0 \\ \end{array} \right] \ \left[ \begin{array}{c} \Delta x\\ \Delta y\\ \Delta u\\ \Delta v\\ \Delta w \end{array} \right] &= \ -\left[ \begin{array}{c} \nabla f(x) - u - A^T w\\ -v - w\\ Ux - \tau e \\ Vy - \tau e\\ Ax + y - b \end{array} \right] \end{align} where $0$ corresponds to all-zeros matrix of appropriate size and $I$ denotes an identity matrix of appropriate size.

Answer 1

My answer maybe off-topic as you ask explicitly for a primal-dual interior point algorithm. If you are open for another solver you could try CVX which should work for your problem: http://cvxr.com/cvx/doc/CVX.pdf

CVX is a solver for convex optimization problems with an interface for Matlab. You have to "fit" your problem into the CVX-framework using the sum_log(x) function.

The optimization problem is indeed convex as you have convex constraints and a convex target function.

Please ask if you need further help.