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)

1
vote
2answers
53 views

Optimization with box constraints - via nonlinear function

I have the following convex optimization problem over $\mathbb{R}^n$ with box constraints: $$\begin{align}\text{minimize }&\;f(x)\\ \text{subject to }&\;x \in [-1,1]^n\end{align}$$ I can see ...
3
votes
1answer
40 views

Is there a way to measure how (non)convex a function is, maybe analogous to condition number?

Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has ...
18
votes
5answers
549 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 ...
2
votes
1answer
20 views

Dual polyhedron & dual cone

From Wiki: Def. of dual of polyhedral (polytope): polyhedra are associated into pairs called duals, where the vertices of one correspond to the faces of the other. EX: 2. Def. of dual ...
9
votes
4answers
2k views

Why is the affine hull of the unit circle $\mathbb R^2$?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $\mathbb R^n$ as $$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + \...
14
votes
1answer
121 views

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 ...
0
votes
0answers
27 views

Concave optimization on closed unit ball, using penalty function

Background: I want to solve an optimization problem like $$\begin{align*}\text{minimize }&f(x)\\ \text{subject to }&\|x\| \le 1.\end{align*}$$ where $x \in \mathbb{R}^d$, $\|\cdot\|$ is the $...
7
votes
2answers
140 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
0answers
30 views

Is sum (convex combination) of quadratic function/aggregator quadratic?

We know convex combination of concave/convex functions are concave/convex. While convex combination of two quasi-convex/quasi-concave functions necessarily quasi-convex/quasi-concave. Common ...
1
vote
1answer
39 views

How Do I Check Convexity Using The Actual Definition?

Suppose $f:\mathbb{R}^{+}\rightarrow\mathbb{R}$ is defined as follows: \begin{eqnarray} f(u)=\text{sgn}(\rho)\left(u^{\rho+1}-1\right),~u\geq 0, \end{eqnarray} where $\rho\in (-1,\infty)$, $\rho\neq 0$...
0
votes
2answers
43 views

Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.

When I read the Convex Optimization, Boyd I noticed a statement about determining a function to be convex or not. It is: "A function is convex iff it is convex when restricted to a any line that ...
1
vote
1answer
70 views

Probability that the convex hull of random points is a triangle

Question: Consider a fixed number $k > 3$ of random points in the plane, each independently distributed according to a 2D standard normal distribution. What is the probability that the convex hull ...
7
votes
7answers
2k views

Is every monotone map the gradient of a convex function?

Recently in a seminar someone mentioned that monotone maps are equivalent to gradients of scalar convex functions, but it's not clear to me why this is true. One direction of the equivalence is ...
3
votes
0answers
55 views

References on Rogers-Shephard inequality

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

Simplex - Help with a proof

I am trying to prove the following (basic) claim about simplex. If you check my proof and help me with the part where I stuck, I would appreciate it very much. Let $X$ be a finite set and define $\...
21
votes
1answer
503 views

Does there exist regular planar pentagon?

How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ (treated as a surface) includes 5 points which form a regular planar pentagon?
0
votes
0answers
20 views

The convex (bi)conjugate and the Fourier transform

In the context of convex optimization, I am looking to find a formula for the convex biconjugate of a function $f: X \rightarrow \mathbb{R}$ where $X$ is a real normed vector space, in terms of its ...
0
votes
1answer
663 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
1
vote
0answers
54 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....
8
votes
1answer
455 views

Cones of positive semidefinite matrices generated by matrices of rank $1$

Let $S_n$ be the space of real $n \times n$ symmetric matrices and let $S_n^+$ be the convex cone of positive semidefinite matrices in $S_n$. The extremal rays of this cone correspond to the positive ...
4
votes
1answer
52 views

Convex functions, prove another definition.

I have the next problem: Suppose $f$ is continuos then $f:\mathbb{R}^n\to R$ is convex iff $\forall x,y \in \mathbb{R}^n \left( \int_0^1 f(x+\theta (y-x))d\theta \leq \dfrac{f(x)+f(y)}{2}\right)$. The ...
0
votes
1answer
25 views

Find minimal point of convex set

I'm having some convex set $P \subset \mathbb{R}^n_+$ and a linear-time indicator procedure $I_P(x)$ that allows for each given point $x \in \mathbb{R}^n_+$ to say whether it lies inside $P$ or not. ...
0
votes
1answer
39 views

Convex compact set must have extreme points

I am reading a paper and there is such description as title. Why? I have an example: $(0,1)$. This is a convex set but not closed, so I cannot find an extreme point. However if convex and compact,...
1
vote
1answer
46 views

How many times can strictly convex functions intersect?

Some time ago, I saw a post related to the number of times that two convex (and continuous) functions' graphs can meet. In general, infinitely many times: one can think, for instance, of $g(x):=x^{2}$ ...
3
votes
1answer
51 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
0
votes
1answer
54 views

how do i show that a function $f(x)$ is convex given that the inequality holds

So i have to prove that the inequality below is true if and only if f is convex and Lipschitz continuous. i have the first part down which is to assume f is convex and show the inequality. But i cant ...
1
vote
1answer
44 views

Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}\mathrm{argmin}_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}\mathrm{argmin}_{t}\{t+5\mathbf{E}[...
3
votes
1answer
160 views

the continuity of argmin

how can I show the minimum of a converging sequence of continuous functions is converging to the minimum of the limit of that sequence.i.e. $$\lim_i \text{argmin}_{x} f_{i}(x)=\text{argmin}_{x} \lim_i ...
1
vote
0answers
33 views

A set is affine if and only if its intersection with any line is affine. [duplicate]

How can we prove that the a set is affine if and only if its intersection with any line is affine? In fact, I want to know if there is such theorem that the intersection of two affine set is affine?
4
votes
1answer
56 views

My proof for “$\Gamma =\{X\in \mathbf{R}^{n\times n} \mid X \succeq 0, \text{Tr}(X)=1\}$ is compact”

This problem comes from: How to prove the compactness of the set of Hermitian positive semidefinite matrices In short, we want to prove $$\Gamma =\{X\in \mathbf{R}^{n\times n} \mid X \...
0
votes
1answer
27 views

$\{X \mid \text{trace}(X)=c\}$ is a hyperplane?

A hyperplane is a set of the form: $$\{x\in \mathbf{R}^n \ \ \mid \ \ a^Tx=b, a\in \mathbf{R}^n\}$$ This definition is quite intuitive. However, I am reading some books or paper and they ...
16
votes
1answer
351 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})...
1
vote
1answer
27 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 ...
2
votes
1answer
94 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
42 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(...
0
votes
0answers
9 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
190 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 ...
1
vote
0answers
27 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
101 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
42 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
1answer
54 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
1answer
35 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
48 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)>...
0
votes
1answer
14 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
240 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
48 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
32 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
37 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
24 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 $ ...