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)

17
votes
5answers
467 views
+100

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
10 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 $...
5
votes
0answers
37 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 ...
0
votes
1answer
42 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
26 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
7 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....
0
votes
0answers
12 views

convexity of difference of log-sum-exp

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})...
2
votes
1answer
31 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
11 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
17 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 ...
3
votes
4answers
75 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 ...
0
votes
2answers
36 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
33 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
18 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
59 views
+50

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
21 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
34 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
34 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
18 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
20 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
84 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
41 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
37 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{[\...
1
vote
1answer
1k views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
2
votes
1answer
42 views

Convexity in each argument and directional derivative

Let $f(x,y)$ be a continuous function, convex in each argument separately. Does this imply the existence of one-sided directional derivatives in any direction? For example, does there exist (finite or ...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...
0
votes
0answers
14 views

Uniqueness of projection implies convexity [duplicate]

Prove that for a compact set A in finite dimensional Euclidean space X, A is convex if and only if for any point x in X, the projection of x to A is unique. If we know A is convex, we can show the ...
0
votes
1answer
23 views

Does function that maps bounded convex sets (minus straight line segments) to bounded convex sets must be continuous everywhere?

This question in the title came to my mind while I was sitting with my granny in front of my house maybe about half an hour ago. Although it looks innocent I do not know at the moment some simple ...
2
votes
4answers
71 views

Convex integral inequality

I cannot prove that if $f(x)$ is convex on $[a,b]$ then $f\Big(\frac{a+b}2\Big) \le \frac1{b-a}\int_a^b f(x)\,dx \le \frac{f(a)+f(b)}2 .$
0
votes
0answers
20 views

linearize average success probability constraint

In my optimization problem, I've a constraint to calculate the average success probability of a path. $x_{i,j}$ is binary variable defined as: $$ \begin{align} \label{eq3:1} x_{i,j} = \begin{cases} ...
0
votes
1answer
34 views

Convex or non-convex function

I want to minimize the following function $$\frac{a}{bxy+cd}e^{\frac{a}{bxy+cd}}H+2-\Gamma(1,\frac{eaf}{b(1-x)},\frac{eagf}{bx(1-y)})$$ where $a,b,c,d,e,f,g,H$ are constants and greater than $0$. $\...
0
votes
2answers
400 views

How to prove the convexity of $f$ if the strict epigraph of $f$ is convex

I have trouble to prove the equivalence of the following two definitions of convex function. For convenience, I list them as follows: Def-A. Let $f : I\to \mathbb{R}$ be a function, where $I$ is (and ...
0
votes
0answers
21 views

Inequality for convex functions

Let $a,b:\mathbb{R}\to\mathbb{R}_+$ be two strictly convex and differentiable functions, such that $a\geq b$. Let $x\leq\alpha\leq y\leq\beta$, where $\alpha,\beta\in\mathbb{R}_+$ are two constants. ...
0
votes
0answers
47 views

When we can permute between the integral and convex hull?

Is there a relation between the following expressions? $$\operatorname{conv}\left(\int_{0}^{t} f(s,x)ds :x \in A \right) $$ and $$\int_{0}^{t} \operatorname{conv}(f(s,x):x \in A)\ ds $$ where $A$ ...
2
votes
1answer
37 views

Can a quasiconvex function be made convex by composition with a diffeomorphism?

Assume we are given a continuous quasiconvex function $f: \mathbb{R}^n \to \mathbb{R}$. Intuitively I feel that quasiconvexity means that there should exist a diffeomorphism $h: \mathbb{R}^n \to \...
2
votes
1answer
25 views

Finding minimizer from different order

Let a nonnegative function $f(x,y)$: $\mathbb R^2\to \mathbb R$ be second order continuous differentiable. We also know that $f$ is not convex in its two arguments, but only separately in each of them....
0
votes
0answers
5 views

Invertibility of a polylogarithmic map

Consider a map defined on $\Bbb R\times(0,+\infty)$ and given by $$M:(a,b)\to(\rho,E),$$ $$\rho = \int_{\Bbb R^n}\frac{dx}{1+\exp(a+b|x|^2)}\\E=\int_{\Bbb R^n}\frac{|x|^2dx}{1+\exp(a+b|x|^2)}.$$ I ...