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

learn more… | top users | synonyms

0
votes
1answer
84 views

Show that the dual norm of spectral norm is Nuclear norm.

Could someone help to understand that the dual norm of spectral norm is Nuclear Norm ? We can focus on the real field. Given a matrix $X \in \mathbb{R}^{mn},$ then the spectral norm is defined by: ...
0
votes
1answer
33 views

is this a convex optimization problem?

Can someone clarify is this a convex optimization problem or not. $min \| X-UV\|_{F}\quad $ s.t $ \quad U \geq ,V\geq0$ . If not , what makes the problem non-convex?
3
votes
1answer
110 views

Newton's method vs. gradient descent with exact line search

tl;dr: When is gradient descent with exact line search preferred over Newton's method? I simply don't understand why exact line search is ever useful, and here's my reasoning. Let's say I have a ...
0
votes
0answers
54 views

Nonsmooth optimization

Now I have a chance taking a course in nonsmooth optimization, the course outline writes: convex analysis, subdifferential calculus and proximal mapping. various numerical algorithms to solve ...
1
vote
0answers
29 views

sup is bounded or not?

The sup is as following: $c_f = sup_{x,s\in D} \ f(y) - f(x) - (y-x)^Tb$ where $y=x+\alpha(s-x)$, $\alpha \in (0,1 )$ is constant and $b$ is a constant vector. $D$ is a convex compact set and ...
1
vote
1answer
33 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
114 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
1
vote
1answer
50 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 ...
0
votes
1answer
43 views

What's the difference between interior and relative interior?

As defined in Convex Optimization written by Stephen Boyd, both interior and relative interior seems to describe a same thing: a set that peels away it's boundary points. So what on earth is the ...
0
votes
1answer
47 views

How to solve this convex resource allocation problem numerically? CVX doesn't work.

I got a resource allocation problem as follows: \begin{eqnarray} \min &\sum_{i=1}^M \frac{1}{1 + \text{exp}(C_i + \frac{r_i}{1+r_i})} ;\\ &\sum_{i=1}^M r_i \le R;\\ &r_i \ge 0 ...
0
votes
1answer
22 views

Projection on Epigraph of a convex function

Given a convex function $h:\mathbb{R}^n \mapsto \mathbb{R}$, and a point $(x,\alpha) \in \mathbb{R}^n \times \mathbb{R}$, how can I find a closed formula to compute the projection of $(x,\alpha)$ in ...
1
vote
0answers
104 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...
0
votes
0answers
14 views

How do I show that expected squared error stochastic optimization problem has a global optimum?

I was interested in showing that minimizing the following had a global optimum: $$ \mathbb{E}_{ (x , y) \sim P_{x,y}}[(\hat{x}(y) - x]$$ where $\hat{x}(y)$ is a linear function i.e. $\hat{x}(y) = ...
0
votes
1answer
30 views

Verifying stationary points - check my answer please - Has a hessian

Can someone check this for me; For $f(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2-x_1x_2+x_2x_3-x_1x_3-x_1+x_2$ the stationary point occurs at $\nabla f(x)^T =\left[ \begin {array}{c} 0\\ 0\\ 0\\ ...
0
votes
1answer
25 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
2
votes
0answers
57 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...
0
votes
0answers
23 views

Optimize log functions over polytopes

Let's consider the following optimization problem min $\sum_{i=1}c_i\log x_n $ subject $Ax\leq b$ ie, it is to optmize a weighted sum of logarithms over a polytope ($Ax\leq b$). Clearly if $c_i$'s ...
0
votes
0answers
39 views

How to prove that convex function has an increasing slope?

A function $f(x)$ in some domain $a\leq x \leq b$ is convex if and only if for any $x_1 < x_2 < x_3$ from domain $[a,b]$, $$\frac{(f(x_2)-f(x_1))}{(x_2-x_1)} \leq ...
0
votes
1answer
25 views

Is this a convex program?

I have a nonlinear optimization problem $\min \sum_{i=1}^n \sum_{j=1}^n y_{i,j}$ subject to $x_i- y_{i,j}x_j\leq 0$ $0\leq x_i\leq 1$ $y_{i,j}>0$ The question is whether this is a convex ...
0
votes
0answers
27 views

convex function - global minimum

Suppose that $f(x):R^p \rightarrow R$ is a convex function with global minimum, say 0. Let $C=(x: f(x)=0)$, i.e. the set of the global minimum. Suppose that there exist at least one point $y$ such ...
2
votes
1answer
32 views

Does $\log(f(X))$ concave implies $\log(f(X^{-1}))$ convex?

One of my professor claims that $\log f(X)$ concave implies that $\log(f(X^{-1}))$ convex where $X$ is symmetric positive definite matrix. $\log(f(X))$ is a function defined on symmetric positive ...
1
vote
0answers
23 views

Subspace of tangent feasible directions

If $h: \mathbb{R}^3 \to \mathbb{R}^3$ defined by $h(x_1,x_2,x_3) = (x_1^3 - x_2 + x_3^2, x_2,x_1+x_2+x_3)$ I define $V(x)$ as a subspace formed by all directions tangent to some constrained set at ...
1
vote
0answers
36 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq ...
1
vote
0answers
21 views

Why is this set a subset of its polyhedral approximation - contradicting the gradient inequality?

Say we have a set $C:= \{y\in \mathbb{R}^n : g_i(y) \leq 0, \space i=1,...,m\}$ where $g_i : \mathbb{R}^n \to \mathbb{R}$ are convex and differentiable functions, then we have $\tilde C : = \{y: ...
1
vote
0answers
22 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
1answer
19 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: ...
0
votes
0answers
17 views

About the alternating optimization

The problem is defined as follows: $$ min_{A,B,C} f(A,B,C) $$ and the problem couldn't solve by gradient descent or close-form solution. Thus, the usual way is to use the alternating optimization: ...
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 ...
1
vote
2answers
26 views

How to prove that given log function is convex

How to prove that $log(1+e^{-x})$ is a convex function? [from comment]: I have tried with the basic definition of convex function..... like $f(ax+by) \leq af(x)+bf(y)$... but was not able to solve ...
0
votes
1answer
29 views

Steepest Descent Sequence

How can I compute the first three iterates for the steepest descent sequence $f(x_1,x_2) = \frac{(x_1^2+3x_2^2)}{2}$ beginning at $x_0 = (\frac{\sqrt{3}}{2}, \frac{1}{2 \sqrt{3}})^T$ $\nabla ...
2
votes
1answer
32 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
1
vote
0answers
53 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 ...
0
votes
0answers
18 views

Property of probability density function (pdf)

If $X$ is a random variable with a log-concave pdf. And suppose $Z = h(X)$ If $h(X)$ is convex, can we say $Z$ has a log-concave pdf? If $h(X)$ is affine, can we say $Z$ has a log-concave pdf? ...
1
vote
0answers
50 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 ...
0
votes
0answers
23 views

Dot product - geometrical interpretation in convex analysis

I am studying a theorem on the characterization of solutions in nondifferentiable convex problems. Say that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and $f: \mathbb{R}^n \to ...
6
votes
1answer
76 views

References for hemicontinuity?

Let $X$ be a real vector space, $K\subset X$ be a nonempty and convex set. The mapping $f:X\rightarrow\mathbb{R}$ is said to be hemicontinuous if for every $u,v\in K$, the mapping ...
0
votes
1answer
42 views

Convexity of problem with inverse matrix

I am trying to solve the next problem \begin{aligned} & \underset{P}{\text{maximize}} & & \log \det P \\ & \text{subject to} & & A^T P^{-1} + P^{-1} A \preceq 0 \\ ...
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
41 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) ...
0
votes
0answers
32 views

convexity of inverse of a matrix

I know that the function $f(X)$ which maps matrix $X$ to $Tr((X)^{-1})$ is convex for symmetric positive definite $X$. This has also been answered in Is the trace of inverse matrix convex? for ...
0
votes
1answer
39 views

Does analytical solution exist for this convex euclidean affine projection problem with non-negativity constraints?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
1answer
34 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
1
vote
0answers
31 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, ...
0
votes
2answers
96 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
1
vote
1answer
33 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
2
votes
0answers
32 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
0
votes
1answer
68 views

Proof - extreme point of a convex set

everybody! I am wondering how to prove the following theorem: Let $S \subset \mathbf{R}^{n}$ be a non-empty closed convex set. Then $S$ has at least one extreme point iff $S$ does not contain any ...
0
votes
1answer
37 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
3
votes
1answer
36 views

How to show $ \sup \inf g(x,y) \leq \inf \sup g(x,y)$?

Came across this little practice exercise, and I couldn't properly convince myself of this relation: Let $X,Y \subset \mathbb{R}^n$ and $g:X\times Y \rightarrow \mathbb{R}$. Show that $$\sup_{y \in ...