Hot answers tagged

4

You additionally need that your set is bounded, otherwise it may have too few extreme points: any convex, closed cone has only one extreme point For any closed, convex $C$, consider $C \times \{0\}$: no extreme points. If your set is bounded, it is (assuming that the ambient space is finite-dimensional) compact. By Krein-Milman, the set is the convex ...


4

What I have found is that looking at the dual problem with a custom prox function is almost always helpful. To derive it, I first rewrite the problem as follows: \begin{array}{ll} \text{minimize} & \tfrac{1}{2} \| x - \hat{x} \|_2^2 + t \\ \text{subject to} & \| x \|_2 \leq t \\ & x \succeq 0 \end{array} where $t$ is a new variable. To ...


3

No, that conclusion does not hold because generally, the product of two convex functions need not be convex. As an example, $f(x, y) = x y^{-1}$ (for $x, y > 0$) is a posynomial function, but not convex: $$ f(\frac{1+5}{2}, \frac{1+3}{2}) = \frac 32 > \frac 43 = \frac 12 \left( f(1, 1) + f(5, 3)\right) $$


2

We need the $\lambda_i$s positive in order to penalize a violation of the constraints $f_i(x)\leq 0$. More precisely, if they were negative, minimizing $L$ would likely give $x$s for which $f_i(x)>0$ (because then $\lambda_if_i(x)<0$ making $L$ smaller) which is in violation to our primal problem. The final inequality holds by construction of the $L$. ...


2

Consider the yellow and orange convex figures, which have the same bounding ellipsoid but different bounded ellipsoids. Therefore, given just the bounding ellipsoid you cannot determine the bounded ellipsoid. (Nor vice versa.) You must know the figure $K$. A better, limiting, example: Suppose $K$ is an ellipsoid. Then the bounding ellipsoid and the ...


2

The inequality for large $x$ implies that $\lambda_2\geq1.$ The function $f(x)=\lambda_1+\lambda_3x^2$ determines a parabola centered around the $Y$ axis (where in order to cover the case $\lambda_3=0$ we temporarily agree to call a horizontal line a parabola, as well). Thus for any given $\lambda_2\geq1$ we look for a parabola centered around the $Y$ axis ...


2

Let $f(x,y)=\log(e^{x+y}+1)$. Then, we have $$\frac{\partial f(x,y)}{\partial x}=\frac{\partial f(x,y)}{\partial y}=\frac{e^{x+y}}{e^{x+y}+1}=1-\frac{1}{e^{x+y}+1}$$ and $$\frac{\partial^2 f(x,y)}{\partial x^2}=\frac{\partial^2 f(x,y)}{\partial y^2}=\frac{\partial^2 f(x,y)}{\partial x\partial y}=\frac{e^{x+y}}{(e^{x+y}+1)^2}>0$$ Therefore, since the ...


2

No I don't think so. Taking log x = p & log y = q. You can write it as $f(ap + bq) \leq f(p)^a f(q)^b$ Now replace p and q by x and y.


2

In my understanding (and in a very large generality), an optimization problem $$\min\{f(x), \;\;x\in C\}$$ is convex if $C$ is convex, and $f:C\to\mathbb{R}$ is convex. As an example, we often give the following framework, where $C$ is described by equality and inequality constraints: $$\min\{f(x), \;\;\forall 1\leq i \leq n, g_i(x)=0, \;\;\forall 1\leq ...


2

Second derivate is $-\dfrac{e^x}{(1+e^x)^2}<0$. So the correct answer is in your book: $f$ is not convex. Indeet, it is concave.


1

Note your terminology error. You asked if the function was convex--but you gave us an entire optimization model. You should be asking instead if your model is a convex optimization problem, not a convex function. And in fact, your objective function is concave---but it needs to be. So it's all the more important to get that terminology correct. The ...


1

Perhaps this situation is analogous to the derivative versus directional derivative (as might be familiar from multi-variable calculus). Recall, given a function say $f:R^n \to R$, the gradient is defined as $\nabla f = \sum_{i = 1}^n \frac{\partial f}{\partial x_i} dx_i$ or alternatively $\left(f_{x_1}, f_{x_2}, \dots, f_{x_n}\right)$ while the ...


1

EDIT: after posting this I noticed from the tags that this is specifically about convex functions. In this case I don't know that to tell you. I'll just leave this answer up, though, in case someone might find it useful for something. This is far from a complete answer, but here's a counterexample: let $$f(x) = \begin{cases} -1 & x < 1 \\ 0 & x ...


1

If $A$ is non-symmetric, there is no $f : \mathbb{R}^n \to \mathbb{R}^n$, such that $f'(x) = A \, x + c$. Indeed, this would imply that the Hessian $f''(x) = A$ is non-symmetric. (However, there are other methods to deal with problem (1).)


1

You have $\nabla(f\circ g)(x) = f'(g(x)) \, \nabla g(x)$. Consequently $$\nabla^2(f \circ g)(x) = f''(g(x)) \, \nabla g(x) \, \nabla g(x)^\top + f'(g(x)) \, \nabla^2 g(x).$$ Then, it is easy to check the definiteness of the Hessian.


1

Figured it out! As Erwin pointed out, the formulation above is valid (save the fact that it should be optimized over x and t together). In order to write it in the form suggested by the problem, I needed to stack x and t: $$\min_{u=[x^T\;t^T]^T}\begin{bmatrix}0\\1\end{bmatrix}^T\begin{bmatrix}x\\t\end{bmatrix} \quad \text{subject to}\; \begin{bmatrix}I ...


1

$rank(M) = \min\{r|\exists V \in L(m,r), W \in L(n,r). M = V^TW \}$ where $L(m,n)$ is the space of $n\times m$ matrices is my rewriting of the (intended) meaning of your definition. You should verify that it is equivalent. I think this definition (particularly compared to your definition of rank as the dimension of the image) makes it much easier to answer ...


1

A function $f$ is called log-convex if $\ln f$ is convex. It is not that difficult to show that a sum of two log-convex functions is log-convex. All you need to do is to notice that the function $\exp g_i$ is log-convex. Another approach would be to show by definition for the case $m=2$ and then generalise to an arbitrary $m$.


1

Hint Note that $$\dfrac{\partial f}{\partial x}=\dfrac{y^{\alpha+1}}{(x+y)^2}>0.$$ Thus, if $x>x_0$ then $f(x,y_0)>f(x_0,y_0).$ So, the maximum point is of the form $(b,y).$ But, on those points it is $$g(y)=f(b,y)=\dfrac{by^{\alpha}}{b+y}.$$ You only need to maximize the function $g(y)$ in $ [0,c].$


1

I do not agree. It looks correct to me. First of all, if variables $x$ and $y$ are unconstrained, it is correct to have $=$ type constraints in the dual. Authors are not required to specify that a variable is unconstrained, they only have to specify which ones are not, and how. This makes sense. If your primal is a minimization problem and constraints are ...


1

It is not necessarily continuous. For example, the function $f(x,y)=x^2,\, y\leq 0$ and $f(x,y)=(x-1)^2,\,y>0$, where $x\in [-2,2]$, $y\in[-1,1]$. You can see that if $\,y\to 0^+\quad x^*(y)\to 1$ and if $\,y\to 0^-\quad x^*(y)\to 0$, because $x^*(y)=0,\,y\leq 0$ and $x^*(y)=1,\,y>0$



Only top voted, non community-wiki answers of a minimum length are eligible