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

learn more… | top users | synonyms

2
votes
1answer
43 views

What is the name of this object?

Suppose I have a convex set $K\subset X$, where $X$ is say a real Hilbert space (for simplicity). Then, given some $a\in \Bbb{R}$, let $$ \hat{K}=\{x:\langle x,y\rangle \leq a \;\forall y\in K\} $$ ...
1
vote
2answers
63 views

What is the motivation behind strong convexity

Definition : A function is said to be $\beta$-strongly convex if, $f(\theta w + (1-\theta) w') \le \theta f(w) + (1-\theta) f(w') - \frac{\beta}{2}\theta(1-\theta)(w-w')^2$ What is the motivation ...
3
votes
3answers
100 views

Newton's method intuition

In optimisation the Newton step is $-\nabla^2f(x)^{-1}\nabla f(x)$. Could someone offer an intuitive explanation of why the Newton direction is a good search direction? For example I can think of ...
1
vote
1answer
39 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
0
votes
1answer
41 views

Prove that proximal function is convex

How to prove that the proximal function $$ \Phi (y) \equiv \min_x \left(f(x)+\frac{1}{2} ||x-y||_2^2\right) $$ is a convex function of $y$ if $f(x)$ is a convex function of $x\in \mathbb{R}^n $? ...
0
votes
0answers
49 views

Is this 0-sublevel $\sum (a_i 2^{\alpha_i x}) - \sum (b_i 2^{\beta_i x}) \leq 0$ a convex set?

I have this 0-sublevel set $a 2^{\alpha x} - b 2^{\beta x} \leq 0$ where $a_i$ and $b_i$ are non-negative. I can proof its convexity by using the definition. First, whenever $\alpha x$ and $\beta x$ ...
1
vote
2answers
59 views

Application of Fenchel Young- Inequality

i'm stuck on the weak duality ineqiality. For $X,Y$ euclidean spaces: $f: X\rightarrow (-\infty,\infty]$, $g: Y\rightarrow (-\infty,\infty]$ and $A:X\rightarrow Y$ linear bounded mapping. I want to ...
2
votes
1answer
41 views

How to prove a set is convex

Let $E = \{x\mid (x - c)^{T} P^{-1} (x-c) \le 1 \}$, where $P$ is symmetric positive definite. Show that $E$ is convex. Here is what I did. It seems like $E$ is an ellipsoid. We want to show that ...
0
votes
0answers
6 views

Confusion related to derivation of dual

I was reading this paper . I have some confusion related to the derivation of the dual. In the Duality and optimality conditions, they have said that the gradient is $-P_V(X^{-1}) + C$ I didn't ...
0
votes
0answers
6 views

Confusion related to dual being concave

I have some confusion related to the dual being concave $$ g(\lambda, \mu) = inf_x L(x,\lambda,\mu) = inf_x(f_o(x) + \sum_{i=1}^{m}\lambda_if_i(x) + \sum_{j=1}^{m'}\mu_ih_i(x) $$ why is it concave? ...
1
vote
0answers
101 views

Sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
1
vote
1answer
43 views

Property for the subdifferential and duality mapping in context of the Moreau-Yosida regularization

I have a question arising from the Moreau-Yosida regularization in Banach spaces. The real Banach space $X$ and its dual $X^*$ are both reflexive strictly convex, $f:X \rightarrow \mathbb{R} \cup ...
0
votes
1answer
35 views

Convexity of a second order cone

Does the following set define a second order cone? Anyway, is it a convex set? $(x,t)$ so that $\lVert(Ax+b)\rVert^{2} \le t(c^{t}x+d)$ $x \in R^{n}$ (A being a matrix, b,c vectors of the ...
1
vote
0answers
30 views

Is $A^TP+PA<0$, $P>0$ and $A^TP+PA\leq-I$, $P\geq I$ equivalent?

Consider the LMI, where $A$ is a Hurwitz matrix: $A^TP+PA<0$, $P>0$, minimize trace(P) According to Stephen Boyd's book, the inequalities are homogeneous in P and hence can by replaced with ...
1
vote
1answer
31 views

Is $|| AXB-C ||_F$ convex?

Let $A \in \mathbb R^{n\times n}$, $B \in \mathbb R^{n\times n}$, $C \in \mathbb R^{n\times n}$ be constant matrices. Is the following convex? minimize $|| AXB-C ||_F$ for $X>0$, where $|| \dots ...
0
votes
1answer
101 views

Gradient of a norm with a linear operator

In mathematical image processing many algorithms are stated as an optimization problem, where we have an observation $f$ and want recover an image $u$ that minimizes a objective function. Further, to ...
1
vote
0answers
31 views

Cauchy point,derivation: whe the constrianed optimizitaion is not used

Sorry for the slightly longer question. Consider the following definition of the Cauchy point $h_{i}^{C}=\alpha_{i}^{C}h_{i}.$ It can be found minimizing a quadratic form ...
0
votes
1answer
39 views

Is this a valid transformation?

I have the following objective: \begin{equation} \max_{\mathcal{I}} \sum_{m=1}^{M}w_m\sum_{n \in N_m}^{ }I_{m}^{n} \end{equation} subject to some constraints, beside tha fact that the variables ...
0
votes
2answers
26 views

Concave function applied to equally distant points

Is the next statement true? Let $f$ be concave and $a \leq b \in dom(f)$. For any $c \geq 0$ such that $a+c, b+c \in dom(f)$ then $$ f(b+c) - f(b) \leq f(a+c) - f(a) $$ If it is, how would you prove ...
1
vote
0answers
47 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
2
votes
1answer
66 views

Does the center of a convex region lie within that region?

There's probably a simple result that says this is true, but I sure can't find it. It seems obvious, though. Let $D$ be a closed, compact region in $\Re^n$. Further, let $D \subseteq [0,l]^n$ and ...
0
votes
0answers
30 views

Optimization objective modification for matrix factorization.

I have the following optimization objective: Here A is an mXn user-item rating matrix. W is a nXn weight vector that I am trying to learn. beta and lambda are parameters passed in. ...
1
vote
1answer
58 views

Minimizing a linear function on a strictly convex set.

All the theorems that I know considering the uniqueness of a solution to a minimization/maximization problem requires the strict convexity/strict concavity of the objective function. But consider the ...
0
votes
0answers
22 views

Error of the norm of solution in linear least-squares

How can we estimate the solution norm ($\Vert x \Vert$) error, separate from the solution ($x$) error in solving $Ax=y$ (linear least-squares problem)? Is the error of $\Vert x \Vert$ higher or lower ...
1
vote
1answer
15 views

Show that every polytope is bounded

The definition of polytope is the convex hull of a finite set. Thus: $$ \parallel\sum_j\lambda _j x_j\parallel\le\sum_j\lambda_j\parallel x_j\parallel\le\sum_j\lambda_j\max_j \parallel ...
0
votes
1answer
13 views

Show that diagonal of a square is not a face

Let C be a convex set in $R^n$. We say that F is a face of C if the following condition holds: if $x_1, x_2 \in C$ and $(1-\lambda)x_1+\lambda x_2 \in F$ for some $0\lt \lambda \lt 1$ then $x_1, x_2 ...
0
votes
1answer
33 views

Optimization of quadratic fractions

Is there an efficient way (for example to convexify, lower bound (except special cases), or something like that) to optimize quadratic fractions? For example: $$ min_x \frac{x^\top A x + x^\top B ...
1
vote
0answers
32 views

Differentiability of the Value (Support) Function

Consider the following problem, \begin{align} c(y,\mathbf{w})=\inf_{\substack{\mathbf{x} \in \mathbb{R}^n_{+} \\ \text{s.t. }f(\mathbf{x}) \geq y }} \mathbf{w} \cdot \mathbf{x} \end{align} where ...
0
votes
0answers
27 views

Hessian of a conic function

i got a conic System: $Ax =b, x\in C$, where $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m$ and C is the cone of the $n\times n$ positive semidefinite matrices, so ...
0
votes
0answers
31 views

How to prove the concavity of this function

How to check the concavity of the following function? \begin{equation} \log\left|\mathrm{diag}(\gamma_1,\ldots,\gamma_n)A + \mathbf{I} \right|, \end{equation} where \begin{equation} \gamma_i = ...
4
votes
2answers
111 views

Conjugates of norms

How would one find the conjugate of the following : $$f(x) = \|x\|^2 /2$$ The conjugate function is defined as $ f^*(y) = \max_x y^Tx - f(x)$ I am stuck at how I can derive the explicit form for ...
2
votes
0answers
29 views

Semidefinite Program formulation

I have the following problem and would like to formulate that as an SDP. I am not sure how to approach this : A set $S$ is given such that : $$ S = \{P \in R^{n \times m} : ||p_i - c_i|| \leq d_i ...
1
vote
0answers
75 views

Whitening matrix for Fast ICA

I have a matrix $X $ with dimension say $ m \times n $ with $ m> n $. I am trying to whiten this matrix in matlab by first taking the $C= \operatorname{covariance}(X)$ followed by eigenvalue ...
2
votes
1answer
93 views

Smooth Hinge Loss Lipschitz Constant

Given the smooth hinge loss $L_\epsilon$ as follows $L_\epsilon(y_i (w^T x_i + b)) = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{(1-y_i (w^T x_i + b))^2}{2 \delta} & 1 - \delta < y_i (w^T ...
0
votes
0answers
11 views

Proximal operator involving frame analysis operator

Combettes and Pesquet (paper) contains a result that the proximal operator of a composite function $f\circ L$, where $L$ is a semi-orthogonal operator $L$ such that $LL^*=\nu\cdot Id$, is given by ...
0
votes
1answer
38 views

Projection on a convex set

If I have a convex set $ S$ and if I project an $ x$ onto $S$. Is it true that $x $ would project onto a unique element of $S$. Why? What would be considered different if the set $S$ was non-convex?
2
votes
1answer
31 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
0
votes
0answers
20 views

Quadratically minimization of trace with constraints

For positive and symmetric matrix $S\in \{-1,0,1\}^{N\times N}$, how to minimize the following function: $$ \begin{align} &\min_{Y}~ \text{trace}(YSY^T) + \left\|AY-B\right\|_2^2\\ &s.t. ~~ ...
0
votes
1answer
57 views

Projection operator and convex sets

I was wondering if the projection operator onto a convex set was differentiable? [ An explanation would be helpful ] .
0
votes
1answer
21 views

Concavity of a function that is obtained from another concave function

Let $f(x):[0,1]\rightarrow \mathbb{R}$ be a strictly concave function such that $f(0)=f(1)=0$. Let $x^*$ denote the maximizer of $f(x)$. For any value $x\in[0,x^*)$, there exists exactly one other ...
1
vote
0answers
40 views

constraint optimization of quadratic-over-linear

I need to optimize the following quadratic-over-linear objective: $$ \frac{x^TAx}{c^T x} $$ subject to $$\mathbf{1}^Tx = 1$$. Where $A$ is a diagonal (with all positive entries ) matrix and $c$ ...
1
vote
1answer
33 views

Motivation : min cut and max flow

Can someone explain the motivation behind the min cut and max flow problem?
1
vote
0answers
37 views

Joint cost function with Lagrangian

How can I formulate joint cost functions if Lagrangians are involved? For example, if I have $J_1 = \|\mathbf{Ax} - \mathbf{b}\|^2_2 + \lambda f$ and $J_2 = \|\mathbf{Cx} - \mathbf{d}\|^2_2$, ...
0
votes
1answer
79 views

Is exponential of a concave function concave?

is this function: $$\exp\Big(-||Ax||^2\Big)$$ concave in A?? I know that exponential of a convex function is convex, but is exponential of a concave function concave??
1
vote
1answer
55 views

Please explain this theorem with picture

I logically understand this theorem, but I don't intuitively understand with picture. Let $S$ be a nonempty convex open set in $\mathbb R^n$ and let $f\colon S\to\mathbb R$ be differentiable on ...
1
vote
0answers
32 views

Is there a textbook treatment of Ky Fan's minimax theorem and its generalizations?

Theorem 2 in Ky Fan(1952) is a powerful tool in zero-sum games, which states: Let $X$ be a compact Hausdorff space and $Y$ an arbitary set (not topologized). Let $f$ be a real-valued function on ...
1
vote
0answers
15 views

References or texts for learning about the augmented lagrangian?

I am reading a paper about a convex model for non-negative matrix factorization. In the paper it describes how to do such a technique and it says that it uses the augmented Lagrangian. I can't find ...
0
votes
1answer
23 views

Proportion of domain in which convex function is small

Let $K \subseteq \mathbb R^n$ be a compact convex set with volume $V$, and let $f: K \to [0,1]$ be a convex function with domain $K$. Assume that $\min_{x \in K} f(x) = 0$. I claim that, for every ...
0
votes
0answers
14 views

Verifying if the gradient is correct or not

I was following this article to verify if the gradient that I had derived and calculated was correct or not Let say my function if $f(\theta)$. The derivative/gradient wrt $\theta$, $g(\theta)$ ...
0
votes
1answer
14 views

Optimization issues with positive definite constraints

I have an optimization problem where I have to optimize a function f(A) where A is a matrix(sparse). Like A = \begin{array}{cccc} A_1 & A_0 & A_0 & 0 \\ A_0 & A_2 & 0 & A_0 ...