4
$\begingroup$

I proposed a similar question involving logarithms, but the problem is about scalar.

I am trying to solve the more generalized form:

$$ \min_{\mathbf{x} \in \mathbb{R}^N_+} \left( \sum_i \left( h_i^T(\mathbf{x}\circ\mathbf{x}) - \mathbf{c_1}\log h_i^T(\mathbf{x}\circ\mathbf{x})\right) + r_1\parallel \mathbf{x} - \mathbf{c_2}\parallel_2^2 \right)$$

where $\mathbf{c_1} \in \mathbb{R}^+$, $\mathbf{c_2} \in \mathbb{R}^N_+$, $h_i \in \mathbb{R}^{N}_+$ is each column of a known matrix, $r_1 \in \mathbb{R}^+$. All are constants.

So, for scalar quadratic eqation, we can find the square root via dividing $(1+r_1)$, but when $1$ is a matrix $H$, how to deal with this form?

But I don't know whether directly extension of scalar quadratic equation is right. Can anyone help me? Thanks in advance!


Edit: formulate the problem to make it clearly.

$\endgroup$
7
  • 1
    $\begingroup$ It's not clear what is meant by argmin of a vector argument. Is it the vector with minimum length? $\endgroup$ – greg Nov 27 '19 at 2:07
  • $\begingroup$ @greg That means the $x$ corresponding to the cost function $f(x)$ which has the minmium value. Please see en.wikipedia.org/wiki/Arg_max. $\endgroup$ – stander Qiu Nov 27 '19 at 2:22
  • $\begingroup$ @greg I think you are talking about two different things. argmin refers to the $x$ when $f(x)$ has minimum value, not $x$ with minimum value in some metrics. If $f(x)$ is a convex optimization problem, then $x^*$ is the solution of $f(x)$ when $ f'(x) = 0 $. $\endgroup$ – stander Qiu Nov 27 '19 at 2:51
  • $\begingroup$ @greg Or in other terms: hope to find the $x^*$ when $f(x)$ has the minimum value. $\endgroup$ – stander Qiu Nov 27 '19 at 2:52
  • $\begingroup$ Okay, but you still haven't told us what the function $f(x)$ is. $\endgroup$ – greg Nov 27 '19 at 3:59
3
$\begingroup$

Using a convention where uppercase latin letters are matrices, lowercase latin are vectors, and greek letters are scalars, define the following variables. $$\eqalign{ \rho &= r_1,\quad \lambda = c_1,\quad a = c_2,\quad H = [\,h_1\;h_2\;h_3\ldots] \\ w &= H(x\circ x),\quad W = {\rm Diag}(w),\quad X = {\rm Diag}(x) \\ dw &= 2HX\,dx,\quad Q = I-\lambda W^{-1} \\ y &= w - \lambda\log(w) \;\implies\; dy = (I-\lambda W^{-1})\,dw = 2QHX\,dx \\ \phi &= \rho(x-a):(x-a) + {\tt\large 1}:y \\ }$$ where the scalar on the final line is the objective function written using a colon to represent the trace/Frobenius product, i.e. $\;A:B = {\rm Tr}(A^TB)$.

Calculate the differential and gradient of the final scalar. $$\eqalign{ d\phi &= 2\rho(x-a):dx + {\tt\large 1}:dy \\ &= 2\rho(x-a):dx + {\tt\large 1}:2QHX\,dx \\ &= \big(2\rho(x-a) + 2XH^TQ{\tt\large 1}\big):dx \\ \frac{\partial\phi}{\partial x} &= 2\rho(x-a) + 2XH^TQ{\tt\large 1} \\ }$$ Set the gradient to zero, substitute $Q$, and multiply by $\frac{1}{2}X^{-1}$ $$\eqalign{ 0 &= \rho{\tt\large 1} - \rho\bigg(\frac{a}{x}\bigg) + H^T{\tt\large 1} - \lambda H^T\bigg(\frac{{\tt\large 1}}{w}\bigg) \\ \bigg(\frac{\rho a}{x}\bigg) &= \rho{\tt\large 1}+H^T{\tt\large 1}-\lambda H^T\bigg(\frac{{\tt\large 1}}{w}\bigg)\\ x &= \frac{\rho a}{\rho{\tt\large 1} + H^T\Big({\tt\large 1}-\frac{\lambda{\tt\large 1}}{w}\Big)} \\ }$$ This is not an explicit solution because the vector $w$ in the denominator on the RHS is a function of $x$, but it can form the basis of an iterative numerical method.

NB: The notation $\big(\frac{a}{b}\big)$ represents element-wise division of the vector $a$ by the vector $b$.

$\endgroup$
1
  • $\begingroup$ Hi, I am sorry that I cant access to the Internet these days. The bonus has expired. Sorry that I could not response in time. Thanks for you answer! $\endgroup$ – stander Qiu Dec 7 '19 at 10:01

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.