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

learn more… | top users | synonyms

1
vote
1answer
8 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
0answers
6 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
0answers
7 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
16 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
15 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 ...
0
votes
0answers
16 views

Book on duallity and sensitivity in nonlinear optimization

I am looking for a recommended book on duallity and sensitivity in nonlinear optimization, as duallity and sensitivity is a well studied topic in LP , I am struggeling to find books in this subject ...
0
votes
0answers
18 views

Continuity of optimisation problem

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
-2
votes
0answers
18 views

Pos of Matrix is a closed set? [on hold]

"Pos of matrix" $:= \{ \sum_{i=1}^n \lambda_i *a_i \mid \lambda_i \geq 0 ,\ a_i \text{ are columns of matrix, } 1\leq i \leq n\}$ that matrix have $n$ columns. Prove that "Pos of matrix" is a closed ...
1
vote
1answer
27 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 ...
0
votes
0answers
20 views

pos of matrix is close [on hold]

"Pos of matrix" := $\{ \sum_{i=1}^{m}\lambda_i *a_i |\ \lambda_i \geq 0 ,\ a_i\ \text{are columns of matrix,}\ 1\leq i \leq n\}$ that Matrix have $n$ columns. prove that "Pos of matrix" ...
0
votes
0answers
11 views

Optimization with KL-divergence in CVX [on hold]

I am trying to solve an optimization problem whose objective is KL-divergence (there are only linear equality constraints and nonnegativity constraints). In particular, my goal is to obtain a solution ...
1
vote
1answer
19 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
24 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
29 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
2answers
20 views

Finding when a function is concave [closed]

Given the function below $f=e^{ax^2+bx}$ what are the conditions on $a$ and $b$ such that $f$ wil be concave Thanks
0
votes
1answer
56 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
0answers
28 views

strong convex implies exp-concave

Prove that if f is strong convex (for some m>0) $\mbox(\nabla f(\mathbf{x})-\nabla f(\mathbf{y}))^{T}(\mathbf{x}-\mathbf{y})\geq m||\mathbf{x}-\mathbf{y}||_{2}^{2} $ then f is also ...
0
votes
1answer
34 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 ...
-4
votes
0answers
43 views

Positive solutions to $A^T A x \geq 0$ [closed]

Find a positive solution $x$ to the linear inequality $A^T A x \geq 0$. $A$ is an arbitrary matrix. I was wondering if there is a general solution. EDIT: One special solution is when $A^TA$ is row ...
3
votes
1answer
46 views

$\arg\max$ of an increasing function grows as the region grows.

$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
39 views

Non-convex function with global minimum [duplicate]

I am working on a complicated objective function which I suppose is not convex. But when I use a global optimization tool that can find all its local minimums, it will always converge to the same ...
0
votes
0answers
28 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
28 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
19 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
votes
0answers
19 views

Help understanding the specification of constraints for cvxopt

This is an example from the cvxopt documentation and I am trying to understand how the L2 constraints are specified to the solver. The problem is specified as: ...
0
votes
0answers
27 views

Krein Milman Property

If a closed bounded (not compact) set $X$ in a Banach space $B$ (like $L^1$) has extreme point(s), must the max of a linear functional defined on $X$ occur at one of them? I suppose it depends on $B$. ...
0
votes
0answers
15 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\\ $$ ...
0
votes
0answers
16 views

Minimizing a function known to have a unique local and global minimum

Quasi-convex functions are a class of functions known to have a unique local and global minimum, which can minimized over convex sets using numerical methods with convergence guarantees. A function is ...
1
vote
0answers
26 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
54 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
27 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^ ...
0
votes
0answers
24 views

How to solve the least square with $L_2$ norm constraint directly?

I answered the question Why are additional constraint and penalty term equivalent in ridge regression? earlier, but I myself still have some questions on it. To solve \begin{align} \min_{\beta} ...
2
votes
1answer
38 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
45 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} ...
0
votes
0answers
10 views

Reference material on Alternating Minimization Algorithm

I am looking for some good reference material (book/paper) for learning Alternating Minimization Algorithm. Any recommendation from optimization experts will be much appreciated. Thank you.
1
vote
2answers
195 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
22 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
33 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
41 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
46 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
34 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
54 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
24 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 ...
1
vote
1answer
36 views

Convexity of Conjugate Function on Determinant

If $f: \mathbb R^n \to \mathbb R$ then $conj(f) : \mathbb R^n\to \mathbb R$ is defined as $conj(f)(y) = \sup_{x \in dom_f} (y^Tx - f(x))$ and it is called the conjugate function of $f$. if $f(X) = ...
0
votes
0answers
36 views

Does every boundary segment of a convex polyhedron lies on one of its faces?

When I was reading this note, I found Theorem 3.1.5 said: Let $P\in\mathbb{R}^n$ be a polytope whose affine dimension is $d$. Then, every point on the boundary of $P$ lies in a facet of $P$. I have ...
1
vote
1answer
28 views

condition for uniform input to minimize convex function

Let $f:\mathbb{P}(X) \rightarrow \mathbb{R}$ be a convex function where $\mathbb{P}(X)$ is the set of probability distribution on (finite) set $X$. I am looking for condition on $f$ so I can said ...
1
vote
1answer
51 views

Is standard eigenvalue optimization problem convex

For any arbitrary symmetric matrix A , is the standard eigenvalue problem convex $ \lambda_{max}(A)= \max_{\|x\| \leq1} x^{T}Ax$
1
vote
0answers
32 views

Tucker's theorem from Farkas lemma

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ...
0
votes
0answers
20 views

How can I solve $\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$ in a closed form depending on projection?

I'm trying to solve the minimization problem $$\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$$ where $b \in \mathbb{R}^n$, $X \subset \mathbb{R}^n$ is a convex set. And $A$ is a symmetric ...
3
votes
0answers
31 views

Are these equivalent definitions of faces of convex sets?

I consulted several books and found that the definitions of faces and exposed faces of convex sets are a bit messy. Many books just treat them as the same stuff. In book "foundations of ...