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

learn more… | top users | synonyms

0
votes
1answer
17 views

Continuity of Parameterized Optimal Solution

Suppose for every $y$, $f(x,y)$ is strictly convex in $x$. Further, $f(x,y)$ is continuous in $y$. Let $\mathcal X$ be compact (in my problem, $\mathcal X$ is an interval). Can anyone suggest any ...
-1
votes
1answer
14 views
1
vote
0answers
22 views

Prove Jensen Inequality holds for a function

Given function $$f:\mathbb{R}^n_{+} \rightarrow \mathbb{R}, \ f(x) = \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}$$ Show that for any $x, y \in \text{dom} \ f, \theta \in [0,1]$, ...
0
votes
1answer
17 views

What is the maximum of the following function?

Let $f(x,y) = \frac{xy^\alpha}{x+y},\alpha\in(0,\infty)$. How to compute $$\sup_{(x,y)\in[a,b]\times [0,c]}\frac{xy^\alpha}{x+y},$$ with $b>a>0$?
0
votes
1answer
14 views

Convex function (vector composition rule)

I'm looking at the Boyd & Vandenberghe slides on Convex Optimization. In slide 18, it applies the rules of vector composition on an example to say that it is convex. The example given is ...
0
votes
1answer
9 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
2
votes
1answer
36 views

Are posynomial functions convex?

I know that you can transform a posynomial function into an exponential function, which is convex. Does this imply that all posynomial functions are convex?
0
votes
0answers
10 views

Find the dual problem to a quadratic program

Consider the quadratic program: minimize $x_1^2 + 2x_2^2 - x_1x_2 - x_1$ subject to $x_1 + 2x_2 \leq u_1, x_1 - 4x_2 \leq u_2, 5x_1 + 5x_2 \leq 1$ Could anyone explain to me how to find the dual ...
1
vote
1answer
33 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
1
vote
0answers
23 views

How to prove that unnormalized neg entropy is strongly convex with respect to 1-norm?

the unnormalized negative entropy of $\mathbf{x} \in \mathbb{R}^n_+$ is $$ g(\mathbf{x}) = \sum_i (x_i \log(x_i) - x_i) $$ it is stated that $g(\mathbf{x})$ is strongly convex with respect to 1-norm, ...
0
votes
0answers
6 views

Explain the dual problem to D-optimal design problem

Given the following D-optimal design problem $$ \text{minimize } \log \det (\sum_{i=1}^p x_i v_i v_i^T)^{-1}\\ \text{subject to } x \geq 0, {\bf{1}}^T x = 1 $$ Find the dual problem. I don't ...
0
votes
0answers
15 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
0answers
29 views

What non-convex functions be written as the $\min$ of multiple convex functions?

I am working on an optimization framework that can be used to optimize objective functions that can be written as the $\min$ of several convex functions. I was thinking about the generality of this ...
0
votes
0answers
20 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
2
votes
1answer
37 views

About a definition of “rank” of a matrix.

I am familiar with the definition of rank of a matrix as either (1) the maximal number of linearly independent rows or columns or (2) as the dimension of the image of the matrix. Another ...
1
vote
1answer
13 views

Log transformations of function domain and inequalities

If I know that for some function $f$, the following is true for $x, y \geq 0$: $f(\log (x^a y^b)) \leq f(\log x)^a f(\log y)^b$ Can I make the claim that $f(x^a y^b) \leq f(x)^a f(y)^b$ If I ...
0
votes
1answer
45 views

Probability that max cos(φ)x + sin(φ)y according to uniform distribution = (8,5)

max $x_2$ subject to $x_1 - 2x_2 \le 0$ $2x_1 - 3x_2 \le 2$ $x_1 - x_2 \le 3$ $-x_1 + 2x_2 \le 2$ $-2x_1 + x_2 \le 0$ Optimal solution: (8, 5) --> $x_2 = 5$ Now assume that the objective is ...
3
votes
0answers
61 views
+50

Gradient of the dual function for a nonlinear program

I'm attempting to find a proof for a property from Floudas' Nonlinear and Mixed-Integer Optimization book. Consider a nonlinear optimization problem of the form \begin{align} \min_{{\bf x}}&\quad ...
0
votes
0answers
18 views

Convex problem with linear constraints

I wish to solve the following nonlinear program: $$\min_{\substack{x_i\ge 0\\x_1\le x_1+x_3\le x_2}}h_1 x_1+h_2x_2+h_3 x_3+k_1(\tau-x_1)^++k_2(\tau-x_2)^++k_3(x_2-x_1-x_3)^+$$ I have the KKT ...
-1
votes
0answers
40 views

Prove that $f(x,y) = x/(y^2+1)$ is convex

Suppose $f(x,y) = x/(y^2+1)$. I was trying to prove that this function is convex. So I took partial double-derivative and constructed the Hessian for this function. Here the Hessian is a 2 by 2 matrix ...
0
votes
1answer
18 views

Tracking a vehicle moving with uniform velocity?

Suppose there are three cell towers at three positions $P_1$, $P_2$ and $P_3$. A vehicle is moving at uniform speed along a straight line. Three towers are pinging the vehicle at certain ...
0
votes
1answer
20 views

How to show the Hessian matrix of such functions are positive semi-definite?

Let $f:R\to R$, $g:R^n\to R$. Thus $f\circ g:R^n\to R$. Now suppose $f$ is non-decreasing and convex while $g$ is convex. In additon, $f,g$ are of $C^2$. I want to show that their composition is ...
0
votes
2answers
15 views

why Quasiconvex function is not concave?

A quasiconvex function is a function whose all sublevel set are convex. I am curious to know whether a quasiconvex function is a concave function.
0
votes
0answers
21 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
-1
votes
0answers
32 views

Optimization Problem Solving [closed]

I have some ambiguity about mathematical optimization problem modeling and solving because I don't have much more mathematical skills. Basically, I am from computer science background much more in the ...
0
votes
1answer
34 views

Gradient of Least Squares function

I have trouble understand the gradient of equation 3.12 with respect to $W$. Tn is a scalar output variable, $\phi(x)$ and $W$ are $N \times 1$ dimensional. According to the book, the gradient ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
0answers
23 views

On the proof of corner points maximising or minimising a linear function over a bounded convex region

This proof says if $Z_P \ne Z_Q$, then $Z$ is maximised (or minimised, I guess) at one of the endpoints -- of what exactly? $\overline{PQ}$? So the maximum value of $Z$ occurs at either $P$ or $Q$? ...
0
votes
0answers
20 views

Can we relax the assumption of nonnegativity in this proof on convexity of a feasible region in a linear programming problem?

Is the $\color{red}{\text{non-negativity constraint (see red box)}}$ used at all in the proof? If so, where? If not, does the proof then hold for a standard LP problem without the non-negativity ...
1
vote
0answers
19 views

Moreau Decomposition with Bregman Distance

I am working with a non-Euclidean proximity operator defined by a Bregman distance function $D(\cdot, \cdot)$: $$ \operatorname{prox}_f(x) = \operatorname*{argmin}_u \{ f(u) + D(u, x) \} $$ Is ...
0
votes
1answer
28 views

Identify if optimization problem is convex or non-convex?

I have formulated optimization problem for building, where cost concerns with energy consumption and constraints are related to hardware limits and model of building. To solve this formulation, I need ...
0
votes
1answer
14 views

Optimization problem for non-symmetric normal cone inclusion or antiderivative of Ax+b

I have the following equation: $$ -(\mathbf{A}\mathbf{x} + \mathbf{c}) \in \mathcal{N}_{C}(\mathbf{x}) \qquad (1) $$ where $\mathbf{A} \in \mathbb{R}^{n\times n}$ is symmetric and positive definite, ...
1
vote
1answer
27 views

Duality and the Positive Lagrange Multiplier

Suppose I have the following optimization problem: \begin{align} \min &f(x) \\ & f_1(x) \leq 0 \\ & \vdots \\ & f_k(x) \leq 0 \\ & g_(x) = 0 \\ ...
0
votes
0answers
27 views

Number of optimas of product of convex functions

I am dealing with a function, which is a product of two strongly convex functions, and trying to determine the number of its local minimum. For example, I have $$H=f(x)\cdot g(x)$$, in which both $f$ ...
1
vote
1answer
29 views

Is closed convex set with finite number of extreme points convex polyhedron

I have this simple question related to convex set and convex polyhedron. As the content in the title, it's basically my question: Is closed convex set with finite number of extreme points convex ...
0
votes
1answer
17 views

How to interpret the regular condition in this theorem about cones in convex analysis?

Theorem:Let $K_1,\dots, K_m$ be convex cones in $R^n$ and let $K = K_1 \cap K_2 \cap \dots K_m$. If $K_1 \cap int(K_2) \cap \dots \cap int(K_m) \neq \emptyset$(regularity assumption), then $K^\circ = ...
0
votes
0answers
29 views

Fin min $\sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})$ subject to… [closed]

Given $a_{ij} \ge 0, b_{ij}$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject to}\quad &\sum_{i=1}^m x_{ij} \le 1 \quad \forall ...
0
votes
0answers
17 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
1
vote
1answer
47 views

Is $-\ln(1+e^x)$ a convex function?

Is $-\ln(1+e^x)$ a convex function? My answer book says no because its second derivative is $-\dfrac{e^{2x}}{(1+e^x)^2}$ but I am sure that it is incorrect. I have that the second derivative is ...
0
votes
0answers
11 views

uniform lower bound for convex combination of a sequence of positive semidefinite matrices

Assume: a sequence of positive semidefinite matrices $A_k^i\in M_{m,n}, m<n$, $i\in\mathcal{N}$, and they have the following property: $$\underline{a}I \leq A_k^i(A_k^i)^T\leq \overline{a}I.$$ ...
0
votes
1answer
25 views

Solving SVM classifier with two weight vectors

I am trying to implement a paper that basically proposes the following way to train two classifiers on some data with two types of labels. I do not know how to tweak existing solvers for SVM to do the ...
0
votes
1answer
20 views

Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal ...
0
votes
0answers
15 views

Slater point and Ideal Slater point

How do we show that an ideal slater point lies in the relative interior of the Feasible set (of a convex optimisation problem)?
0
votes
1answer
22 views

Does the non-expansion property of the projection operator hold for all definitions of norm?

For convex problem, of course. I vaguely remember this holds for weighted norm also. But I am curious if there are some general conclusions about what kinds of norm will fit in this framework?
1
vote
3answers
34 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
1
vote
0answers
34 views

Scaled proximal operator for proximal Newton method

The scaled proximal operator was introduced as an extension of the (regular) proximal operator: $prox^H_h(x) = \arg\min_y h(y) + \frac{1}{2}\|y-x\|^2_H$. (See ...
0
votes
1answer
54 views

Is $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ concave? [closed]

I want to maximize the capacity function $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ with respect to $F$, subject to the constraints: (1) $\operatorname{trace} F \le Pt$ (2) ...
0
votes
1answer
24 views

Is this a concave function?

Suppose $\gamma \in R^{1}$ and $\beta \in R^{k}$. Let $f(\gamma,\beta) = (y_{2} - \gamma y_{1}) - (y_{3} - \gamma y_{2}) \exp(x^{\prime}\beta)$. Then is $f$ a concave function of ...
2
votes
0answers
19 views

Is it possible to use regularization to minimize the (expected) number of non-zero digits in a number?

This question may be slightly related to this question on length of the representation of a number in a certain basis. Introduction / Background In image and video coding, particularly the ...