Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
1answer
56 views

How to do optimization on expression which includes Reciprocal

The conditions are: $w$ is a known value, and $x_{11} >0, x_{12}>0, ..., x_{nn}>0;$ \begin{equation} x_{11} \leq w \end{equation} \begin{equation}x_{12} + x_{22} \leq w\end{equation} ...
1
vote
1answer
36 views

Semicontinuity of the product of two functions

Let $f(x)$ be a left continuous and non-increasing real-valued function. Can I prove that $f(x)x$ is upper semicontinuous?
1
vote
0answers
29 views

Proving $~\sum_{cyclic}\left(\frac{1}{y^{2}+z^{2}}+\frac{1}{1-yz}\right)\geq 9$

$a$,$b$,$c$ are non-negative real numbers such that $~x^{2}+y^{2}+z^{2}=1$ show that $~\displaystyle\sum_{cyclic}\left(\dfrac{1}{y^{2}+z^{2}}+\dfrac{1}{1-yz}\right)\geq 9$
1
vote
0answers
172 views

Choosing the vector that minimizes this sum related to the rearrangement inequality

The rearrangement inequality states that, for two sets of real numbers $x_1\leq\dots{}\leq x_n$ and $y_1\leq\dots{}\leq y_n$, the sum $\sum_{i=1}^n x_{\sigma(i)}y_i$ is minimized for the particular ...
1
vote
0answers
101 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
2answers
36 views

Terminology for maximize/minimize choice

I'm writing optimization software where the user needs to decide whether they want to minimize or maximize the value the objective function (where the output will contain many putative optimal ...
1
vote
0answers
77 views

Reasons for the worst-case scenario in robust optimization

When we solve an optimization problem, containing in his objective function an uncertain parameter (i.e. random variable), using robust optimization techniques such as the max-min approach, we first ...
1
vote
1answer
93 views

Help deriving simple linear regression formulas

I'm reading the Wikipedia article Simple Linear Regression . In the article they write a function to be minimized by choosing $\alpha$ and $\beta$: $$Q(\alpha,\beta) = \sum_{i=0}^{n} (y_i - \alpha - ...
1
vote
0answers
69 views

Propose suitable algorithm for min-max optimization problem

Consider: \begin{equation}\min_{x, y} \max_{\omega} | f(x, y, \omega) |\end{equation} where $(x , y)\in \mathbb{R}\times \mathbb{R} $ and $\omega \in (0, \infty)$. $f$ is the result of dividing ...
1
vote
2answers
257 views

Is the hessian negative semi-definite if we have an interior maximum?

Is it true that given a smooth scalar field f on a domain D , if f attains a maximum (minimum) on the interior of D then the hessian of f evaluated at this max (min) is negative (positive) ...
1
vote
1answer
115 views

Help with local extrema of $f(x)=x^4-5x^2$

Find the coordinates of any local extreme points and inflection points of the function $f(x)=x^4-5x^2$ My try: Find critical points: $f^{\prime}(x)=4x^3-10x=0$ $f^{\prime}(x)=2x(2x^2-5)=0 ...
1
vote
1answer
59 views

Simplifying This Boolean Expression? (A Little Rusty)

I have the Boolean expression: F = A'B'C'D + A'BC'D' + ABC + AB'C'D' + ABCD'. Note that the ' indicates the negation of the variable by my convention. I am trying to show that F = BC + A'C' + B'D' is ...
1
vote
1answer
74 views

Direction of steepest descent and minimization?

I have the following linear function: $min$ 1/2 $<x, x>$ + $r^Tx$ for every x belonging to $R^n$, $r^Tx$ belongs to $R^n$ Now, = $x^TAy$ and A is symmetric positive definite. = $x^TAy$ is ...
1
vote
0answers
41 views

Effect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
1
vote
1answer
52 views

Range Of Quartic Polynomial Of Two Variables

$a$,$b$ are real numbers such that $~3\leq a^{2}+ab+b^{2}\leq 6$. I would like to find the range of $~a^{4}+b^{4}$. Is it possible to find it with (well-known) AM-GM, CS, etc...?
1
vote
0answers
43 views

Convex hull of a 0/1 set in $ \mathbb{R}^d$

Reading in my textbook, I found the following example: $$ $$Let S $ \subseteq $ {0,1}$^d$ be an arbitrary 0/1 set in $ \mathbb{R}^d$ and the Polyhedron Q = conv(S). It can be shown easily that the set ...
1
vote
1answer
44 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
1
vote
0answers
36 views

Representing a 2D function as a sum of rectangles of arbitrary shape and orientation

Suppose I am given a non-negative function $f(x,y)$ defined for $x \in [0,1]$ and $y \in [0,1]$. I'd like to represent this function as a weighted sum $w_i$ of a small number of rectangular apertures. ...
1
vote
0answers
70 views

minimum strength of the edges occurring in any path P

Let $G=(V,E)$ be a graph and let $s: E \to \mathbb{R}^+$ be a function. Let us call $s(e)$ the strength of the edge $e$. For any path $P$ in $G$, the reliability of $P$ is, by definition, the minimum ...
1
vote
0answers
211 views

Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
1
vote
0answers
106 views

Optimization problem of quadratic function - Compressive sensing

I got the optimization problem in Compressive sensing in form $f =arg min \ \frac{\mu}{2} ||\Phi.f-y||^2 + \frac{\lambda}{2} ||f-v-w||^2$ where $\Phi$ is orthogonal Gaussian sensing matrix ...
1
vote
1answer
50 views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ...
1
vote
0answers
48 views

find conditions on input data such that a linear system has (no) feasible points

As a result of the apllication of Farkas' lemma I obtained the following problem: Let $ m,n,q \in \mathbb{N} $, $ b \in \mathbb{N}^m, l \in \mathbb{N}^m $ with $ l_i \mid q$ for all $ i=1,\ldots,m $. ...
1
vote
1answer
123 views

pairwise disjoint subsets of divisors of $ n $ (maximum number)

Let $ n \in \mathbb{N} $, $ n>1 $ and $ a_1,\ldots,a_k \in \mathbb{N} $ (not necessarily distinct!) with $ a_i \mid n $ for all $ i=1,\ldots,k $ be given. Assume that $ \sum_{i=1}^k a_i = K\cdot n ...
1
vote
0answers
95 views

How to solve an optimization problem with non-convex Frobenius norm constraint?

The form of my problem is: $$ \min_W \|Y-WX\|_F^2-\|V-WU\|_F^2 $$ $$ s.t. \|W\|_F=1 $$ All five variables are matrices. Since the norm constraint is a non-convex one, I have no idea how to solve this ...
1
vote
0answers
69 views

a question about Lagrange multiplier?

Q)Given $x_1+x_2+...+x_n=a$ where $a>0$, find the extremum value of $f(x_1,x_2,...,x_n)=x_1^k+x_2^k+...+x_n^k$ Also, find the range of $k$ in which the extremum value of $f$ is a maximum ...
1
vote
1answer
226 views

Sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
1
vote
2answers
43 views

maximize $x^a + y^b$ subject to $p_1x+p_2y=w$ utility max.

This is a utility maximzation problem maximize $x^a + y^b$ subject to $p_1x+p_2y=w$ (utility maximization problem) Anyone has any idea, there are no restrictions on $a$ and $b$, as far as i can see ...
1
vote
0answers
306 views

How to solve nonlinear constrained optimization in Matlab?

I have to solve a nonlinear constrained function in matlab, and I am not familiar with it's commands. the problem is: minimize $E(b,c)$ constraints: $k1< c\sqrt{b}< k2 ; c/6>k3$ Note: E(b,c) ...
1
vote
0answers
36 views

Is the Support Vector Classifier in some sense optimal?

My question is, is the original hard-margin support vector classifier optimal in some sense? If you have an answer that refers to the soft-margin SVC instead, I'd also be interested. I know that the ...
1
vote
0answers
52 views

Minimization via eigendecomposition of Hadamard matrix products

Let $\boldsymbol{\mathcal{R}}$ and $\boldsymbol{\mathcal{M}}$ be $n\times n$ Hermitian matrices (which are known) and let $\boldsymbol{\mathcal{G}}$ be a rank one $n\times n$ (unknown) Hermitian ...
1
vote
1answer
37 views

organizing rectangles on top of each other

We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the ...
1
vote
0answers
31 views

Maximization problem on a graph

Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$. $$ \max \sum_{(u,v)\in E} ...
1
vote
0answers
15 views

Find Maximum of Function $L(p)=\prod_{i=1}^{20}\left[ (1-p)A_{i}+pB_{i}\right]$

The $A_{i}'s$ and $B_{i}'s$ are known. I seek the $p$ which maximizes $L(p)$. I thought it might be easier to maximize $\log L(p)$ instead $L(p)$, but I think it is a dead end $\log ...
1
vote
0answers
156 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
1
vote
0answers
20 views

Internals of a MIP Solver

I would like to learn about the internals of a Mixed Integer Programming (MIP) solver. Which concepts shall I read about? Are there a couple of standard books which can be a good start?
1
vote
0answers
46 views

Differentiability of the Value (Support) Function

Consider the following problem, \begin{align} c(y,\mathbf{w})=\inf_{\substack{\mathbf{x} \in \mathbb{R}^n_{+} \\ \text{s.t. }f(\mathbf{x}) \geq y }} \mathbf{w} \cdot \mathbf{x} \end{align} where ...
1
vote
0answers
275 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
1
vote
0answers
32 views

Minimum of two convex functions

I'm having trouble showing the below statement is true. $\hat{\alpha}=\arg\min_\alpha \frac{1}{n} \sum_{i=1}^{n} f(u_i - h(v_i, \alpha))$ where $h(v_i, \alpha)$ is linear in $\alpha$. ...
1
vote
0answers
2k views

Profit Maximization Question of a Leontief (Perfect Complements) Production Function?

This is a question from my intermediate micro economics text book. Any help is very appreciated! Given Info: Company ST (a company which offers custom travel-planning services) is a ...
1
vote
0answers
48 views

How to express coprimality as a constraint in an optimization problem over integers?

I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$. Let us refer to this optimization problem ...
1
vote
0answers
52 views

Prove that $\{(x, y): x\in ri (dom f), y >f(x)\}\subset ri (epi f)$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
1
vote
0answers
59 views

Orthogonal Procrustes Variant

(author note: this question was also asked on mathoverflow). The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both ...
1
vote
0answers
29 views

Regulating the speed of a clock

I want to regulate the speed of a clock but with each regulation there is a random change whose size increases with the size of the intended change. Formally speaking, let $a_n$ be the error in the ...
1
vote
0answers
64 views

Optimal vs Optimum

What is the difference when a mathematician says, in respect to some optimization, "optimal" point vs "optimum" point? Can we use them as nouns too? I mean like "The optimal is..." or "The optimum ...
1
vote
0answers
30 views

abstract optimization problem

Suppose we have general optimization problem $f(x)\rightarrow min$, where x is an element of some algebraic structure (e.g. x is rotation matrix and is an element of SO(3)). There are plenty of ways ...
1
vote
0answers
41 views

Minimization problem with PMP

Problem: Solve $\int_0^1(x^2+u^2)dt \rightarrow min$, subject to $x'(t) = u(t) + x(t)$ and $x(0) = 0$. Our approach to the solution We solve this problem using the Pontryagin Maximum Principle. ...
1
vote
1answer
55 views

Maximizing Value of Function

I have three variables $p \geq 0$, $q \geq 0$, $r \geq 0$ and a positive constant $m$. Let $m = p + q +r$. How can I show that the maximum value of $pq + r$ is no more than $\frac{m^2}{4}$? It's ...
1
vote
0answers
35 views

Decomposition of a symmetric semi-definite matrix into sums of sparse symmetric semi-definite matrix

I'll first provide the background. Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables $x^{(1)},\ldots,x^{(n)}$. We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is ...
1
vote
1answer
55 views

Name this partition of a set problem.

I have a problem related (presumably) to set theory and I can't find the name of it. I just want you to name it so I can do some more research. Given a set $S$of $n$ elements $S= \{s_{1}, s_{2}, ...