Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

5
votes
1answer
490 views

Minimizing l-infinity norm of complex vector

I have an $n$-dimensional complex vector space, and I want to minimize the $L_\infty$ norm of a point that is constrained to an $m$-dimensional affine subspace. That is, Given $\mathbf{z} \in ...
1
vote
1answer
119 views

directional derivative sublinear of a convex function sublinearity problem to show

How to show the following: If $f:\mathbb R^d \rightarrow \mathbb R$ is convex then its directional derivative is sublinear? Thank you...
2
votes
1answer
60 views

Possibility of Unboundedness in Least Squares Minimization

Suppose we have the quadratic minimization problem \begin{equation} \min_x \frac{1}{2} x^TPx + q^Tx +r \end{equation} We know that when $P$ is symmetric positive semi-definite, but the optimality ...
2
votes
2answers
114 views

Constrained maximization problem

I need help with the following optimization problem $$ \max\;\alpha\ln(x(1-y^2))+(1-\alpha)\ln(z) $$ where the maximization is with respect to $x,y,z$, subject to \begin{align} \alpha ...
2
votes
2answers
74 views

Geometric difference between $x^TAx$ and $x^TAx + b^Tx + c$

What is the difference between $x^TAx$ and $x^TAx + b^Tx + c$ geometrically? Some analogous examples from quadriatic equations would be great.
0
votes
1answer
77 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
218 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
105 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
112 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
56 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
80 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
38 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
84 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?
1
vote
1answer
52 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 ...
2
votes
2answers
167 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
266 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
195 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
125 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
107 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
29 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 ...
1
vote
1answer
99 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 ...
5
votes
1answer
2k views

How the dual LP solves 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
120 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
90 views

Primal-Dual pair in SDP

Let's we have a primal model like $\max~~ x + \langle I, Z \rangle$ $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 ...
2
votes
1answer
1k 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
110 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
1answer
162 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
321 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
1answer
263 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
93 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
47 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]..." ...
4
votes
0answers
255 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
854 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
39 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
91 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
46 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
60 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
59 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
59 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
50 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
116 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
39 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
93 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
179 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 ...
3
votes
0answers
190 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
28 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
93 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
255 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
59 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
98 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 ...