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

learn more… | top users | synonyms

1
vote
0answers
40 views

Optimization of sum of logs

I have an optimization problem of the form $$\operatorname*{argmax}_{\mathbf{w}} \sum_i \log(1 + \mathbf{w} \cdot \mathbf{k_i})$$ given some set of vectors, $\mathbf{ \{k_i\} }$. I have tried both ...
1
vote
1answer
206 views

How to project gradient vector to subspace defined by linear constraints

I have the following set of linear constraints: $$\begin {align}\textbf{y}^T\textbf {x} &= 0 \\ \textbf {0} &\leq\textbf {x} \leq C\cdot\textbf {1},\end {align}$$ where $\textbf {y} \in ...
0
votes
1answer
131 views

Is the normalized duality mapping symmetric?

In the area of functional analysis, nonlinear operator theory, the normalized duality mapping on a Banach space $X$ is a set valued map from $J:X\rightarrow 2^{X^*}$ given by \begin{align} ...
1
vote
1answer
135 views

Product of linear and convex function

More specific, how many maxima are there for product of these two functions: $ f(x) = ax + b $, and $ a > 0 $ $ g(x) $ is (strongly) decreasing convex function, $ \lim_{x\rightarrow\infty} g(x) = ...
0
votes
1answer
43 views

A maximization problem within the simplex

Let $\lambda_i$ be an ordered list of $N$ positive numbers, $\lambda_1<\lambda_2<\dots<\lambda_N$. I'm looking for the extrema of the function $$ f=\left(\sum_{i=1}^N p_i \lambda_i ...
0
votes
1answer
23 views

Example of convex subset (unbounded) with $\text {rec} (C) = {0}$

Example of convex subset (unbounded) with $\text {rec} (C) = {0}$ I've proved that for a bounded convex subset $C$ it always holds that $\text {rec} (C) = {0}$. However, now I'm looking for an ...
1
vote
1answer
39 views

How can a second-order cone problem be expressed as a conic problem?

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could ...
0
votes
1answer
34 views

Find the edges of a polyhedron P.

Given the polyhedron $P = \{v \in \mathbb R^2 \mid Av \le b\}$ with $A = \begin{bmatrix} -1 & -1 \\ 2 & -1 \\ -1 & 2 \\ 1 & 2 \end{bmatrix}$ and $b = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 2 ...
0
votes
2answers
102 views

How to check if given polyhedron is empty

Consider a polyhedron specified as following set of equalities and inequalities $$ \begin{aligned} &\mathbf{A}\mathbf{x} = \mathbf{b},\\ &\mathbf{x} \geqslant \mathbf{0}. \end{aligned} $$ Are ...
1
vote
1answer
22 views

Is every optimization problem with a piece-wise affine objective function the dual of some differentiable problem?

It is well known that a problem can have a $C^1$ objective function and a convex feasible set, while the dual problem can be piece-wise $C^1$ only. So I'm wondering - if you have a piece-wise affine, ...
1
vote
1answer
138 views

Proximal Operator of $\ell_{\infty,1}$ norm of a matrix

How can I calculate the proximal operator of mixed norm $\ell_{\infty,1}$ for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_{\infty,1} + \frac{1}{2\tau} ||X-Y||_F^2$ where ...
0
votes
1answer
27 views

Relaxing the elements of a matrix

I try to understand a specific part of the paper "Consistent shape maps via semidefinite programming", where a binary symmetric Input matrix $X^{in}$ is given with $X^{in} \in \{0,1\}^{nm \times nm}$ ...
1
vote
0answers
43 views

Do quasi-Newton methods check the second-order optimality condition?

I have a practical question about quasi-Newton methods. In quasi-Newton methods, Hessian matrix is approximated. It seems to be impossible for them to check the second optimality condition. In ...
0
votes
2answers
76 views

Weighted least squares with nuclear norm minimizaiton, how to optimize?

Nuclear norm minimization is very popularization and formulation is least squares term with nuclear norm term as following, $$\min\limits_{X} ...
2
votes
0answers
22 views

Sion Minmax theorem for integral operators

Suppose $f, g\in S=L^p([0,1],\Sigma,\mu,[0,1])$. The objective $L:S\times S\to R$ is given by $$L(f,g)= \int f (h-g) d\mu, $$ where $h\in S$ is fixed. Could we apply Sion Minmax theorem to conclude ...
2
votes
2answers
177 views

Why a convex cone cannot have more than one extreme point?

The way I define an extreme point is : A point which cannot be defined as a convex combination of two distinct points. I'm not able to extend this and show why a convex cone cannot have more than ...
3
votes
1answer
36 views

Convexity of |y-X'w|^2 given that inverse of X does not exist

Can we say anything about the convexity of the $|y-X^Tw|^2$ if we know that inverse of $X$ does not exist? Hessian is $2XX^T$. Given that X is not invertible, can we conclude that $XX^T$ is ...
0
votes
0answers
38 views

Convergence of backtracking and gradient descent.

I am thinking a bit about the following exercise: Let $f(x) = x_1^2 + x_2^2$ with dom $f = \{ (x_1,x_2):x_1 > 0 \}$. The optimal value of this problem is $p^* =1$, but it is never attained since ...
2
votes
1answer
136 views

Check if convex polygon is completely contained completely within another convex polygon.

How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities: pcp = ...
0
votes
1answer
14 views

If a quadratic form $f$ takes the minimum on a triangle in a vertex, what can I say about min of $f$ on edges of a subdivision?

Let $f(x)=x^2+y^2$ be the Euclidean square-norm and $A,B,C\in\mathbb{R}^2$ be vertices of a triangle $\Delta$ such that $f$ takes the maximum on $\Delta$ in $C$, the minimum in $A$ and takes the ...
0
votes
0answers
45 views

Using semidefinite programming to solve the following problem

I am struggling with the following problem, and wonder is SDP can help: $$\mathrm{maximize\ } \alpha_{10}+\alpha_5+(\alpha_2+\alpha_8)/2 \mathrm{\ subjected\ to\ } \mathrm{T_1}\succeq0, ...
1
vote
1answer
24 views

Convex combination and convex set

From where does $tx + (1-t)x'$ originate from? I am selfstudying an economists book, and this is popping up all of a sudden. I get that it's a line between $x$ and $x'$, but why? And is $tx' + (1-t)x$ ...
0
votes
1answer
47 views

Solving Constrained Least-Squares

I need to solve a constrained least-squares (LS) problem as follows $min_X \text{ } ||Y-AX||_F^2$ $s.t. \text{ } {X\in \chi}$ where $A\in R^{n\times m}$, $(n\ge m)$ , $X\in R^{m\times k}$ and ...
1
vote
1answer
31 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
45 views

For a non-convex function f, how to find a function g such that $g\circ f$ is strictly convex?

The following function $f(x)={1\over (1+e^{-x})}$ is non-convex but $\ln(f(x))$ is convex. Given a non-convex function $f$, can we find a function $g$ such that $g\circ f$ is strictly convex? If yes, ...
0
votes
0answers
37 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
1
vote
1answer
47 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
1
vote
1answer
90 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
1
vote
1answer
177 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
0
votes
0answers
43 views

Formulate an optmization problem as a convex optmization problem

Let $P$ be a polyhedron, i.e. $P = \{ x \in \mathbb{R}^{n}\, |\,\, a_{i}^{T}x \leq b_{i} \}$. Define $R$ as the rectangle given by $\{ x \in \mathbb{R}^{n}\, \mid\, \, l \preceq x \preceq u \}$. Find ...
0
votes
1answer
87 views

intuition behind subspace of $R^n$

Hi: I've been reading an optimization text by Charles Byrne, "A First Course In Optimization". I'm currently going through the chapter where he explains things about convex sets and convex functions ...
0
votes
1answer
39 views

proof that length of difference of projections implies equality of length of normals

Hi: I'm reading a book on optimization and there is an interesting stated theorem but I don't know how to prove it. Notation: Let $P_{c}(x)$ denote the projection of onto a convex set c which is a ...
3
votes
1answer
81 views

Climbing a hill with increasing & concave marginals. As you climb, do all coordinates go to $\infty$?

$f_1,\dots,f_N:\mathbb{R}^+\rightarrow\mathbb{R}^+$ are strictly increasing, bounded functions whose derivatives monotonically decrease to $0$ as their argument increases. (Picture the shape of the ...
0
votes
0answers
57 views

How can I minimize a quadratic on the unit simplex?

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex ...
1
vote
0answers
97 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
0
votes
0answers
25 views

How can I solve $\min \{ \langle A(x),y\rangle + f(y) \text{ s.t. } y \in S^n, \operatorname{tr}(y) =1, y \geq 0\}$?

I'm trying to solve the problem $$\min \{ \langle A(x),y\rangle + f(y) \mid y \in S^m, \operatorname{tr}(y) =1, y \geq 0\}$$ where $x \in \mathbb{R}^n$, $y \in S^M$, that is, it's a symmetric $m$ by ...
1
vote
0answers
43 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
1
vote
0answers
84 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
2
votes
1answer
69 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
0
votes
0answers
47 views

Find an optimal solution for $\min_{x} F(x)$ analytically

I want to find an analytical solution (exact/closed-form) for $x$ of the following minimization problem: $$\min_{x} b x \left[e^\left(\frac{a}{x}\right)-1\right]+d (1-c-x) \left[e^ ...
2
votes
1answer
127 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
1
vote
2answers
66 views

Is the optimum of this problem unique?

I have a convex optimisation problem: $$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$ The KKT conditions are: $$\lambda=\begin{cases} ...
1
vote
2answers
248 views

(Updated) Geometric Illustration of Monotone and Maximal Monotone Maps

I am writing a note about the Monotone and Maximal Monotone maps from the following book http://link.springer.com/book/10.1007%2Fb97594 In this book we read a map ...
0
votes
1answer
43 views

Is this function jointly convex in its variables?

I have a function which I suspect is jointly convex, but have a difficult time proving it, especially since the Hessian is messy. The function is $f(y_i,i=1.2,\ldots,N)=\sum_i l_i w_i + y_i$, where ...
0
votes
0answers
166 views

Is there a unique saddle value for a convex/concave optimization?

Here is the question: Consider a function of two variables $f(x,y)$ on some compact domain. Let it be convex in $x$ and concave in $y$. Is it true that $f(x,y)$ has a uniqe saddle point ...
0
votes
1answer
171 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
4
votes
1answer
54 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
1
vote
1answer
134 views

how to write largest circle inscribed inside a triangle as an optimization problem?

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$. My institution is to cast to ...
4
votes
2answers
158 views

Learning about convex optimisation

I'm interested in learning a bit about convex optimisation. The wikipedia article contains the following paragraph: The convexity of $f$ makes the powerful tools of convex analysis applicable. ...
0
votes
0answers
25 views

Quick Constrained Optimization Huerstistics

I am wondering if there is a way to find very quick optimization heuristics for the form. $$ f(x) = cx^a $$ $$ s.t. $$ $$ L \le Ax \le B$$ $$ 0 \le x \le \infty $$ I know with only a few variables ...