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 (1)

1
vote
0answers
27 views

Proving an inequality for convex and increasing functions [on hold]

Can anyone show the following: Let $f:R^+ \rightarrow R^+$ be a strictly increasing function and $f(0)=1$, then for $\forall x,y>0$ we have ...
0
votes
1answer
30 views

What's the solution for $\max_{x\in(0,1]}: \{-1-x\}$

What's the solution for the following optimization problem? Is the constraint set convex? $$\max_{x\in(0,1]}:\{-1-x\}$$
5
votes
2answers
131 views

Isoperimetric inequality, isodiametric inequality, hyperplane conjecture… what are the inequalities of this kind known or conjectured?

Question: Which inequalities similar to the famous isoperimetric inequality is known? conjectured? I recently learned about some inequalities which are all similar to the famous isoperimetric ...
0
votes
1answer
17 views

Confusions of Convex Set

I am interested in the properties of convex set in $\mathbb R^n$ and want to clarify the three statements below $A$ is an open convex set. Can we get the conclusion that $\bar{A}$ is convex? ...
0
votes
0answers
4 views

Sum of quasi-concave function and linear function

Let $F(k)$ have the following properties: $$ F(k) \in C^1 \\ F'(k) > 0 \\ F(0)=0 \\ \lim_{k \to \infty} F'(k) = 0, \lim_{k \to 0} F'(k) = \infty \\ F ~\text{strictly quasi-concave}. $$ Then, let ...
0
votes
1answer
20 views

Analog of Birkhoff's theorem for doubly stochastic matrices

Birkhoff's theorem states that extreme point of the set of doubly stochastic matrices are permutation matrices. An $n \times n$ matrix $A$ is doubly stochastic if each row and column sums to 1. What ...
0
votes
2answers
26 views

Critical points and Convexity?

Function $f(x)$ has no critical points in $M$, can we say $f(x)$ is either convex or concave over $M$?
0
votes
0answers
20 views

No critical points means convex or conave? [on hold]

If we don't know whether $f(x)=0$ is convex or concave or not, but we know under certain constraint sets there is no critical points of $f(x)$ inside meaning the solution of $df(x)=0$ is outside the ...
0
votes
1answer
27 views

Compact and convex discrete set

I am working with discrete sets but I have a doubt: is the set $\{ 0,1\}$ compact and convex? And the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$?
0
votes
0answers
8 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
2
votes
2answers
90 views

Convex cone question.

Hoi, let $V$ be finite dimensional real vector space with inner product $\left\langle . \right\rangle$ and let $\Gamma \neq \{0\}$ be a closed convex cone. Let $$\Gamma_0^{\perp}:=\{v\in ...
0
votes
1answer
368 views

generalized inequalities defined by proper cones

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ? ...
0
votes
1answer
15 views

Certain property of convex functions…

I come to you with yet another qualifying problem we can't seem to solve... Let $f:$ $(0,\infty) \to \Bbb R$ be convex, and let $\lim_{x \to 0}f(x)=0$. Show that $g(x)$ = $f(x) \over x$ is increasing ...
0
votes
1answer
332 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
0
votes
1answer
48 views

alternative definition of Affine map

Let $f:X\longrightarrow Y$ be a function on real vector spaces (note that $X,Y$ have arbitrary dimensions). If $T(x)=f(x)-f(0)$ is linear, $f$ is called an affine map. Prove that $f$ is affine if ...
0
votes
1answer
20 views

Redefine a discrete compact set

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,\ldots,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as ...
0
votes
1answer
22 views

Define a compact and convex set through inequality constraints

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,...,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as $\{x ...
4
votes
2answers
74 views

On the convexity of a particular form of integrals

EDIT: I made some critical corrections below. Let $\mathcal{H}\colon\mathbf{w}\cdot\mathbf{x}+c=0$ be a hypeplane in $\mathbb{R}^n$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$, be a non-negative, ...
1
vote
1answer
42 views

How to use Markov-Kakutani fixed point theorem to show that abelian groups are amenable?

Recall that a group $\Gamma$ is amenable if there exists a state $\mu$ on $l^{\infty}(\Gamma)$ which is invariant under the left translation action: for all $s\in \Gamma$ and $f\in ...
0
votes
0answers
21 views

Convex cones and positively homogenous and subadditive functional

Let $V$ be a linear topological space, $K \subsetneq V$ a convex, closed cone with $0 \in K$ and $k \in K \setminus (-K)$. Show that the functional $\varphi : V \to \mathbb R \cup \{ \pm \infty \}$ ...
0
votes
1answer
196 views

Checking convexity

I know that the function $(\mathbf{a}-\mathbf{b})'(\mathbf{a}-\mathbf{b})$ is convex in $\mathbf{a}$ ($\mathbf{a}$ and $\mathbf{b}$ are vectors, not scalars). Would ...
1
vote
0answers
29 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
0
votes
1answer
31 views

Motivating convex sets.

I am kind of TAing for a class of real analysis, and I would like to speak a little about convex sets tomorrow, and explain why they are important. What kind of examples could I give? I was thinking ...
5
votes
1answer
208 views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
0
votes
2answers
30 views

The Fundamental Theorem of Matrix Games, and the “indifference” method of solving games

In the following we will consider two-person zero-sum games. Let $A = (a_{ij})$ be the payoff-matrix of such a game. In this book the fundamental theorem of such games is states as: Theorem: Given ...
1
vote
3answers
63 views

Is convex hull of a finite set of points in $\mathbb R^2$ closed?

Is the convex hull of a finite set of points in $\mathbb R^2$ closed? Intuitively, yes. But not sure how to show that. Thanks!
0
votes
1answer
29 views

Min of concave symmetric function on a convex set

Consider the convex set $$C=\left\{ \mathbf{x}\in \mathbb{R}^N :0\le x_1\le x_2\le\dots\le x_i\le x_{i+1}\le \ldots\le x_N\le \frac 1{N-1}\text{ and } \sum_{k=1}^{N}x_k=1\right\}$$ I need to minimize ...
0
votes
1answer
13 views

Volume of Minkowski sum of a point and a hypercube

Let $A$ be a single point and $B$ a unit cube in $\mathbb{R}^n$, what is then the volume $\lambda \mapsto \mathrm{Vol}\big((1-\lambda)A + \lambda B\big)$? I am not exactly sure, what the set ...
0
votes
3answers
66 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...
0
votes
0answers
8 views

Pseudoconcavity of a fractional function q(x)=f(x)/g(x) if f(x) is nonnegative concave and g(x) is positive convex?

I know from Chandra that $q(x)=\frac{f(x)}{g(x)}$ is strong pseudoconcave if $f(x)$ is nonnegative concave and $g(x)$ is strictly positive convex. Is there a theorem that states $q(x)$ is ...
3
votes
1answer
24 views

Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
4
votes
1answer
62 views

A question about pyramids (polytopes)

Let's use the following definition of a face: A nonempty convex subset $F$ of a convex set $C$ is called a face of $C$ if $\alpha x + (1-\alpha) y \in F$ with $x, y \in C$ and $0 < \alpha < 1$ ...
2
votes
1answer
50 views

Relation between mean width and diameter

Question: Let $A$ be a compact set in $\mathbb R^n$. Is it always true that $\text{mean-width}(A) \ge C \cdot \text{diam}(A)$ for some constant $C$ depending only on the dimension? If not, is it ...
1
vote
0answers
29 views

Quickly checking if an inequality holds on a convex region

Let $C$ be a given convex polygon in $\mathbb{R}^2$ containing the origin and let $a$, $\mathbf{b}$, and $Q\succeq0$ be a given scalar, vector, and matrix respectively. Is there a fast way to verify ...
0
votes
0answers
35 views

Why is pointwise maximum a convex function?

It seems like if you have a family of function $$g = \{a(x), \: b(x), \: c(x), \:d(x)\}$$ $$\text{given} \:\: f(x):= max(g),$$ $$\text{if} \: f(1) = a(1), \: f(2) = b(2), \: f(3) = c(3), \: f(4) = ...
2
votes
2answers
39 views

Prove: $f: (a,b) \rightarrow \mathbb{R}$ is convex iff for every triple $x_1,x,x_2 \in (a,b)$…

Assignment: Prove that a function $f : (a,b) \rightarrow \mathbb{R}$ is convex if and only if for every triple $x_1,x,x_2 \in (a,b)$ with $x_1 < x < x_2$ following inequality is satisfied: ...
0
votes
1answer
24 views

Why does convexity of a function required the following

What is the significance of the following condition $$\forall x_1, x_2 \in dom(f) , \forall \theta \in [0, 1], f(\theta x - (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$ and why isn't the ...
0
votes
2answers
39 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
2
votes
1answer
44 views

Let $f: [a,b] \rightarrow R$ be convex. If f is not constant, then the supremum of $f$ is not inside of [a,b].

I could use some help with this proof. Let $a,b \in \mathbb{R}, \ a<b \ \ f: [a,b] \rightarrow \mathbb{R}$ be convex. Prove: If f is not constant, then the point, where the supremum of ...
2
votes
2answers
35 views

Convexity / Concavity --> Formal Definition

How do I show that $f(x, y)=(x + y)^2$ is convex/concave using the formal definition of convexity/concavity?
0
votes
1answer
17 views

How do I justify that a second order cone is an intersection of half space

I am studying convex optimization right now, and the text book claims that a second order cone is a collection of intersections of half space $$K_n = \bigcap_{ u:\|u\|_2 \leq 1} \{(x,y) \in R^{n+1 } ...
1
vote
0answers
25 views

Is continuity preserved under Max operator and Euclidean norm?

Suppose that the functions $f_i: \mathbb{R}^k \rightarrow \mathbb{R}$ are all continuous over $\mathbb{R}^k$ for $i=1,...,k$. Is the function $$ g(x)=\|\max\{0,f_1(x)\},...,\max\{0,f_k(x)\}\|^2 $$ ...
0
votes
0answers
19 views

Hyperplane - soft and hard questions

This would be a rather long question. Apologies for that. Instead of asking three separate questions I've consolidated them in one. I am trying to learn hyperplanes, convex hulls, separations theorems ...
2
votes
0answers
18 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
0
votes
0answers
19 views

Non-subdifferentiable convex function

Is there any convex function $f$ on a norm space $X$ such that $\partial f(x)=\emptyset$ at every $x\in X$? Thanks in advance.
1
vote
1answer
29 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
20 views

Tangent cone of graph and epigraph sets.

Let us first recall the definition of tangent cone $\; T(\bar x; \Omega)$ of a subset $\Omega$ at $\bar x \in \Omega$, where $X$ is a Banach space: $$T(\bar x; \Omega)=\{v\in X:\; \; \exists ...
0
votes
0answers
23 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
0
votes
2answers
27 views

Relation between sum of a max and max of a sum?

Consider $\frac{1}{T}\sum_{t=1}^{T}\max\{ 0,a_t\}$. Can we say whether this is greater or equal then $\max\{ 0,\frac{1}{T}\sum_{t=1}^{T}a_t\}$?
1
vote
1answer
35 views

The closednees in Moreau - Rockafellar Theorem.

One says that $x\mapsto \langle x^*,x\rangle +\alpha\;$ is an affine minorant of $f: \; X\to \overline{\mathbb R}\;$ if $\;\langle x^*,x\rangle +\alpha \leq f(x)\;$ for all $x\in X$. The Moreau - ...