3
$\begingroup$

Let $ x \in \mathbb{R}^n_+$ be a variable such that $\sum_{i=1}^n x_i = 1$. In other words, $x$ is in a probability simplex. I am working on barrier-like functions in nonconvex optimization over such $x$.

Let $f(x) = ||(DR) \cdot(x - \frac{1}{n} \mathbf{1})||_2^2$, where $D$ is a diagonal matrix (off-diagonals are zero), and $R$ is a rotation matrix (non-zero). If we maximize $f(x)$ over $x$, then the maximum value is at an extreme point (convex maximization over a bounded space). So we will have $x_i = 1$ for one $i$ and $x_j = 0$ for all other $j \neq i$. But, if we minimize $f(x)$, then we get $x = \frac{1}{n}\mathbf{1}$, as a norm-squared is non-negative, and this achieves $0$.

Now, let $g(x) = \sum_{i=1}^n \ln(x_i)$. Notice that if we maximize $g$, then the solution is $x = \frac{1}{n}\mathbf{1}$, and if we minimize it, the solution is at an extreme point as $\ln(0) = -\infty$.

So, instead of maximizing $f(x)$, if we maximize $f(x) + g(x)$, then thanks to $g$, we will not have an extreme point solution, and the solution will be slightly going towards the middle of the simplex.

Now my question follows: If I don't select $D$ and $R$ appropriately, then the solution tends to be either very close to the extreme point of the simplex, or directly has $x= \frac{1}{n}\mathbf{1}$ (i.e., same solution if we didn't have $f$). So I am looking for a way to select $D$ and $R$ in a clever way such that the solution is not straightforward. In other words, I don't want the sum-log term to dominate the solution, but also don't want to have a solution that is very close to the extreme points.

Is there any research about selecting such $D$ and $R$ in a good way? I believe rotation matrix is very important here.

$\endgroup$
  • 1
    $\begingroup$ Perhaps you could formulate this as a Bilevel optimization problem, where the inner optimization is maximization with respect to $x$ and the optimization is with respect to $D$ and $R$ where you quantify your preferences into an objective function.for the outer optimization problem. $\endgroup$ – Mark L. Stone Oct 17 at 22:59

Your Answer

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

Browse other questions tagged or ask your own question.