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

learn more… | top users | synonyms

1
vote
0answers
17 views

Convex optimization when Hessian is non-invertible

1) Are there any extensions to Newton's method for finding minimum of a convex function when the Hessian is singular ? (I have all positive eigenvalues in the Hessian except one which is zero) I ...
0
votes
0answers
14 views

In what ways would a course on convex optimization be useful in game theory?

From talking to several other people in the past, it seems that convex optimization is really a tiny subset of game theory in that it only models the behavior of one single player and does not take ...
1
vote
0answers
8 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
0
votes
1answer
22 views

about scaling property of proximal operator

If the proximal operator of $f(x)$ is $\text{prox}_{\lambda f}(x)$, what about $cf(x)$ and $f(cx)$, c is a scalar. For example, If $f(x) = ||x||_{1}$, $x \in \mathbb{R}^{n}$, how about the proximal ...
0
votes
0answers
24 views

Maximum volume inscribed ellipsoid inside nonconvex polyhedron

In Convex Optimization (Boyd, Vandenberghe), an algorithm for finding the maximum volume inscribed ellipsoid inside a convex polyhedron is given on p. 414 (8.4.2 Maximum volume inscribed ellipsoid) [I ...
0
votes
1answer
31 views

Dual problem of piecewise linear function

I would like to see the geometric interpretation of the relationship between the primal problem and the dual problem on the $x,y$-plane. So I am looking at an example of minimizing the maximum of some ...
-1
votes
0answers
14 views

Increasing a singular value [on hold]

Can any one tell me the effect of increasing one singular value (say 10 times ) larger than others.Whether it has any importance in optimization Problems .
3
votes
2answers
61 views

Is the minimum of a parametric convex function convex again?

Let $I$ and $J$ be compact intervals. Let $f:I\times J\to\mathbb R$ be differentiable and strictly convex. Is the function $g:I\to\mathbb R$ defined by $$ g(x) = \min_{y\in J} f(x,y) $$ ...
4
votes
2answers
97 views

Are these two optimization problems equivalent to each other?

Let $\mathbf{x}=[x_1,\ldots,x_K]^T$. For a fixed vector $\mathbf{a}$, I have the following optimization problem : \begin{array}{rl} \min \limits_{\mathbf{x}} & | \mathbf{a}^T \mathbf{x} | \\ ...
0
votes
0answers
27 views

Reason for use $L^2$-Norm instead of $L^1$-Norm in Optimization [on hold]

In optimization we use $\min\; \Vert Ax-b\Vert_{2}^2$ instead of $\min\; \Vert Ax-b\Vert_{2}$ because second is not differentiable. But I am looking for a clean and mathematical reason for this. And ...
0
votes
0answers
17 views

Show that the set $\{y_1a_1+y_2a_2: -1\le y_1,y_2\le 1\}$ is a polyhedron

Show that the set is a polyhedron and express it in the form: $S = \{Ax\leq b, Fx = g\}$, $S=\{y_1a_1+y_2a_2 | -1\leq y_1\leq 1, -1\leq y_2\leq 1\}$ where $a_1,a_2\in\mathbb{R}^n$ My attempt: A ...
0
votes
1answer
45 views

Can a convex function have local maxima?

I have read that a convex function can have local maxima. It seems that this must happen on the boundary of the domain, otherwise there should be a region in which the function is concave. Is this ...
0
votes
1answer
32 views

Finding extreme point of a set determined by two planes in $\mathbb R^3$

Problem asks to find a extreme point the set $\{(x,y,z) \mid x-2y \leq 3 , 2y+3z \geq 4 \}$. But I don't think it has a extreme point, because it is intersection of two hyper planes in 3D, which ...
0
votes
1answer
27 views

Biconjugate of a nonconvex function

Is biconjugate of a non-convex function, the tightest lower bound on that function? If yes why?
-1
votes
2answers
38 views

Joint Convexity Proof

Let $x$ be $n \times 1$ vector and $Y$ be $n \times n$ matrix. Prove that $f(x,Y) = x'Y^{-1}x$ is jointly convex in $x$ and $Y$ when $Y \succ 0$.
3
votes
1answer
61 views

proximal operator of weighted L1 norm

I hope to solve this problem. $$\min \quad \left\| CX \right\|_{1} $$ $$ \text{s.t.}\quad AX=b, X >0 $$ where $C \in \mathbb{R}^{m \times m}$, $X \in \mathbb{R}^{m \times n}$, $A \in ...
1
vote
1answer
53 views

Optimum is achieved when both variables are equal

Consider the problem $\max_{y,z:\|y\|_\infty,\|z\|_\infty \leq 1}y^TBz$, where $B$ is symmetric, positive semidefinite, $y,z\in \mathbb{R}^n$, $\|z\|_\infty=\max_{i\in\{1,\ldots,n\}}|z_i|$. It turns ...
1
vote
0answers
27 views

how to get orthogonal rank 1 approximations?

The situation: I have $k$ matrices $A_i$, which are all real and of size $m\times n$. Now I would like to find the matrices $\tilde{A}_i$ of $A_i$ so that 1) $\tilde{A}_i$ is of rank 1 (thus a rank 1 ...
1
vote
0answers
35 views

Finding a polynomial approximation of a PDF

I would like to find a polynomial $P(x)=\sum_{d=1}^D P_dx^d$ of degree $D$, where its derivative is larger than or equal to a given pdf $f(x)$ in $[0,1-\epsilon]$, for any $\epsilon>0$. Note that ...
0
votes
1answer
39 views

Fenchel Duality in Prof. Bertsekas' lecture

Please see this link, p.39-41 (sufficient to answer my question), before (1.47) for detailed. For convenience, the relevant part is shown as: I am confused in two things: The ...
0
votes
0answers
16 views

Extreme pts of a polyhedral feasible set

Consider a linear program $\min \{c^T x:Px=q,x\geq 0 \}$, where $P \in \mathbb{R}^{m \times n}$. $x\geq 0$ means each component of $x_i$ of x is nonnegative. The feasible set is $\{x:Px=q,x\geq ...
0
votes
0answers
21 views

Some problems in finding conjugate function

Ask the following fundamental problems: How to derive the conjugate function of $g(y)$ if given "$\underset{y \geq 0}{\text{sup}}\{g(y)-y^Tx\}$"? My attempt is as following: \begin{align*} ...
2
votes
1answer
51 views

Conjugacy relation in the primal and dual problem

The following is my derivation in the Conjugacy relation in the primal and dual problem. I am shaky in it; so hope for some advices. Consider the following problem, $f(x),g(x)$ are convex ...
0
votes
1answer
48 views

How can I solve a nonlinear optimization problem where constraint contains exponential term?

I have the optimization problem as below: $\hspace{10mm} \text{Maximize} \sum_{k} \alpha_k {R}_k $ $ \hspace{10mm}\text{subjcet to:} $ $ \hspace{10mm}\exp \left[ - (2^{{R}_k } -1) \left( ...
0
votes
0answers
17 views

Optimization problem: solving one implies solving the reverse?

I am looking to solve an optimazation problem $Maximize_{x} [A(x)]$ s.t. $B(x)\geq B_0$, where $B_0$ is a constant. If I solve this problem (i.e, finding the optimal $x^*$ that optmize while ...
0
votes
0answers
30 views

Minimizing the sum of the $4^\text{th}$ power of a matrix entries.

Consider a real $n\times n$ matrix $X$. Suppose I would like to minimize the sum of the squares of its entries as a penalty term in some convex minimization. I can write the term using the Frobenius ...
0
votes
1answer
10 views

Conditions of convergence of stochastic subgradient algorithm

It is well known that for appropriate step size, $E[g^t] \in \partial f(x^t)$ is sufficient conditions for this subgradient algorithm to converge. What I'm wondering is whether the requirement has to ...
1
vote
0answers
17 views

Condition for product of increasing and decreasing functions to be quasiconcave?

Is there any condition for product of increasing and decreasing functions to be quasiconcave? More specifically, I am having in mind a condition for $F(x)\cdot(1-G(x))$ to be quasi concave where $F$ ...
0
votes
2answers
26 views

Reference Request: Soft handed text on duality theory?

Can anyone recommend a text on duality theory which includes basic formulation of the primal and dual formulation and some introduction to minimax problems? Preferably having some computation in ...
0
votes
0answers
13 views

The normal cone at the optimum of unconstrained convex optimization is always $\{0\}$?

I am studying the convex optimization: $\min_x f(x)$, where $x$ is a vector of $p$ elements. In the book CONVEX ANALYSIS AND NONLINEAR OPTIMIZATION Theory and Examples BORWEIN, section 2.1, I ...
0
votes
0answers
20 views

choosing gradienet flows to meet specific requirements, mainly remaining within a convex set

In this paper: http://arxiv.org/pdf/1308.5376v1.pdf, a set of conditions governing the choice of vector field are given. Let $\Delta^n$ be the closed unit simplex in dimension $n$, then for every ...
1
vote
1answer
90 views

Trace minimization subject to diagonal constraints

Problem Revisited - Edited for conciseness: We are given two set of data points X [$p \times n$] and Y [$q \times n$]. Let us assume $X = \hat{X} + \tilde{X}$ and $Y = \hat{Y} + \tilde{Y}$ I am ...
0
votes
0answers
32 views

Optimize $\max _{x_1,x_2,…,x_N} N , \text{ s.t.} \sum_{i=1}^N f(x_i) \le a$

$Is there general theory for solving optimization problem of the following kind \begin{align} &\max _{x_1,x_2,...,x_N} N \\ \text{ s.t.}& \sum_{i=1}^N f(x_i) \le a\\ &\sum_{i=1}^N g(x_i) ...
1
vote
2answers
41 views

What is the relation between these two definitions of an ellipsoid

There are two definitions of an ellipsoid in Boyd's book (Convex Optimization) $E = \{ x | (x-x_c)^T P (x-x_c) \leq 1 \}$ In the above, P is a positive semi definite matrix. $ E=\{ x_c+Au |\; ...
1
vote
1answer
44 views

What's the best way to optimize this energy function, and is it convex?

I have an energy function $E({\bf y})=||\,g({\bf Ay+c})-{\bf d}\,||^2_2 + ||\,{\bf y-e}\,||^2_2 + \alpha\,|{\bf y}|_1$ I need to minimize this with respect to $\bf y$, all other variables being ...
0
votes
0answers
28 views

Test for convexity

Consider the online learning setting where instantaneous loss is given by \begin{equation} \ell_t(f_t;(\mathbf{x}_t,y_t))=\max \left( {0,\left( \left( {\frac{N}{P}} \right){I_{(y_t = 1)}} + \left( ...
0
votes
0answers
16 views

Is there any relationship between the rank of mode-k unfolding of tensor X and the rank of X?

I want to solve the following optimization problem: $$\min \|Ax-b\|_2^2 + rank(X)\ \ (*)$$ where $X$ is a three order tensor, $x$ is vec($X$). Many work replace the model as the following one: ...
1
vote
0answers
32 views

Need help using matlab optimization tools [closed]

I'm working on some project involving large scale matrix and i need your help to solve an optimization problem with matlab, the problem is the following: $ \min_L \{\alpha Tr(Y^{t}LY) + ...
0
votes
0answers
18 views

solve least absolute deviation with non-negative constraints

We have an $m\times n$ matrix $A$, a vector $x$ of length $n$ and a vector $y$ with length $m$. We want to minimize the absolute deviation $|y-Ax|$, with all $x \geq 0$. What kind of toolkit should we ...
0
votes
0answers
13 views

Finding an unfrustrated set of local linear constraints with given minimal value

Let $ \{F_{i}\} $ be a finite set of linear functional on a convex closed subset $B\subset\mathbb{R}^{n}$ such that each $F_i$ is $k-local$ (acts on $k<<n$ variables only). Assume ...
0
votes
0answers
22 views

Clarke subdifferential

I have the following problem: Let $\phi \in L^\infty([0,1]).$ We define Lipschitz function $f :[0,1] \to \mathbb{R}$ as follows $$f(x) = \int_0^x \phi(s)ds.$$ Prove that Clarke sub-differential ...
0
votes
0answers
28 views

When exactly are quadratic objective functions polynomial time solvable

I'm considering quadratic programming problems of the form: $$ \max x^tQx+Bx$$ subject to the linear constraint $$ Ax \le b $$ I read that if is the case that $$ x^tQx + Bx \ge 0 \ \forall x$$ or ...
2
votes
0answers
31 views

Least expensive way to “walk” with a convex potential

Let $V(x)$ be a non-decreasing, convex function on $\mathbb{R}^+$. Fix some positive integers $L$ and $k \leq L$. Let $A_{L,k}$ be the space whose elements are sequences of positive integers $r= ...
0
votes
0answers
17 views

Nonsmooth Gauss-Seidel minimization (coordinate descent)

I have attempted to implement the coordinate descent algorithm for a separably convex problem of the form $$\min \sum f_i(x_i) \\ \text{s.t.} \ Ax = b $$ using the augmented Lagrangian ...
0
votes
1answer
32 views

L1 norm differentiablility

I am trying to understand the Least Absolute Deviation algorithm, which basically is min l1-norm(z) subject to z=Ax-b I want to understand how is the l1-norm ...
0
votes
0answers
29 views

Optimization problem involving semidefinite matrix variable that is constrained to be a tensor product

I would like to solve the following optimization problem. With scalar $R$ and nine (mutually orthogonal) $9$-dimensional column vectors $\vec v_i$ all given ($\vec v_i\!'$ is the row vector Hermitian ...
1
vote
1answer
21 views

Minimum of biconjugate of a nonconvex $f(x)$ is the minimum of $f(x)$ also?

In Fazel (2002) Matrix rank minimization with applications, Ch. 5.1.4-5.1.5, the author finds an analytic expression for the convex biconjugate of their nonconvex function; however, they state that ...
-1
votes
1answer
50 views

How can a Euclidean ball is a convex set

A convex set is one which has line segment between two points from the set and the line is subset of the set, How to prove Euclidean ball and ellipsoids are convex set ?
0
votes
0answers
17 views

Optimization problem shortest path distance and critical node detection problem (interdiction).

I am trying to formulate this optimization problem, max $d_{ij}$ where $d_{ij}$ is the shortest distance between active nodes i and j. However my problem is connecting my decision variable with the ...
1
vote
0answers
51 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...