Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

learn more… | top users | synonyms

1
vote
0answers
21 views

Nesterov's Methods for minimizing composite functions

There are some methods originally from Nesterov, which accelerates optimization methods, e.g. Nesterov 1983, Nesterov 2003, Nesterov 2005 ( smooth minimization of non-smooth functions), Nesterov 2013 (...
-1
votes
0answers
17 views

algorithms to solve convex problems [on hold]

which algorithms are used to solve convex / SOCP problems? for instance, which numerical algorithm is implemented in Sedumi or cvxgen? interior-point methods, or something else? Thanks
0
votes
0answers
29 views

optimize a Quadratic Matrix Programming with multi-spherical constraints

I have got the following quadratic problem restricted on the Cartesian product of Euclidean spheres. $\underset{X \in \mathbb{R}^{n\times 3}}{\text{min}}$ $Q(X) = \frac{1}{2} Tr(X^TA X) + Tr(B^T X)$ ...
1
vote
0answers
28 views

Practical application of envelope theorem for linear programs

Assume that we have solved a (standard) linear program $$ \text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0, $$ and would like to know how sensitive is the optimal ...
0
votes
1answer
24 views

Limits of argmin ratios and sums

In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms \begin{equation} \lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...
0
votes
0answers
33 views

Minimizing component-wise convex functions [migrated]

I want to minimize a function $f(\vec x,\vec y)$, whereby $\vec x$ and $\vec y$ are vectors. If I hold $\vec x$ constant, $f(\vec x,\vec y)$ is convex with respect to $\vec y$, and the reverse is true ...
1
vote
0answers
38 views

Minimization over function space [closed]

This is the first time I encounter a problem where I need to minimize a function defined in a function space. Define the function space $A=\{\theta:\mathbb{R}^3 \rightarrow\mathbb{R}|\ \theta\ \text{...
1
vote
0answers
20 views

Can the extragradient method be computed only based on proximal steps?

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the ...
0
votes
0answers
64 views

How to solve this nonlinear optimization problem?

I have a nonlinear optimization problem with linear constraints. How to solve this? $\sigma_i$ and $\rho_i$ are the optimization variables. $\min\hspace{1mm}\max\hspace{1mm}\left\{\frac{\sigma_1}{c_1-...
0
votes
0answers
38 views

Limit of argmin of sum

Suppose that I know $f_n\rightarrow f$ and $g_n\rightarrow g$ are both continuous maps from a Complete Riemmanian Manifold $X$ to $\mathbb{R}$ which converge pointwise almost everywhere. Then is it ...
1
vote
0answers
39 views

Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$. Define linear functions $f(x)= a_1x_1+ \...
0
votes
0answers
18 views

A possible condition on a set of vectors to be uniquely determined by their gramian?

Suppose you are given a gramian matrix $G=W^TW\in R^{k\times k}$, $W\in R^{d\times k},\;d>k$. The given gramian $G$ determines, up to a unitary transformation, the columns of $W$, i.e. an ...
0
votes
0answers
33 views

Optimizing sum of approximate and exact functions

This is a research question that I had asked in Math.SE about a month ago, but even after putting a bounty on it, I did not get any answers. I have two real values functions, where one ($g(w;x):\...
0
votes
0answers
16 views

Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...
0
votes
0answers
23 views

Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...
1
vote
0answers
29 views

Which algorithm is most efficient for a specific QP problem

I have a QP problem of the following kind: $\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$ s.t. $l\leq \alpha \leq u$ The matrix $M$ is symmetric and positive definite and of ...
1
vote
0answers
18 views

Concavity of maxima [closed]

Suppose we have the following optimization problem : $\min\limits_x kf(x) + g(x)$ where $f$ is a decreasing convex function in $x$ and $g$ is an increasing convex function. Can we say that $x^*$ is ...
4
votes
0answers
79 views

Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing. For ...
4
votes
2answers
77 views

About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form or ...
4
votes
0answers
136 views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
1
vote
0answers
33 views

Minimum of sum of modulus [closed]

How can I evaluate the minimum of $$ \left|7x-1\right|+\left|7y-5\right|+\left|7z-1\right| $$ if $x,y,z$ are non negative reals such that $ x+y+z=1$ and $y^2 \le xz$? Is there a standard way to ...
3
votes
1answer
125 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 ...
1
vote
1answer
44 views

On optimizing a function whose projection and projected vector go through a linear transformation

Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...
0
votes
0answers
36 views

Bounds on the curvature of a sequence of convex functions

Let $\{f_n\}$ be a sequence of (real-valued) smooth convex functions on $[0,1]$, with $f_n(0) = f_n(1) = 0$ for all $n$. Let $t_n \in [0,1]$ be the minimizer of $f_n$ and assume that $M_n:= f_n(t_n) ...
-1
votes
1answer
51 views

Does element-wise concavity guarantee joint concavity?

I have a function of two variables, and I have checked that along one direction (fixing another variable), it is a monotonically increasing and concave function. Whereas in another direction (fixing ...
10
votes
2answers
288 views

More general than semidefinite program?

I was TAing my convex optimization class and explaining that Linear Programs are a special case of Second Order Cone Programs, which are themselves special cases of Semidefinite Programs. My question ...
0
votes
1answer
101 views

Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem. Does anyone know if the LPG is a convex ...
0
votes
0answers
46 views

Find optimal value for a regularization parameter in generalized eigenvalue problem

Consider the generalized eigenvalue problem : $ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $ where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
0
votes
0answers
43 views

Nuclear norm maximization

I am trying to solve a nuclear norm maximization problem: $$\arg \max_{Q \in O(n)} \|WQV^T\|_*$$ where $Q$ is an $n \times n$ orthogonal matrix and $W$ and $V$ are real $d \times n$ matrices. I've ...
2
votes
1answer
251 views

Is this a log-concave function?

Let $(a_k)$ be a log-concave positive decreasing sequence. Is $\sum\limits_{k=1}^n a_k(1-e^x)^{k-1}$ log-concave in $x<0$, for each natural $n$?
1
vote
1answer
97 views

A bound on the number of bilinear functions needed in order to obtain the minmax

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$. Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...
0
votes
0answers
21 views

Bounding the error of the optimal solution from an approximated objective

Let $f$ be a smooth convex function defined in a bounded region $X$ and its Hessian is bounded $m I \le |\frac{\partial^2 f(x)}{\partial x^2}| \le M I$ for some $M>m>0$. Let $x^*=argmin_{x\in X} ...
0
votes
0answers
48 views

Question on solving an optimization problem using Variable splitting and ADMM

Tell me if I have found the right approach to the following optimization problem: $$ min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2 \\ s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0 $$ $A$ and $\Phi$ ...
1
vote
1answer
82 views

Envelope theorem for second derivative

I am maximizing a function $f(x,z)$ on $x$ ($z$ is treated a parameter in the maximization). The function $f$ is strictly concave on both variables. I know how to use the envelope theorem for the ...
1
vote
0answers
40 views

Is this QCQP convex or nonconvex

\begin{equation} \begin{split} \min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x \end{split} \end{equation} s.t. $$ g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\} $$ $$ g_i(x)=\frac{...
1
vote
0answers
73 views

Projecting on a a special polyhedron

Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron $$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$ Notice that $\mathcal P_X$ is symmetric about the origin. ...
1
vote
0answers
43 views

Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
5
votes
1answer
296 views

Minimize Frobenius norm

My question is the following: Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...
1
vote
0answers
39 views

convergence of unconstrained convex optimization

I encounter an optimization problem. The simplified version is like following: Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. $...
1
vote
2answers
64 views

Sensitivity analysis in minimum norm problems under a linear constraint

Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff. Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...
1
vote
0answers
50 views

Derivatives of Minkowski function?

Let $A\subset \mathbb R^n$ and $M$ be the convex hull of the set $A$, e.g., $M:=Conv(A)$. The Minkowski function on $M$ is defined as follows \begin{align*} &f: \mathbb R^n \to \mathbb R\\ &f(...
0
votes
0answers
60 views

Well-posedness of gradient flows

For a convex lower-semicontinuous functional on a Hilbert space $I\colon H\rightarrow\mathbb{R}$, it is shown in Evans' PDE that the Hilbert-space-valued ODE $$\begin{cases}\mathbf{u}'(t)\in-\partial ...
14
votes
1answer
375 views

Minimize sum of $\ell_2$ norm and linear combination, on simplex

Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
-1
votes
1answer
63 views

Convex Optimization in an Ellipsoid

Suppose we want to minimize a linear objective inside an ellipsoid that is, $\min _x l^Tx$ such that $(x - \mu)^TA(x - \mu) \leq \beta ^2$. Here, A is PSD and $\mu$ is a fixed vector. Can this be ...
0
votes
0answers
23 views

Maximizing modular function subject to supermodular constaint

I'm trying to solve a constrained optimization problem with submodular functions and get some nice properties of the solution. Unfortunately, I think I am in a setting where Topkis' theorem does not ...
3
votes
1answer
104 views

Finding a semigroup that maximizes the trace of a sum of matrices

Let $H$ be a finite semigroup containing $n$ elements from a compact group $G$. I am trying to solve $$\max_{h_i,\ h_j\ \in\ H} \operatorname{tr} \sum_{i,\ j\ \leq\ n} \rho(h_i^{-1} h_j)(A_j A_i^T)$$...
0
votes
0answers
48 views

How to use the property of Frobenius norm in this proof?

Let $A \in \mathcal{S}^{n}$($\mathcal{S}^{n}$ is the $n \times n$ symmetric matrix space), $P,Q \in\mathbb R^{n \times n}$, and $\rho \geq 0$ be given. Show that: $$A \succeq P^{T}ZQ+Q^{T}Z^{T}P$$ for ...
3
votes
1answer
146 views

Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...
0
votes
1answer
272 views

L-infinity-norm regularized proximity problem

I have a question: $$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$ where $t, \lambda$ are given constant. I think this may be a classic problem? However, I didn't find closed form of its ...
1
vote
0answers
57 views

Log convexity for the norm of a vector-valued function

Log convexity of various functions defined on the space of Hermitian matrices plays an important role in matrix analysis and probability theory. Given $v \in \mathbb{C}^n$, $D$ a diagonal matrix with ...