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

learn more… | top users | synonyms

0
votes
0answers
13 views

Duality gap problem

I have checked that the objective function is concave and the constraint functions are convex. Now to find the duality gap, one need to find the optimum of the primal and dual problem, and find the ...
0
votes
0answers
13 views

max and min values on symmetric polytope

Let $-N\leq t \leq N$. Let $A$ be regular $(N-1)$-dimensional simplex with vertices $(t,0, \ldots, 0)\ldots (0, 0,\ldots, t)$ and $B$ be regular $(N-1)$-dimensional simplex with vertices $(t-N+1,1, ...
0
votes
0answers
13 views

No critical points means convex? [on hold]

If we don't know whether $f(x)=0$ is convex or not, but we know under certain constraint sets there is no critical points of $f(x)$ inside meaning the solution of $df(x)=0$ is outside the constraint ...
0
votes
2answers
33 views

Minimize Function over Convex Subset

Suppose that C is a closed convex subset of $\mathbb R^n$ and $x \in \mathbb R^n$. The projection of $\mathbf x$ onto C is the closest point $\mathbf y \in C : \mathbf z = \mathbf y$ minimizes ...
0
votes
2answers
19 views

Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Suppose We have this optimization problem which is convex $\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$ But the product of different objective function is ...
1
vote
1answer
37 views

Convex Functions and Subsets

Suppose that $f, g: \mathbb R^n \to \mathbb R $ are $C^1$ convex functions. Show that $C = ${$\mathbf x \mid g(\mathbf x) \leq 0$} is a convex subset of $\mathbb R^n$. Show that if $\nabla f(\mathbf ...
0
votes
0answers
19 views

Convex cones and positively homogenous and subadditive functional

Let $V$ be a linear topological space, $K \subsetneq V$ a convex, closed cone with $0 \in K$ and $k \in K \setminus (-K)$. Show that the functional $\varphi : V \to \mathbb R \cup \{ \pm \infty \}$ ...
0
votes
1answer
29 views

Min of concave symmetric function on a convex set

Consider the convex set $$C=\left\{ \mathbf{x}\in \mathbb{R}^N :0\le x_1\le x_2\le\dots\le x_i\le x_{i+1}\le \ldots\le x_N\le \frac 1{N-1}\text{ and } \sum_{k=1}^{N}x_k=1\right\}$$ I need to minimize ...
0
votes
0answers
35 views

Why is pointwise maximum a convex function?

It seems like if you have a family of function $$g = \{a(x), \: b(x), \: c(x), \:d(x)\}$$ $$\text{given} \:\: f(x):= max(g),$$ $$\text{if} \: f(1) = a(1), \: f(2) = b(2), \: f(3) = c(3), \: f(4) = ...
0
votes
1answer
24 views

Why does convexity of a function required the following

What is the significance of the following condition $$\forall x_1, x_2 \in dom(f) , \forall \theta \in [0, 1], f(\theta x - (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$ and why isn't the ...
0
votes
2answers
39 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
0
votes
1answer
17 views

How do I justify that a second order cone is an intersection of half space

I am studying convex optimization right now, and the text book claims that a second order cone is a collection of intersections of half space $$K_n = \bigcap_{ u:\|u\|_2 \leq 1} \{(x,y) \in R^{n+1 } ...
0
votes
0answers
22 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
1
vote
1answer
29 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
33 views

Derivative of a minimum

The expression, $e=\left(x(t,w)-c_x\right){}^2+\left(y(t,w)-c_y\right){}^2$, has a local minimum with respect to $t$ at some $t_0(w)$. Now what does $t_0'(w)$ look like?! $x,y\in C^2$ with respect to ...
1
vote
1answer
16 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
4
votes
0answers
138 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
1
vote
1answer
37 views

An application of Separation Theorem

Let $X$ be a Hausdorff locally convex topological vector space. Suppose $X_0 \subset X$ is nonempty convex set, $g:\; X\to \mathbb R^m$ is a convex vector function (each component $g_i(x): X\to ...
0
votes
1answer
37 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
1
vote
1answer
22 views

Confusion related to the convexity of a bunch of functions

I have this confusion related to the convexity of some function.I was reading this paper - www.sigkdd.org/sites/default/files/issues/V14-01-02-Ye.pdf‎. I have this graph consisting of nodes denoted by ...
0
votes
1answer
15 views

Finding the maximum/minimum of a homogeneous function on $R^n$

Suppose that $f:R^n\to R$ is homogeneous. Also, suppose that the $argmin_xf(x)$ is non-empty. Is it true that if there exist $x^*\in R^n$ such that $f(x^*)=0$, then $x^*=argmin_xf(x)$?
1
vote
1answer
23 views

Dual formulation of an SDP problem

Could you help me formulate the dual problem to this SDP? maximize $\frac{1}{2} Tr(GW)$, subject to $ G \ge 0$ (and G symmetric), and $ \forall i$, $ G_{ii} = G_{1i} = G_{i1} $ Note that $G$ and ...
0
votes
1answer
28 views

Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form): $$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$ When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in ...
1
vote
1answer
27 views

KKT point of a constrained optimization problem

Min$_{x}~x$ Subject to $x \geq 0$ For this problem, is $(x^{*}, \lambda^{*})=$$(0,0)$ a KKT point ? My try : I formulated corresponding Lagrangian and tried to find out the KKT point(s). ...
0
votes
1answer
24 views

How to realize $\lambda_{max}(X)$ is convex?

How to realize is convex (f is convex) X is symmetric. (S.Boyd's book p.82, Example 3.10) It is easy to undertand like f = x^2 is convex; however, it is a bit hard for me to understand this ...
3
votes
1answer
72 views

How to minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$ subject to constraints?

My textbook came up with a solution without explanation. I'm looking for a systematic way of solving the following optimization problems and similar ones (by hand), because I'm drawing a blank: ...
0
votes
1answer
27 views

Solving the cost function optimization problem using linear programming

My cost function is in the form $$ \Delta u^T P \Delta u + q^T \Delta u$$How shall I put it in the form of $c^T x$ to be able to solve it using linear programming?
0
votes
1answer
16 views

Unique critical point and psd implies pd and hence strict relative maximum

Let $f(x)$ be of class $C^{(2)}$ on an open set A, $x_0\in A\subseteq R^n$ a critical point. In addition, the hessian matrix of f(x) at $x_0$, $H(x_0)=\{f_{ij}\}|_{x=x_0}$, is positive semi-definite. ...
0
votes
0answers
16 views

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, ...
0
votes
2answers
25 views

A statement for convex sets

The following statement is true or false? Given a convex set $S$ then for any $y \in S$ and $\theta\in[0,1], \theta \in \mathbb R$ there exist $y_1,y_2 \in S, y_1 \ne y, y_2 \ne y$ such that ...
0
votes
1answer
25 views

Inequality description of Convex hull

Given a finite collection of points $p_1,p_2,\ldots,p_m \in \mathbb{R}^n$, what are the inequalities describing their convex hull $\text{Conv}\{p_1,p_2,\ldots,p_m\}$?
0
votes
1answer
25 views

Convert SOCP from quadratic form to generalized inequality form

I have formulated a Second-order Cone Problem (SOCP) in “quadratic” form with a norm inequality constraint. To use a certain solver (ECOS, to be precise), I need to rewrite it to a form that makes use ...
0
votes
0answers
17 views

Deriving the optimal value for the intercept term in SVM

I was reading andrew ng's machine learning lecture notes on SVM. I came across the following equation (finding the optimal value for the intercept term $b$ in the SVM problem): However, I have no ...
0
votes
0answers
23 views

Mixed Integer Non Linear Problem for Relaxation Approach

I have the following problem. I have meat markets$(\mathcal{T}_1)$ and vegetable markets$(\mathcal{T}_2)$. $(\mathcal{T}_1) \cup (\mathcal{T}_2) = T$ and $(\mathcal{M}) \cap (\mathcal{V}) = ...
0
votes
1answer
32 views

Convex functions -> quasi-convex functions -> … can we weaken the assumptions?

First of all let me say that I'm new to optimization. I realized that quasi-convex functions share with convex functions some nice properties, so I wonder if we can push the weakening a little ...
0
votes
1answer
178 views

How to calc $\min ||J\Delta\tau + D||_*$

How to calculate $$ \min_{\tau} ||J_1 \tau_1 + \cdots + J_p \tau_p + D ||_* $$ where $\tau_1, \cdots, \tau_p \in \mathbb{R}$ $J_1, \cdots, J_p, D \in \mathbb{R}^{m \times n}$ $||\cdot||_*$ is sum ...
3
votes
2answers
55 views

Distribution of the Objective Value and the Variables in an Optimization Program

For random variables $X$ and $Y$, where $X\sim f(X;\theta)$ ($X$ is drawn from some distribution with pdf $f$ which is parametrized by $\theta$ ), $Y=g(X)$; we know that we can find the pdf of $Y$ if ...
1
vote
1answer
19 views

Propertise of a Dual Cone

In Convex Optimization by Boyd (P.51) said that " $y\in K^*$ iff $-y$ is the normal of hyperplane that supports $k$ at the origin ($K^*$ is a dual cone of $K$) " what does it mean geometrically? I ...
0
votes
0answers
21 views

Describing a Dual Cone

1)Does dual cone define just for proper cone or all kinds of cone ? 2)Can someone show me a figure that shows a dual cone of a cone ? In Convex Optimization by Boyd (P.51) said that " $y\in k^*$ iff ...
0
votes
0answers
31 views

Normal vector of a Hyperplane

I'm reading convex optimization by Boyd and I have a problem with normal of a hyperplane how many normal can we assume for a hyperplane at just one point? is it true that we can assume many vectors ...
0
votes
0answers
39 views

How can I show that two objective functions are the same?

I am trying to understand the relationship between the constrained and unconstrained versions of a convex optimization problem. The unconstrained problem is as follows: $$\min_{X}||X-Y||_2^2 + \lambda ...
0
votes
1answer
38 views

Maximizing minimum distance between points placed in a polygon

I would like to maximize the minimum spacing between a fixed number of points ($x_i \in \mathbb{R}^2$) placed inside a polygon in the plane. The minimum spacing includes distance to the polygon. ...
0
votes
0answers
40 views

Online convex programming: Projection followed by normalization

I have the following projected gradient descent online linear programming problem which has been well studied in www.cs.cmu.edu/~maz/publications/techconvex.pdf‎ $\mathbf{y}_{t+1}=\mathbf{w}_t - ...
0
votes
1answer
23 views

How can I prove this problem is quasiconvex?

I'm doing a convex optimization problem. It requires me to fit a rational function to an exponential function. I assumed the original problem would be a quasiconvex optimization problem and based on ...
-2
votes
0answers
67 views

Homework: Proving stationary point over a closed convex set.

I'm stuck on this and need some help. I know the definition of a stationary point over a set. $x \in X \implies \nabla f(x^*)^T(x-x^*) >= 0$ How do i show it? I've thought of beginning by ...
0
votes
1answer
28 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
0
votes
2answers
35 views

Nonempty interior feature of a proper cone

one of feature of proper cone is solid which means a proper cone has nonempty interior what dose nonempty interior mean ? I was reading Boyd convex optimization and I saw this term "Nonempty ...
0
votes
2answers
56 views

Solution in general for a seemingly simple problem

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} ...
0
votes
0answers
26 views

Prove that a point is optimal in LP-problem

I have the following LP-problem: Minimize $B_1^t Y_1 + B_2^t Y_2 + B_3^t Y_3$ subject to $$ (C_1,C_2,I) \begin{pmatrix} Y_1 \\ Y_2 \\ Y_3 \end{pmatrix}\geq 2 \text{ and } Y\geq 0 $$ where $B_1$ is ...
0
votes
1answer
44 views

How can the sum of two closed cones be not closed?

Can there be two closed cones $K_1$ and $K_2$ in $\mathbb{R}^3$ such that $K_1+K_2$ need not be closed?