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)

2
votes
2answers
34 views

Interior point of inequations

Let $P$ detonate $(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
0answers
2 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
17 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$ ...
11
votes
5answers
271 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 ...
1
vote
0answers
48 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
20 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
30 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
31 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 ...
0
votes
0answers
13 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
18 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
20 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
51 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 ...
1
vote
1answer
84 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 ...
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
26 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
36 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
68 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
46 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 ...
0
votes
1answer
23 views

Exact line search in convex optimization

For a convex function $f$ what do we know about convexity of the exact line search problem? $$\min_{\alpha \ge 0} f(x+ \alpha p_k)$$ I think because the function is convex and is linear in variable, ...
1
vote
1answer
25 views

Showing that this set satisfies the closed criterion

Suppose we have the subset $S = \{ \lambda v \mid \lambda \geq 0 \} + K $, where $v$ is a vector in $\mathbb{R^3}$ and $K$ is a convex hull of six other vectors. How do I show that it satisfies the ...
0
votes
1answer
90 views

Why is the dual cone of $l^1$ is $l^\infty$?

I just noticed somewhere in Convex Optimization that the dual cone of $l^1$ is $l^\infty$! (A diamond in $\mathbb{R}^2$ for $l^1$ is a square in $\mathbb{R}^2$ for $l^\infty$.) In fact I cannot ...
0
votes
1answer
18 views

Upper bound for sum of powers

I have a sequence of positive real numbers $\{x_i\}_{i=1}^{N}$ and $k \in \mathbb{N}$. I was wondering if one can find an upper bound of the type $$ \sum_{i=1}^{N}{x_i^k} \leq f\left(\sum_{i=1}^{N}{...
5
votes
4answers
422 views

Algorithm to find the point in a convex polygon closest to an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$? A linear algorithm of course works, computing the ...
0
votes
0answers
9 views

Is this implicit mapping convex?

I am interested in the convexity properties of the following mapping on the $n\times 1$ vector $x$: $$ x_{j}=y_{j}^{\beta}\left(\sum_{i=1}^{n}B_{ij}x_{i}\right)^{\alpha} $$ where $\beta>0$, $y_j\...
5
votes
2answers
62 views

Convex sets in infinite dimensional Banach spaces

I am reviewing functional analysis and getting stuck in this question. Let $X$ be an infinite dimensional Banach space. Show that there exist convex sets $K_1, K_2$ such that $K_1\cap K_2=\emptyset,...
1
vote
2answers
51 views

A convex set in $\mathbb{R}^n$ whose closure is $\mathbb{R}^n$

Let $S$ be a convex set in $\mathbb{R}^n$. Prove that if a closure of S is $\mathbb{R}^n$ then $S=\mathbb{R}^n$
0
votes
0answers
27 views

Is generalized mean convex / concave?

The generalized mean can be given using the following equation: $ M_p(x_1, \dots, x_n) = (\frac{1}{n}\sum_i x_i^p)^{1/p} $ Is it convex /concave when $p<1$ ?