Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
0
votes
1answer
58 views
convex conjugate $f^*$ is proper if both $f$ and $f^{**}$ are
If $f$ and $f^{**}$ on $\mathbb R^d$ are proper functions where
$f^*$ stands for the convex conjugate of $f$ why does that follow that $f^*$ is proper, too?
Thanks a lot...
1
vote
2answers
77 views
Positive Second derivative and convexity
Let $f:\mathbb R\to\mathbb R$, maps a point $x \in \mathbb R$. $f$ is twice differentiable. Show that if second derivative is positive for all $x$ then $f$ is convex
Is there anyway to prove this ...
0
votes
0answers
50 views
convex lsc function affine minorant theorem proof
How to show the following:
f:R^n->R
A lower semicontinuous convex function f equals the pointwise supremum
of all its affine minorants.
Thank you!
2
votes
0answers
69 views
How to minimize the supremum of two convex functions?
Given $f_1(x)$, $f_2(x)$, $x\in \mathbb{R}^d$, two convex functions, we define the following problem:
$\underset{x\in C}{{\rm minimize}}\,{\rm ...
0
votes
1answer
35 views
Epigraph supported at some point meaning of the sentence
Can you tell me what does the following sentence mean?
Let $z \in \mathbb{R}^d$ and $(-z,1)$ supports epigraph of $f$ at $(x_0,f(x_0))$
Thank you..
1
vote
1answer
49 views
On the convexity of the element-wise norm 1 of a pseudoinverse
Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as
$$
\|A\|_1= \sum_{i,j} |A_{i,j}|.
$$
Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
0
votes
0answers
36 views
Uncertaint linear program
I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It ...
0
votes
1answer
50 views
Is a convex, nondecreasing function of an invex function invex?
Is a convex, nondecreasing function of an invex function invex?
More broadly, where can I find a list of special properties of functions of invex functions?
0
votes
1answer
42 views
Does the following relation always hold?
Given two functions $$f_1(x)=g_1(x)+h(x)$$ and $$f_2(x)=g_2(x)+h(x)$$ I know that $f_1(x)$ and $f_2(x)$ are monotone increasing. If $g_2(x)<g_3(x)<g_1(x)$, then is it true that ...
1
vote
2answers
59 views
How to find projection to polyhedron
I have a problem:
find $min||\overrightarrow{x}||$ where
$A\overrightarrow{x} \leqslant \overrightarrow{b}$
Is it possible to get analytic solution?
Or which iteration method should I use?
2
votes
2answers
72 views
What does it mean to restricting a function to a line in convex optimization?
In lecture 3 of the course Convex Optimization conducted by Stephen Boyd at 21 minutes mark he says that a function is convex if its convex when we restrict it to a line. What does he mean by ...
1
vote
0answers
105 views
How to find $\kappa$ to minimize integral $I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) \mathrm{d}x$
I am trying to find such value $\kappa \in (0,1)$ that would minimize the integral
\begin{equation}
\begin{aligned}
I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) ...
2
votes
0answers
73 views
Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables
I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this.
Read ...
0
votes
1answer
54 views
Direction of recession, convex analysis
Hi how to show the following:
Let $C$ and $D$ be two non-empty closed convex sets
with no common direction of recession. Then $C - D$ is closed.
Thanks a lot...
0
votes
1answer
25 views
Intersection of a 2-Dimensional body and a Line given west-most point and south-most point
I have a 2-Dimensional Closed Convex Compact Body $\mathbb{S}$(a set, for eg, a circular disc)). Assume, it has a non-zero intersection with the all-negative quadrant. Consider the following 2-D point ...
0
votes
1answer
54 views
Removing redundant half-spaces that bound a convex polytope
I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 ...
0
votes
0answers
60 views
Show $\lambda'(0)= 0 $ and $\lambda''(0) \ge 0$
Consider
$$\lambda(c)= \frac{1}{2}x(c)Px(c)-ax(c) \:\:where \:x(c) = (1-t)x_0 + tx_1$$
where $P\in {\mathbb{R^{dxd}}}$, and a,x$\in\mathbb{R^d}$.
Show $\lambda'(0)= 0 $ and $\lambda''(0) \ge 0$.
I've ...
3
votes
1answer
116 views
Does solving the LP dual SOLVE the primal LP?
When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual."
I know that both the primal LP and its dual must have the same optimal objective value ...
4
votes
2answers
94 views
proving this inequality related to conjugate functions
For $x \in \mathbb{R}^n$ let us denote $x_{[i]}$ the $i$th largest component of $x$ s.t
$$
x_{[1]} \geq x_{[2]} \geq x_{[3]}\ge\cdots
$$
The function
$$
f(x)= \sum_{i=1}^r x_{[i]}
$$
is the sum of ...
4
votes
0answers
38 views
Primal-Dual pair in SDP
Let's we have a primal model like
$\max~~ x + Z $
$s.t. ~~~Ax + y I - Z \preceq B$
$~~~~~~~~~Z \succeq 0, ~X \geq 0, ~~y ~free$
where $A, B \in {\mathbb R^{n \times n}}$. The capital letters ...
2
votes
1answer
159 views
Prove the supremum of the set of affine functions is convex
Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
-1
votes
2answers
86 views
Is $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \in \mathbb{R}_+$, a convex function?
Let $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \ge 0$. Is $f$ a convex function? Why?
$\ \\$
Edit (in view of the comments below)
The Hessian matrix is $H=[0\, 1; \,1 \,0]$, which is indefinite (in ...
0
votes
0answers
46 views
Finding descent direction of quadratic function
I have a quadratic function: $f(x) = 24x_1+14x_2+x_1x_2$
and point $x_0 = (2,10)^T$ with $f(x_0) = 208$
And the first question is "give descent direction r in $x_0$"
The second question "is f convex ...
3
votes
2answers
85 views
A standard quadratic minimization problem
Consider the "Complex" Quadratic minimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1
\end{align}
...
1
vote
0answers
71 views
Generalization of soft threshold operator?
For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator:
$\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$
where $\circ$ is ...
3
votes
0answers
51 views
On the duality gap for quasiconvex optimisation problems
This stack exchange question got me thinking about quasiconvex analysis.
Given a compact,convex subset $X\subset \mathbb{R}^n$ and a quasiconvex function $f:X\rightarrow \mathbb{R}$
Define the ...
1
vote
1answer
28 views
SVT algorithm and the value of tau.
SVT stands for singular value thresholding. It is an algorithm used in "matrix completion" problems. see http://svt.stanford.edu/ for basics.
What is the meaning of "for large values of [tau]..." ...
1
vote
0answers
80 views
Convex analysis books and self study.
I have taken some courses in Convex optimization. Now I would like to know a little bit more about the pure mathematical side. Is there any good books in convex analysis?
I have read and worked with ...
1
vote
2answers
138 views
Explain `All polyhedrons are convex sets´
My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
2
votes
0answers
24 views
convex optimization with inconsistent constraints
If you have a problem in convex optimization where all $N$ constraints ($N >> 0$) yield no possible solution but you are able to rank, or weight the constraint in terms of their importance are ...
1
vote
0answers
41 views
Minimize a complex quadratic subject to two convex quadratic constraints
I have the following the optimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\}
\\\ ...
1
vote
1answer
38 views
Showing that $T+S$ is firmly nonexpansive
Show that $T+S$ is firmly nonexpansive considering that $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$.
Definition: We say that $F$ is firmly nonexpansive if: ...
1
vote
0answers
32 views
Parameterized convex optimization
I'm trying to formulate a game so that at Nash equilibrium I achieve supply equales demand. Then I ran into this problem.
For all $i,$ $v_{i}\left(x_{i}\right)$ is concave
in $x_{i}$. The value ...
1
vote
0answers
47 views
Closed form for Lagrange dual
Can Lagrange dual always be computed in closed form? Can you give me a simple example where the dual is not analytically computable?
3
votes
1answer
53 views
Show that $Z=T(2S−I)+I−S$ is firmly nonexpansive
Suppose $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Let $I$ be identity operator. I want to show that $Z=T(2S−I)+I−S$ is firmly nonexpansive.
Definition. We say ...
1
vote
0answers
43 views
why is it important to have $\max_x \min_y f(x,y)=\min_y \max_x f(x,y)$?
I am currently trying to understand the minimax theorem of Von Neumann and the improved versions of this theorem.
At any case we have the property
$$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} ...
2
votes
1answer
63 views
Continuity of solutions to convex optimization problems
Let $x_A$ solve
$$
\min J(x) \quad \text{subject to} \quad Ax=b
$$
and $x_B$ solve
$$
\min J(x) \quad \text{subject to} \quad Bx=b
$$
given that $\|A-B\|_\text{operator} \leq \epsilon$ and that $J$ is ...
0
votes
1answer
34 views
Numerically solving linear equation and optimization
I have to solve for $x$ in the linear equation $Ax=B$. However, $A$ has singular values that are close to zero (very small). So direct inversion is not a good idea. I wanted to solve for $ x$ using ...
2
votes
1answer
63 views
Approximating a function with a convex function
Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous, differentiable function. Is there a known algorithm that fits $f$ with $g$, which is an order-$n$ polynomial that is convex, in the least ...
6
votes
0answers
102 views
Subgradient of convex minimization duality
$$\min(f_0(x))$$
$$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$
$$f_i : \text{convex};\quad x : \text{variable}$$
It is also considered that $g(y)$ is the optimal value of the problem ...
1
vote
0answers
63 views
How to show that a function is piecewise linear
Let z(t) = min $(c+t d)^T x$
s.t $Ax <= b$
Show that Z(t) is a concave, piecewise linear function of t.
I'm really not sure how to even start proving this, I would really ...
1
vote
1answer
25 views
Does linearity decompose down convex sums?
I'm doing some convex optimisation where I'm minimising sum function $f(x) = \sum g_i(x)$, where the $g$'s are convex (and hence so is $f$) and the sum is finite.
In doing so it turns out that $f$ is ...
2
votes
1answer
45 views
Initial solution to a Convex Optimization problem
I am aware that in a convex optimization problem, the initial solution does not matter as the algorithm guarantees convergence to the global minimum/maximum. But what if the initial solution does not ...
1
vote
0answers
123 views
Linear programming: writing a problem with artificial variables?
Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
2
votes
0answers
45 views
Convexity of a function
Suppose we have $F: R^n \longrightarrow R$ , $P: R^n \longrightarrow R^n$ and $G: R^n \longrightarrow R$ all nice- let's say given by polynomial and $P$ is invertible - such that $F(x) =G( P(x) )$.
...
1
vote
1answer
42 views
how can I proof the GLOBAL optimality of a problem where the feasible region is disjoint?
I want to minimize the following function. It has two variable, $x$ and $y$ are real. I want proof the global optimality. But the feasible region of the variables are disjoint. My question is, how can ...
2
votes
1answer
161 views
A variation of the Assignment Problem
In the following Wikipedia article about the Assignment Problem in the Example section, it says:
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
1answer
101 views
Max function on a closed compact convex set.
Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function
\begin{align}
f(x)=max(x_1,x_2,\ldots,x_N)
...
0
votes
1answer
89 views
Convex optimization problem to quadratic programming problem
Briefly, have the following problem:
\begin{equation}
\sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\
s.t.\\\\
A \bar x \leq b
\end{equation}
where $ F( \bar x ) $ is a ...
0
votes
1answer
134 views
a convex function on a 2 dimensional closed convex set
Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane
...
