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)

0
votes
0answers
13 views

Least squares optimization problem, KKT conditions and derive expression for $x^*$

minimize $\|Ax-b\|^2$ subject to $Kx=d$ where $K$ is a constant a) Give the KKT conditions b) Derive an algebraic expression for the optimal solution $x^*$ c) Determine the point $x^*$ that ...
0
votes
1answer
15 views

How to find the point in convex set $C$ that is closest to $y\notin C$?

How to find the point in convex set $C$ that is closest to $y\notin C$? $C=\{ x\in \mathbb{R^2}:(x_1-1)^2+(x_2-1)^2\le1 \}$ and let $y\notin C $ but $y\notin \mathbb{R^2} $.
1
vote
0answers
27 views

Intuitive way to find the minimum surface in $\mathbb R^3$?

Suppose we have two arbitrary closed curves which intersect neither each other nor themselves. By intuition, I guess that the minimum surface ending at boundaries is unique and it is achieved by this ...
0
votes
4answers
47 views

What does it actually mean if a cost function is differentiable?

I am just learning about optimization, and having trouble understanding the idea behind differentiating cost functions. I have read that for standard optimization problems, the cost function needs to ...
2
votes
0answers
19 views

Determine Critical points in optimisation problem

So I have this problem where I am supposed to calculate the max and min value of a function $f(x,y)=x+2y$ restricted by the disk $x^2+y^2\le 1 $. I have calculated the $df/dx $ and $df/dy$ and they ...
0
votes
2answers
14 views

Single nonzero value constraint formulation in linear programming problem statement

I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$. Another constraint is that if we take a predefined subset of ...
0
votes
0answers
15 views

An optimization problem for non-homogenous poisson process with unknow distribution

Jobs arrive at an M/M/1 type server according to an non-homogenous Poisson process with rate parameter $\lambda_k$. Where $\lambda_k$ and $\mu_k$ denotes the arrival rate and service rate at $k_{th}$ ...
0
votes
0answers
12 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
29 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$ ...
0
votes
1answer
25 views

Use graphical methods to solve the linear programming problem. Maximize:

Use graphical methods to solve the linear programming problem. Maximize: $z= 4x+2y$ subject to : $x-y\le 7$ $19x+12y\le 228$ $18x+18y \le 324$ $x\ge 0,y\ge 0$ the max is ?? when x= ?? and ...
0
votes
0answers
5 views

Minimize real valued scalar function $f(Q)$, where $Q=diag(\vec{q})$ subject to $q_j\geq0$ $\forall j\in\{1,2,…,m\}$ (positive vector)

Let variable vector $\vec{q}$ of size $m\times1$, and its diagonal counterpart $m\times m$ matrix $Q=diag(\vec{q})$, for some $m\in\mathbb{N}$. Define fixed parameter $n\times1$ vectors $\vec{p}, ...
0
votes
0answers
11 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
0
votes
1answer
14 views

Calculating min/max of a multivariate function on a region

This video shows an example of how to find the absolute maxima and minima of the function $f=xy+y^2$ at the region $\{(x,y):|x|\leq1,|y|\leq2\}$. I understand why he set $f_x, f_y$ to $0$, checked ...
0
votes
0answers
13 views

super-additive, sub-additive, and shapely value limitations?

I am working on the coalition formation. Most of the scientist used concept of shapely value for distributing the utility among the members of coalition. Up to my understanding, shapely value is good ...
0
votes
0answers
37 views

Maximization of sum of functions

Let $w,a\in R^n$, and $B\in R^{n\times n}_{++}$ (the set of $n\times n$ positive definite matrices). We know that the following function (which is a specific form of the Rayleigh quotient) has a ...
0
votes
1answer
24 views

A question about a proof in nonlinear programming book

I have a question about the proof of Proposition 1.2.1 (Stationarity of limit points for gradient methods) in the nonlinear programming book (2nd edition) by Bertsekas. At the beginning of the proof ...
0
votes
2answers
55 views

Max value of trignometric function $\sin \left(x+\frac\pi6\right)+\cos \left(x+\frac\pi6\right)$

Question: The maximum value of $\sin \left(x+\dfrac{\pi}{6}\right)+\cos \left(x+\dfrac{\pi}{6}\right)$ is at what value of $x$. I solved the problem by setting the slope of the function to zero and ...
1
vote
1answer
33 views

Curve fit minimizing the sum of the deviation

I'm fitting a curve taking the smaller sum of deviations for each parameter tested, the smaller sum returns me the parameter that gives the best fit. Here is the algorithm for a test $f(x, ...
3
votes
1answer
27 views

The dual function of composite functions

Given $X$ $Y$ are two finite dimensional Hilbert space. Let $K$: $X\to Y$ be linear and $F$: $Y\to \mathbb R^+$ is convex. Let us use $F^\ast$ to denote the dual (conjugate) function of $F$. Recall $$ ...
0
votes
0answers
9 views

Is this Frobenius norm optimization problem possible? [on hold]

$argmin_{A,B,C_i}\sum_{i=2}^{N}||AX_1B-AX_iC_iB||_F^2$ $X1$,...,$X_i$ are known matrices, and I'd like to obtain $A$, $B$, $C_i$.
0
votes
0answers
18 views

Sensitivity Analysis: Calculating Allowable increase/Decrease for a Binding Constraint

Let say we have the following equations: Objective Function = $7T+5C$ Contraints $3T + 4C \le 2400$ $2T + C \le 1000$ $C \le 450$ $T\le 100$ How would we calculate the allowable increase and ...
-1
votes
0answers
45 views

Find the solution to the following LPP by solving its dual. [on hold]

Minimize : $ Z = 300X_1 + 110X_2$ Subject to : \begin{align*} 30X_1 + 5X_2 &\geq 6 \\ 20X_1 + 10X_2 &\geq 8 \\ X_1, X_2 &\geq 0 \end{align*}
0
votes
0answers
23 views

Taking derivate wrt a vector

I'm trying to read through Wiki's description of the Levenberg-Marquardt algorithm. I've taken linear algebra, but I've always been fuzzy about taking derivatives with respect to a vector and just ...
3
votes
2answers
34 views

Distance between a plane and set of points

Suppose $m$ data points belonging to a class represented by matrix $A$. Therefore, the size of matrix $A$ is $m\times n$. In addition, suppose $w\cdot x + b=0$ be equation of a plane in ...
3
votes
1answer
49 views

Methods to Minimize Functions and Integrals over $\mathbb{N}$.

In a paper I'm writing, I have to minimize a messy function $f(\mu,n)$ where $\mu \in \mathbb{R}$ and $n \in \mathbb{N}$. That is, given $\mu \in \mathbb{R}$, I need to minimize the one variable ...
0
votes
0answers
56 views

Is this a game theory problem or optimization problem?

Consider a problem that looks for a $x$ that can make the following problem into some equilibrium state (similar to an equilibrium solution to a min-max problem in game theory) $$ \max_x f(x)$$ $$ ...
4
votes
0answers
27 views

Shaking a box of rocks (Optimal Packing)

My coworker was telling me that when he plants seeds on his farm, he puts them all in a large container on the tractor and after a period of just driving, the seeds are more densely packed than when ...
-2
votes
1answer
21 views

Maximum of uniform random variable [on hold]

Suppose I want to compute: $\max \{E[2 \min(\theta, I)]-I\}$ where $I$ is the choice variable and $\theta$ is a uniform variable in [0,1]. How should I do it?
1
vote
2answers
26 views

Fit polynomial function using experimental data (least squares)

I want to fit the polynomial function $f(x) = \alpha_0 +\alpha_1 x +\alpha_2 x^2 $ using given data such that the errors $y_c-f(x_c)$ are minimized (least squares). Obtained is the experimental ...
1
vote
0answers
36 views

Finding extrema of function of three variables

So i have to study this function and find out if there are any local or absolute extrema : $ f:\mathbb{R}^3 \rightarrow \mathbb{R} :$ $$ f(x,y,z)=2-\left(z-\sqrt{x^2+y^2}\right)^2 + ...
2
votes
0answers
59 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq ...
0
votes
0answers
18 views

Finding limit and maximizer

Let $f(x):=x^\alpha - k \cdot (x+c)^\alpha$, defined for $x>0$, where $k,c>0$ and $0<\alpha<1$. Question: solve $\max_{x>0} f(x)$. Below are my thoughts: Calculate $f'(x) = \alpha ...
2
votes
0answers
27 views

Expected number of times a set of 10 integers (selected from 1-100) is selected before all 100 are seen

Suppose I have a set of 100 integers. I randomly choose 10 of those, make a note of which ones I selected, and repeat the process. What is the expected number of times this process must be repeated ...
1
vote
0answers
78 views

Optimal allocation in network

We want to analyse specialization matters in a given network (N,g). Nodes represent individuals that can produce goods and services (just like in our usual economy) and that can be consumers too. ...
-1
votes
1answer
34 views

prove $\max \mathbf{a}^T \mathbf{b}_i \leq \mathbf{a}^T \mathbf{c}_i$

Can I prove the following (with or without assumptions, e.g. all the elements in $\mathbf{a}$ or $\mathbf{b}$ are positive? $\max \mathbf{a}^T \mathbf{b}_i \leq \mathbf{a}^T \mathbf{c}_i$ where ...
0
votes
0answers
15 views

Is it possible to prove $\arg\min_a f(\max(\mathbf{a}^T\mathbf{b}_i)) = \arg\min_a f(\mathbf{a}^T\max(\mathbf{b}_i))$

I have the following optimization problem, $ \arg\min_\mathbf{a} f(\max(\mathbf{a}^T\mathbf{b}_i))\;\; i=1, \dots ,N$ where $\mathbf{a}$ and $\mathbf{b}_i$ are vectors of dimension $d$. Let $B = ...
1
vote
0answers
23 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
0
votes
0answers
11 views

Optimization on SE(3) with matrix logarithm

I am trying to optimize the following equation on manifold SE(3). $$Z(e^{\epsilon}) = \text{logm}{((e^{\epsilon}X)^{-1}W^{-1}e^{\epsilon}XY)}$$ Note that $W, X, Y, e^{\epsilon} \in SE(3)$ and $W, X, ...
0
votes
1answer
14 views

Linear objective with quadratic constraints

I have the problem $$ \text{maximize } f= c^Tx \\ \text{subject to } x^T Q x \leq 1 \\ x,c \in \mathbb{R}^n \text{ , } Q \in \mathbb{R}^{n \times n} $$ and $ Q $ is additionally symmetric positive ...
1
vote
0answers
23 views

Regression linearization to apply Gauss-Newton

I want to try and use Gauss-Newton in order to estimate a solution to the regression problem with normalizing factor $$\min_{x \in \mathbb{R}^n}: \|y - Ax\|_2^2 + \lambda\|x\|_1.$$ To do this, I have ...
1
vote
1answer
45 views

Find vector that maximizes $f(x) = 2x_1^2+2x_2^2-x_3^3+2x_1x_2$

Find the vector with $||x||^2=x^Tx=1$ that maximizes the following function. $f(x) = 2x_1^2+2x_2^2-x_3^3+2x_1x_2$ I have rewritten the quadratic form as $f(x) = \frac{1}{2}x^T \begin{bmatrix} ...
1
vote
1answer
51 views

Optimize for happiness and equality

I'm trying to solve an optimization problem: There are $N$ students who can choose to enroll into $C$ courses, each of them has a set of 3 preferences $P = \{c_1, c_2, c_3\}$ about the courses they ...
2
votes
0answers
54 views

Upperbound for $\sum_{i=1}^n\frac{1}{x_i^2}$?

Suppose that $x_i>0$, $i=1,\ldots,n$. I'm looking for an upperbound (doesn't have to be particularly tight) of $\sum_{i=1}^n\frac{1}{x_i^2}$ in terms of some symmetric function of ...
1
vote
0answers
18 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
2
votes
0answers
19 views

Why does minimizing $H[f] =\sum^{N}_{i=1}(y_i-f(x_i))^2+\lambda \| Pf \|^2 $ leads to solution of the form $ f(x) =\sum^N_{i=1}c_iG(x; x_i)+p(x)$?

I was reading the following paper of dimensionality reduction (1) and also one on theory of networks for approximations and learning (2) and was trying to understand how the regularization problem ...
0
votes
0answers
17 views

Integer problem to minimize cuttings

A company has to make 4 items in the given quantities. item1 =4 item 2=2 item3=1 item 4=1 Te surfaces has to be covered in plywood.The company has got 3 ...
2
votes
1answer
62 views

Folding a paper such that the size of one sides be as minimum as possible?

Suppose that we have an A4 paper like this: How to fold this paper such that the bottom-right corner overlap the left edge of the paper and that the size of AB side be as minimum as possible. It ...
0
votes
0answers
6 views

Complexity of the Dinic, Malhotra, Kumar and Maheshwari (DMKM) method

I'm asked to prove that the complexity of the DMKM method is $\mathcal{O}(m\cdot n^{\frac23})$ if all capacities in a network are equal to 1. I have no clue where to start, can anyone give me a hint? ...
1
vote
0answers
11 views

How to obtain the minimizer parameter $\lambda$ for this computational complexity?

I'm trying to read a certain text, where they reach a computational complexity depending on scalars $a,b,c$ and a parameter $\lambda >0$ $$ O\left(\left\lceil\sqrt{\lambda a + \lambda^2 b^2} ...
1
vote
1answer
30 views

Global Optimization, symmetric solutions

Does anyone have the idea to solve the global multivariate minimization problem as below? $$\text{minimizes}\quad (x_1x_2x_3+x_1x_4x_5+x_1x_6x_7+x_2x_4x_6+x_2x_5x_7+x_3x_4x_7)-(x_1+x_2+x_4+x_7) \\ ...