Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (3)

7
votes
0answers
62 views
+50

The Teichmüller space $T_g$ of a closed riemann surface $S_g$ of genus $g \geq 2$ can't be parametrized by $6g-6$ geodesic length functions

Setting: It is well known that the Teichmüller space $T_{g,b}$ of an oriented Riemann surface $S_{g,b}$ of genus $g \geq 2$ with $b \geq 1$ boundary components (satisfying $2g + b \geq 3$) can be ...
1
vote
1answer
10 views

How to give a formula of the perimeter of a $r$-neighborhood of a smooth set in $2D$?

Let $A$ be a simply connected open set in $\mathbb{R}^2$ with smooth boundary. Define $$A^r := \{x \in \mathbb{R}^2: d(x, A) \le r \},$$ where $d$ is the distance function. Let $P$ denote the ...
1
vote
1answer
51 views

Continuously differentiable function injective on convex set

Can you help me solve the following exercise: (a) Let $n\in \mathbb N$ and $G \subset \mathbb R^n$ a convex set, $f:G\to \mathbb R^n$ continuously differentiable with $$det\left(\begin{matrix} \...
1
vote
0answers
35 views

Proof of the rotation matrix is an extreme point of $\text{conv } SO(n)$

Define the set of rotation matrices: \begin{equation} \begin{aligned} SO(n) := \{X\in \textbf{R}^{n\times n}: X^TX=I, \text{det}(X)=1\} \end{aligned} \end{equation} I want to prove that if $X\in SO(...
1
vote
0answers
26 views

Probability that the convex hull of random points is a triangle

Question: Given a fixed number $k > 3$ of random points in the plane, distributed according to a 2D standard normal distribution, what is the probability that all of them lie within the same ...
0
votes
0answers
15 views
+100

References on Rogers-Shephard inequality

If $K\subset \mathbb{R}^n$ is a convex body, let $K'$ be the convex hull of $K$ and $-K$. One of Rogers-Shephard inequalities asserts: $$\operatorname{vol}(K') \le 2^n \operatorname{vol}(K).$$ ...
0
votes
0answers
8 views

Is $ \frac{F}{A}+c_p D K \sqrt{A}+c_g \Theta^2+c_e a D + t e (1-\Theta) D+ \frac{t a}{A}$ quasiconvex?

I am trying to check if the following function is jointly quasiconvex in $A>0,a,\theta \geq 0$. $$ \frac{F}{A}+c_p D K \sqrt{A}+c_g \Theta^2+c_e a D + t e (1-\Theta) D+ \frac{t a}{A}$$ The ...
0
votes
2answers
187 views

Computing subgradients, a basic example.

A vector $v \in \mathbb{R}^n$ is a subgradient of a convex function at $x$ if $$f(y) \geq f(x) + <v, y - x>$$ for all $y \in dom(f).$ The set of all sub gradients is known as the sub ...
0
votes
0answers
12 views

Width of a cone

Let $V=\{v_k\}$ be a collection of vectors of $\Bbb{R}^n$, and define their cone to be the set of all their non-negative linear combinations: $$ C(V):=\Big\{ \sum_k a_k\,v_k; \; a_k\ge 0 \Big\}\;. $$ ...
4
votes
5answers
98 views

Feasible point of a system of linear inequalities

Let $P$ denote $(x,y,z)\in \mathbb R^3$, which satisfies the inequalities: $$-2x+y+z\leq 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
2
votes
1answer
38 views

Solve the closed form solution for argmax of $ x^Ty - x^T\ln(x)$

Let $y \in \mathbb{R}^n, \ln(x) = \begin{bmatrix} \ln(x_1) \\ \vdots \\ \ln(x_n) \end{bmatrix} \in \mathbb{R}^n$ Show that $$x^* = \text{argmax}_{x \in \mathcal{D}} \quad x^Ty - x^T\ln(x)$$ ...
0
votes
0answers
16 views

Mean value theorem for a gradient of convex function

This is from an article, page 19. Let $J(u)=\sum \sqrt {u_i^2+\epsilon}$, and $p^{k+1}=\nabla J(u^{k+1})$, $p^{k}=\nabla J(u^{k})$. Since $J$ is convex, the mean value theorem tells us that $$p^{k+...
0
votes
1answer
51 views

How to prove $(1-x) y \ge 0$ is a convex set?

$x \epsilon [0,1], y> 0 $ Let $(1-\underline{x}) \underline{y} \geq 0 $ and $(1-\bar{x}) \bar{y} \geq 0 $ Let $t \epsilon [0,1]$ $[1- (t\underline{x}+ (1-t)\bar{x})] (t\underline{y}+ (1-t)\bar{y}...
0
votes
0answers
16 views

Properties of trajectories generated by subgradient dynamical system

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function and $x_0\in\mathbb{R}^n$. Consider the subgradient dynamical system: $$ (*) \begin{cases} \dot{x}(t)\in-\partial f(x(t)), \quad \text{a.e....
5
votes
0answers
163 views

Convexity of difference of log-sum-exp: $f(x_1, x_2, x_3, x_4) = \log(e^{x_1} + e^{x_2}) - \log(e^{x_1} + e^{x_2} + e^{x_3} + e^{x_4})$

I would like to know whether the following function $f: \mathbf{R}^4 \to \mathbf{R}$ is concave or not: $$ f(x_1, x_2, x_3, x_4) = \log(e^{x_1} + e^{x_2}) - \log(e^{x_1} + e^{x_2} + e^{x_3} + e^{x_4})...
0
votes
1answer
33 views

Proving that the following is a convex subset

It is given that $I(S)=\{z|\exists x,y \in \mathbb{R}$ such that $(x,y,z)^t \in S$}$\subseteq \mathbb{R}$. How do I show that I(S) is a convex subset? We know that $S \subseteq \mathbb{R}^3$ is ...
1
vote
1answer
46 views

If y is not an exterior point of $K$, then there exists a $x$ in $K$. Is it true?

For a vector $v = (x_1,\ldots,x_d)^t \in \mathbb{R}^d$, we let the function $f$ be $f(v)=|v|^2=v^tv=x_1^2+\cdots+x_d^2$. Is it possible to show that there exists a x $\in K$ which satisfies $f(x)>...
17
votes
5answers
504 views

How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?

Let $A$ be a real $m \times n$ matrix. How do you prove that $\{ Ax \mid x \geq 0, x \in \mathbb R^n \}$ is closed (as in, contains all its limit points)? The inequality $x \geq 0$ is ...
0
votes
1answer
13 views

Continuous, midpoint (strictly) quasi-concave function is (strictly) quasi-concave?

It is known that Midpoint-Convex and Continuous Implies Convex. I am wondering can midpoint quasi-concavity and continuity implies quasi-concavity? If not, what conditions are required instead?
3
votes
5answers
234 views

Sum of real powers: $\sum_{i=1}^{N}{x_i^{\beta}} \leq \left(\sum_{i=1}^{N}{x_i}\right)^{\beta}$

Let $\{x_i\}_{i=1}^{N}$ be positive real numbers and $\beta \in \mathbb{R}$. Can we say that: $$ \sum_{i=1}^{N}{x_i^{\beta}} \leq \left(\sum_{i=1}^{N}{x_i}\right)^{\beta}$$ I know that this holds if $...
0
votes
1answer
44 views

Does being Nonempty Compact Set on $\mathbb{R^+_2}$ imply being Convex set?

Look at the domain of a function $y=x-2$ where $x\in\mathbb{R_+}$. Then, the triangle produced by x and y-intercepts is bounded and closed. So it is compact. Suppose it is also nonempty. Does this ...
0
votes
0answers
27 views

Convexity of the weighted norm

We all know that $f(x)=\|x\|^2$, with $x\in\mathbb{R}^n$, is a strictly convex function of $x$. But know let's spicy up the problem. Let $v\in\mathbb{R}^n$ be a unit vector, i.e., $\|v\|=1$. We want ...
0
votes
0answers
8 views

Is this constraint convex? Determinant of the Hessian is 0.

$a\leq e p_a D A (1-\Theta)$ $a,A$, and $\Theta$ are nonnegative decision variables and all others are positive parameters. Checking the Hessian tells me all of the leading principal minors are zero....
2
votes
1answer
34 views

Upper bound for $\sum_{i=1}^{N}{x_i^{\beta_i}}$

$\{x_i\}_{i=1}^{N}$ a sequence of positive real numbers and $\{\beta_i\}_{i=1}^{N} $ are real numbers such that $\underset{1 \leq i \leq N}\min{\beta_i}$ > 1. Is it possible to find an upper bound of ...
-1
votes
0answers
23 views

Convex subset and linear equalities

Let S denote the set of $(a,b,c)$ $\in$ ${\mathbb{R^3}}$ which satisfies the following equalities: $-2a+b+c \leq 4 $ $a-2b+c \leq 1 $ $2a+2b-c \leq 5 $ $ a \geq 1 $ $ b \geq 2 $ $ c \geq 3 $ ...
1
vote
2answers
98 views

Decrease in the size of gradient in gradient descent

Gradient descent reduces the value of the objective function in each iteration. This is repeated until convergence happens. The question is if the norm of gradient has to decrease as well in every ...
1
vote
0answers
20 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
0
votes
2answers
51 views

A linear map from $ R^3$ into $R^2$

Suppose $a\in (0,1)$ and $$X=\{(x_1,x_2,x_3)\in R^3: a x_1+(1-a) x_2+ x_3\leq 3, x_i\geq 1, i=1,2,3.\}.$$ Define a linear map $\Gamma$ by $(x_1,x_2,x_3)\to (a x_1+(1-a) x_2, x_3)$ . Do we ...
1
vote
2answers
34 views

Inequality involving a convex function

I am stuck, showing the following inequality in an easy way (using only inequalities or something): Let $x\in [-a,a]$ for some $a>0$ and $p\in (1,2)$. I want to show that there then exists a ...
0
votes
0answers
20 views

To prove some of the allegations.

Good day to all! Please help me with the solution of problems in convex analysis. I have tried to use the Hahn-Banach theorem, and theorems about the basic functions, but I unfortunately can't do ...
0
votes
1answer
7 views

Strongly monotone and cocoercive

A map $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ is $m$-strongly monotone if $$ (x-y)^{\sf T}((f(x)-f(y)) \geq m \|x-y\|_2^2 $$ for $m > 0$ and is $\delta$-cocoercive if $$ (x-y)^{\sf T}((f(x)-f(y)) \...
2
votes
1answer
1k views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
2
votes
0answers
62 views

Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project. Say I have two sets of points in three dimensional Cartesian space: A and B. The problem I would like to solve is to find the convex hull V of ...
1
vote
1answer
22 views

Is the root of a sum of squared differences convex?

Let $x \in \mathbb{R}^n$. Let there be a collection of functions $d_i = (x_j - x_k)^2$ (note that the subscripts $j$ and $k$ are fixed for each $d_i$, and there can be repeated use of subscripts on ...
0
votes
1answer
35 views

Related to Caratheodary theorem

If $P$ is a set of vectors $\textbf{x}_i$'s where every $\textbf{x}_i$ is of dimension $d$ and $|P|=K$. In this case at many places I have seen that the vectors $\textbf{x}_2-\textbf{x}_1,\textbf{x}...
0
votes
1answer
64 views

Is the closure of a geodesically convex set convex?

Is the closure of a geodesically convex set convex? If so, is there a simple proof for it? In $ \mathbb{R}^n $ there is a simple proof for it through convergent sequences. How should I apply it on ...
0
votes
1answer
35 views

Needing help with convex analysis

If $f$ is a closed proper convex function defined on $\mathbb{R}^n$, prove that the function $\varphi$ defined by $\varphi(\lambda)=f((1-\lambda)x+\lambda y)$, where $x \in \text{dom}f, y \in \mathbb{...
1
vote
0answers
19 views

Does the (strict) concavity of a function depends on the space in which we consider it?

For instance, $f(x)=\sqrt{x}$ is clearly strictly concave in $\mathbb{R}_+$ but if we consider that function in two dimensions, i.e. $f(x,y)=\sqrt{x}$ with $(x,y)\in\mathbb{R}^2_+$, it seems that it ...
1
vote
0answers
14 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
1answer
22 views

On accelerated Proximal Gradient Methods

I am working on accelerated optimization scheme, which unified in the paper by Paul Tseng, "On Accelerated Proximal Gradient Methods for Convex-Concave Optimization". But unfortunately, it is ...
1
vote
1answer
21 views

The gradient of a convex function is controlled by its oscillation on a larger ball

My problem is Let $f:\mathbb R^n\longrightarrow R$ be a convex function. Knowing that $$|\nabla f(x)|=\sup_{y\neq x}\frac{[f(x)-f(y)]^+}{|x-y|}$$ ($[f(x)-f(y)]^+$ represents $\max\{[f(x)-f(y)],...
1
vote
1answer
52 views

A spectrahedron is a quadric cone when matrices in LMI are in $\mathbb{R}^{2\times 2}$

I am watching a lecture (just at the beginning around 0:50-0:57). The note says when $n=2$, $\mathcal{S}$ is a quadric cone; however, it seems that the professor says "a quadratic cone". On ...
3
votes
2answers
85 views

Solution set of an LMI is convex

I was going through Boyd and Vandenberghe's Convex Optimization book. There they mentioned (at page number $38$) that the solution set of a linear matrix inequality (LMI) is convex. $$A(x)=x_1A_1+\...
4
votes
1answer
187 views

An explicit construction for an everywhere discontinuous real function with $F((a+b)/2)\leq(F(a)+F(b))/2$?

I would like to know an explicit method on constructing an everywhere discontinuous real function $F$ with the property: $$F((a+b)/2)\leq(F(a)+F(b))/2.$$ There is a non-constructive example (with the ...
1
vote
1answer
68 views

How to find an everywhere discontinuous real function with $F((a+b)/2)<(F(a)+F(b))/2$?

In here I posted a non-constructive everywhere discontinuous real function with $$F((a+b)/2)=(F(a)+F(b))/2$$ based on the using of Hamel basis. And Conifold answered there that there is no explicit ...
2
votes
2answers
42 views

Interior of a preimage of a continuous function

Let $ f:\mathbb{R}^n\rightarrow \mathbb{R} $ be convex. Let there exist a point $ x_0 $ with $ f(x_0)<0 $. Prove that $$ \operatorname{int}\left\lbrace f(x)\ge 0 \right\rbrace = \left\...
0
votes
0answers
27 views

How do I prove that this function is concave on $f_{ij}(x)$?

I am trying to apply convex optimization to the following problem- ${f^*}(x) = \mathop {\arg \max }\limits_{{f_i}(x)} \sum\limits_i {\ln \left\{ {u_i^* - \sum\limits_j {\frac{1}{{\left( {1 - {\rho _{...
0
votes
1answer
52 views

Directional Derivative defines Descent Direction

Let $f:\mathbb{R}^m \mapsto \mathbb{R}$ be a proper convex function that is not necessarily differentiable and let $x\in\mathbb{R}^n$ be such that $\mathbf{0} \notin \partial f(x)$. I want to prove ...
0
votes
1answer
38 views

How to prove the following function is convex?

I was working on a problem and it reduced to show that $$f(a)=log\Big(\sum_{i=1}^{r}a^ix_i\Big)~~a>1, x_i>0$$ is convex. I have $$f^{\prime \prime}(a)=\frac{\partial^2f(a)}{\partial a^2}=\frac{[\...