2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ I have typed your equations using MathJax, please check that it is correct. $\endgroup$
    – nicoguaro
    May 4 at 18:28
  • 3
    $\begingroup$ Is $v$ a positive definite matrix? Does $x \geq 0$ mean that all components of $x$ are nonnegative? $\endgroup$
    – nicoguaro
    May 4 at 18:29
  • $\begingroup$ Hi @nicoguaro, thanks for the help! Yes the equation is correct, and yes, $v$ must be at least positive semidefinite and all the $x > 0$ in every iteration $\endgroup$ May 5 at 2:55

2 Answers 2

4
+25
$\begingroup$

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)$.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks @Root of All Things for this suggestion, but I was wondering if transforming it to logarithms will cause any deviation in the minimum point of the objective function? $\endgroup$ May 5 at 2:57
  • $\begingroup$ It shouldn't, in my experience. Note that this transformation requires including the reverse transformation in the objective function: $minf=(e^y)^T v(e^y)−r^T(e^y)$, where this exponential isn't a matrix exponential but the element-wise exponential. This gives the minimum point in the y-space, but that's just one transform away from the minimum point in the x-space. $\endgroup$ May 6 at 3:27
  • 2
    $\begingroup$ That sounds reasonable, I will try this transformation to see its efficiency. Thank you! $\endgroup$ May 7 at 16:30
3
$\begingroup$

$ \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} \\ }$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.