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

learn more… | top users | synonyms

4
votes
3answers
254 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 ...
4
votes
1answer
585 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
54 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 $? ...
1
vote
2answers
158 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
57 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 ...
1
vote
1answer
226 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
106 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
57 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
40 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
45 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
221 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
83 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
45 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
29 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
76 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
79 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 ...
1
vote
1answer
155 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 ...
1
vote
1answer
48 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
14 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
47 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
46 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 ...
4
votes
2answers
567 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
41 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
152 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
308 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
1answer
52 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
57 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
1answer
105 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
25 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 ...
4
votes
1answer
196 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
47 views

Motivation : min cut and max flow

Can someone explain the motivation behind the min cut and max flow problem?
1
vote
0answers
117 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
403 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
59 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
45 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
1answer
29 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
30 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
1answer
16 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 ...
1
vote
0answers
60 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
0
votes
1answer
544 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
3
votes
1answer
965 views

Affine sets and affine hull

Mathematically an affine hull can be expressed as $ Aff[C] = \{\theta_1x_1 + \theta_2x_2 .... \theta_nx_n| x_i \in C \ \ \sum_{i=1}^{n}\theta_i = 1 \}$ Intuitively can anyone explain what this ...
0
votes
2answers
72 views

Non-elementwise Matrix Derivatives

Let A,B,C,D,X be matrices. I'd like to perform a Gradient Descent minimization to the loss functin $$ tr[(AXBX^TC-D)^T(AXBX^TC-D)] $$ My question is, how to take the gradient efficiently w.r.t. $B$? ...
1
vote
1answer
1k views

Prove convexity of squared Euclidean norm

I need to prove that the square of the Euclidean norm is convex, so: $||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$. Can I use the triangular inequality (if yes, how?) or should I ...
1
vote
1answer
96 views

strict separation theorem?

Im learning and we have a theorem that says: Let $C$ be a non-empty, convex subset of $\mathbb R^d$ and let $p \in \mathbb R^d$ be a point which is not in the closure of $C$. Then there exists a ...
0
votes
0answers
18 views

Confusion related to a function used for optimization

I have a function $f(x)$, such that at point $x'$, it attains its minimum value, but the gradient at this point $x'$ is not equal to $0$. On the other hand the function $f(x)$ has slightly higher ...
1
vote
1answer
94 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
1
vote
2answers
176 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? ...
0
votes
1answer
35 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
0
votes
1answer
104 views

(pseudo-/quasi-)convexitiy of ratio between quadratic and affine function

Let $X\subseteq\mathbb{R}^n$. I have the following function $f:X\rightarrow\mathbb{R}$: $$ f({\bf x})= \frac{c_1 + \sum_{i=1}^n a_ix_i +\sum_{i=1}^n b_ix_i^2}{c_2+\sum_{i=1}^n d_i x_i}\enspace.$$ All ...
3
votes
2answers
118 views

why is argmin $\|w\|^2$ equivalent to $\operatorname{argmax} 1/\|w\|$

I was wondering why the maximization of $1/\|w\|$ is equivalent to minimizing the squared norm of $w$. Shouldn't it be equivalent to just minimizing the norm of $w$? This is a very basic optimization ...