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

learn more… | top users | synonyms

1
vote
0answers
68 views

Is the function $f(A)=-\log(tr(A^{-1}))-\log(\det(A))$ convex?

I am trying to show the following function is convex or not $$f(A)=-\log(\text{trace}(A^{-1}))-\log(\det(A)),$$ where $ A$ is positive definite. I know $\text{trace}(A^{-1}), -\log(\cdot)$ and ...
1
vote
0answers
51 views

Proximal Mapping of Composition with Linear Operator

I've posted this question on math overflow but got no answer, so I think it might not be a research level question so I decided to post it here too. Let $A$ be an orthogonal matrix. It is well known ...
1
vote
0answers
92 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
1
vote
0answers
45 views

Difficulty in understanding a solution: Constraint minimization of sum of Non-symmetric matrices

I am trying to understand why there is significance difference in the performance of two proposed solutions. Original question (Constraint minimization of sum of Non-symmetric matrices) ...
1
vote
0answers
40 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
1
vote
0answers
34 views

How to find a hyperplane

Let $A, B ⊂ \mathbb{R}^n$ be two nonempty sets such that $A ∩ B = ∅$. $H(A, B) := \{(w, d) ∈ \mathbb{R}^{n+1} : \sup_{x\in A} \langle w,x\rangle ≤ d ≤ \inf_{y \in B} \langle w, y\rangle \}$ How do I ...
1
vote
0answers
88 views

Showing convexity of a function with the restriction over an arbitrary line proof

Let $f : \mathbb{R}^n → \mathbb{R}_∞$ be a function and let $C ⊂ dom f$ be a convex set. $$**Part I**$$ Prove that $f$ is a convex function if and only if $f$ is convex over every line $L_{v,x_0}$ ...
1
vote
0answers
109 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
1
vote
0answers
16 views

Is epi(max(f,g)) the intersection of epi(f) and epi(g)?

On an exam, I found the question "is max($f(x),g(x))$" convex if $f,g$ are convex? This lead me to the question in the topic. Is the intersection of epi$(f)$ and epi$(g)$ = epi($\max(f,g)$)? If so, ...
1
vote
0answers
41 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
1
vote
0answers
24 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
1
vote
0answers
49 views

Compressed sensing: converse of a theorem

Theorem: Suppose that the signal length $N$ is a prime integer. Let $\Omega$ be a subset of $\{ 0, \ldots , N-1 \}$ and let $f$ be a vector supported on $T$ such that $|T| < \dfrac{1}{2}|\Omega|$ ...
1
vote
0answers
119 views

Dynamic programming problem for discrete linear time varying system

I'm working on a linear time varying discrete(LTV) multi input multi output(mimo) system. I formulate the problem description in the following way $$x_i(k+1) = x_i(k)\cdot A_i(k) + B_i(k)\cdot ...
1
vote
0answers
45 views

How nuclear norm is convex whereas weighted nuclaer norm is not?

In (http://nuit-blanche.blogspot.in/2014/05/wnnm-weighted-nuclear-norm-minimization.html), it is stated that nuclear norm of a matrix $\mathbf{X}$, given as $||\mathbf{X}||_{*}=\sum_{i} ...
1
vote
0answers
32 views

Entropy proerty

Let $a,b,c>0$ be distinct postive reals. Define four different probability distributions: $$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$ ...
1
vote
0answers
32 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
1
vote
0answers
39 views

Minimization using logarithmic barrier function

I'm thinking of the quadratic problem(QP) \begin{align} &\underset{x\in \mathrm{R}^n}{\mathrm{Minimize}}\ \ \ \frac{1}{2}x^\top{}Qx + f^\top{}x\\ &\mathrm{subject\ to}\ \ \ \ a_ix \leq b_i\ ...
1
vote
0answers
73 views

Conic hull of outer products

Consider the set of rank-k outer products, defined as $\{XX^T | X \in R^{n\times k}, rankX = k \}$. Describe its connic hull in simple terms. I have found the solution of this exercise but I have ...
1
vote
0answers
64 views

Using Taylor's theorem and Lagrange form of the reminder to prove the second order condition for convexity

I try to prove the second order condition for convexity. So far' I've done the following: First, I prove second order => convexity: Let $f$ be a function with positive semi-definite Hessian. Using ...
1
vote
0answers
38 views

Property of Newton step for self-concordant convex functions

Suppose $f(x)$ is a convex and self-concordant function minimized at $x^*$. I have two starting points $\tilde{x}_0$ and $\hat{x}_0$ such that $|\hat{x}_0-x^*| \le |\tilde{x}_0 - x^*|$. We also know ...
1
vote
0answers
47 views

Distributed convex optimization problem

Consider the optimization problem $$ \min_{ x_1, \ldots, x_N } \sum_{i=1}^{N} f_i( x_i ) \\ \text{s.t.: } \sum_{i=1}^{N} x_i \in X, \ x_i \in X_i \ \forall i \in \{1, \ldots, N\} $$ where $f_1, ...
1
vote
0answers
118 views

About Intersection of two convex polytope?

the intersection of two convex hull of two polytope P and Q , is it the convex hull of the intersection of P&Q ? Conv(P) ∩ Conv(Q) = conv(P∩Q) ???.
1
vote
0answers
55 views

Is there any way to transform a non-convex optimization problem into a convex one?

I have an optimization problem which is described as $$\begin{array}{ll} \text{minimize}_x & c^{T}x\\ \text{subject to} & Gx \preceq h\\ & -x^{T}Px - qx - r \leq 0 \end{array} $$ where ...
1
vote
0answers
27 views

Is there a good textbook/book out there that explains sub gradients thoroughly?

I was interested in learning and understanding sub gradients as much as I could from some good resource. I know what the definition is, but I seem unable to apply the definition to prove basic facts ...
1
vote
0answers
32 views

Partial concave maximization of subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
1
vote
0answers
64 views

What is the left derivative of the hinge loss function in the context of subgradients?

Let: $$|a|_+ = max\{0,a\}$$ Then the Hinge loss function (in the context of classification in Machine Learning) is: $$V(-yf(x)) = |1 - yf(x)|_+$$ Note that $y \in \{-1,1\}$ Let $f(x) = \langle w, ...
1
vote
0answers
74 views

Proving/deciding concavity of a function of two variables

I would like to formally prove that the function $f(x,y) = \frac{(c+1)e^{-x}(xe^{x+y}+y)}{(c+2)(e^{x+y}-1)+e^y} $ is concave ($ c>2$ is a constant, and both $x,\, y \in \mathbf{R_+}$). Plots of ...
1
vote
0answers
38 views

When result of max of min problem is equal to min of max problem

Let's assume there are two functions $f(x)$ and $g(x)$. I want to know when the optimal $x$ of max of min of $f(x)$ and $g(x)$ is not equal to optimal $x$ of min of max of $\frac{1}{f(x)}$ and ...
1
vote
0answers
144 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
1
vote
0answers
24 views

Extra information needed to distinguish combinatorially isomorphic polytopes

The title pretty much sums up my question: what extra information do we need (or what is an example of sufficient information) on top of the face lattice in order to completely characterize a convex ...
1
vote
0answers
86 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
0answers
52 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
1
vote
0answers
51 views

Farthest point on a parallelotope from the origin

I have two related questions. First, consider a maximal independent set of vectors $\{v_1,\cdots,v_k\}$ in $k$ dimensional space. The rows of a square matrix $A$ are from those vectors. The origin is ...
1
vote
0answers
62 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
1
vote
0answers
31 views

How to convexify (relax) this L0 eigenvalue optimization problem?

Let $C_1,\dots,C_L$ be $N\times N$ hermitian matrices. Let $d<0$ be a given negative constant. Then consider the optimization problem \begin{align} \max_{r\in \mathcal{R}^{L\times 1}} &\mid\mid ...
1
vote
0answers
108 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
1
vote
0answers
24 views

Can this type of constraint be recasted to a convex constraint?

I have an optimization problem where all the constraints are linear but some of the type: $$ y_i = \frac{x_i}{\sum_k x_k} $$ It seems that the equality can be relaxed to an inequality adding the ...
1
vote
0answers
48 views

When does l1 regularisation give a sparse solution?

I was maximising a likelihood function, which is convex. I know that the system has a K-sparse solution. I wanted to know the conditions (or some sufficient conditions) on the likelihood function ...
1
vote
0answers
76 views

An Orthogonal Projection with Weighted Norm

In the context of solving a convex program via projected gradient descent i am facing the following problem: $$\min_{x\in\mathbb R^2}\lVert x-y\rVert_M^2,\qquad\lVert x\rVert\le1$$ or written ...
1
vote
0answers
43 views

find the angles of a given vector sum

Assume you have n vectors in 2D space, with different fixed magnitudes $l_i$. The problem is to find the angle of each vector such that vector sum is a specific vector. That is, $\sum l_i \cos ...
1
vote
0answers
49 views

Primal-dual subgradient method

In these notes, an extension of the subgradient method is presented in Section 8 (page 30). The method is described so quickly and neither convergence analysis (compared to classical subgradient for ...
1
vote
0answers
28 views

Confusion related to proximal newton method

I was reading this method related to proximal newton methods http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf. I came across this page I didn't get what this part means $ ...
1
vote
0answers
83 views

First order necessary conditions for nondifferentiable nonconvex minimization problem

I am interested in first order necessary conditions for the following minimization problem where the function $f$ is continuous, nondecreasing and concave, with $f(0)=0$, but not necessarily ...
1
vote
0answers
31 views

Detecting faces of polytopes

I am working in convex geometry for the summer with little experience beforehand. It's a lot of fun but it does mean I don't know some of the basic things. I'm interested in the orbits of finite ...
1
vote
0answers
61 views

Infinity norm minimization

I am wondering how to minimize an objective function of the following form: $$\min_{\mathbf{x}\in\mathcal{R}^{MN}} \|\mathbf{x}-\mathbf{y}\|_\infty + \lambda\mathrm{TV}(\mathbf{x})$$ Here, ...
1
vote
0answers
39 views

Interpreting constraints in an optimization problem

I am working on an optimization-based image denoising project in which I have three "flavors" of an optimization problem, one constrained and two unconstrained. They are given as follows: ...
1
vote
0answers
93 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
1
vote
0answers
22 views

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, ...
1
vote
0answers
109 views

Reference table of “tricks” for converting problems to standard LP, QP, SOCP, etc. form?

Where can I find a decent source/reference that which I can use to look up the various standard "tricks" for converting typical problems to standard form in LP, QP, SOCP, etc.? The Charnes-Cooper ...
1
vote
0answers
201 views

Until now, what is the fastest optimization algorithm of non-smooth convex functions

I am wondering if I minimize a non-smooth convex function, which solver should I choose. I think I should choose a fastest one with a big convergence rate. Subgradient descent is always on the ...