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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 3:27
  • 2
    $\begingroup$ That sounds reasonable, I will try this transformation to see its efficiency. Thank you! $\endgroup$ May 7, 2022 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 and acknowledge you have read our privacy policy.

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