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

learn more… | top users | synonyms

1
vote
2answers
199 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
1
vote
1answer
152 views

Proximal operator

What is a proximal operator and how would one derive it in general for a function? In particular, if I had a function: $ f(x) = x^TQx + b^Tx + c $ How would I get the proximal operator for this if Q ...
1
vote
1answer
132 views

Convex combination of orthogonal matrices

How would I show that the convex combination of orthogonal matrixes has spectral norm $ \leq 1$? (I have some idea how to do it ... but right now I'm stuck). Also, how would I prove that the unit ...
1
vote
2answers
85 views

Optimal Configuration for a Set of Points

Consider a set of $n$ points on the plane with positions $\mathbf{p}_1,\dots,\mathbf{p}_n$, such that each point $i$ has at least one neighbor $j$ at a distance of no more than $\lambda$ away from it ...
1
vote
1answer
67 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
64 views

Is this function convex or not?

Is this function convex ? $$ f(\mathbf y) = { \left| \sum_{i=1}^{K} y_i^2e^{-j\frac{2\pi}Np_il} \right| \over\sum_{i=1}^{K}y_i^2} $$ where : $ P = \{p_1,p_2,\cdots,p_K\} \subset\{1,2,\cdots,N\} $ I ...
1
vote
1answer
567 views

Convexity of the squared Frobenius norm of a matrix

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
1
vote
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
2answers
75 views

When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

When $$ \min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y) \qquad? $$ I mean when we are minimizing a function with respect to two variables, under what conditions we are allowed to ...
1
vote
1answer
67 views

Proof of convexity of a function

I have to prove that function $J(x)=e^{x^3+x^2+1}$ is convex on $[0,\infty]$. I used a Theorem which says: **$U\subset R^n$ is convex set with non-empty interior and $J\in C^2(U)$. Function $J$ is ...
1
vote
1answer
150 views

Convex hull of an open set is an open set

I have to prove this. Actually, I have the proof, but I don't understand one part. It says: "Since $\operatorname{co}A$ is intersect of all convex sets that contain set A, it follows that ...
1
vote
1answer
866 views

Pointwise supremum of a convex function collection

In Hoang Tuy, Convex Analysis and Global Optimization, Kluwer, pag. 46, I read: "A positive combination of finitely many proper convex functions on $R^n$ is convex. The upper envelope (pointwise ...
1
vote
1answer
353 views

Closed form solution of a convex optimization problem

Suppose we want to solve the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x,y,z}{\text{minimize}} && x(a-y) \\ & \text{subject to} && ...
1
vote
2answers
390 views

Maximize the product of linear functions

Suppose $f(x,y) = \prod_{i=1}^n (a_ix+b_iy)$ where $n$ is a constant larger than 500, and $a_i>0$, $b_i>0$ are known coefficient. There is only one global maximum. What's the most efficient ...
1
vote
2answers
104 views

computational strategy for solving convex-concave minmax problem

Assume f(x,y) is convex in $x$ and concave in $y$. Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.) But can we find a ...
1
vote
1answer
193 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
1
vote
1answer
95 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}$. ...
1
vote
2answers
616 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 ...
1
vote
1answer
400 views

What is a good technique to decide step size in sub-gradient method for dual decomposition?

I am looking at the following paper to implement dual decomposition for my algorithm: http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf On Pg.29 they suggest setting the step ...
1
vote
1answer
28 views

In an engineering/optimisation context, does set $E$ have any special significance?

I am reading a paper about optimsation and the description, while mostly being a very good description, makes reference to some variables being in some set $E$. For example, it states that parameter ...
1
vote
2answers
478 views

Proof of Convexity?

Given a positive semidefinite matrix $A$, is $\operatorname{Tr}X^TAX$ a convex function in $X$? Am looking for a proof of convexity or non-convexity, whichever is true.
1
vote
1answer
455 views

Convex Conjugate of Absolute Norm

Let $f:\mathbb{R}\rightarrow[-\infty,\infty]$ be a continuous function. The convex conjugate of $f$ is: $$f^*(p) := \sup_{x\in\mathbb{R}}\{px-f(x)\}~.$$ Furthermore, let us define the subderivative ...
1
vote
1answer
878 views

Prove convexity/concavity of a complicated function

Can anyone help me to prove the convexity/concavity of following complicated function...? I have tried a lot of methods (definition, 1st derivative etc.), but this function is so complicated, and I ...
1
vote
1answer
97 views

Please help me find the maxima of this expression

I want to find $p$ which maximizes the given functional. $p$ is a function of the form $\mathbb{R}^2 \to \mathbb{R}$. $\Omega$ is a region in the 2-d plane. $\underset{p}{\sup} \int_\Omega \{ ...
1
vote
1answer
214 views

Supremum of vector dot-product

I am curious what is the precise math reasoning behind this: $$ \sup \{ a_i^T u | \lVert u\rVert_2 \leq r \} = r \lVert a_i \rVert_2$$ It is on page 148, last line, of Boyd's Convex Optimization ...
1
vote
2answers
452 views

Proving quadratic function is bounded (vector input)

I am reading Boyd's Convex Optimization textbook and I am looking at example 3.22, line 2. It says $y^T x - \frac12 x^T Q x$ is bounded from above for all possible values of $y$. Also, it is ...
1
vote
1answer
316 views

Can Minkowski difference be realized with support functions?

Minkowski sum of two compact convex sets is easily computed if they are represented in terms of support functions, one just adds the two support vectors for each direction. $X \oplus Y = \{x+y : x ...
1
vote
1answer
202 views

Scaling a decimal number to have leading digit 5 or more

Suppose we are given two real numbers: $a, b \in \mathbb{R}$, $b > a$. Find $m \in \{1, 2, 2.5, 5\}$ and $k \in \mathbb{Z}$, satisfying the following condition: $\frac{b-a}{m10^k} \in [5,10)$. How ...
1
vote
1answer
11 views

Fenchel duality in conic program

The question is from the textbook Convex Optimization Algorithms, prof. Bertsekas, p.511 A special case of Fenchel duality is the following: \begin{equation} ...
1
vote
2answers
45 views

Gradient mapping minimization problem

I am trying to solve this particular problem which can be found in this paper: $$\underset{y\in\Delta_n}{\text{argmin}}\{\langle\nabla f(x),y-x\rangle+\dfrac{1}{2}L\|y-x\|_1^2\}$$ I tried formulating ...
1
vote
1answer
28 views

Is this function composition convex?

Say we have two functions $f:R^n\rightarrow R$ , $g:R^m\rightarrow R^n$. Given that $f$ is convex, under what conditions on $f$ and $g$ we will be able to say that the composition function ...
1
vote
1answer
18 views

Can I write $\mathbb{S}_+^3$ as a norm cone?

Let $\mathbb{S}^3_+$ be the set of $3\times 3$ symmetric semi-definite positive matrix. I wonder whether I can write $\mathbb{S}^3_+$ as a norm cone, i.e., $$\exists A\in \mathbb{R}^{m\times 9}, C, ...
1
vote
1answer
41 views

How to resolve total variation $F(u)=f(u)+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$

Given $u(x)=[u_1(x)..u_N(x)]$, $0 \le u_i(x) \le 1, \sum_i^N u_i(x)=1$ and the cost function is: $$F(u)=f(u(x))+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$$ where $u_i(x)$ is a value that indicate ...
1
vote
1answer
20 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
1
vote
1answer
28 views

what does separable convex program mean?

In literature,a separable program is formulated like this: $$\min_{x_{1},...x_{n}}\sum_{i=1}^{n}f_{i}(x_{i})$$ where $f_{i}$ is a closed proper convex function. My question is what does 'closed' ...
1
vote
1answer
29 views

does constant convexity assures global minimum

I have the following question: Consider a function $f:R^n \longrightarrow R$, s.t.: there is a point $x_0 \in R^n$ s.t. $\frac{\partial f}{\partial x^k} =0$ $\forall k$. the hessian matrix ...
1
vote
1answer
40 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
1
vote
1answer
81 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
1
vote
1answer
89 views

How to project gradient vector to subspace defined by linear constraints

I have the following set of linear constraints: $$\begin {align}\textbf{y}^T\textbf {x} &= 0 \\ \textbf {0} &\leq\textbf {x} \leq C\cdot\textbf {1},\end {align}$$ where $\textbf {y} \in ...
1
vote
1answer
23 views

How can a second-order cone problem be expressed as a conic problem?

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could ...
1
vote
1answer
28 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
35 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
1
vote
1answer
27 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
1
vote
1answer
73 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
1
vote
1answer
51 views

how to write largest circle inscribed inside a triangle as an optimization problem?

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$. My institution is to cast to ...
1
vote
1answer
73 views

Convex Optimization: do Primal Dual methods need to start with strictly feasible point?

I'm learning about Primal-Dual interior point algorithms from Boyd & Vandenberghe Convex Optimization, ch.11.7. Now the text mentions: In a primal-dual interior-point method, the primal and ...
1
vote
1answer
46 views

Proving a function of matrix is convex

I have a function of a matrix and a vector $f(A,b)=y^\top (I-A)^{-1} b$ and I want to know the conditions under which it is convex. For functions of a vector, the positive definiteness of the Hessian ...
1
vote
1answer
55 views

How to derive the solution in quadratic optimization

I'm reading the book "Convex Analysis and Optimization" written by Prof. Bertsekas. In Example 2.2.1, there are the following description: I don't know how to ...
1
vote
1answer
22 views

Show the following statements are equivalent - convexity

Let $C \subset \mathbb{R}^n$ be a set. Show the following are equivalent: (a) The set $C$ is convex. (b) The function $\delta_C : \mathbb{R}^n \to \mathbb{R} \cup \infty$ defined as: ...
1
vote
1answer
36 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...