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

learn more… | top users | synonyms

1
vote
1answer
21 views

Can be x_1 * x_2 >= x_3 * x_4 represented as a second order conic (SOCP) constraint?

I'll like to know if the constraint x_1 * x_2 >= x_3 * x_4 can be represented as an SOCP constraint. Note that setting matrix A = [ x_1 x_3 \\ x_4 x_2] the constraint is equivalent to det(A) >= 0, ...
1
vote
1answer
35 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where ...
1
vote
1answer
54 views

Optimization of a convex target function with inequality constraints

I want to solve the following optimization problem: \begin{equation} \begin{split} \text{maximize} &\;\;\; \ln x_1+\ln x_2+\ln x_3+\ln x_4 \\ \text{s.t} &\;\;\; x_4\le4 \\ ...
1
vote
1answer
36 views

Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
1
vote
1answer
35 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
1
vote
2answers
134 views

Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Suppose We have this optimization problem which is convex $\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$ But the product of different objective function is ...
1
vote
1answer
98 views

KKT point of a constrained optimization problem

Min$_{x}~x$ Subject to $x \geq 0$ For this problem, is $(x^{*}, \lambda^{*})=$$(0,0)$ a KKT point ? My try : I formulated corresponding Lagrangian and tried to find out the KKT point(s). ...
1
vote
2answers
42 views

A statement for convex sets

The following statement is true or false? Given a convex set $S$ then for any $y \in S$ and $\theta\in[0,1], \theta \in \mathbb R$ there exist $y_1,y_2 \in S, y_1 \ne y, y_2 \ne y$ such that ...
1
vote
1answer
208 views

How to find a positive semi-definite linear combination?

Suppose we are given two explicit symmetric matrices $X$ and $Y$ and we'd like to find a non-zero real linear combination $aX+bY$ that is positive semi-definite (if possible). Is there a way to go ...
1
vote
2answers
477 views

Why is this weighted least squares cost function a function of weights?

Here is a picture from my book regarding weighted least squares: Totally lost here, so I extracted the main nested issues confusing me: First Question: I know that in any LSE we want to minimize ...
1
vote
1answer
64 views

How to obtain primal problem from Lagrangian?

If you're trying to optimize $\min_x f_0(x)$ subject to $f_i(x) \leq 0$ then the Lagrangian would be $$L(x, \lambda) = f_0(x) + \sum_i \lambda_i f_i(x)$$ The dual problem is $\max_\lambda g(y)$ ...
1
vote
1answer
80 views

Could anyone give me an example of non-smooth strong convex function? [closed]

Could anyone give me an example of non-smooth strong convex function? I cannot figure out one.
1
vote
1answer
40 views

An equation related to covariance matrix, square root of the matrix, and Euclidean norm.

How can I prove this equation: $${ ({ x }^{ T }\Sigma x) }^{ 1/2 }={ \left\| { \Sigma }^{ 1/2 }x \right\| }_{ 2 }$$ In which $\Sigma $ is a covariance matrix. I tried some numerical examples in ...
1
vote
2answers
87 views

Hessian matrix and epigraphs

I'm working on a homework assignment concerning convex optimization and I came across a problem involving the convexity of the function and the convexity of the domain of the function. Consider the ...
1
vote
1answer
47 views

Convex Function Help and Counterxample

Given $g: \mathbb{R}^n \to \mathbb{R}$ is convex and $f:\mathbb{R} \to \mathbb{R}$ is convex and increasing. Show that $(f \circ g): \mathbb{R}^n \to \mathbb{R}$ is convex. I had no problem proving ...
1
vote
1answer
433 views

convexity of matrix “soft-max” (log trace of matrix exponential)

In convex optimization it is often convenient to use the following smooth approximation to $\max\{x_1, \ldots, x_n\}$: $$ f_\lambda(x_1, \ldots, x_n) = \frac{1}{\lambda}\log \sum_{i = 1}^n{e^{\lambda ...
1
vote
1answer
147 views

minimum trace norm on the set of matrices with fixed diagonal entries

What is the min nuclear norm (sum of singular values) on all $n \times n$ matrices$A$ whose diagonal is fixed. i.e. $diag(A) = v$ Is it true that the diagonal matrix is a minimizer?
1
vote
2answers
213 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
163 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
135 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
65 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
598 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
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
69 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
157 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
914 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
362 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
401 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
107 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
205 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
97 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
641 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
410 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
483 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
461 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
887 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
217 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
464 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
317 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
93 views

Trace minimization subject to diagonal constraints

Problem Revisited - Edited for conciseness: We are given two set of data points X [$p \times n$] and Y [$q \times n$]. Let us assume $X = \hat{X} + \tilde{X}$ and $Y = \hat{Y} + \tilde{Y}$ I am ...
1
vote
1answer
19 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
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
19 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
42 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
21 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$?