All Questions
Tagged with convexity oc.optimization-and-control
33 questions
51
votes
7
answers
23k
views
Is all non-convex optimization heuristic?
Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...
- 2,383
8
votes
2
answers
275
views
Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l \rangle −f_1(x)−f_2(x)$ via convex duality?
I am attempting to solve the argument maximization problem
$$\arg\sup_x \{ \langle x,l \rangle − f_1(x)−f_2(x) \} \ \ \ \ \ \ \ \ \ \ (1)$$
where the functions $f_1$ and $f_2$ are concave but ...
- 101
7
votes
3
answers
913
views
Some questions about Invexity
Recently, I am looking into a non-convex optimization problem whose points satisfying KKT conditions can be obtained. Then the problem becomes how to decide whether the KKT conditions are sufficient ...
- 95
7
votes
2
answers
2k
views
Computational complexity of unconstrained convex optimisation
What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
- 561
7
votes
3
answers
6k
views
Minimize trace of inverse of convex combination of matrices.
Hello! (First question--please forgive me if its unclear.)
I am interested in efficient/approximate optimization techniques for minimizing a norm of a convex combination of symmetric, positive semi-...
- 181
5
votes
2
answers
1k
views
Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions?
The cone of symmetric positive semidefinite $n\times n$ matrices is the convex hull of rank $1$ matrices. That is, every symmetric positive semidefinite matrix is a convex combination of rank 1 ...
user2529
5
votes
1
answer
1k
views
Lipschitz properties of minima/minimizers of convex functions of two variables
Suppose I have a function $f(x,y)$ from $\mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ that is convex in both $x$ and $y$. Set
$g(y) = \min_{x} f(x,y)$
What I would like is for $g(y)$ to be ...
- 165
4
votes
1
answer
933
views
Conjugate function for matrix mixed norm
I am familiar with the conjugate function of the vector norm, which uses the concept of dual norm and is defined as follows:
$$\|\mathbf{y}\|_p^*=\max_{\mathbf{x}}\left(\mathbf{x}^T\mathbf{y}-\|\...
- 111
4
votes
1
answer
308
views
Going in the direction of the gradient
First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$.
Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$.
Now my ...
- 571
4
votes
0
answers
184
views
This function looks quasiconvex, can't understand why
Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
- 41
3
votes
2
answers
266
views
Fixed point iteration on symmetric biconvex function
Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
- 705
3
votes
1
answer
525
views
Linear and Isometric Automorphism Groups of the PSD Cone
Let $S_+$ be the cone of psd matrices ($n\times n$ real symmetric positive semidefinite matrices). This cone is a metric space induced from the inner product $\langle A,B\rangle = tr (AB)=tr(BA)$.
...
user2529
3
votes
2
answers
1k
views
A lower bound of a particular convex function
Hello,
I suspect this reduces to a homework problem, but I've been a bit hung up on it for the last few hours. I'm trying to minimize the (convex) function $f(x) = 1/x + ax + bx^2$ , where $x,a,b>...
- 645
3
votes
1
answer
2k
views
Global minimum of nonlinear least square
We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem:
Minimize $J(x)=\Vert f(x)-z\Vert^2$
subject to box ...
- 33
3
votes
0
answers
97
views
Projection onto level set of convex functional
Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and let $F:L^2_{\mathbb{P}}(\mathcal{F})\rightarrow (-\infty,\infty]$ be bounded-blow, convex, lower semi-continuous, and not identically ...
- 5,405
2
votes
3
answers
596
views
a different algebra/representation for convex sets
Hi,
I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the ...
- 21
2
votes
1
answer
3k
views
Sufficient conditions for gradient descent convergence
I have an unconstrained optimisation problem with convex objective function $f(x)$. Suppose I have access only to some function of the gradient $\hat{\nabla}= g(\nabla f)$, and I take gradient steps ...
- 561
2
votes
1
answer
183
views
Exponential optimization problem
\begin{eqnarray}
\arg\max_{k}\sum_{i=1}^{p}\sum_{j=1}^{p}\exp\left(-{\frac{\left(X(i,j)-{U_k}(i,j)\right)^2}{2}}\right),\:\: k=0,\dots,p
\end{eqnarray}
where $X$ and $U_k$ are the $p\times p$ matrices,...
- 21
2
votes
2
answers
315
views
On a version of gradient descent
I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme
$$ x(t+1) = x(...
- 571
2
votes
1
answer
296
views
Lipschitz Constant of the convex extension of a submodular function
The title says it all :)
Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function $g:[0,1]^n\...
- 243
2
votes
1
answer
511
views
Generalized unique nearest point problem for a compact, convex set in a strictly convex Banach space.
If $X$ is a Real Banach space with strictly convex norm, it is known that for any non-empty compact, convex set $K$ and point $x_0\notin K$, there exists a unique point $z_0\in K$ minimizing the ...
2
votes
1
answer
308
views
Can subgradient infer convexity?
It is known that
If $f:U→ R$ is a real-valued convex function defined on a convex open set in the Euclidean space $R^n$, a vector v in that space is called a subgradient at a point $x_0$ in $U$ if for ...
- 95
2
votes
1
answer
294
views
Necessary conditions for optimality in Banach spaces
Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...
- 21
2
votes
1
answer
661
views
minimizing functions over simple matrix inequalities
I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example:
$min \Sigma x_i ln ...
- 121
2
votes
0
answers
136
views
Fixed area, largest mass -- is there a name?
Let $x\in \mathbb{R}^n$ and let $s_k(x)$ denote the sum of the $k$ largest entries of $x$. The function $s_k(x)$ is well-known to be convex and is often used in optimization, such as
https://inst....
1
vote
2
answers
6k
views
If a quadratic form is positive definite on a convex set, is it convex on that set?
Consider a real symmetric matrix $A\in\mathbb{R}^{n \times n}$. The associated quadratic form $x^T A x$ is a convex function on all of $\mathbb{R}^n$ iff $A$ is positive semidefinite, i.e., if $x^T A ...
- 3,059
1
vote
1
answer
313
views
Nonlinear low-rank approximation - corrected
I would like to state that this is related to a past question of mine which contained errors and now appears in the corrected form, with the erroneous one deleted and closed.
In my research of linear ...
- 620
1
vote
0
answers
150
views
Hessian matrix positive definiteness (concavity test) [closed]
I have a rather simple scenario based optimization problem:
Maximize
$$
Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c
$$
subject to $Q_1{...
- 11
1
vote
1
answer
193
views
What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?
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 \mathbb{R}^{...
- 13
0
votes
1
answer
203
views
Eigenvalues of a given parametrized matrix.
Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as
\begin{align}
\mathbf{C}=\left(\mathbf{I}*\frac{1}{\...
- 1,421
0
votes
0
answers
166
views
Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general
Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...
0
votes
0
answers
1k
views
A question regarding Danskin's theorem
Suppose $\phi({\bf x},{\bf z})$ is a continuous function of two arguments,
$\phi: {\mathbb R}^N \times Z \rightarrow {\mathbb R}$,
where $Z \subset {\mathbb R}^m$ is a (non-empty) compact convex ...
- 13
0
votes
1
answer
180
views
(probably simple) optimization question
Suppose you have a concave function defined over a non-polyhedral convex cone and you are interested in the infimum. What would be standard approaches to tackle the question? (The cone is actually PSD ...
- 6,962