How to ensure the numeric value is always positive in Optimization Python?

Question

I am currently performing optimization onto a quadratic function by manually coding the algorithm:

$$\min f = x^T v x - r^T x\\ \text{subject to } x \geq 0\, .$$

Here, optimizing the function without the constraint above is not a problem at all. However, if I want to add this inequality constraint, I do not know how can I implement it in Python. I have seen Scipy Optimization Package uses np.clip to clamp the array within the bound, but it is forcing negative values to 0, thus somehow affecting the answer to finding the minimum point.

I wish to know if there is any other method to naturally ensure the array of numeric values always stays positive in every iteration?

Answer 1

Consider a variable transform. Assuming you care about the individual entries of $x$ and not something like its determinant, you can transform the $x_i$ such that the new variable $y_i$ is not bounded but the $x_i$ are. Logarithms are helpful for this;

$y_i=log(x_i)$

Then you can adjust your objective function to include the transform back to $x$ and optimize for $y=(-\infty, \infty)$.

Answer 2

$ \def\bbR#1{{\mathbb R}^{#1}} \def\a{\alpha}\def\b{\beta}\def\l{\lambda} \def\o{{\tt1}}\def\p{\partial} \def\LR#1{\left(#1\right)} \def\diag#1{\operatorname{diag}\LR{#1}} \def\Diag#1{\operatorname{Diag}\LR{#1}} \def\trace#1{\operatorname{Tr}\LR{#1}} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\c#1{\color{red}{#1}} \def\CLR#1{\c{\LR{#1}}} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} $Introduce an unconstrained vector $w$ and use it to construct an $x$ vector such that $x>0$ using an elementwise exponential function $$\eqalign{ x &= {e^w} \qiq dx = x\odot dw \\ }$$ Then calculate the gradient of the function with respect to $w$ and follow the usual prescription of setting it to zero and solving for the optimal vector. $$\eqalign{ f &= V:xx^T - r:x \\ df &= \LR{2Vx - r}:dx \\ &= \LR{2Vx - r}:\LR{x\odot dw} \\ &= x\odot \LR{2Vx - r}:dw \\ \grad{f}{w} &= x\odot \LR{2Vx - r} \;\doteq\; 0 \\ r &= 2Vx \\ x &= \frac 12V^+r \\ }$$ In the above, $V^+$ denotes the pseudoinverse, $(\odot)$ denotes the elementwise/Hadamard product, and $(:)$ denotes the matrix inner product, i.e. $$\eqalign{ A:A &= \|A\|^2_F \\ A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;=\; \trace{A^TB} \\ A:\LR{B\odot C} &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}\LR{B_{ij}C_{ij}} \\ &= \sum_{i=1}^m\sum_{j=1}^n \LR{A_{ij}B_{ij}}C_{ij} \\ &= \LR{A\odot B}:C \\ }$$ Substitute this back into the original function $$\eqalign{ f &= x^TVx - r^Tx \\ f &= \frac 14\LR{r^TV^+VV^+r} - r^TV^+r \\ &= \frac 14\LR{r^TV^+r}- \LR{r^TV^+r} \\ &= -\frac 34\LR{r^TV^+r} \\ }$$